Full Text:   <2409>

CLC number: TP14

On-line Access: 

Received: 2005-08-03

Revision Accepted: 2005-10-19

Crosschecked: 0000-00-00

Cited: 35

Clicked: 4484

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2006 Vol.7 No.4 P.607~614

10.1631/jzus.2006.A0607


Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem


Author(s):  Chen Ai-ling, Yang Gen-ke, Wu Zhi-ming

Affiliation(s):  Department of Automation, Shanghai Jiao Tong University, Shanghai 200240, China

Corresponding email(s):   chengchengcal@sjtu.edu.cn

Key Words:  Capacitated routing problem, Discrete particle swarm optimization (DPSO), Simulated annealing (SA)


Chen Ai-ling, Yang Gen-ke, Wu Zhi-ming. Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem[J]. Journal of Zhejiang University Science A, 2006, 7(4): 607~614.

@article{title="Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem",
author="Chen Ai-ling, Yang Gen-ke, Wu Zhi-ming",
journal="Journal of Zhejiang University Science A",
volume="7",
number="4",
pages="607~614",
year="2006",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2006.A0607"
}

%0 Journal Article
%T Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem
%A Chen Ai-ling
%A Yang Gen-ke
%A Wu Zhi-ming
%J Journal of Zhejiang University SCIENCE A
%V 7
%N 4
%P 607~614
%@ 1673-565X
%D 2006
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2006.A0607

TY - JOUR
T1 - Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem
A1 - Chen Ai-ling
A1 - Yang Gen-ke
A1 - Wu Zhi-ming
J0 - Journal of Zhejiang University Science A
VL - 7
IS - 4
SP - 607
EP - 614
%@ 1673-565X
Y1 - 2006
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2006.A0607


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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1] Baker, B.M., Ayechew, M.A., 2003. A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5):787-800.

[2] Bell, J.E., McMullen, P.R., 2004. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18(1):41-48.

[3] 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.

[4] 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.

[5] 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.

[6] Dantzig, G.B., Ramser, R.H., 1959. The truck dispatching problem. Management Science, 6:80-91.

[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., 1994. A tabu search heuristic for the vehicle routing problem. Management Science, 40:1276-1290.

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

[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., 1992. The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59(3):345-358.

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

[13] Osman, I.H., Potts, C.N., 1989. Simulated annealing for permutation flow shop scheduling. Omega, 17(6):551-557.

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

[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., 2003. A hybrid particle swarm optimization for distribution state estimation. IEEE Trans. on Power Systems, 18(1):60-68.

[17] 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.

[18] Toth, P., Vigo, D., 2002. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Vol. 9. SIAM, Philadelphia, PA.

[19] van Laarhoven, P.J.M., Aarts, E.H.L., Lenstra, J.K., 1992. Job shop scheduling by simulated annealing. Operations Research, 40:113-125.

[20] 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).

[21] 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.

[22] Yang, S.Y., Wang, M., Jiao, L.C., 2004. A Quantum Particle Swarm Optimization. Proceeding of the 2004 IEEE Congress on Evolutionary Computation, 1:320-324.

[23] 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).

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE