Routing optimization with time windows under uncertainty

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 propose a new formulation for the tsptw, where we explicitly express the service starting time at each customer’s location as a convex piecewise affine function of the travel times, which would enable us to obtain the tractable formulation of the corresponding distributionally robust problem. We also 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.