Genetic algorithm for large dynamic vehicle routing problem on GPU

摘要

Vehicle Routing Problems (VRPs) are fundamental optimization problems of distribution logistics and transportation systems. In the real-world, VPRs are dynamic in the sense that new customer requests continuously arrive over time, after a number of vehicles have already started their tours. These new requests must be incorporated into already planned routes. Dynamic VRPs require making decisions as fast as possible. This needs solution methods with high computational efficiency especially for large size problems. The aim of this paper is to attempt to achieve this objective. So, we design a new genetic algorithm for the Dynamic VRP and we implement it on Graphics Processing Units (GPU). The proposed approach is based on a simple method that inserts new requests in already planned routes then it optimizes the resulting solution via genetic operators that we introduced. We evaluated its effectiveness on some published benchmarks and on our own large instances (up to 3000 nodes) and we compared it to other recent works on Dynamic VRPs.