The Traveling Purchaser Problem with time-dependent quantities
| Autor: | Michel Gendreau, Renata Mansini, Michele Vindigni, Enrico Angelelli |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Traveling purchaser problem
050210 logistics & transportation Mathematical optimization 021103 operations research General Computer Science Heuristic (computer science) 05 social sciences 0211 other engineering and technologies Structure (category theory) Time-dependent quantity 02 engineering and technology Management Science and Operations Research Purchasing Branching strategy Set (abstract data type) Bounding overwatch Simple (abstract algebra) Traveling Purchaser Problem Modeling and Simulation 0502 economics and business Integer (computer science) Mathematics |
| Zdroj: | Computers & Operations Research. 82:15-26 |
| ISSN: | 0305-0548 |
| DOI: | 10.1016/j.cor.2017.01.001 |
| Popis: | 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. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect