- -

New Facets and an Enhanced Branch-and-Cut for the Min-Max K-Windy Rural Postman Problem

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

New Facets and an Enhanced Branch-and-Cut for the Min-Max K-Windy Rural Postman Problem

Mostrar el registro sencillo del ítem

Ficheros en el ítem

Thumbnail
Nombre: Benavent;Corberán ...
Tamaño: 348.8Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir
[Cerrado]
Nombre: JMSanchis_Network ...
Tamaño: 278.4Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor
dc.contributor.author Benavent López, Enrique es_ES
dc.contributor.author Corberán, Angel es_ES
dc.contributor.author Plana, Isaac es_ES
dc.contributor.author Sanchís Llopis, José María es_ES
dc.date.accessioned 2020-09-18T03:35:34Z
dc.date.available 2020-09-18T03:35:34Z
dc.date.issued 2011-11 es_ES
dc.identifier.issn 0028-3045 es_ES
dc.identifier.uri http://hdl.handle.net/10251/150338
dc.description.abstract [EN] The min-max windy rural postman problem is a multiple vehicle version of the windy rural postman problem, WRPP, which consists of minimizing the length of the longest route to find a set of balanced routes for the vehicles. In a previous paper, an ILP formulation and a partial polyhedral study were presented, and a preliminary branch-and-cut algorithm that produced some promising computational results was implemented. In this article, we present further results for this problem. We describe several new facet-inducing inequalities obtained from the WRPP, as well as some inequalities that have to be satisfied by any optimal solution. We present an enhanced branch-and-cut algorithm that takes advantage of both these new inequalities and high quality min-max K-WRPP feasible solutions obtained by a metaheuristic. Computational results on a large set of instances are also reported. © 2011 Wiley Periodicals, Inc. es_ES
dc.description.sponsorship Contract grant sponsor: Ministerio de Ciencia e Innovacion of Spain; Contract grant numbers: MTM2006-14961-C05-02, MTM2009-14039-C06-02 es_ES
dc.language Inglés es_ES
dc.publisher WILEY-BLACKWELL es_ES
dc.relation.ispartof Networks es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Facets es_ES
dc.subject Multivehicle es_ES
dc.subject Rural postman problem es_ES
dc.subject Windy postman problem es_ES
dc.subject Windy rural postman problem es_ES
dc.subject Multi-vehicles es_ES
dc.subject Postman problems es_ES
dc.subject Windy rural postman problems es_ES
dc.subject Algorithms es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title New Facets and an Enhanced Branch-and-Cut for the Min-Max K-Windy Rural Postman Problem es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1002/net.20469 es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MICINN//MTM2009-14039-C06-02/ES/Modelos Y Metodos De Programacion Matematica Y Sus Aplicaciones (Optimos2)/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MEC//MTM2006-14961-C05-02/ES/OPTIMOS: OPTIMIZACION PARA LA MOVILIDAD SOSTENIBLE/ es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada es_ES
dc.description.bibliographicCitation Benavent López, E.; Corberán, A.; Plana, I.; Sanchís Llopis, JM. (2011). New Facets and an Enhanced Branch-and-Cut for the Min-Max K-Windy Rural Postman Problem. Networks. 58(4):255-272. https://doi.org/10.1002/net.20469 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1002/net.20469 es_ES
dc.description.upvformatpinicio 255 es_ES
dc.description.upvformatpfin 272 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 58 es_ES
dc.description.issue 4 es_ES
dc.relation.pasarela S\211865 es_ES
dc.contributor.funder Ministerio de Educación y Ciencia es_ES
dc.description.references D. Ahr Contributions to multiple postmen problems 2004 es_ES
dc.description.references Ahr, D., & Reinelt, G. (2002). New Heuristics and Lower Bounds for the Min-Max k-Chinese Postman Problem. Lecture Notes in Computer Science, 64-74. doi:10.1007/3-540-45749-6_10 es_ES
dc.description.references Ahr, D., & Reinelt, G. (2006). A tabu search algorithm for the min–max k-Chinese postman problem. Computers & Operations Research, 33(12), 3403-3422. doi:10.1016/j.cor.2005.02.011 es_ES
dc.description.references D. Applegate R. E. Bixby V. Chvátal W. Cook Finding cuts in the TSP 1995 es_ES
dc.description.references Benavent, E., Carrotta, A., Corberán, A., Sanchis, J. M., & Vigo, D. (2007). Lower bounds and heuristics for the Windy Rural Postman Problem. European Journal of Operational Research, 176(2), 855-869. doi:10.1016/j.ejor.2005.09.021 es_ES
dc.description.references Benavent, E., Corberán, A., Plana, I., & Sanchis, J. M. (2009). Min-Max K -vehicles windy rural postman problem. Networks, 54(4), 216-226. doi:10.1002/net.20334 es_ES
dc.description.references Benavent, E., Corberán, Á., & Sanchis, J. M. (2009). A metaheuristic for the min–max windy rural postman problem with K vehicles. Computational Management Science, 7(3), 269-287. doi:10.1007/s10287-009-0119-2 es_ES
dc.description.references Corberáan, A., Letchford, A. N., & Sanchis, J. M. (2001). A cutting plane algorithm for the General Routing Problem. Mathematical Programming, 90(2), 291-316. doi:10.1007/pl00011426 es_ES
dc.description.references Corberán, A., Plana, I., & Sanchis, J. M. (2007). A branch & cut algorithm for the windy general routing problem and special cases. Networks, 49(4), 245-257. doi:10.1002/net.20176 es_ES
dc.description.references Corberán, A., Plana, I., & Sanchis, J. M. (2008). The Windy General Routing Polyhedron: A Global View of Many Known Arc Routing Polyhedra. SIAM Journal on Discrete Mathematics, 22(2), 606-628. doi:10.1137/050640886 es_ES
dc.description.references Frederickson, G. N., Hecht, M. S., & Kim, C. E. (1978). Approximation Algorithms for Some Routing Problems. SIAM Journal on Computing, 7(2), 178-193. doi:10.1137/0207017 es_ES
dc.description.references Pearn, W. L. (1994). Solvable cases of the k-person Chinese postman problem. Operations Research Letters, 16(4), 241-244. doi:10.1016/0167-6377(94)90073-6 es_ES
dc.description.references I. Plana The windy general routing problem 2005 es_ES


Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem