The Vehicle Routing Problem with Time Windows (VRPTW) consist of determining a set of feasible vehicle routes to deliver goods to a set of customers using a hierarchical objective; first minimising the number of vehicles used and, second, the total driving distance.A three-stage method is proposed for the VRPTW. The first stage aims at minimising the number of vehicle used, whereas the second and third phase aims at minimising the travel distance. The first stage maintains an ejection pool with temporarily unserved customers, and tries to insert these customer into the existing solution. If a new candidate solution for the minimum number of vehicles is found, a route is removed and the customers from the route is placed in the ejection pool. If the heuristic terminates without finding a new candidate solution where all customers are served, the first stage returns the last found candidate solution that serves all the customers. The second stage usesan Adaptive Large Neighborhood Search (ALNS) algorithm to minimise the travel distance, during the second phase all of the generated routes are considered by solving a set cover problem. The ALNS algorithm uses 4 destroy operators, 2 repair operators and a local search method. The third stage isa Branch-Cut-and-Price (BCP) matheuristic which considers a reduced problem instance, with onlya small subset of the total arcs. This work contributes to the existing literature by integrating a set cover model with ALNS and by using BCP as a post-optimization procedure.
展开▼
