National University of Singapore
August 15, 2019, 15:00, Room ODY 4 03 (click here for the map)
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 Fulfillment 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 heuristic, and explore their speedup strategies. We demonstrate their effectiveness through extensive computational studies. In particular, our solution greatly improves on-time arrival per- formance 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. This is a joint work with with Yu Zhang, Zhenzhen Zhang and Andrew Lim.
Dr. Melvyn Sim is Professor and Provost's Chair at the Department of Analytics & Operations, NUS Business school. His research interests fall broadly under the categories of decision making and optimization under uncertainty with applications ranging from finance, supply chain management, healthcare to engineered systems. He is one of the active proponents of Robust Optimization and has given invited talks in this field at international conferences. Dr. Sim won second places in the 2002 and 2004 George Nicholson best student paper competition and first place in the 2007 Junior Faculty Interest Group (JFIG) best paper competition. He is also the recipient of the 2009 NUS outstanding young researcher award. Dr. Sim serves as an associate editor for Operations Research, Management Science and Mathematical Programming Computations.