A Study on Distributed Meta-Heuristic Approach for Routing Planning

We consider a pickup and delivery problem with time windows. This problem is a complicated one in which multiple kinds of decisions are included. The problem requires that any paired pickup and delivery locations have to be served by one vehicle and the pickup location has to be scheduled before the corresponding delivery location in the route. In order to find near-optimal routing plans, we discuss a distributed meta-heuristic approach. The key idea is that the problem is decomposed into a set of partial problems, in which the number of customers assigned to each vehicle is fixed, and each partial problem is solved by meta-heuristics such as simulated annealing heuristics. Then, we propose a parallel search method to find promising partial problems effectively. The effectiveness and the potential of the proposed approach are evaluated by a series of computational experiments