This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Cortés, C. E. Articles by Muñoz-Carpintero, D. Search for Related Content

Hybrid Adaptive Predictive Control for a Dynamic Pickup and Delivery Problem

Civil Engineering Department, Universidad de Chile, Avenue Blanco Encalada 2002, Santiago, Chile
Electrical Engineering Department, Universidad de Chile, Avenue Tupper 2007, Santiago, Chile
Electrical Engineering Department, Universidad de Chile, Avenue Tupper 2007, Santiago, Chile
Electrical Engineering Department, Universidad de Chile, Avenue Tupper 2007, Santiago, Chile
ccortes{at}ing.uchile.cl
dsaez{at}ing.uchile.cl
alfnunez{at}ing.uchile.cl
dimunoz{at}ing.uchile.cl

This paper presents a hybrid adaptive predictive control approach that includes future information in real-time routing decisions in the context of a dynamic pickup and delivery problem (DPDP). We recognize in this research that when the problem is dynamic, an additional stochastic effect has to be considered within the analytical expression of the objective function for vehicle scheduling and routing, which is the extra cost associated with potential rerouting arising from unknown requests in the future. The major contributions of this paper are: first, the development of a formal adaptive predictive control framework to model the DPDP, and second, the development and coding of an ad hoc particle swarm optimization (PSO) algorithm to efficiently solve it. Predictive state-space formulations are written on the relevant variables (vehicle load and departure time at stops) for the DPDP. Next, an objective function is stated to solve the real-time system when predicting one and two steps ahead in time. A problem-specific PSO algorithm is proposed and coded according to the dynamic formulation. Then, the PSO method is used to validate this approach through a simulated numerical example.

Key Words: pickup-and-delivery system; dynamic vehicle routing problem; hybrid predictive control; particle swarm optimization
History: Received: March 2005; revised: October 2007; accepted: October 2008.