Optimization Online


Routing Optimization with Time Windows under Uncertainty

Yu Zhang (waltyuzhang***at***gmail.com)
Roberto Baldacci (r.baldacci***at***unibo.it)
Melvyn Sim (dscsimm***at***nus.edu.sg)
Jiafu Tang (tangjiafu***at***dufe.edu.cn)

Abstract: We study an a priori Traveling Salesman Problem with Time Windows (TSPTW) in which the travel times along the arcs are uncertain and the goal is to determine within a budget constraint, a route for the service vehicle in order to arrive at the customers' locations within their stipulated time windows as well as possible. In particular, service at customer's location cannot commence before the beginning of the time window and any arrival after the end of the time window is considered late and constitutes to poor customer service. In articulating the service level of the TSPTW under uncertainty, we propose a new decision criterion, called the essential riskiness index, which has the computationally attractive feature of convexity that enables us to formulate and solve the problem more effectively. As a decision criterion for articulating service levels, it takes into account both the probability of lateness and its magnitude, and can be applied in contexts where either the distributional information of the uncertain travel times is fully or partially known. We show how to optimize the essential riskiness index via Benders decomposition and present cases where we can obtain closed-form solutions to the subproblems. We also illustrate in our numerical studies that this approach scales well with the number of samples used for the sample average approximation. The approach can be extended to a more general setting including Vehicle Routing Problem with Time Windows with uncertain travel times and customers' demands.

Keywords: vehicle routing problem, uncertain travel time, time windows, distributionally robust optimization

Category 1: Robust Optimization

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 08/30/2016
Entry Accepted: 08/30/2016
Entry Last Modified: 05/17/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