Optimization Online


Robust Data-Driven Vehicle Routing with Time Windows

Yu Zhang (waltyuzhang***at***gmail.com)
Zhenzhen Zhang (isezz***at***nus.edu.sg)
Andrew Lim (isealim***at***nus.edu.sg)
Melvyn Sim (dscsimm***at***nus.edu.sg)

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 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.

Keywords: vehicle routing, Service Ful fillment Risk Index, distributionally robust optimization

Category 1: Robust Optimization

Category 2: Applications -- OR and Management Sciences (Transportation )

Category 3: Stochastic Programming


Download: [PDF]

Entry Submitted: 11/29/2018
Entry Accepted: 11/29/2018
Entry Last Modified: 07/27/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society