Colombi, M.; Corberán, A.; Mansini, R.; Plana, I.; Sanchís Llopis, JM. (2017). The Hierarchical Mixed Rural Postman Problem: Polyhedral analysis and a branch-and-cut algorithm. European Journal of Operational Research. 257(1):1-12. https://doi.org/10.1016/j.ejor.2016.07.026
Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/107353
Title:
|
The Hierarchical Mixed Rural Postman Problem: Polyhedral analysis and a branch-and-cut algorithm
|
Author:
|
Colombi, Marco
Corberán, Angel
Mansini, Renata
Plana, Isaac
Sanchís Llopis, José María
|
UPV Unit:
|
Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada
|
Issued date:
|
|
Abstract:
|
[EN] The Hierarchical Mixed Rural Postman Problem is defined on a mixed graph where arcs and edges that require a service are divided into clusters' that have to be serviced in a hierarchical order. The problem generalizes ...[+]
[EN] The Hierarchical Mixed Rural Postman Problem is defined on a mixed graph where arcs and edges that require a service are divided into clusters' that have to be serviced in a hierarchical order. The problem generalizes the Mixed Rural Postman Problem and thus is NP-hard. In this paper, we provide a polyhedral analysis of the problem and propose a branch-and-cut algorithm for its solution based on the introduced classes of valid inequalities. Extensive computational experiments are reported on benchmark instances. The exact approach allows to find the optimal solutions in less than 1 hour for instances with up to 999 vertices, 2678 links, and five clusters.
[-]
|
Subjects:
|
Hierarchical Routing Problems
,
Mixed Rural Postman Problem
,
Branch-and-cut
,
Polyhedral analysis
|
Copyrigths:
|
Cerrado |
Source:
|
European Journal of Operational Research. (issn:
0377-2217
)
|
DOI:
|
10.1016/j.ejor.2016.07.026
|
Publisher:
|
Elsevier
|
Publisher version:
|
https://doi.org/10.1016/j.ejor.2016.07.026
|
Project ID:
|
info:eu-repo/grantAgreement/GVA//PROMETEO%2F2013%2F049/ES/Modelos y algoritmos para problemas de optimización combinatoria/
info:eu-repo/grantAgreement/MINECO//MTM2015-68097-P/ES/MODELOS Y ALGORITMOS PARA PROBLEMAS DE RUTAS DE VEHICULOS Y DE LOCALIZACION DE SERVICIOS/
|
Thanks:
|
The work by Angel Corberan, Isaac Plana, and Jose M. Sanchis was supported by the Spanish Ministerio de Economia y Competitividad and Fondo Europeo de Desarrollo Regional (FEDER) through project MTM2015-68097-P (MINECO/FEDER) ...[+]
The work by Angel Corberan, Isaac Plana, and Jose M. Sanchis was supported by the Spanish Ministerio de Economia y Competitividad and Fondo Europeo de Desarrollo Regional (FEDER) through project MTM2015-68097-P (MINECO/FEDER) and by the Generalitat Valenciana (project GVPROMETEO2013-049).
[-]
|
Type:
|
Artículo
|