Memetic Algorithm for Large-Scale Real-World Vehicle Routing Problems with Simultaneous Pickup and Delivery with Time Windows

Abstract

The vehicle routing problem is a combinatorial optimization problem which has many real-world applications from supply chain management to public transportation. Many variants of the vehicle routing problem (VRP) exist with different constraints to reflect a variety of transportation scenarios faced by different industries. In this thesis, we examine the VRP variant referred to as the vehicle routing problem with simultaneous pickup and delivery with time windows (VRPSPDTW). In particular, we tackle a set of 20 recently released large-scale VRPSPDTW problem instances that were derived from the data of actual customers served by the transportation company known as JD Logistics. A memetic algorithm (MA) using an altered version of the Best-Cost-Route-Crossover is proposed and applied to this problem set. The proposed MA is able to find new best known solutions and performs better on average for all 20 instances in comparison to previous efforts. Comparative experiments are performed with other state-of-the-art crossovers to validate the effectiveness of the altered BCRC when used in the proposed MA. In addition, the dynamic VRPSPDTW (DVRPSPTW) is introduced by providing a mathematical formulation of the problem and transforming existing VRPSPDTW instances into dynamic instances. We perform a preliminary study on these dynamic instances using the proposed MA in conjunction with a simple but effective vehicle loading strategy, and the results are provided to promote further research into this dynamic variant.