Multi-objective Memetic Algorithm Based on Three-Dimensional Request Prediction for Dynamic Pickup-and-Delivery Problem with Time Windows

摘要

A multi-objective memetic algorithm based on three-dimensional request prediction is proposed in this paper to solve dynamic pickup-and-delivery route problems with time windows. Dynamic requests are predicted in three dimensions including two space coordinates and time based on the statistical distribution of historical data. The predictive routes are planned firstly and tuned subsequently when the real requests occur. Tri-objective route planning problem based on route length, served time and workload is optimized by the proposed multi-objective memetic algorithm based on prediction, which combines multi-objective genetic algorithm with a locality-sensitive hashing based local search. The proposed algorithm is compared with the other two popular algorithms on two test problems and the experimental results show the efficiency of the proposed algorithm.