Please wait a minute...
ZJUS-A
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering)  2006, Vol. 7 Issue (4 ): 20-    DOI: 10.1631/jzus.2006.A0607
    
Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem
Chen Ai-ling, Yang Gen-ke, Wu Zhi-ming
Department of Automation, Shanghai Jiao Tong University, Shanghai 200240, China
Download:     PDF (0 KB)     
Export: BibTeX | EndNote (RIS)      

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.

Key words： Capacitated routing problem      Discrete particle swarm optimization (DPSO)      Simulated annealing (SA)     
Received: 03 August 2005     
CLC:  TP14  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Chen Ai-ling
Yang Gen-ke
Wu Zhi-ming
Cite this article:

Chen Ai-ling, Yang Gen-ke, Wu Zhi-ming. Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(4 ): 20-.

URL:

http://www.zjujournals.com/xueshu/zjus-a/10.1631/jzus.2006.A0607     OR     http://www.zjujournals.com/xueshu/zjus-a/Y2006/V7/I4 /20

[1] Francisco J. Martinez-Martin, Fernando Gonzalez-Vidosa, Antonio Hospitaler, Víctor Yepes. Multi-objective optimization design of bridge piers with hybrid heuristic algorithms[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2012, 13(6): 420-432.
[2] Taher NIKNAM, Babak AMIRI, Javad OLAMAEI, Ali AREFI. An efficient hybrid evolutionary optimization algorithm based on PSO and SA for clustering[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2009, 10(4): 512-519.
[3] Peng-fei LIU, Ping XU, Shu-xin HAN, Jin-yang ZHENG. Optimal design of pressure vessel using an improved genetic algorithm[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(9): 1264-1269.