The Traveling Purchaser Problem with time-dependent quantities. (June 2017)

• Record Type: Journal Article
• Authors: Angelelli, E.; Gendreau, M.; Mansini, R.; Vindigni, M.
• Is Part Of: Computers & operations research. Volume 82(2017)
• Page Start: 15
• Page End: 26
• Publication Date: 2017-06
• Subjects: Traveling Purchaser Problem -- Time-dependent quantity -- Branching strategy; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.01.001
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A novel time dependent version of the Traveling Purchaser Problem is presented. A LP model introducing constrains to represent dynamically changing quantities is defined. An exact method based on a branch-and-cut algorithm exploiting the structure of the problem is described. Experiments over a wide set of instances show the efficacy of the proposed approach. Abstract: The deterministic Traveling Purchaser Problem looks for a tour visiting a subset of markets in order to satisfy a positive discrete demand for some products at minimum traveling and purchasing costs. In this paper, we assume that the quantities available in the markets for all the products are time-varying decreasing at a constant rate. We propose a compact mixed integer formulation for the problem, and strengthen it with the introduction of connectivity constraints. A new branching strategy and a primal heuristic enforcing the bounding operations have been embedded into a branch-and-cut framework. The branching rule exploits a simple valid inequality and the potential presence of necessary markets. The resulting method outperforms CPLEX 12.6 when used to solve the proposed model. The algorithms have been tested on standard TSPLIB instances, modified to include products and quantities that decrease at different rates of consumption.