A Hybrid PSO Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup


Article Preview

In this paper a hybrid algorithm named IPSO-VND is proposed and applied to solving the vehicle routing problem with simultaneous pickup and delivery (VRPSPD). The IPSO-VND algorithm combines two meta-heuristics: Improved Particle Swarm Optimization (IPSO) is used to find a group of excellent solutions, and then the Variable Neighborhood Descent (VND) is implemented to deeply search to achieve the optimal solution around these solutions. During the IPSO procedure, in order to make up for the change of a particle’s position, a velocity component is added to the movement of any particle which has been optimized or made feasible. During the VND procedure, three different neighborhood structures: insertion, swap and cross are successively used. Computational results on the benchmark problems show that our IPSO-VND algorithm is effective.



Advanced Materials Research (Volumes 655-657)

Edited by:

Zhengyi Jiang, Xianghua Liu, Sihai Jiao and Jingtao Han




S. X. Wang et al., "A Hybrid PSO Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup", Advanced Materials Research, Vols. 655-657, pp. 2326-2330, 2013

Online since:

January 2013




[1] Dantzig GB, Ramser J H. The truck dispatching problem. Management Science, 1959, 6 (1): 80-91.

DOI: https://doi.org/10.1287/mnsc.6.1.80

[2] Tang MontanéF A , GalvÃo R D. A tabu search algorithm for the vehicle routing problem with simultaneous pick up and delivery service. Computers & Operations Research, 2006, 33 (3): 595-619.

DOI: https://doi.org/10.1016/j.cor.2004.07.009

[3] Mosheiov G. The traveling salesman problem wit h pick up and delivery. European Journal of Operational Research, 1994, 79 (2): 299-310.

DOI: https://doi.org/10.1016/0377-2217(94)90360-3

[4] Min H. The multiple vehicle routing problem with simultaneous delivery and pickup points. Transportation Research A, 1989, 23A (5): 377-386.

[5] Dethloff J. Vehicle routing and reverse logistics:The vehicle routing problem with simultaneous delivery and pick-up[J]. OR Spektrum,2001,23(1): 79-96.

DOI: https://doi.org/10.1007/pl00013346

[6] Crispim J, BrandÃo J. Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls. Journal of t he Operational Research Society, 2005, 56 (11) : 1296-1302.

DOI: https://doi.org/10.1057/palgrave.jors.2601935

[7] Chen J F, Wu T H. Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, 2006, 57 (5): 579-587.

DOI: https://doi.org/10.1057/palgrave.jors.2602028

[8] CHEN Ping, HUANG Hou-Kuan, DONG Xing-Ye. A Hybrid Heuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pickup. Chinese Journal of Computers. Vol. 31 No. 4 Apr. (2008).

DOI: https://doi.org/10.3724/sp.j.1016.2008.00565

[9] GE Hong-wei, WANG Yin-nian. Improved simulated annealing genetic algorithm for VRPSPD problem. Computer Engineering and Applications, 2010, 46(30): 36-39.

[10] ZHANG Tao, LIU Yang, ZHANG Yue-jie. PSO-ACS Mixed Algorithm for Vehicle Routing Problem with Simultaneous Pick-up and Delivery. Journal of System Simulation, Vol. 22 No. 3 Mar., (2010).

DOI: https://doi.org/10.1109/icmlc.2009.5212205

[11] Eberhart R, Kennedy J. A new optimizer using particles swarm theory[C]. Proc Sixth International Symposium on Micro Machine and Human Science. Nagoya, Japan: IEEE Service Center, Piscataway, 1995. 39-43.

DOI: https://doi.org/10.1109/mhs.1995.494215

[12] WANG Wanliang, WU Bin, ZHAO Yanwei, et al. Particle swarm optimization for open vehicle routing problem [J]. Lecture Notes in Artificial Intelligence, 2006, 4114: 999-1007.

DOI: https://doi.org/10.1007/978-3-540-37275-2_126

[13] Salhi S, Nagy G. A cluster insertion heuristic for single and multiple depot vehicle routing problem with backhauling[J]. Journal of the Operational Research Society,1999,50(10):1034-1042.

DOI: https://doi.org/10.1057/palgrave.jors.2600808