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. (2019). Routing optimization with time windows under uncertainty. MATHEMATICAL PROGRAMMING, 175(1-2), 263-305 [10.1007/s10107-018-1243-y].
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.File | Dimensione | Formato | |
---|---|---|---|
10.1007_s10107-018-1243-y.pdf
accesso riservato
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
Open Access dal 24/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.