A Methodology Based on Evolutionary Algorithms to Solve a Dynamic Pickup and Delivery Problem Under a Hybrid Predictive Control Approach

Abstract

This paper presents a methodology based on generic evolutionary algorithms to solve a dynamic pickup and delivery problem formulated under a hybrid predictive control approach. The solution scheme is designed to support the dispatcher of a dial-a-ride service, where quick and efficient real-time solutions are needed. The scheme considers different configurations of particle swarm optimization and genetic algorithms within a proposed ad-hoc methodology to solve in real time the nonlinear mixed-integer optimization problem related with the hybrid predictive control approach. These consist of different techniques to handle the operational constraints (penalization, Baldwinian, and Lamarckian repair) and encodings (continuous and integer). For parameter tuning, a new approach based on multiobjective optimization is proposed and used to select and study some of the evolutionary algorithms. The multiobjective feature arises when deciding the parameters with the best trade-off between performance and computational effort. Simulation results are presented to compare the different schemes proposed and to advise conditions for the application of the method in real instances.