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 in deterministic models usually fail to deliver promised on-time services in the real world of uncertainty, causing potential loss of customers and revenue. In this study, we propose a new formulation for the data-driven Vehicle Routing Problem with Time Windows (VRPTW) under uncertain travel times that is compatible with the paradigm of distributionally robust optimization. To mitigate the lateness as much as possible, our model minimizes an innovative decision criterion on the delays, termed the Service Ful llment Risk Index (SRI), while limiting the travel cost within a budget. The SRI accounts for both the late arrival probability and its magnitude, captures the risk and the Wasserstein ambiguity in travel times, and is efficiently evaluable in closed form. In particular, the closed-form solution reduces the VRPTW under the Wasserstein ambiguity of interest to the problem under the empirical distribution with advanced deadlines. To solve the problem, we develop a Benders decomposition algorithm and a variable neighborhood search meta-heuristic, and explore their speedup strategies. We demonstrate their effectiveness through extensive computational studies. In particular, our solution greatly improves on-time arrival performance with slightly increased expenditure than the deterministic solution. Our SRI also outperforms the canonical decision criteria, lateness probability and expected lateness duration, in out-of-sample simulations.

Keywords: Vehicle routing, Service Ful llment Risk Index, Wasserstein ambiguity set, Data-driven optimization, 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: 11/29/2018

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