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

Andreatta, G., Lulli, G. (2008). A multi-period TSP with stochastic regular and urgent demands. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 185(1), 122-132 [10.1016/j.ejor.2006.12.040].

A multi-period TSP with stochastic regular and urgent demands

LULLI, GUGLIELMO
2008

Abstract

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
Articolo in rivista - Articolo scientifico
routing; Markov processes; logistics
English
16-feb-2008
185
1
122
132
none
Andreatta, G., Lulli, G. (2008). A multi-period TSP with stochastic regular and urgent demands. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 185(1), 122-132 [10.1016/j.ejor.2006.12.040].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: https://hdl.handle.net/10281/980
Citazioni
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 10
Social impact