Dynamic Memory Memetic Algorithm for VRPPD With Multiple Arrival Time and Traffic Congestion Constraints

Abstract

With the new distribution demands emerging continuously in the last decade, the distribution mode is changing gradually in various applications, such as e-commerce, emergency relief supplies distribution, the last-mile delivery, and so on. We formulate vehicle routing problem with pickup and delivery (VRPPD), while simultaneously considering multiple arrival time and traffic congestion constraints. Our model focuses on the clear changes of the distribution mode to meet the fast-delivery requirements in the last decade, which is characterized by the multi-batch arrival of goods in 24 hours and time-varying congestion in various time windows. Besides, we propose dynamic memory memetic algorithm, which updates its dynamic memory by whether to promote populations to find new better solutions or not. This is an effective acceleration mechanism to promote the population progress. Meanwhile, dynamic memory memetic algorithm determines the serious congestion tasks in the delivery route and transforms them into normal congestion or even non-congestion tasks. Test sets with 30 test problems are constructed by using real distribution data from Alibaba Cloud and traffic congestion data from Baidu Map in Shanghai. By comparing with four compared algorithms, the effectiveness, efficiency, and robustness of our proposed algorithm in non-congestion and congestion tests are simultaneously demonstrated.

Keywords

• VRPPD
• pickup and delivery problem
• dynamic memory
• distribution mode
• the~multi-batch arrival of goods
• traffic congestion