Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering

Doris Sáez, Cristián E. Cortés, Alfredo Núñez

Research output: Contribution to journalArticleScientificpeer-review

75 Citations (Scopus)

Abstract

In this paper, we develop a family of solution algorithms based upon computational intelligence for solving the dynamic multi-vehicle pick-up and delivery problem formulated under a hybrid predictive adaptive control scheme. The scheme considers future demand and prediction of expected waiting and travel times experienced by customers. In addition, this work includes an analytical formulation of the proposed prediction models that allow us to search over a reduced feasible space. Predictive models consider relevant state space variables as vehicle load and departure time at stops. A generic expression of the system cost function is used to measure the benefits in dispatching decisions of the proposed scheme when solving for more than two-step ahead under unknown demand. The demand prediction is based on a systematic fuzzy clustering methodology, resulting in appropriate call probabilities for uncertain future. As the dynamic multi-vehicle routing problem considered is NP-hard, we propose the use of genetic algorithms (GA) that provide near-optimal solutions for the three, two and one-step ahead problems. Promising results in terms of computation time and accuracy are presented through a simulated numerical example that includes the analysis of the proposed fuzzy clustering, and the comparison of myopic and new predictive approaches solved with GA.

Original languageEnglish
Pages (from-to)3412-3438
Number of pages27
JournalComputers and Operations Research
Volume35
Issue number11
DOIs
Publication statusPublished - 2008
Externally publishedYes

Keywords

  • Dynamic pick-up and delivery problem
  • Fuzzy clustering
  • Genetic algorithms
  • Predictive control

Fingerprint Dive into the research topics of 'Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering'. Together they form a unique fingerprint.

  • Cite this