dc.contributor
Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa
dc.contributor
Universitat Politècnica de Catalunya. GNOM - Grup d'Optimització Numèrica i Modelització
dc.contributor.author
Fernández Aréizaga, Elena
dc.contributor.author
Laporte, Gilbert
dc.contributor.author
Rodríguez Pereira, Jessica
dc.identifier
Fernandez, E., Gilbert, L., Rodríguez-Pereira, J. A branch-and-cut algorithm for the multidepot rural postman problem. "Transportation science", Març 2018, vol. 52, núm. 2, p. 353-369.
dc.identifier
https://hdl.handle.net/2117/126907
dc.identifier
10.1287/trsc.2017.0783
dc.description.abstract
This paper considers the Multidepot Rural Postman Problem, an extension of the classical Rural Postman Problem in which there are several depots instead of only one. The aim is to construct a minimum cost set of routes traversing each required edge of the graph, where each route starts and ends at the same depot. The paper makes the following scientific contributions: (i) It presents optimality conditions and a worst case analysis for the problem; (ii) It proposes a compact integer linear programming formulation containing only binary variables, as well as a polyhedral analysis; (iii) It develops a branch-and-cut algorithm that includes several new exact and heuristic separation procedures. Instances involving up to four depots, 744 vertices, and 1,315 edges are solved to optimality. These instances contain up to 140 required components and 1,000 required edges.
dc.description.abstract
Peer Reviewed
dc.description.abstract
Postprint (author's final draft)
dc.format
application/pdf
dc.relation
https://pubsonline.informs.org/doi/abs/10.1287/trsc.2017.0783?journalCode=trsc
dc.relation
info:eu-repo/grantAgreement/MINECO//MTM2015-63779-R/ES/OPTIMIZACION DISCRETA PARA PROBLEMAS INTEGRADOS EN LOGISTICA Y TRANSPORTE/
dc.relation
info:eu-repo/grantAgreement/MINECO//MTM2012-36163-C06-05/ES/MODELOS Y METODOS DE PROGRAMACION MATEMATICA Y SUS APLICACIONES SUS APLICACIONES/
dc.subject
Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica
dc.subject
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències
dc.subject
Numerical analysis
dc.subject
Programming (Mathematics)
dc.subject
worst-case analysis
dc.subject
branch-and-cut
dc.subject
multi-depot rural postman problem
dc.subject
polyhedral analysis
dc.subject
Anàlisi numèrica
dc.subject
Programació (Matemàtica)
dc.subject
Classificació AMS::65 Numerical analysis::65K Mathematical programming, optimization and variational techniques
dc.subject
Classificació AMS::90 Operations research, mathematical programming::90C Mathematical programming
dc.title
A branch-and-cut algorithm for the multidepot rural postman problem
