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

Kuwait Journal of Science

FARZAD DIDEHVAR²  FARHAD RAHMATI²  MOHAMMAD SEDIGHPOUR³  MAJID YOUSEFIKHOSHBAKHT²  VAHID AHMADI¹ 

[1] Ahvaz Branch, Islamic Azad University, Ahvaz, Iran;Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran;Hamedan Branch, Islamic Azad University, Hamedan, Iran

关键词: Ant colony optimization;    candidate list;    local search techniques;    np-hard Problems;    open vehicle routing problem;   

DOI  :  

学科分类：社会科学、人文和艺术（综合）

来源: Kuwait University * Academic Publication Council

【 摘 要 】

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.

【 授权许可】

Unknown