Comparative Analysis of Capacitated Arc Routing Formulations for Designing a New Branch-Cut-and-Price Algorithm
| Autor: | Eduardo Uchoa, Diego Pecin |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
050210 logistics & transportation
021103 operations research Computer science 05 social sciences 0211 other engineering and technologies Transportation 02 engineering and technology Work (electrical) 0502 economics and business Column generation Current (fluid) Integer programming Arc routing Algorithm Civil and Structural Engineering |
| Zdroj: | Transportation Science. 53:1673-1694 |
| ISSN: | 1526-5447 0041-1655 |
| DOI: | 10.1287/trsc.2019.0900 |
| Popis: | The current best exact algorithms for the Capacitated Arc Routing Problem are based on the combination of cut and column generation. This work presents a deep theoretical investigation of the formulations behind those algorithms, classifying them and pointing out similarities and differences, advantages and disadvantages. In particular, we discuss which families of cuts and branching strategies are suitable for each alternative and their pricing complexities. That analysis is used to justify key decisions on constructing a new branch-cut-and-price algorithm that combines several features picked from the capacitated arc routing literature with some features adapted from the most successful recent algorithms for node routing. The computational experiments show that the resulting algorithm is indeed effective and can solve almost all open instances from the classical benchmark sets. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|