Solving Capacitated Vehicle Routing Problem Using Variant Sweep and Swarm Intelligence

M. A. H.  Akhand; Zahrul Jannat  Peya; Tanzima  Sultana; M. M. Hafizur  Rahman

doi:10.6180/jase.2017.20.4.13

Solving Capacitated Vehicle Routing Problem Using Variant Sweep and Swarm Intelligence

Computer Science and Information Engineering

M. A. H. Akhand This email address is being protected from spambots. You need JavaScript enabled to view it.¹, Zahrul Jannat Peya¹, Tanzima Sultana¹ and M. M. Hafizur Rahman²

¹Department of Computer Science and Engineering, Khulna University of Engineering & Technology, Khulna-9203, Bangladesh
²Xiamen University, Malaysia, Sunsuria City, Sepang 43900 Selangor, Malaysia

Received: November 7, 2016
Accepted: January 3, 2017
Publication Date: December 1, 2017

Download Citation: ||https://doi.org/10.6180/jase.2017.20.4.13

ABSTRACT

Capacitated vehicle routing problem (CVRP) is a real life constraint satisfaction problem in which customers are optimally assigned to individual vehicles (considering their capacity) to keep total travel distance of the vehicles as minimum as possible while serving customers. Various methods are used to solve CVRP in last few decades, among them the most popular way is splitting the task into two different phases: assigning customers under different vehicles and then finding optimal route of each vehicle. Sweep clustering algorithm is well studied for clustering nodes. On the other hand, route optimization is simply a traveling salesman problem (TSP) and a number of TSP optimization methods are applied for this purpose. This study investigates a variant of Sweep algorithm for clustering nodes and different Swarm Intelligence (SI) based methods for route generation to get optimal CVRP solution. In conventional Sweep algorithm, cluster formation starts from smallest angle and consequently advances to consider all the nodes. In variant Sweep of this study, cluster formation are considered from different starting angles. On the other hand, four TSP optimization methods including recent ones are considered for route optimization. The experimental results on a large number of benchmark CVRPs revealed that clustering with proposed variant Sweep and route optimization with Velocity Tentative Particle Swarm Optimization is able to produce better solution. Finally, the proposed mythology is found to achieve better solutions for several CVRPs when compared with prominent existing methods.

Keywords: Capacitated Vehicle Routing Problem, Sweep Clustering, Genetic Algorithm, Ant Colony Optimization, Producer-scrounger Method, Velocity Tentative Particle Swarm Optimization

REFERENCES

[1] Yeun, L. C., Ismail, W. R., Omar, K. and Zirour, M., “Vehicle Routing Problem: Models and Solutions,” Journal of Quality Measurement and Analysis, Vol. 3, No. 1, pp. 205218 (2008).
[2] Chen, A., Yang, G. and Wu, Z., “Hybrid DiscreteParticle Swarm Optimization Algorithm for Capacitated Vehicle Routing Problem,” Journal of Zhejiang UniversitySCIENCEA,Vol.7,No. 4,pp. 607614 (2006). doi: 10.1631/jzus.2006.A0607
[3] Tan, W. F., Lee, L. S., Majid, Z. A. and Seow, H. V., “Ant Colony Optimization for Capacitated Vehicle Routing Problem,” Journal of Computer Science, Vol. 8, No. 6, pp. 846852 (2012). doi: 10.3844/jcssp.2012. 846.852
[4] Nazif, H. and Lee, L. S., “Optimised Crossover Genetic Algorithm for Capacitated Vehicle Routing Problem,” Applied Mathematical Modelling, Vol. 36, pp. 2110–2117 (2012). doi: 10.1016/j.apm.2011.08.010
[5] Tavakoli, M. M. and Sami, A., “Particle Swarm Optimization in Solving Capacitated Vehicle Routing Problem,” Bulletin of Electrical Engineering and Informatics, Vol. 2, No. 4, pp. 252257 (2013).
[6] Nurcahyo, G. W., Alias, R. A., Shamsuddin, S. M. and Sap, M. N. Md., “Sweep Algorithmin VehicleRouting Problem for Public Transport,” Journal Antarabangsa (Teknologi Maklumat), Vol. 2, pp. 5164 (2002).
[7] Han, S. and Tabata, Y., “A Hybrid Genetic Algorithm for the Vehicle Routing Problem with Controlling Lethal Gene,” Asia Pacific Management Review, Vol. 7, No. 3, pp. 405426 (2002).
[8] Suthikarnnarunai, N., “A Sweep Algorithm for the Mix Fleet Vehicle Routing Problem,” in Proc. of the International Multi Conference of Engineers and Computer Scientists, Vol. 2, March 1921, Hong Kong (2008).
[9] Shin, K. and Han, S., “ACentroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem,” Computing and Informatics, Vol. 30, pp. 721–732 (2011).
[10] Yousefikhoshbakht, M. and Khorram, E., “Solving the Vehicle Routing Problem by a Hybrid Meta-heuristic Algorithm,” Journal of Industrial Engineering International, Vol. 8, No. 11 (2012). doi: 10.1186/2251712X-8-11
[11] Kanthavel, K. and Prasad, P., “Optimization of Capacitated Vehicle Routing Problem by Nested Particle Swarm Optimization,” American Journal of Applied Sciences, Vol. 8, No. 2, pp. 107112 (2011). doi: 10.3844/ajassp.2011.107.112
[12] Aziz, M. M. A., El-Ghareeb, H. A. and Ksasy, M. S. M., “Hybrid Heuristic Algorithm for Solving CapacitatedVehicleRouting Problem,”International Journal of Computers & Technology, Vol. 12, No. 9, pp. 3845 3851 (2014).
[13] Goldberg, D. E., Genetic Algorithm in Search, Optimization and Machine Learning, New York: Addison – Wesley (1989).
[14] Stutzle, T. and Dorigo, M., “The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances,” International Series in Operations Research and Management Science, Kluwer (2001). doi: 10.1007/0-306-48056-5_9
[15] Liao, Y. F., Yau, D. H. and Chen, C. L., “Evolutionary Algorithm to Traveling SalesmanProblems,” Computers & Mathematics with Applications, Vol. 64, No. 5, pp. 788–797 (2012). doi:10.1016/j.camwa.2011.12.018
[16] Akhand, M. A. H., Imran Hossain, Sk. and Akter, S., “A Comparative Study of Prominent Particle Swarm Optimization Based Methods to Solve Traveling Salesman Problem,”International Journal ofSwarm Intelligence and Evolutionary Computation, Vol. 5, No. 3,
paper id 139 (10 pages) (2016). doi: 10.4172/20904908.1000139
[17] Akhand, M. A. H., Shill, P. C., Forhad Hossain, Md., Junaed, A. B. M. and Murase, K., “Producer-scrounger Method to Solve Traveling Salesman Problem,” I. J. Intelligent Systems and Applications, Vol. 7, No. 3, pp. 2936 (2015). doi: 10.5815/ijisa.2015.03.04
[18] Venkatesan, S. R., Logendran, D. and Chandramohan, D., “Optimization of Capacitated Vehicle Routing Problem using PSO,” International Journal of Engineering Science and Technology, Vol. 3, pp. 74697477 (2011).
[19] Boonkleaw, A., Suthikarnnarunai, N. and Srinon, R., “Strategic Planning and Vehicle Routing Algorithm for Newspaper Delivery Problem: Case Study of Morning Newspaper, Bangkok, Thailand,” in Proc. of the World Congress on Engineering and Computer Science 2009, Vol. 2, October 2022 (2009).
[20] Na, B., Jun, Y. and Kim, B., “Some Extensions to the Sweep Algorithm,” Int J Adv Manuf Technol, Vol. 56, pp.1057–1067(2011).doi:10.1007/s00170-011-3240-7
[21] Baker, B. M. and Ayechew, M. A., “A Genetic Algorithm for the Vehicle Routing Problem,” Computers & Operations Research, Vol. 30, pp. 787800 (2003). doi: 10.1016/S0305-0548(02)00051-5
[22] Vaira, G., GeneticAlgorithm for VehicleRouting Problem,PhD.Thesis,VilniusUniversity,Lithuania(2014).
[23] Reed, M., Yiannakou, A. and Evering, R., “An Ant Colony Algorithm for the Multi-compartment Vehicle Routing Problem,” Applied Soft Computing, Vol. 15, pp. 169176 (2014). doi: 10.1016/j.asoc.2013.10.017
[24] Kao, Y., Chen, M. and Huang, Y., “A Hybrid Algorithm Based on ACO and PSO for Capacitated Vehicle Routing Problems,” Mathematical Problems in Engineering, Article ID 726564 (17 pages) (2012). doi: 10.1155/2012/726564
[25] He, S., Wu, Q. H. and Saunders, J. R., “Group Search Optimizer: an Optimization Algorithm Inspired by Animal Searching Behavior,” IEEE Transactions on Evolutionary Computation, Vol. 13, No 5, pp. 973 990 (2009). doi: 10.1109/TEVC.2009.2011992
[26] Eberhart, R. and Kennedy, J., “A New Optimizer Using Particles Swarm Theory,” Roc Sixth International Symposium on Micro Machine and Human Science (Nagoya, Japan) IEEE Service Center, Piscataway, NJ:39-43 (1995). doi: 10.1109/MHS.1995.494215
[27] Wang, K. P., Huang, L., Zhou, C. G. and Pang, W., “Particle Swarm Optimization for Traveling Salesman Problem,” in Proc. International Conference on Machine Learning and Cybernetics, pp. 1583–1585, November (2003). doi: 10.1109/ICMLC.2003.1259748
[28] Yan, X., Zhang, C., Luo, W., Li, W., Chen, W. and Liu, H., “Solve Traveling SalesmanProblemUsing Particle Swarm Optimization Algorithm,” IJCSI International Journal of Computer Science Issues, Vol. 9, No. 6(2), pp. 264271 (2012).
[29] Akhand, M. A. H., Akter, S., Rashid, M. A. and Yaakob, S. B., “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 221232 (2015).
[30] Marinakis, Y., Iordanidou, G. and Marinaki, M., “Particle Swarm Optimization for the Vehicle Routing Problem with Stochastic Demands,” Applied Soft Computing, Vol. 13, No. 4, pp. 16931704 (2013). doi: 10.1016/j.asoc.2013.01.007
[31] Xiang, T., Pan, D. and Pei, H., “Vehicle Routing Problem Based on Particle Swarm Optimization Algorithm with Gauss Mutation,” American Journal of Software Engineering and Applications, Vol. 5, No. 1, pp. 16 (2016). doi: 10.11648/j.ajsea.20160501.11
[32] Large CapacitatedVehicleRouting ProblemInstances. Available: http://neo.lcc.uma.es/vrp/vrp-instances/