A New Two-Stage Heuristic For Vehicle Routing Problem with Time Windows

摘要

The vehicle routing problem with time windows is a famous combinatorial optimization problem. The m-VRPTW is a variant of the VRPTW in which only a limited number of vehicles are available, whose feasible solution may include some un-served customers due to the limited vehicles. The primary objective of m-VRPTW is to maximize the number of customers served, while the second is to minimize the total travel distance. We present a new two-stage heuristic to solve m-VRPTW, we firstly introduced adaptive k-means to create initial solutions, with an Ejection Pool (EP) to hold temporarily un-served customers and an Adaptive Memory to keep good solutions. What's more, we proposed a new operator called Transfer to improve our initial solutions.Then, we minimized the total distance using an improved AMP algorithm(IAMP). The experimental results show consistently good performance of our algorithm when compared with other methods.