Comparative Analysis of Capacitated Arc Routing Formulations for Designing a New Branch-Cut-and-Price Algorithm
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, the authors 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.
- Record URL:
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
-
Supplemental Notes:
- Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
-
Authors:
- Pecin, Diego
- Uchoa, Eduardo
- Publication Date: 2019-11
Language
- English
Media Info
- Media Type: Web
- Features: References;
- Pagination: 1673-1694
-
Serial:
- Transportation Science
- Volume: 53
- Issue Number: 6
- Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
- ISSN: 0041-1655
- Serial URL: http://transci.journal.informs.org/
Subject/Index Terms
- TRT Terms: Alternatives analysis; Branch and bound algorithms; Graph theory; Optimization; Routing
- Subject Areas: Operations and Traffic Management; Planning and Forecasting; Transportation (General);
Filing Info
- Accession Number: 01723789
- Record Type: Publication
- Files: TRIS
- Created Date: Nov 27 2019 10:36AM