A Combination of Meta-heuristic and Heuristic Algorithms for the VRP, OVRP and VRP with Simultaneous Pickup and Delivery

Abstract

Vehicle routing problem (VRP) is a Nondeterministic Polynomial Hard combinatorial optimization problem to serve the consumers from central depots and returned back to the originated depots with given vehicles. Furthermore, two of the most important extensions of the VRPs are the open vehicle routing problem (OVRP) and VRP with simultaneous pickup and delivery (VRPSPD). In OVRP, the vehicles have not return to the depot after last visit and in VRPSPD, customers require simultaneous delivery and pick-up service. The aim of this paper is to present a combined effective ant colony optimization (CEACO) which includes sweep and several local search algorithms which is different with common ant colony optimization (ACO). An extensive numerical experiment is performed on benchmark problem instances addressed in the literature. The computational result shows that suggested CEACO approach not only presented a very satisfying scalability, but also was competitive with other meta-heuristic algorithms in the literature for solving VRP, OVRP and VRPSPD problems. Keywords: Meta-heuristic algorithms, Vehicle Routing Problem, Open Vehicle Routing Problem, Simultaneously Pickup and Delivery, Ant Colony Optimization.