A robust optimization approach for the vehicle routing problem with cross-docking under demand uncertainty

被引:15
作者
Yu, Vincent F. [1 ,2 ]
Anh, Pham Tuan [1 ]
Baldacci, Roberto [3 ]
机构
[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] Hamad Bin Khalifa Univ, Qatar Fdn, Coll Sci & Engn, Div Engn Management & Decis Sci, POB 34110, Doha, Qatar
关键词
Uncertainty modeling; Robust optimization; Uncertain demand; Vehicle routing problem with cross-docking; Adaptive large neighborhood search; LARGE-NEIGHBORHOOD SEARCH; TIME WINDOWS; PRICE; HEURISTICS; BRANCH;
D O I
10.1016/j.tre.2023.103106
中图分类号
F [经济];
学科分类号
02 ;
摘要
This research addresses the Vehicle Routing Problem with Cross-docking under Demand Uncertainty (VRPCD-DU) where a set of homogeneous vehicles is used to transport orders from the suppliers to the corresponding customers via a cross-dock. VRPCD-DU considers customer demand volumes as random variables and determines a minimum cost delivery plan that is feasible for all anticipated demand realizations. A robust optimization counterpart of a deterministic VRPCD formulation is derived where support for the demand is a polyhedral set. The robust formulation can only be used to solve small VRPCD-DU instances, and an effective adaptive large neighborhood search (ALNS) algorithm is proposed for solving large instances. Extensive numerical experiments are conducted on benchmark sets for both VRPCD and VRPCD-DU. The results show that the ALNS algorithm computes new best-known solutions of the VRPCD benchmark instances. Moreover, demand uncertainty is extensively analyzed by investigating managerial insights. The price of robustness (PoR) is compared by considering various budget sets and alternative partitioning methods for the customers (i.e., "random" and "clustered"). The findings imply that a higher probability of capacity constraints' violation is generally observed for the suppliers and that customer partitioning methods share similar PoR.
引用
收藏
页数:34
相关论文
共 63 条
[1]   Models and Algorithms for Stochastic and Robust Vehicle Routing with Deadlines [J].
Adulyasak, Yossiri ;
Jaillet, Patrick .
TRANSPORTATION SCIENCE, 2016, 50 (02) :608-626
[2]   Optimization-Based Adaptive Large Neighborhood Search for the Production Routing Problem [J].
Adulyasak, Yossiri ;
Cordeau, Jean-Francois ;
Jans, Raf .
TRANSPORTATION SCIENCE, 2014, 48 (01) :20-45
[3]  
Agra Agostinho, 2012, Combinatorial Optimization. Second International Symposium, ISCO 2012. Revised Selected Papers, P249, DOI 10.1007/978-3-642-32147-4_23
[4]   The robust vehicle routing problem with time windows [J].
Agra, Agostinho ;
Christiansen, Marielle ;
Figueiredo, Rosa ;
Hvattum, Lars Magnus ;
Poss, Michael ;
Requejo, Cristina .
COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (03) :856-866
[5]   The Robust Traveling Salesman Problem with Time Windows Under Knapsack-Constrained Travel Time Uncertainty [J].
Bartolini, Enrico ;
Goeke, Dominik ;
Schneider, Michael ;
Ye, Mengdie .
TRANSPORTATION SCIENCE, 2021, 55 (02) :371-394
[6]   Robust optimization - methodology and applications [J].
Ben-Tal, A ;
Nemirovski, A .
MATHEMATICAL PROGRAMMING, 2002, 92 (03) :453-480
[7]   The price of robustness [J].
Bertsimas, D ;
Sim, M .
OPERATIONS RESEARCH, 2004, 52 (01) :35-53
[8]   Robust discrete optimization and network flows [J].
Bertsimas, D ;
Sim, M .
MATHEMATICAL PROGRAMMING, 2003, 98 (1-3) :49-71
[9]   Theory and Applications of Robust Optimization [J].
Bertsimas, Dimitris ;
Brown, David B. ;
Caramanis, Constantine .
SIAM REVIEW, 2011, 53 (03) :464-501
[10]  
Birge JR, 2011, SPRINGER SER OPER RE, P3, DOI 10.1007/978-1-4614-0237-4