Robust Data-Driven Vehicle Routing with Time Windows

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.