Robust Data-Driven Vehicle Routing with Time Windows

Yu Zhang (), Zhenzhen Zhang (), Andrew Lim () and Melvyn Sim ()
Additional contact information
Yu Zhang: Department of Supply Chain Management, School of Business Administration, Southwestern University of Finance and Economics, Chengdu 611130, China; Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore 117576;
Zhenzhen Zhang: Department of Management Science, School of Economics and Management, Tongji University, Shanghai 200092, China;
Andrew Lim: Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore 117576;
Melvyn Sim: Department of Analytics & Operations, NUS Business School, National University of Singapore, Singapore 119077

Operations Research, 2021, vol. 69, issue 2, 469-485

Abstract: 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 with 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.

Keywords: vehicle routing; Service Fulfillment Risk Index; distributionally robust optimization (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
https://doi.org/10.1287/opre.2020.2043 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:2:p:469-485

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().