Yu Zhang, Zhenzhen Zhang, Andrew Lim, Melvyn Sim
Operations Research, 69(2), 469-485, 2021
Recommend Reason
On-time delivery is of utmost importance in today’s urban logistics. However, travel times are uncertain and classical deterministic routing solutions often fail to ensure timely delivery. In the paper, we propose a robust solution that exploits travel times data to determine the best routes for maximal timely delivery. We introduce a new decision criterion, the service fulfillment risk index (SRI), which accounts for both the late arrival probability and its magnitude. Together with Wasserstein distance–based ambiguity in travel times, SRI can be evaluated efficiently in closed form. Simulation studies demonstrate that handling uncertainty improves service punctuality, and that incorporating ambiguity prevents overfitting. Most importantly, SRI outperforms the canonical decision criteria of lateness probability and expected lateness duration.
About the Authors
Yu Zhang, Southwestern University of Finance and Economics
Zhenzhen Zhang, School of Economics and Management, Tongji University
Andrew Lim, National University of Singapore
Melvyn Sim, National University of Singapore
Keywords
vehicle routing, Service Fulfillment Risk Index, distributionally robust optimization
Brief Introduction
Optimal routing solutions based on deterministic models usually fail to deliver promised on-time services in an uncertain real world, which can lead to the loss of customers and revenue. We study a vehicle routing problem with time windows (VRPTW) toward the end of mitigating the risk of late customer arrivals as much as possible when travel times are based on empirical distributions. To prevent overfitting, we propose a distributionally robust optimization model that uses a Wasserstein distance-based ambiguity set to characterize ambiguous distributions that are close to the empirical distribution. Our model minimizes the decision criterion regarding delays, termed the service fulfillment risk index (SRI), while limiting budgeted travel costs. The SRI accounts for both the late arrival probability and its magnitude, captures the risk and ambiguity in travel times, and can be evaluated efficiently in closed form. Under the Wasserstein distance-based ambiguity, the closed-form solution reduces the VRPTW of interest to the problem under empirical travel times where all deadlines are advanced by some Wasserstein distance-related durations. To solve the problem, we develop an exact branch-and-cut approach and a variable neighborhood search meta-heuristic algorithm, and explore their speedup strategies. The effectiveness of these algorithms is established by extensive computational studies. In particular, our solution greatly improves on-time arrival performance with only modest increases in expenditures compared to the deterministic solution. Finally, our SRI also performs better during out-of-sample simulations than do the canonical decision criteria of lateness probability and expected lateness duration.
Link
