Oriental Journal of Computer Science and Technology

Open Access Open Access  Restricted Access Subscription Access

Capacitated Vehicle Routing Problem Solving through Adaptive Sweep based Clustering plus Swarm Intelligence based Route Optimization


Affiliations
1 Dept. of Computer Science and Engineering, Khulna University of Engineering & Technology Khulna, Bangladesh
2 Kazuyuki Murase, Graduate School of Engineering, University of Fukui, Fukui, Japan
 

Capacitated Vehicle Routing Problem (CVRP) is an optimization task where customers are assigned to vehicles aiming that combined travel distances of all the vehicles as minimum as possible while serving customers. A popular way among various methods of CVRP is solving it in two phases: grouping or clustering customers into feasible routes of individual vehicles and then finding their optimal routes. Sweep is well studied clustering algorithm for grouping customers and different traveling salesman problem (TSP) solving methods are commonly used to generate optimal routes of individual vehicles. This study investigates effective CVRP solving method based on recently developed adaptive Sweep and prominent Swarm Intelligence (SI) based TSP optimization methods. The adaptive Sweep cluster is a heuristic based adaptive method to select appropriate cluster formation starting angle of Sweep. Three prominent SI based TSP optimization methods are investigated which are Ant Colony Optimization, Producer-Scrounger Method and Velocity Tentative Particle Swarm Optimization (VTPSO). Genetic Algorithm is also considered since it is the pioneer and well-known population based method. The experimental results on two suites of benchmark CVRPs identified the effectiveness of adaptive Sweep plus SI methods in solving CVRP. Finally, adaptive Sweep plus the VTPSO is found better than other tested methods in this study as well as several other prominent existing methods.

Keywords

Capacitated Vehicle Routing Problem, Sweep Clustering, Adaptive Sweep, Ant Colony Optimization, Producer-Scrounger Method, Velocity Tentative Particle Swarm Optimization.
User
Notifications
Font Size

  • G. B. Dantzig and J. H. Ramser, 1959, “The Track Dispatching Problem”, Management Science, Vol. 6, No. 1, pp. 80-91, Oct., 1959.

  • G. Laporte, M. Gendreau, J-Yy. Potvin, and F. Semet., “Classical and modern heuristics for the vehicle routing problem”, International Transactions in Operational Research, Vol. 7, 285-300, 2000.

  • P. Toth and D. Vigo, “The Vehicle Routing Problem”, SIAM Monographs on Discr. Math. Appl. 9, 2001

  • T. Caric, A. Galic, J. Fosin, et al., “A Modelling and Optimization Framework for Real World Vehicle Routing Problems”, Vehicle Routing Problem, ISBN 978-953-7619-091, Austria: In-Tech, 2008.

  • S. N. Kumar and R. Panneerselvam, “A Survey on the Vehicle Routing Problem and Its Variants”, Intelligent Information Management, Vol. 4, pp. 66-74, 2012.

  • Report on overview of the Vehicle Routing Problem. Available: https://info.maths.ed.ac.uk/assets/files/Projects/17.pdf

  • F. Takes, “Applying Monte Carlo Techniques to the Capacitated Vehicle Routing Problem”, Msc. Thesis, Leiden University, The Netherlands, February 26, 2010.

  • K. Shin, “A Centroid-Based Heuristic Algorithm for the Capacitated Vehicle Routing Problem”, Computing and Informatics, vol. 30, pp. 721–732, 2011.

  • R. Z. Farahani, “The Vehicle-Routing Problem,” Logistics Operations and Management: Concepts and Models, ISBN: 978-0-12-385202-1, USA: Elsevier Insights, 2011.

  • M. M. A. Aziz, H. A. El-Ghareeb and M. S. M. Ksasy, “Hybrid Heuristic Algorithm for solving Capacitated Vehicle Routing Problem”, International Journal of Computers & Technology, Vol. 12, no.9, pp. 3845-3851, 2014.

  • G. Vaira, “Genetic Algorithm for Vehicle Routing Problem,” PhD. Thesis, Vilnius University, Italy, 2014.

  • N. M. Darani, V. Ahmadi, Z. S. Eskandari and M. Yyousefikhoshbakht, “Solving the Capacitated Clustering Problem by a Combined Meta-Heuristic Algorithm,” Journal of Advances in Computer Research, vol. 4, no. 1, pp. 89-100, 2013.

  • B. E. Gillett and L. R. Miller, “A heuristic algorithm for the vehicle dispatch problem,” Operations Research, vol. 22, no. 2 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.

  • S. Han and Yy. Tabata, “A Hybrid Genetic Algorithm for the Vehicle Routing Problem with Controlling Lethal Gene,” Asia Pacific Management Review, vol. 7,no. 3, pp. 405-426, 2002.

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

  • B. Na, Yy. Jun and B. Kim, “Some Extensions to the Sweep Algorithm,” Int J AdvManufTechnol, vol. 56, pp. 1057–1067, 2011.

  • H. Nazif and L. S. Lee, “Optimized Crossover GA for Capacitated Vehicle Routing Problem”,” ELSEVIER, vol. 36, pp. 2110–2117, 2012.

  • M. Yyousefikhoshbakht and E. Khorram, “Solving the vehicle routing problem by a hybrid meta-heuristic algorithm,” Journal of Industrial Engineering International, vol. 8(11), 2012.

  • W. F. Tan, L. S. Lee, Z. A. Majid and H. V. Seow, “Ant Colony Optimization for CVRP”, Journal of Computer Sciences, pp 846-852, 2012.

  • Y y. Kao, M. H. Chen and Yy. T. Huang, “A Hybrid Algorithm based on ACO and PSO for CVRP”, Research Article,Mathematical Problems in Engineering, vol. 2012, 2012.

  • K. Kanthavel and P. Prasad, “Optimization of CVRP by Nested Particle Swarm Optimization” American Journal of Applied Sciences, vol. 8, pp. 107-112, 2011.

  • M. M. Tavakoli and A. Sami, “Particle Swarm Optimization in Solving Capacitated Vehicle Routing Problem”, Bulletin of Electrical Engineering and Informatics, Vol. 2, No. 4, pp. 252-257, ISSN: 2089-3191, December 2013.

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

  • C. Pornsing, “A Particle Swarm Optimization for the Vehicle Routing Problem,” PhD. Thesis, University of Rhode Island, USA, 2014.

  • M. A. H. Akhand, Z. Jannat, T. Sultana and Al-Mahmud, “Optimization of Capacitated Vehicle Routing Problem using Producer-Scrounger Method,” in Proc. of 2015 IEEE International WIE Conference on Electrical and Computer Engineering (WIECON-ECE 2015), BUET, Dhaka, Bangladesh, pp. 297-300, December 19-20, 2015.

  • M. A. H. Akhand, Z. Jannat, K.Murase,”Capacitated Vehicle Routing Problem solving using Adaptive Sweep and VTPSO ”, IJACSA, vol 8,No.12,2017.

  • P. Boonsam and N. Suthikarnnarunai, “Assignment Problem and Vehicle Routing Problem for an Improvement of Cash Distribution,” Proceedings of the World Congress on Engineering and Computer Science 2011, Vol II, WCECS 2011, October 19-21, 2011, San Francisco, USA.

  • M. A. H. Akhand, T. Sultana, M. I. R. Shuvo and Al-Mahmud, “Constructive and Clustering Methods to Solve Capacitated Vehicle Routing Problem,” Orient. J. Comp. Sci. and Technol., vol.10, no. 3, paper id 6623(10 pages), 2017.

  • D. E. Goldberg, ‘Genetic Algorithm in Search, Optimization and Machine Learning’, New Yyork: 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, P. C. Shill, Md. Forhad Hossain, A. B. M. Junaed, and K. Murase, “Producer-Scrounger Method to Solve Traveling Salesman Problem”, I. J. Intelligent Systems and Applications, vol. 7, no. 3, pp. 29-36, 2015.

  • M. A. H. Akhand, S. Akter, M. A. Rashid and S. B. Yyaakob, “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.

  • K. P. Wang, L. Huang, C. G. Zhou and W. Pang, “Particle swarm optimization for traveling salesman problem,” in Proc. International Conference on Machine Learning and Cybernetics, November 2003, pp. 1583–1585.

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


Abstract Views: 247

PDF Views: 4




  • Capacitated Vehicle Routing Problem Solving through Adaptive Sweep based Clustering plus Swarm Intelligence based Route Optimization

Abstract Views: 247  |  PDF Views: 4

Authors

Zahrul Jannat Peya
Dept. of Computer Science and Engineering, Khulna University of Engineering & Technology Khulna, Bangladesh
M. A. H. Akhand
Dept. of Computer Science and Engineering, Khulna University of Engineering & Technology Khulna, Bangladesh
Kazuyuki Murase
Kazuyuki Murase, Graduate School of Engineering, University of Fukui, Fukui, Japan

Abstract


Capacitated Vehicle Routing Problem (CVRP) is an optimization task where customers are assigned to vehicles aiming that combined travel distances of all the vehicles as minimum as possible while serving customers. A popular way among various methods of CVRP is solving it in two phases: grouping or clustering customers into feasible routes of individual vehicles and then finding their optimal routes. Sweep is well studied clustering algorithm for grouping customers and different traveling salesman problem (TSP) solving methods are commonly used to generate optimal routes of individual vehicles. This study investigates effective CVRP solving method based on recently developed adaptive Sweep and prominent Swarm Intelligence (SI) based TSP optimization methods. The adaptive Sweep cluster is a heuristic based adaptive method to select appropriate cluster formation starting angle of Sweep. Three prominent SI based TSP optimization methods are investigated which are Ant Colony Optimization, Producer-Scrounger Method and Velocity Tentative Particle Swarm Optimization (VTPSO). Genetic Algorithm is also considered since it is the pioneer and well-known population based method. The experimental results on two suites of benchmark CVRPs identified the effectiveness of adaptive Sweep plus SI methods in solving CVRP. Finally, adaptive Sweep plus the VTPSO is found better than other tested methods in this study as well as several other prominent existing methods.

Keywords


Capacitated Vehicle Routing Problem, Sweep Clustering, Adaptive Sweep, Ant Colony Optimization, Producer-Scrounger Method, Velocity Tentative Particle Swarm Optimization.

References