The Traveling Purchaser Problem (TPP) is an interesting procurement and routing NP-hard problem that finds application in several domains. The problem aims at determining a tour starting at and ending to the depot while visiting a subset of markets in such a way that a demand for each product is satisfied and that the cost globally spent for purchasing the products and visiting the markets is minimized. The deterministic TPP ignores the uncertain nature of some parameters involved in the model, thus typically providing recommendations with limited practical application. While the deterministic version of the TPP has been largely studied (e.g. see [1]), very few contributions exist in the literature for the TPP under uncertainty [2]. This work proposes a scenariobased stochastic and capacitated version of the TPP which explicitly takes into account uncertainty in prices and/or products availability. Injecting stochastic elements in the model allows us to manage closely real-life applications. We cast the model within a two-stage stochastic paradigm based on a distinction between the first-stage variables, which have to be decided upon before the outcomes of the stochastic variables are observed, and the second stage variables which have to be decided after the uncertainty is resolved. To efficiently solve the problem, we develop a tailored heuristic approach designed to exploit the specific problem structure. Encouraging preliminary computational results are provided. References: [1] G. Laporte, J. Riera-Ledesma, J.J. Salazar-Gonzalez, A branch-and-cut algorithm for the undirected Traveling Purchaser Problem, Operation Research 51(6), pp. 940-951 (2003). [2] S. Kang, Y. Ouyang, The traveling purchaser problem with stochastic prices: exact and approximate algorithms, European Journal of Operational Research 209(3), pp. 265-272 (2011).

The Traveling Purchaser Problem Under Uncertainty / Bruni, M. E; Beraldi, P; Manerba, Daniele; Mansini, R.. - (2012). (Intervento presentato al convegno AIRO 2012).

The Traveling Purchaser Problem Under Uncertainty

MANERBA, DANIELE;
2012

Abstract

The Traveling Purchaser Problem (TPP) is an interesting procurement and routing NP-hard problem that finds application in several domains. The problem aims at determining a tour starting at and ending to the depot while visiting a subset of markets in such a way that a demand for each product is satisfied and that the cost globally spent for purchasing the products and visiting the markets is minimized. The deterministic TPP ignores the uncertain nature of some parameters involved in the model, thus typically providing recommendations with limited practical application. While the deterministic version of the TPP has been largely studied (e.g. see [1]), very few contributions exist in the literature for the TPP under uncertainty [2]. This work proposes a scenariobased stochastic and capacitated version of the TPP which explicitly takes into account uncertainty in prices and/or products availability. Injecting stochastic elements in the model allows us to manage closely real-life applications. We cast the model within a two-stage stochastic paradigm based on a distinction between the first-stage variables, which have to be decided upon before the outcomes of the stochastic variables are observed, and the second stage variables which have to be decided after the uncertainty is resolved. To efficiently solve the problem, we develop a tailored heuristic approach designed to exploit the specific problem structure. Encouraging preliminary computational results are provided. References: [1] G. Laporte, J. Riera-Ledesma, J.J. Salazar-Gonzalez, A branch-and-cut algorithm for the undirected Traveling Purchaser Problem, Operation Research 51(6), pp. 940-951 (2003). [2] S. Kang, Y. Ouyang, The traveling purchaser problem with stochastic prices: exact and approximate algorithms, European Journal of Operational Research 209(3), pp. 265-272 (2011).
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/11583/2663706
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo