Cuckoo search via Lévy flights for the capacitated vehicle routing problem

Subject Areas : Mathematical Optimization

Jon Henly Santillan ¹ , Samantha Tapucar ² , Cinmayii Manliguez ³ , Vicente Calag ⁴

1 - Department of Mathematics, Physics, and Computer Science, University of the Philippines Mindanao, Mintal, 8022, Davao, Philippines
2 - Department of Mathematics, Physics, and Computer Science, University of the Philippines Mindanao, Mintal, 8022, Davao, Philippines
3 - Department of Mathematics, Physics, and Computer Science, University of the Philippines Mindanao, Mintal, 8022, Davao, Philippines
4 - Department of Mathematics, Physics, and Computer Science, University of the Philippines Mindanao, Mintal, 8022, Davao, Philippines

Received: 2020-10-06 Accepted : 2020-10-06 Published : 2018-06-01

Keywords: Capacitated vehicle routing problem . Combinatorial optimization . Cuckoo search . Le´vy flights,

Abstract :

For this paper, we explored the implementation of the cuckoo search algorithm applied to the capacitated vehicle routing problem. The cuckoo search algorithm was implemented with Lévy flights with the 2-opt and double-bridge operations, and with 500 iterations for each run. The algorithm was tested on the problem instances from the Augerat benchmark dataset. The algorithm did not perform well on the problem instances, save for a select few on which the algorithm achieved the close to near-optimal result and one on which the algorithm achieved the optimal result. Increasing the number of iterations for each run of the algorithm on the two large-scale problem instances led to obtaining solutions closer to the optimal solution compared to the ones obtained with fewer number iterations. This gives an idea that the larger the problem instance becomes, the slower the algorithm converges to the optimal solution. Several other factors may also have contributed to the overall performance of the algorithm. Regardless of its performance, the algorithm was able to obtain routes that satisfied the constraints of the capacitated vehicle routing problem. The potential of the cuckoo search algorithm in solving combinatorial problems is demonstrated in this study in which the performance of the algorithm on routing problems was explored.