A Parallel Matheuristic for Solving the Vehicle Routing Problems

In this chapter, we present a matheuristic approach for solving the Vehicle Routing Problems (VRP). Our approach couples the Ant Colony Optimization (ACO) algorithm with solving the Set Partitioning (SP) formulation of the VRP. As the ACO algorithm, we use a rank-based ant system approach where an agent level-based parallelization is implemented. The interim solutions which correspond to single vehicle routes are collected in a solution pool. To prevent duplicate routes, we present an elimination rule based on an identification key that is used to differentiate the routes. After a pre-determined number of iterations, the routes accumulated in the solution pool are used to solve the SP formulation of the problem to find a complete optimal solution. Once the optimal solution is obtained it is fed back to ACO as an elite solution that can be used in the pheromone reinforcement procedure. Our experimental study using the well-known VRP with Time-Windows benchmark instances of Solomon shows that the proposed methodology provides promising results.