Solving the open vehicle routing problem by a hybrid ant colony optimization

Abstract

The open vehicle routing problem (OVRP) is a variant of vehicle routing problem (VRP) in which the vehicles are not required to return to the depot after completing a service. Since this problem belongs to NP-hard Problems, many metaheuristic approaches like ant colony optimization (ACO) have been used to solve it in recent years. The ACO has some shortcomings like its slow computing speed and local-convergence. Therefore, in this paper a hybrid ant colony optimization called HACO is proposed in which a new state transition rule, an efficient candidate list, several effective local search techniques and a new pheromone updating rule are used in order to achieve better solutions. Experimentation shows that the algorithm is successful in finding solutions within almost 3% of known optimal solutions on classical thirty one benchmark instances. Additionally, it shows that the proposed algorithm HACO finds twenty one best solutions of classical instances and is competitive with eight existing algorithms for solving OVRP. Furthermore, the size of the candidate lists used within the algorithm is a major factor in finding improved solutions and the computational times for the algorithm compare satisfactorily with other solution methods.

Keywords

• Ant colony optimization
• candidate list
• local search techniques
• np-hard Problems
• open vehicle routing problem