Oriental Journal of Computer Science and Technology

Open Access Open Access  Restricted Access Subscription Access

Constructive and Clustering Methods to Solve Capacitated Vehicle Routing Problem


Affiliations
1 Dept. of Computer Science and EngineeringKhulna University of Engineering & Technology (KUET)Khulna-9203, Bangladesh
2 Dept. of Computer Science and EngineeringKhulna University of Engineering & Technology (KUET) Khulna-9203, Bangladesh
 

Vehicle Routing Problem (VRP) is a real life constraint satisfaction problem to find minimal travel distances of vehicles to serve customers. Capacitated VRP (CVRP) is the simplest form of VRP considering vehicle capacity constraint. Constructive and clustering are the two popular approaches to solve CVRP. A constructive approach creates routes and attempts to minimize the cost at the same time. Clarke and Wright's Savings algorithm is a popular constructive method based on savings heuristic. On the other hand, a clustering based method first assigns nodes into vehicle wise cluster and then generates route for each vehicle. Sweep algorithm and its variants and Fisher and Jaikumar algorithm are popular among clustering methods. Route generation is a traveling salesman problem (TSP) and any TSP optimization method is useful for this purpose. In this study, popular constructive and clustering methods are studied, implemented and compared outcomes in solving a suite of benchmark CVRPs. For route optimization, Genetic Algorithm (GA), Ant Colony Optimization (ACO) and Velocity Tentative Particle Swarm Optimization (VTPSO) are employed in this study which are popular nature inspired optimization techniques for solving TSP. Experimental results revealed that parallel Savings is better than series Savings in constructive method. On the other hand, Sweep Reference Point using every stop (SRE) is the best among clustering based techniques.

Keywords

Routing Problem, Constructive Method, Clustering Method, Clarke And Wright’s Savings Algorithm, Sweep Algorithm, Fisher And Jaikumar Algorithm, Genetic Algorithm, Ant Colony Optimization And Velocity Tentative Particle Swarm Optimization.
User
Notifications
Font Size

  • G. B. Dantzig and J. H. Ramser, “The Track Dispatching Problem”, INFORMS, Management Science, vol. 6, no. 1 pp. 80-91, October, 1959.

  • Christofides N, Mingozzi A, Toth P,“The vehicle routing problem”, In: Christofides N, Mingozzi A, Toth P, Sandi C, editors.

  • S. R.Venkatesan, D. Logendran, D. Chandramohan, “Optimization of Capacitated Vehicle Routing Problem using PSO”, International Journal of Engineering Science and Technology (IJEST), vol 3, pp. 7469-7477, October 2011.

  • Jens Lysgaard, “Clarke & Wright’s Savings Algorithm”, Department of Management Science and Logistics, the Aarhus School of Business, 1997.

  • A. Poot & G. Kant, “A Savings Based Method for Real-Life Vehicle Routing Problems”, Econometric Institute Report EI 9938/A, August 1, 1999.

  • T. Doyuran, B. Çatay, “A robust enhancement to the Clarke-Wright savings algorithm”, Technical notes, Faculty of Engineering and Natural Sciences, Sabanci University, Tuzla, Istanbul, Turkey, 2011.

  • T. Pichpibula, R. Kawtummachai, “An improved Clarke and Wright savings algorithm for the capacitated vehicle routing problem”, Science Asia, vol. 38, pp. 307–318, 2012.

  • B. E. Gillet and L. R. Miller. “A Heuristic Algorithm for the Vehicle Dispatch Problem”, Operations Research, vol. 22, pp. 340-349, 1974.

  • G. W. Nurcahyo, R. A. Alias, S. M. Shamsuddin and M. N. Md. Sap, “Sweep Algorithm in vehicle routing problem for public Transport”, Journal Antarabangsa (Teknologi Maklumat), vol. 2, pp. 51-64, 2002.

  • N. Suthikarnnarunai, “A Sweep Algorithm for the Mix Fleet Vehicle Routing Problem”, In Proceedings of the International Multi-Conference of Engineers and Computer Scientists 2008 Vol II, IMECS 2008, 19-21 Hong Kong, March 2008.

  • M. L. Fisher and R. Jaikumar, “A Generalized Assignment Heuristic for Vehicle Routing”, Networks, vol. 11, pp. 109-124, 1981.

  • D. E. Goldberg, “Genetic Algorithm in Search, Optimization and Machine Learning,” New York: Addison – Wesley, 1989.

  • T. Stutzle and M. Dorigo, “The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances,” International Series in Operations Research and Management Science, Kluwer, 2001.

  • M. A. H. Akhand, S. Akter, M. A. Rashid and S. B. Yaakob, “Velocity Tentative PSO: An Optimal Velocity Implementation based Particle Swarm Optimization to Solve Traveling Salesman Problem,” IAENG International Journal of Computer Science, vol. 42, no.3, pp 221-232, 2015.

  • Byungsoo Na, Yeowoon Jun & Byung-In Kim, “Some extensions to the sweep algorithm”, Int J Adv Manuf Technol, vol. 56, pp. 1057–1067, 2011.

  • Y. F. Liao, D. H. Yau and C. L. Chen, “Evolutionary Algorithm to Traveling Salesman Problems,” Computers & Mathematics with Applications, vol. 64, no. 5, pp. 788–797, 2012.

  • Large Capacitated Vehicle Routing Problem Instances. Available: http://neo.lcc.uma.es/vrp/vrp-instances/


Abstract Views: 287

PDF Views: 2




  • Constructive and Clustering Methods to Solve Capacitated Vehicle Routing Problem

Abstract Views: 287  |  PDF Views: 2

Authors

M. A. H. Akhand
Dept. of Computer Science and EngineeringKhulna University of Engineering & Technology (KUET)Khulna-9203, Bangladesh
Tanzima Sultana
Dept. of Computer Science and EngineeringKhulna University of Engineering & Technology (KUET)Khulna-9203, Bangladesh
M. I. R. Shuvo
Dept. of Computer Science and EngineeringKhulna University of Engineering & Technology (KUET) Khulna-9203, Bangladesh
Al-Mahmud
Dept. of Computer Science and EngineeringKhulna University of Engineering & Technology (KUET) Khulna-9203, Bangladesh

Abstract


Vehicle Routing Problem (VRP) is a real life constraint satisfaction problem to find minimal travel distances of vehicles to serve customers. Capacitated VRP (CVRP) is the simplest form of VRP considering vehicle capacity constraint. Constructive and clustering are the two popular approaches to solve CVRP. A constructive approach creates routes and attempts to minimize the cost at the same time. Clarke and Wright's Savings algorithm is a popular constructive method based on savings heuristic. On the other hand, a clustering based method first assigns nodes into vehicle wise cluster and then generates route for each vehicle. Sweep algorithm and its variants and Fisher and Jaikumar algorithm are popular among clustering methods. Route generation is a traveling salesman problem (TSP) and any TSP optimization method is useful for this purpose. In this study, popular constructive and clustering methods are studied, implemented and compared outcomes in solving a suite of benchmark CVRPs. For route optimization, Genetic Algorithm (GA), Ant Colony Optimization (ACO) and Velocity Tentative Particle Swarm Optimization (VTPSO) are employed in this study which are popular nature inspired optimization techniques for solving TSP. Experimental results revealed that parallel Savings is better than series Savings in constructive method. On the other hand, Sweep Reference Point using every stop (SRE) is the best among clustering based techniques.

Keywords


Routing Problem, Constructive Method, Clustering Method, Clarke And Wright’s Savings Algorithm, Sweep Algorithm, Fisher And Jaikumar Algorithm, Genetic Algorithm, Ant Colony Optimization And Velocity Tentative Particle Swarm Optimization.

References





DOI: https://doi.org/10.13005/ojcst%2F10.03.02