Abstract
Capacitated vehicle routing problem (CVRP) is an NP-hard problem. For large-scale problems, it is quite difficult to achieve an optimal solution with traditional optimization methods due to the high computational complexity. A new hybrid approximation algorithm is developed in this work to solve the problem. In the hybrid algorithm, discrete particle swarm optimization (DPSO) combines global search and local search to search for the optimal results and simulated annealing (SA) uses certain probability to avoid being trapped in a local optimum. The computational study showed that the proposed algorithm is a feasible and effective approach for capacitated vehicle routing problem, especially for large scale problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Baker, B.M., Ayechew, M.A., 2003. A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5):787–800. [doi: 10.1016/S0305-0548(02)00051-5]
Bell, J.E., McMullen, P.R., 2004. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18(1):41–48. [doi: 10.1016/j.aei.2004.07.001]
Bodin, L., Golden, B.L., Assad, A., Ball, M.O., 1983. The state of the art in the routing and scheduling of vehicles and crews. Computers & Operations Research, 10:69–221.
Christofides, N., Mignozzi, A., Toth, P., 1981. Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxations. Mathematical Programming, 20(1):255–282. [doi: 10.1007/BF01589353]
Cordeau, J.F., Laporte, G., Mercier, A., 2001. A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8):928–936. [doi: 10.1057/palgrave/jors/2601163]
Dantzig, G.B., Ramser, R.H., 1959. The truck dispatching problem. Management Science, 6:80–91.
Eberhart, R., Kennedy, J., 1995. A New Optimizer Using Particle Swarm Theory. Proceeding of the Sixth International Symposium on Micro Machine and Human Science, p.39–43.
Gendreau, M., Hertz, A., Laporte G., 1994. A tabu search heuristic for the vehicle routing problem. Management Science, 40:1276–1290.
Hasan, M., Osman, I.H., 1995. Local search algoirthm for the maximal planar layout problem. International Transactions in Operational Research, 2(1):89–106. [doi: 10.1016/0969-6016(95)00029-7]
Kennedy, J., Eberhart, R., 1995. Particle Swarm Optimization. Proceeding of the 1995 IEEE International Conference on Neural Network, p.1942–1948.
Laporte, G., 1992. The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59(3):345–358. [doi: 10.1016/0377-2217(92)90192-C]
Osman, I.H., 1993. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41(4):421–451. [doi: 10.1007/BF02023004]
Osman, I.H., Potts, C.N., 1989. Simulated annealing for permutation flow shop scheduling. Omega, 17(6):551–557. [doi: 10.1016/0305-0483(89)90059-5]
Salman, A., Ahmad, I., Madani, S.A., 2002. Particle swarm optimization for task assignment problem. Microprocessors and Microsystems, 26(8):363–371. [doi: 10.1016/S0141-9331(02)00053-4]
Shi, Y., Eberhart, R., 1999. Empirical Study of Particle Swarm Optimization. Proceedings of Congress on Evolutionary Computation, p.1945–1950.
Shigenori, N., Takamu, G.J., Toshiki, Y., Yoshikazu, F., 2003. A hybrid particle swarm optimization for distribution state estimation. IEEE Trans. on Power Systems, 18(1):60–68. [doi: 10.1109/TPWRS.2002.807051]
Toth, P., Vigo, D., 1998. Exact Solution of the Vehicle Routing Problem. In: Crainic, T.G., Laporte, G. (Eds.), Fleet Management and Logistics. Kluwer Academic Publishers, Norwell, MA, p.1–31.
Toth, P., Vigo, D., 2002. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Vol. 9. SIAM, Philadelphia, PA.
van Laarhoven, P.J.M., Aarts, E.H.L., Lenstra, J.K., 1992. Job shop scheduling by simulated annealing. Operations Research, 40:113–125.
Wang, Z.Z., Cheng, J.X., Fang, H.G., Qian, F.L., 2004. A hybrid optimization algorithm solving vehicle routing problems. Operations Research and Management Science, 13:48–52 (in Chinese).
Xia, W.J., Wu, Z.M., 2005. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48(2):409–425. [doi: 10.1016/j.cie.2005.01.018]
Yang, S.Y., Wang, M., Jiao, L.C., 2004. A Quantum Particle Swarm Optimization. Proceedings of the 2004 IEEE Congress on Evolutionary Computation, 1:320–324.
Zhao, Y.W., Wu, B., Jiang, L., Dong, H.Z., Wang, W.L., 2004. Study of the optimizing of physical distribution routing problem based on genetic algorithm. Computer Integrated Manufacturing Systems, 10(3):303–306 (in Chinese).
Author information
Authors and Affiliations
Additional information
Project (No. 60174009) supported by the National Natural Science Foundation of China
Rights and permissions
About this article
Cite this article
Chen, Al., Yang, Gk. & Wu, Zm. Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. J. Zhejiang Univ. - Sci. A 7, 607–614 (2006). https://doi.org/10.1631/jzus.2006.A0607
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1631/jzus.2006.A0607