An Improved Particle Swarm Optimization for a Class of Capacitated Vehicle Routing Problems

Document Type : Research Paper

Authors

1 MSc. Student, School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

2 Assistant Professor, School of Industrial Engineering, Iran University if Science and Technology, Tehran, Iran

3 Assistant Professor, School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

4 Instructor, School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

Abstract

Vehicle Routing Problem (VRP) is addressed to a class of problems for determining a set of vehicle routes, in which each vehicle departs from a given depot, serves a given set of customers, and returns back to the same depot. On the other hand, simultaneous delivery and pickup problems have drawn much attention in the past few years due to its high usage in real world cases. This study, therefore, considered a Vehicle Routing Problem with Time Windows and Simultaneous Delivery and Pickup (VRPTWSDP) and formulated it into a mixed binary integer programming. Due to the NP-hard nature of this problem, we proposed a variant of Particle Swarm Optimization (PSO) to solve VRPTWSDP. Moreover, in this paper we improve the basic PSO approach to solve the several variants of VRP including Vehicle Routing Problem with Time Windows and Simultaneous Delivery and Pickup (VRPTWSDP), Vehicle Routing Problem with Time Windows (VRPTW), Capacitated Vehicle Routing Problem (CVRP) as well as Open Vehicle Routing Problem (OVRP). In proposed algorithm, called Improved Particle Swarm Optimization (IPSO), we use some removal and insertion techniques and also combine PSO with Simulated Annealing (SA) to improve the searching ability of PSO and maintain the diversity of solutions. It is worth mentioning that these algorithms help to achieve a trade-off between exploration and exploitation abilities and converge to the global solution. Finally, for evaluating and analyzing the proposed solution algorithm, extensive computational tests on a class of popular benchmark instances, clearly show the high effectiveness of the proposed solution algorithm.

Keywords


-Ai, T. J. and Kachitvichyanukul, V. (2009) “Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem”, Computers & Industrial Engineering,Vol. 56, No. 1, pp. 380-387.
-Allahyari, S., Salari, M., and Vigo, D. (2015) “A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem”, European Journal of Operational Research, Vol. 242, No. 3, pp. 756-768.
-Belmecheri, F., Christian, P., Farouk, Y.and Lionel, A. (2013) “Particle swarm optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windows”, Journal of intelligent manufacturing, Vol. 24, No. 4, pp. 775-789.
-Castro, J. P., Landa-Silva, D., and Pérez, J. A. M., (2009) “Exploring feasible and infeasible regions in the vehicle routing problem with time windows using a multi-objective particle swarm optimization approach”, Nature inspired cooperative strategies for optimization, Springer, Vol. 236, pp. 103-114.
-Chen, A., Yang, G., and Wu, Z., (2006) “Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem”, Journal of Zhejiang University Science A, Vol. 7, No. 4, pp. 607-614.
-Chen, C. Y. and Ye, F. (2012) “Particle swarm optimization algorithm and its application to clustering analysis”, Networking, Sensing and Control, IEEE International Conference.
-Cho, P., Cheung, S. W., Edwards, M. H., Fung, J., (2003) “An assessment of consecutively presenting orthokeratology patients in a Hong Kong based private practice”, Clinical and Experimental Optometry, Vol. 86, No. 5, pp. 331-338.
-Christofides, B., Mingozzi, A., and Toth, P. (1979) “The Vehicle Routing Problem, in Combinatorial optimization”, B. Christofides, Editors. 1979, Chichester: Wiley, pp. 313-338.
-Chun-Hua, L., Hong, Z., and Jian, Z. (2009) “Vehicle routing problem with time windows and simultaneous pickups and deliveries”, Industrial Engineering and Engineering Management, IE&EM 16th International Conference.
-Clerk, M. (2006) “Particle Swarm Optimization”, London: ISTE.
-Cheng, C. Y., Chen, Y. Y., Chen, T. L., Yoo, J. J. (2015) “Using a hybrid approach based on the particle swarm optimization and ant colony optimization to solve a joint order batching and picker routing problem”, International Journal of Production Economics, Vol. 170, No. 3, pp. 805-814.
-Chen, M. C., Hsiao, Y. H., Reddy, R. H., Tiwari, M. K. (2016) “The Self-Learning Particle Swarm Optimization approach for routing pickup and delivery of multiple products with material handling in multiple cross-docks”, Transportation Research Part E: Logistics and Transportation Review, Vol. 91, pp. 208-226.
-Dantzig, G. B. and Ramser, J. H. (1959) “The truck dispatching problem”, Management Science, Vol. 6, No. 1, pp. 80-91.
-Diana, M. and Dessouky, M. M. (2004) “A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows”, Transportation Research Part B: Methodological, Vol. 38, No. 6, pp. 539-557.
-Figureueiredo, E., Ludermir, T. B., and Bastos-Filho, C. (2016) “Many Objective Particle Swarm Optimization”, Information Sciences, Vol. 374, pp. 115-134.
-Goksal, F. P., Karaoglan, I. and Altiparmak, F. (2013) “A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery” Computers & Industrial Engineering, Vol. 65, No. 1, pp. 39-53.
-Gong, Y. J., Zhang, J., Liu, O., Huang, R. Z., Chung, H. S. (2012) “Optimizing the vehicle routing problem with time windows: a discrete particle swarm optimization approach”, Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions, Vol. 42, No. 2, pp. 254-267.
-Han, J., Zhang, G., Hu, Y., Lu, J. (2016) “A solution to bi/tri-level programming problems using particle swarm optimization”, Information Sciences, Vol. 370-371, pp. 519-537.
-Karaoglan, I., Altiparmak, F., Kara, I., Dengiz, B. (2012) “The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach”, Omega, Vol. 40, No. 4, pp. 465-477.
-Kennedy, J. and Eberhart, R. (1955) “particle swarm optimization”, proceedings of IEEE international conference on neural networks, Vol. 4, pp. 1942-1948.
-Kennedy, J. and Eberhart, R. (2001) “Swarm Intelligence”, San Francisco: Morgan Kaufmann Publishers.
-Kim, B. I. and Son, S. J. (2012) “A probability matrix based particle swarm optimization for the capacitated vehicle routing problem”, Journal of Intelligent Manufacturing, Vol. 23, No. 4, pp. 1119-1126.
-Kirkpatrick, S. C., Gelatt, D and Vecchi, M. P.  (1984) “Optimization by simulated annealing: Quantitative studies”, Journal of statistical physics, Vol. 34, No. 5-6, pp. 975-986.
-Küçükoğlu, İ. and Öztürk, N. (2015) “An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows”, Computers & Industrial Engineering, Vol. 86, pp. 60-68.
-Kumar, R. S., Kondaraneni, K., Dixit, V., Goswami, A. and Thakur, L. S. (2016) “Multi-objective modeling of production and pollution routing problem with time window: A self-learning particle swarm optimization approach”, Computers & Industrial Engineering, Vol. 99, pp. 29-40.
-Lichtblau, T. (2002) “Discrete Optimization using Mathematica, in World Multi Conference on Systemic and Informatics”, Callaos, N. Editors, International Institute of Informatics and Systemics, pp. 169-174.
-Liang, J. J., Qin, I. K., Suganthan, P. N., Baskar, S. (2006) “Comprehensive learning particle swarm optimizer for global optimization of multimodal functions”, IEEE transactions on evolutionary computation, Vol. 10, No. 3, pp. 281-295.
-Marinakis, Y. and Marinaki, M. (2008) “A particle swarm optimization algorithm with path relinking for the location routing problem”, Journal of Mathematical Modelling and Algorithms, Vol. 7, No. 1, pp. 59-78.
-Marinakis, Y., Iordanidou, G. R. and Marinaki, M. (2013) “Particle swarm optimization for the vehicle routing problem with stochastic demands”, Applied Soft Computing, Vol. 13, No. 4, pp. 1693-1704.
-Mester, D. and Bräysy, O. (2007) “Active-guided evolution strategies for large-scale capacitated vehicle routing problems”, Computers & operations research, Vol.  34, No. 10, pp. 2964-2975.
-Mester, D., Bräysy, O. and Dullaert, W. (2007) “A multi-parametric evolution strategies algorithm for vehicle routing problems”, Expert Systems with Applications, Vol. 32, No. 2, pp. 508-517.
-Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N. and Teller A. H. (1953) “Equation of state calculations by fast computing machines”, The journal of chemical physics, Vol. 21, No. 6, pp. 1087-1092.
-MirHassani, S. and Abolghasemi, N. (2011) “A particle swarm optimization algorithm for open vehicle routing problem”, Expert Systems with Applications, Vol. 38, No. 9, pp. 11547-11551.
-Moghaddam, B. F., Ruiz, R. and Sadjadi, S. J. (2012) “Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm”, Computers & Industrial Engineering, Vol. 62, No. 1, pp. 306-317.
-Montané, F. A. T. and Galvao, R. D. (2006) “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service”, Computers and Operations Research, Vol. 33, No. 3, pp. 595–619.
-Mokhtarimousavi, S., Rahami, H., Saffarzadeh, M. and Piri, S. (2014) “Determination of the aircraft landing sequence by two meta-heuristic algorithms”, International Journal of Transportation Engineering, Vol. 1, No. 4, pp. 271-284.
-Marinakis, Y., (2015) “An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands”, Applied Soft Computing, Vol. 37, pp. 680-701.
-Naderi, B., Zandieh, M., Balagh, A. K. G. and Roshanaei, V. (2009) “An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness”, Expert systems with Applications, Vol. 36, No. 6, pp. 9625-9633.
-Norouzi, N., Sadegh-Amalnick, M. and Alinaghiyan, M. (2015) “Evaluating of the particle swarm optimization in a periodic vehicle routing problem”, Measurement, Vol. 62, pp. 162-169.
-Pisinger, D. and Ropke, S. (2007) “A general heuristic for vehicle routing problems”, Computers & operations research, Vol. 34, No. 8, pp. 2403-2435.
-Planeta, D. S. (2007) “Priority Queue Based on Multilevel Prefix Tree”, eprint arXiv:0708.2936
-Poli, R., Kennedy, J. and Blackwell, T. (2007) “Particle swarm optimization”, Swarm intelligence, Vol. 1, No. 1, pp. 33-57.
-Romero, R., Gallego, R. and Monticelli, A. (1995) “Transmission system expansion planning by simulated annealing”, IEEE Transactions on Power Systems, Vol. 11, No. 1, pp. 364-369.
-Salari, M., Toth, P. and Tramontani, A. (2010) “An ILP improvement procedure for the Open Vehicle Routing Problem”, Computers & Operations Research, Vol.  37, No. 12, pp. 2106-2120.
-Shi, Y. and Eberhart, R. C. (1998) “A modified particle swarm optimizer”, IEEE international conference on evolutionary computation Proceedings, pp. 69–73.
-Solomon, M. M. and Desrosiers, J. (1988) “Survey paper-time window constrained routing and scheduling problems”, Transportation science, Vol. 22, No. 1, pp. 1-13.
-Solomon, M. M. (1987) “Algorithms for the vehicle routing and scheduling problems with time window constraints”, Operations research, Vol. 35, No. 2, pp. 254-265.
-Thoth, P. and Vigo, D. (2002) “The vehicle routing problem”, Philadelphia, PA: SIAM.
-Tian, J., Ma, W. Z., Wang, Y. L. and Wang, K. L. (2011) “Emergency supplies distributing and vehicle routes programming based on particle swarm optimization”, Systems Engineering-Theory & Practice, Vol. 5, pp. 0-16.
-Ursani, Z., Essam, D., Cornforth, D. and Stocker, R. (2011) “Localized genetic algorithm for vehicle routing problem with time windows”, Applied Soft Computing, Vol. 11, No. 8, pp. 5375-5390.
-Van Laarhoven, P. J. and Aarts, E. H. (1987) “Simulated annealing: theory and applications”, Springer Science & Business Media, Vol. 37, pp. 7-15.
-Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N. and Rei, W. (2012) “A hybrid genetic algorithm for multidepot and periodic vehicle routing problems”, Operations Research, Vol. 60, No. 3, pp. 611-624.
-Wang, H. and Chen, Y. A (2012) “A genetic algorithm for the simultaneous delivery and pickup problems with time window”, Computers and Industrial Engineering, Vol. 62, No. 1, pp. 84-95.
-Wang, H., Sun, H., Li, C., Rahnamayan, S. and Pan, J. S. (2013) “Diversity enhanced particle swarm optimization with neighborhood search”, Information Sciences, Vol. 223, pp. 119-135.
-Wang, K. P., Huang, L., Zhou, C. G. and Pang, W. (2003) “Particle swarm optimization for traveling salesman problem”, International Conference on Machine Learning and Cybernetics, IEEE, Vol. 3, pp. 1583-1585.
-Wang, W., Wu, B., Zhao, Y. and Feng, D. (2006) “Particle swarm optimization for open vehicle routing problem”, Computational Intelligence, Springer, Volume 4114 of the book series, pp. 999-1007.
-Wu, C., Liang, Y., Lee, H. P. and Lu, C. (2004) “Generalized chromosome genetic algorithm for generalized traveling salesman problems and its applications for machining”, Physical Review E, Vol. 70, No. 1, pp. 016701.
-Xiao, J. M., Huang, Y. F., Li, J. J. and Wang, X. H. (2005) “Vehicle Routing Problem Based on Discrete Particle Swarm Optimization”, Systems Engineering, Vol. 4, pp. 97-100.
-Xiao, J. M., Li, J. J. and Wang, X. H. (2005) “particle swarm optimization algorithm for vehicle routing problem1”, Computer Integrated Manufacturing Systems, Vol. 11, No. 4, pp. 577-581.
-Xu, J. and Huang, D. (2007) “Hybrid particle swarm optimization for vehicle routing problem with multiple objectives”, Computer Integrated Manufacturing Systems-Beijing, Vol. 13, No. 3, pp. 573.
-Yannis, M. and Magdalene, M. A. (2010) “Hybrid genetic - particle swarm optimization algorithm for the vehicle routing problem”, Expert Systems with Applications, Vol. 37, No. 2, pp. 1446-1455.
-Zang, H., Jue, J.P. and Mukherjee, B. (2000) “Capacity allocation and contention resolution in a photonic slot routing all-optical WDM mesh network”, Journal of lightwave technology, Vol. 18, No. 12, pp. 1728.
-Zhang, J. (2012) “Particle Swarm Optimization Using Crossover Operator”, Journal of Convergence Information Technology, Vol. 7, No. 4, pp. 287-295.
-Zhang, L., Pang, X. H., Xia, W. and Wu, Z. (2006) “A hybrid particle swarm optimization algorithm for vehicle routing problem with time windows”, Journal of Shanghai Jiaotong University, Vol. 40, No. 11, pp. 1890.
-Zhu, Q., Qian, L., Li, Y. and Zhu, S. (2006) “An improved particle swarm optimization algorithm for vehicle routing problem with time windows”, IEEE Congress on Evolutionary Computation, pp. 1386-1390.