Pasar al contenido principal

MODELOS Y METODOS DE PROGRAMACION MATEMATICA Y SUS APLICACIONES SUS APLICACIONES

MTM2012-36163-C06-05

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Nacional de Proyectos de Investigación Fundamental
Subprograma Subprograma de Proyectos de Investigación Fundamental no Orientada
Convocatoria Proyectos I+D
Año convocatoria 2012
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Secretaría de Estado de Investigación, Desarrollo e Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A branch-and-cut algorithm for the multidepot rural postman problem

  • Fernández Aréizaga, Elena|||0000-0003-4714-0257
  • Laporte, Gilbert
  • Rodríguez Pereira, Jessica|||0000-0002-9726-7531
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., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A branch-and-cut algorithm for the multidepot rural postman problem

  • Fernández Aréizaga, Elena
  • Laporte, Gilbert
  • Rodríguez Pereira, Jessica
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., Peer Reviewed, Postprint (author's final draft)