A Pattern Mining Heuristic for the Extension of Multi-trip Vehicle Routing

Multi-trip vehicle routing problem with a variable number of wagons significantly reduces the number of vehicles and drivers needed to service customers. It is often hard to solve these problems in acceptable CPU times using exact algorithms when the problem contains very big real-world data sets. We use meta-heuristic algorithms to get a solution close to the optimal solutions for vehicle routing problems with a dynamic capacity of a vehicle. First, local search heuristics applied with genetic algorithms are proposed. Then, a pattern-mining algorithm is developed to improve the solutions found from the genetic algorithm. We perform detailed experiments on Solomon instances for vehicle routing problem with time windows (VRPTW). Our experiments establish the effectiveness of the algorithms.