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 条

[1]

Baker B.M., Ayechew M.A., A genetic algorithm for the vehicle routing problem, Computers and Operations Research, 30, 5, pp. 787-800, (2003)

[2]

Bell J.E., McMullen P.R., Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics, 18, 1, pp. 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 and Operations Research, 10, pp. 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, 1, pp. 255-282, (1981)

[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, 8, pp. 928-936, (2001)

[6]

Dantzig G.B., Ramser R.H., The truck dispatching problem, Management Science, 6, pp. 80-91, (1959)

[7]

Eberhart R., Kennedy J., A new optimizer using particle swarm theory, Proceeding of the Sixth International Symposium on Micro Machine and Human Science, pp. 39-43, (1995)

[8]

Gendreau M., Hertz A., Laporte G., A tabu search heuristic for the vehicle routing problem, Management Science, 40, pp. 1276-1290, (1994)

[9]

Hasan M., Osman I.H., Local search algorithm for the maximal planar layout problem, International Transactions in Operational Research, 2, 1, pp. 89-106, (1995)

[10]

Kennedy J., Eberhart R., Particle swarm optimization, Proceeding of the 1995 IEEE International Conference on Neural Network, pp. 1942-1948, (1995)

← 1 2 3 →