Solving the capacitated multi-trip vehicle routing problem with time windows

Abstract

The capacitated multi-trip vehicle routing problem with time windows is a very challenging well-known vehicle routing problem, where each vehicle is allowed to perform more than one trip to serve customers. This multi-trip characteristic is required in wide practical applications, ensuring better utilization of the vehicles. Such a characteristic, however, makes the problem much more difficult to solve, as in the existing literature, only 14 of the 27 benchmark instances with 100 customers have been solved to optimality. In this thesis, we develop a novel three-phase exact method to tackle this challenging problem. In the first and the second phases, we utilize both a route-based and a trip-based integer programming models together, solving their linear programming relaxations sequentially through some column-and-cut generation procedures. In the third phase, we then close the integrality gap by solving a trip-based model through a dynamic time discretization technique. Results from extensive computational experiments over benchmark instances demonstrate the effectiveness and efficiency of our newly proposed exact method. For the first time in the literature, all the 27 benchmark instances are solved to optimality in much less average running time than the best-known exact method in the existing literature. Our three-phase exact method is also flexible and can be adapted to solve several other variants of the problem to optimality efficiently.