A stochastic programming approach for the traveling purchaser problem

摘要

The deterministic traveling purchaser problem (TPP) aims to select a subset of suppliers, offering products at different prices and quantities, to satisfy demand while minimizing travelling and purchasing costs. In this paper, we study a variant of the TPP in which both the available quantities and the purchasing prices are uncertain. This more challenging version of the problem, TPP under uncertainty, allows a purchaser to protect himself against risks of insufficient demand fulfilment and to exploit the benefits of procurement at lower prices. We introduce a two-stage stochastic programming formulation of the problem and we present a tailored solution approach based on a Branch-and-Cut method and on a heuristic approach to find good initial solutions. Extensive computational experiments show the efficiency of the proposed approach in finding the optimal solution of the deterministic equivalent problem for instances with up to 75 suppliers, 50 products and 200 scenarios in less than 2 h.