A Stochastic Programming Approach for the Traveling Purchaser Problem

The deterministic Traveling Purchaser Problem (TPP) aims at selecting a subset of suppliers, offering products at different prices and quantities, so to satisfy a products demand while minimizing traveling and purchasing costs. In this paper, we study a variant of the TPP where both the available quantities and the purchasing prices are uncertain. This more challenging version of the problem, named TPP under uncertainty, allows the purchaser to protect himself against risks of insufficient demand fulfillment and to exploit the benefits of buying at lower price levels. 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 initial solutions. Extensive computational experiments show efficiency of the proposed approach in finding the optimal solution of the deterministic equivalent problem