Solving Vehicle Routing Problem using Ant Colony Optimisation (ACO) Algorithm

  • Wan Amir Fuad Wajdi Othman School of Electrical & Electronic Engineering, Universiti Sains Malaysia
  • Aeizaal Azman Abd Wahab School of Electrical & Electronic Engineering, Universiti Sains Malaysia
  • Syed Sahal Nazli Alhady School of Electrical & Electronic Engineering, Universiti Sains Malaysia
  • Haw Ngie Wong School of Electrical & Electronic Engineering, Universiti Sains Malaysia

Abstract

Engineering field usually requires having the best design for an optimum performance, thus optimization plays an important part in this field. The vehicle routing problem (VRP) has been an important problem in the field of distribution and logistics since at least the early 1960s. Hence, this study was about the application of ant colony optimization (ACO) algorithm to solve vehicle routing problem (VRP). Firstly, this study constructed the model of the problem to be solved through this research. The study was then focused on the Ant Colony Optimization (ACO). The objective function of the algorithm was studied and applied to VRP. The effectiveness of the algorithm was increased with the minimization of stopping criteria. The control parameters were studied to find the best value for each control parameter. After the control parameters were identified, the evaluation of the performance of ACO on VRP was made. The good performance of the algorithm reflected on the importance of its parameters, which were number of ants (nAnt), alpha (α), beta (β) and rho (ρ). Alpha represents the relative importance of trail, beta represents the importance of visibility and rho represents the parameter governing pheromone decay. The route results of different iterations were compared and analyzed the performance of the algorithm. The best set of control parameters obtained is with 20 ants, α = 1, β = 1 and ρ = 0.05. The average cost and standard deviation from the 20 runtimes with best set of control parameters were also evaluated, with 1057.839 km and 25.913 km respectively. Last but not least, a conclusion is made to summarize the achievement of the study.

Downloads

Download data is not yet available.

References

[1] M. Reed, A. Yiannakou, and R. Evering, "An ant colony algorithm for the multi-compartment vehicle routing problem," Applied Soft Computing, vol. 15, pp. 169-176, 2// 2014.
[2] J. E. Bell and P. R. McMullen, "Ant colony optimization techniques for the vehicle routing problem," Advanced Engineering Informatics, vol. 18, pp. 41-48, 1// 2004.
[3] B. Bullnheimer, R. F. Hartl, and C. Strauss, "An improved Ant System algorithm for theVehicle Routing Problem," Annals of Operations Research, vol. 89, pp. 319-328, 1999.
[4] Z. Song, G. Ming, L. Chunfu, W. Chunlin, and X. Anke, "New transition probablity for Ant Colony Optimization: global random-proportional rule," in 2010 8th World Congress on Intelligent Control and Automation, 2010, pp. 2698-2702.
[5] G. Theraulaz and E. Bonabeau, "A Brief History of Stigmergy," Artificial Life, vol. 5, pp. 97-116, 1999.
[6] M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative learning approach to the traveling salesman problem," IEEE Transactions on Evolutionary Computation, vol. 1, pp. 53-66, 1997.
Published
2018-11-06
How to Cite
OTHMAN, Wan Amir Fuad Wajdi et al. Solving Vehicle Routing Problem using Ant Colony Optimisation (ACO) Algorithm. International Journal of Research and Engineering, [S.l.], v. 5, n. 9, p. 500-507, nov. 2018. ISSN 2348-7860. Available at: <https://digital.ijre.org/index.php/int_j_res_eng/article/view/357>. Date accessed: 11 dec. 2018. doi: https://doi.org/10.21276/ijre.2018.5.9.2.