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.

Routing optimization with time windows under uncertainty

Baldacci R.;
2019

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 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.
Zhang Y.; Baldacci R.; Sim M.; Tang J.
File in questo prodotto:
File Dimensione Formato  
10.1007_s10107-018-1243-y.pdf

non disponibili

Tipo: Versione (PDF) editoriale
Licenza: Licenza per accesso riservato
Dimensione 901.34 kB
Formato Adobe PDF
901.34 kB Adobe PDF   Visualizza/Apri   Contatta l'autore
RTSPTW.pdf

embargo fino al 23/02/2019

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 585.52 kB
Formato Adobe PDF
585.52 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/713828
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 16
social impact