×

zbMATH — the first resource for mathematics

Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. (English) Zbl 1166.90319
Summary: 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.

MSC:
90B20 Traffic problems in operations research
90C10 Integer programming
Software:
VRP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baker, B. M.; Ayechew, M. A., A genetic algorithm for the vehicle routing problem, Computers & Operations Research, 30, 787-800, (2003) · Zbl 1026.90013
[2] Bell, J. E.; McMullen, P. R., Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics, 18, 41-48, (2004)
[3] Bodin, L.; Golden, B. L.; Assad, A.; Ball, M. O., The state of the art in the routing and scheduling of vehicles and crews, Computers & Operations Research, 10, 69-221, (1983)
[4] Christofides, N.; Mignozzi, A.; Toth, P., Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxations, Mathematical Programming, 20, 255-282, (1981) · Zbl 0461.90067
[5] Cordeau, J. F.; Laporte, G.; Mercier, A., A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, 52, 928-936, (2001) · Zbl 1181.90034
[6] Dantzig, G. B.; Ramser, R. H., The truck dispatching problem, Management Science, 6, 80-91, (1959) · Zbl 0995.90560
[7] 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.
[8] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Management Science, 40, 1276-1290, (1994) · Zbl 0822.90053
[9] Hasan, M.; Osman, I. H., Local search algoirthm for the maximal planar layout problem, International Transactions in Operational Research, 2, 89-106, (1995) · Zbl 0868.90072
[10] Kennedy, J., Eberhart, R., 1995. Particle Swarm Optimization. Proceeding of the 1995 IEEE International Conference on Neural Network, p.1942-1948.
[11] Laporte, G., The vehicle routing problem: an overview of exact and approximate algorithms, European Journal of Operational Research, 59, 345-358, (1992) · Zbl 0761.90034
[12] Osman, I. H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, 41, 421-451, (1993) · Zbl 0775.90153
[13] Osman, I. H.; Potts, C. N., Simulated annealing for permutation flow shop scheduling, Omega, 17, 551-557, (1989)
[14] Salman, A.; Ahmad, I.; Madani, S. A., Particle swarm optimization for task assignment problem, Microprocessors and Microsystems, 26, 363-371, (2002)
[15] Shi, Y., Eberhart, R., 1999. Empirical Study of Particle Swarm Optimization. Proceedings of Congress on Evolutionary Computation, p.1945-1950.
[16] Shigenori, N.; Takamu, G. J.; Toshiki, Y.; Yoshikazu, F., A hybrid particle swarm optimization for distribution state estimation, IEEE Trans. on Power Systems, 18, 60-68, (2003)
[17] Toth, P.; Vigo, D.; Crainic, T. G. (ed.); Laporte, G. (ed.), Exact solution of the vehicle routing problem, 1-31, (1998), Norwell, MA
[18] Toth, P.; Vigo, D., The vehicle routing problem, (2002), Philadelphia, PA · Zbl 0979.00026
[19] Laarhoven, P. J.M.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by simulated annealing, Operations Research, 40, 113-125, (1992) · Zbl 0751.90039
[20] Wang, Z. Z.; Cheng, J. X.; Fang, H. G.; Qian, F. L., A hybrid optimization algorithm solving vehicle routing problems, Operations Research and Management Science, 13, 48-52, (2004)
[21] Xia, W. J.; Wu, Z. M., An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems, Computers & Industrial Engineering, 48, 409-425, (2005)
[22] Yang, S. Y.; Wang, M.; Jiao, L. C., A quantum particle swarm optimization, Proceedings of the 2004 IEEE Congress on Evolutionary Computation, 1, 320-324, (2004)
[23] Zhao, Y. W.; Wu, B.; Jiang, L.; Dong, H. Z.; Wang, W. L., Study of the optimizing of physical distribution routing problem based on genetic algorithm, Computer Integrated Manufacturing Systems, 10, 303-306, (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.