Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem

被引：140

作者：

Chen A.-L. ^{[1
]}

Yang G.-K. ^{[1
]}

Wu Z.-M. ^{[1
]}

机构：

[1] Department of Automation, Shanghai Jiaotong University

来源：

Journal of Zhejiang University-SCIENCE A | 2006年 / 7卷 / 4期

基金：

中国国家自然科学基金;

关键词：

Capacitated routing problem; Discrete particle swarm optimization (DPSO); Simulated annealing (SA);

D O I：

10.1631/jzus.2006.A0607

中图分类号：

学科分类号：

摘要：

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.

引用

页码：607 / 614

页数：7

共 23 条

[11]

Laporte G., The vehicle routing problem: An overview of exact and approximate algorithms, European Journal of Operational Research, 59, 3, pp. 345-358, (1992)

[12]

Osman I.H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, 41, 4, pp. 421-451, (1993)

[13]

Osman I.H., Potts C.N., Simulated annealing for permutation flow shop scheduling, Omega, 17, 6, pp. 551-557, (1999)

[14]

Salman A., Ahmad I., Madani S.A., Particle swarm optimization for task assignment problem, Microprocessors and Microsystems, 26, 8, pp. 363-371, (2002)

[15]

Shi Y., Eberhart R., Empirical study of particle swarm optimization, Proceedings of Congress on Evolutionary Computation, pp. 1945-1950, (1999)

[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, 1, pp. 60-68, (2003)

[17]

Toth P., Vigo D., Exact solution of the vehicle routing problem, Fleet Management and Logistics, pp. 1-31, (1998)

[18]

Toth P., Vigo D., The vehicle routing problem, SIAM Monographs on Discrete Mathematics and Applications, 9, (2002)

[19]

van Laarhoven P.J.M., Aarts E.H.L., Lenstra J.K., Job shop scheduling by simulated annealing, Operations Research, 40, pp. 113-125, (1992)

[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, pp. 48-52, (2004)

← 1 2 3 →