Limited memory Rank-1 Cuts for Vehicle Routing Problems
| Autor: | Haroldo Gambini Santos, Diego Pecin, Eduardo Uchoa, Marcus Poggi, Artur Alves Pessoa |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
050210 logistics & transportation
Mathematical optimization medicine.medical_specialty 021103 operations research Applied Mathematics 05 social sciences Polyhedral combinatorics Rank (computer programming) 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Industrial and Manufacturing Engineering Dual (category theory) Set (abstract data type) 0502 economics and business Vehicle routing problem medicine Row Software Mathematics |
| Zdroj: | Operations Research Letters. 45:206-209 |
| ISSN: | 0167-6377 |
| DOI: | 10.1016/j.orl.2017.02.006 |
| Popis: | Pecin etal. (2016) introduced a limited memory technique that allows an efficient use of Rank-1 cuts in the Set Partitioning Formulation of Vehicle Routing Problems, motivating a deeper investigation of those cuts. This work presents a computational polyhedral study that determines the best possible sets of multipliers for cuts with up to 5 rows. Experiments with CVRP instances show that the new multipliers lead to significantly improved dual bounds and contributes decisively for solving an open instance with 420 customers. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect