A Two-Stage Heuristic for the Vehicle Routing Problem with Time Windows and a Limited Number of Vehicles

The Vehicle Routing Problem with Time Windows (VRPTW) is an important problem in logistics. The problem is to serve a number of customers at minimum cost without violating the customers´ time window constraints and the vehicle capacity constraint. The m-VRPTW is a variant of the VRPTW in which a limited number of vehicles is available. A feasible solution to m-VRPTW may contain some unserved customers due to the insufficiency of vehicles. The primary objective of m-VRPTW is to maximize the number of customers served. In this paper, we propose a two-stage algorithm for the m-VRPTW. The algorithm first maximizes the number of customers served with an Ejection Pool to hold temporarily unserved customers. Then it minimizes the total travel distance using a multi-start iterated hill-climbing algorithm with classical and new operators including Generalized Ejection Chains. The experimental results showed consistently good performance of the algorithm when compared with other methods.