The Stochastic and Dynamic Traveling Purchaser Problem

The Traveling Purchaser Problem (TPP) looks for a tour starting at and ending to the depot that visits a subset of markets so to satisfy the demand for all products while minimizing purchasing and traveling costs (see Laporte et al. [2]). In this paper we study a more realistic procurement setting where products quantity stochastically decreases due to other purchasers competing on the same products. The global effect of the competitors behavior is assumed to be modeled as an array of m × n stochastic consumption processes independent with respect to the m markets and the n products. The problem is also dynamic since information on quantity availability is revealed over time and the decision maker may react to new information by making new plans. We call this problem the Stochastic Dynamic Traveling Purchaser Problem (SDTPP). The problem finds application in different contexts including procurement and large scale emergencies, as those caused by natural disasters, viral spread diseases and/or terrorist attacks. To the best of our knowledge, this version of the TPP has never been addressed before. In Angelelli et al. [1] a simpler variant is studied where no assumption is made on the consumption processes and the decision maker is assumed to be informed in real-time of all occurring events. We will explore the SDTPP under four different operating scenarios all characterized by the presence of a planner who has computing power and makes decisions and an executor (the purchaser) who runs the service in practice and has a very limited or null computing power. Scenarios differ for the communication tools used between planner and executor, and for the level of information available on the state of the world. As far as communication is concerned, different situations can be figured out ranging from the case where no communication technologies are available (after leaving the depot communication between planner and executor is interrupted) to a complete communication between actors. In terms of information, possible situations range from a minimum, characterized by knowledge of the initial state of the world plus an update collected on the field at visited markets, to a maximum like in internet based systems, where current stock levels of all markets are shared by all commercial partners in real time. The contributions provided are multifold. We introduce two consumption models to estimate products inventory and propose three solution approaches, a stochastic, a deterministic and an hybrid one. The proposed approaches have been compared under the analyzed scenarios in terms of both feasibility and total costs. A comparison with a known approach proposed in the literature is also considered. Extensive computational results show how the hybrid approach provides the best compromise in terms of computational burden and quality of the solution and define interesting guidelines for decision makers involved with similar problems. [1] E. Angelelli, R. Mansini, M. Vindigni, Look-ahead heuristics for the Dynamic Traveling Purchaser Problem, Computers & Operations Research 38 (2011) 1867–1876. [2] G. Laporte, J. Riera-Ledesma, J.J. Salazar-Gonzalez, A Branch-and-Cut Algorithm for the Undirected Traveling Purchaser Problem, Operations Research 6 (2003) 940–951.