The vehicle routing problem with simultaneous pickup and delivery and occasional drivers

被引:23
作者
Yu, Vincent F. [1 ,2 ]
Aloina, Grace [1 ]
Jodiawan, Panca [1 ]
Gunawan, Aldy [3 ]
Huang, Tsung-Chi [1 ]
机构
[1] Natl Taiwan Univ Sci & Technol, Dept Ind Management, Taipei, Taiwan
[2] Natl Taiwan Univ Sci & Technol, Ctr Cyber Phys Syst Innovat, Taipei, Taiwan
[3] Singapore Management Univ, Sch Comp & Informat Syst, Singapore, Singapore
关键词
Simultaneous pickup and delivery; Occasional driver; Simulated Annealing; Vehicle routing problem; TABU SEARCH ALGORITHM; GENETIC ALGORITHM; OPTIMIZATION; SYSTEM; SINGLE;
D O I
10.1016/j.eswa.2022.119118
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This research addresses the Vehicle Routing Problem with Simultaneous Pickup and Delivery and Occasional Drivers (VRPSPDOD), which is inspired from the importance of addressing product returns and the emerging notion of involving available crowds to perform pickup and delivery activities in exchange for some compen-sation. At the depot, a set of regular vehicles is available to deliver and/or pick up customers' goods. A set of occasional drivers, each defined by their origin, destination, and flexibility, is also able to help serve the cus-tomers. The objective of VRPSPDOD is to minimize the total traveling cost of operating regular vehicles and total compensation paid to employed occasional drivers. We cast the problem into a mixed integer linear program-ming model and propose a simulated annealing (SA) heuristic with a mathematical programming-based con-struction heuristic to solve newly generated VRPSPDOD benchmark instances. The proposed SA incorporates a set of neighborhood operators specifically designed to address the existence of regular vehicles and occasional drivers. Extensive computational experiments show that the proposed SA obtains comparable results with the state-of-the-art algorithms for solving VRPSPD benchmark instances - i.e., the special case of VRPSPDOD - and outperforms the off-the-shelf exact solver - i.e., CPLEX - in terms of solution quality and computational time for solving VRPSPDOD benchmark instances. Lastly, sensitivity analyses are presented to understand the impact of various OD parameters on the objective value of VRPSPDOD and to derive insightful managerial insights.
引用
收藏
页数:16
相关论文
共 73 条
[1]   No Free Lunch Theorem: A Review [J].
Adam, Stavros P. ;
Alexandropoulos, Stamatios-Aggelos N. ;
Pardalos, Panos M. ;
Vrahatis, Michael N. .
APPROXIMATION AND OPTIMIZATION: ALGORITHMS, COMPLEXITY AND APPLICATIONS, 2019, 145 :57-82
[2]   A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery [J].
Ai, The Jin ;
Kachitvichyanukul, Voratas .
COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (05) :1693-1702
[3]   The online vehicle routing problem with occasional drivers [J].
Archetti, Claudia ;
Guerriero, Francesca ;
Macrina, Giusy .
COMPUTERS & OPERATIONS RESEARCH, 2021, 127
[4]   Recent challenges in Routing and Inventory Routing: E-commerce and last-mile delivery [J].
Archetti, Claudia ;
Bertazzi, Luca .
NETWORKS, 2021, 77 (02) :255-268
[5]   The Vehicle Routing Problem with Occasional Drivers [J].
Archetti, Claudia ;
Savelsbergh, Martin ;
Speranza, M. Grazia .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 254 (02) :472-480
[6]   A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery [J].
Avci, Mustafa ;
Topaloglu, Seyda .
EXPERT SYSTEMS WITH APPLICATIONS, 2016, 53 :160-171
[7]   A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery [J].
Catay, Buelent .
EXPERT SYSTEMS WITH APPLICATIONS, 2010, 37 (10) :6809-6817
[8]   Vehicle routing problem with simultaneous deliveries and pickups [J].
Chen, JF ;
Wu, TH .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2006, 57 (05) :579-587
[9]  
Dablanc L., 2017, SUPPLY CHAIN FORUM, V18, P203, DOI [DOI 10.1080/16258312.2017.1375375, 10.1080/16258312.2017.1375375]
[10]   The pickup and delivery problem with time windows and occasional drivers [J].
Dahle, Lars ;
Andersson, Henrik ;
Christiansen, Marielle ;
Speranza, M. Grazia .
COMPUTERS & OPERATIONS RESEARCH, 2019, 109 :122-133