Regresar

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

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 pbkp_redictive adaptive control scheme. The scheme considers future demand and pbkp_rediction of expected waiting and travel times experienced by customers. In addition, this work includes an analytical formulation of the proposed pbkp_rediction models that allow us to search over a reduced feasible space. Pbkp_redictive 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 pbkp_rediction 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 pbkp_redictive approaches solved with GA. © 2007 Elsevier Ltd. All rights reserved.