Open AccessAnt Colony Optimization Using Different Heuristic Strategies for Capacitated Vehicle Routing Problem
Author(s) -
Siti Fatimah Mohamad Ayop,
Mohd Shahizan Othman,
Lizawati Mi Yusuf
Publication year - 2020
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/864/1/012082
Subject(s) - vehicle routing problem , swap (finance) , ant colony optimization algorithms , heuristic , computer science , mathematical optimization , routing (electronic design automation) , algorithm , mathematics , computer network , finance , economics
Capacitated Vehicle Routing Problem (CVRP) is a variant of vehicle routing problem (VRP) in which vehicles with restricted capacities required to pick-up or deliver at various locations. The main constraint in CVRP is to pick-up or deliver the goods for the least cost without exceeding the vehicle capacity. Therefore, the main objective of this paper is to minimize the distance travelled by vehicles. Hence, this paper proposed to use Ant Colony Optimization (ACO) with different heuristic strategies to optimize the distance travelled by the vehicles while not exceeding the vehicle capacities. Swapping, reversion, and insertion are the heuristic strategies used to examine the efficiency of neighbour creations in ACO. Christofides data sets are utilized in this paper to experiment on the solution construction in ACO with different heuristic strategies. The results showed that the use of ACO is efficient using the swap, reverse and insert strategies for distance minimization but there are possibilities for the vehicle visiting the same customer more than once. Meanwhile ACO with random combination with swap, reverse and insert are capable to solve CVRP without any possibilities for the vehicle visiting the same customer more than once.