TY - JOUR

T1 - A multi-period TSP with stochastic regular and urgent demands

AU - Andreatta, G.

AU - Lulli, G.

PY - 2008/2/16

Y1 - 2008/2/16

N2 - In this paper, we study the multi-period TSP problem with stochastic urgent and regular demands. Urgent demands have to be satisfied immediately while regular demands can be satisfied either immediately or the day after. Demands appear stochastically at nodes. The objective is to minimize the average long-run delivery costs, knowing the probabilities governing the demands at nodes. The problem is cast as a Markov Process with Costs and, at least in principle, can be solved using an approach originally proposed by Howard [R.A. Howard, Dynamic Programming and Markov Processes, MIT, Cambridge, USA, 1960] for Markov Processes with Rewards. However, the number of states of the Markov Process grows exponentially with the number of nodes in the network which pose a limit on the dimension of the instances that are computationally tractable. We suggest a second Markov approach considering a system (Aggregate Model) whose number of states grows only polynomially with the number of nodes in the network. The important relations between the optimal solutions of the original and the aggregate models will be discussed. Finally, we also propose a hybrid procedure which combines both models. The viability of the proposed methodology is shown by applying the procedure to a numerical example.

AB - In this paper, we study the multi-period TSP problem with stochastic urgent and regular demands. Urgent demands have to be satisfied immediately while regular demands can be satisfied either immediately or the day after. Demands appear stochastically at nodes. The objective is to minimize the average long-run delivery costs, knowing the probabilities governing the demands at nodes. The problem is cast as a Markov Process with Costs and, at least in principle, can be solved using an approach originally proposed by Howard [R.A. Howard, Dynamic Programming and Markov Processes, MIT, Cambridge, USA, 1960] for Markov Processes with Rewards. However, the number of states of the Markov Process grows exponentially with the number of nodes in the network which pose a limit on the dimension of the instances that are computationally tractable. We suggest a second Markov approach considering a system (Aggregate Model) whose number of states grows only polynomially with the number of nodes in the network. The important relations between the optimal solutions of the original and the aggregate models will be discussed. Finally, we also propose a hybrid procedure which combines both models. The viability of the proposed methodology is shown by applying the procedure to a numerical example.

KW - Logistics

KW - Markov processes

KW - Routing

U2 - 10.1016/j.ejor.2006.12.040

DO - 10.1016/j.ejor.2006.12.040

M3 - Journal article

AN - SCOPUS:34548685867

VL - 185

SP - 122

EP - 132

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -