TY - JOUR
T1 - Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering
AU - Sáez, Doris
AU - Cortés, Cristián E.
AU - Núñez, Alfredo
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - Dynamic pick-up and delivery problem
KW - Fuzzy clustering
KW - Genetic algorithms
KW - Predictive control
UR - http://www.scopus.com/inward/record.url?scp=41149117135&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2007.01.025
DO - 10.1016/j.cor.2007.01.025
M3 - Article
AN - SCOPUS:41149117135
SN - 0305-0548
VL - 35
SP - 3412
EP - 3438
JO - Computers and Operations Research
JF - Computers and Operations Research
IS - 11
ER -