- -

Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem

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

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem

Mostrar el registro sencillo del ítem

Ficheros en el ítem

[Pdf]
Nombre: DCGDRPP.pdf
Tamaño: 39Kb
Formato: PDF
Descripción: Versión del Autor
Abrir
[Cerrado]
Nombre: 30-4FormulationsD ...
Tamaño: 650.6Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor
dc.contributor.author Ávila, Thais 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 2018-09-17T07:37:37Z
dc.date.available 2018-09-17T07:37:37Z
dc.date.issued 2017 es_ES
dc.identifier.issn 2192-4406 es_ES
dc.identifier.uri http://hdl.handle.net/10251/107412
dc.description.abstract [EN] The generalized directed rural postman problem is an arc routing problem with many interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets closer than a certain distance to a meter, the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, to get close enough to each meter. We study an extension of this problem in which a fleet of vehicles is available. Given the characteristics of the mentioned application, the vehicles have no capacities but there is a maximum distance (or time) constraint all of them have to satisfy.We introduce four formulations for this problem, propose some families of valid inequalities, and present four branch-and-cut algorithms for its solution. The formulations and the algorithms are compared on a large set of instances. es_ES
dc.description.sponsorship The authors thank the Spanish Ministerio de Economia y Competitividad (project MTM2012-36163-C06-02) and the Generalitat Valenciana (project GVPROMETEO2013-049) for their support. es_ES
dc.language Inglés es_ES
dc.publisher Springer-Verlag es_ES
dc.relation.ispartof EURO Journal on Computational Optimization es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Distance constrained es_ES
dc.subject Multivehicle es_ES
dc.subject Generalized directed rural postman problem es_ES
dc.subject Close-enough arc routing problem es_ES
dc.subject Branch-and-cut es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s13675-015-0053-8 es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MINECO//MTM2012-36163-C06-02/ES/MODELOS Y METODOS DE PROGRAMACION MATEMATICA Y SUS APLICACIONES (OPTIMOS3)/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/GVA//PROMETEO%2F2013%2F049/ES/Modelos y algoritmos para problemas de optimización combinatoria/ 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 Ávila, T.; Corberán, A.; Plana, I.; Sanchís Llopis, JM. (2017). Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem. EURO Journal on Computational Optimization. 5(3):339-365. https://doi.org/10.1007/s13675-015-0053-8 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1007/s13675-015-0053-8 es_ES
dc.description.upvformatpinicio 339 es_ES
dc.description.upvformatpfin 365 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 5 es_ES
dc.description.issue 3 es_ES
dc.relation.pasarela S\342982 es_ES
dc.contributor.funder Ministerio de Economía y Competitividad es_ES
dc.contributor.funder Generalitat Valenciana es_ES
dc.description.references Ávila T, Corberán Á, Plana I, Sanchis JM (2015) A new branch-and-cut algorithm for the generalized directed rural postman problem. Transp Sci. doi: 10.1287/trsc.2015.0588 es_ES
dc.description.references Benavent E, Carrotta A, Corberán Á, Sanchis JM, Vigo D (2007) Lower bounds and heuristics for the windy rural postman problem. Eur J Oper Res 176:855–869 es_ES
dc.description.references Benavent E, Corberán Á, Plana I, Sanchis JM (2009) Min–max k-vehicles windy rural postman problem. Networks 54:216–226 es_ES
dc.description.references Corberán Á, Laporte G (eds) (2014) Arc routing: problems, methods, and applications MOS-SIAM series on optimization, Philadelphia es_ES
dc.description.references Corberán Á, Plana I, Sanchis JM (2015) Arc routing problems: data instances. http://www.uv.es/corberan/instancias.htm es_ES
dc.description.references Drexl M (2007) On some generalized routing problems. PhD thesis, Rheinisch-Westfälische Technische Hochschule, Aachen University es_ES
dc.description.references Drexl M (2014) On the generalized directed rural postman problem. J Oper Res Soc 65:1143–1154 es_ES
dc.description.references Gendreau M, Laporte G, Semet F (1997) The covering tour problem. Oper Res 45:568–576 es_ES
dc.description.references Gomory RE, Hu TC (1961) Multi-terminal network flows. J Soc Ind Appl Math 9:551–570 es_ES
dc.description.references Hà M-H, Bostel N, Langevin A, Rousseau L-M (2014) Solving the close enough arc routing problem. Networks 63:107–118 es_ES
dc.description.references Shuttleworth R, Golden BL, Smith S, Wasil EA (2008) Advances in meter reading: heuristic solution of the close enough traveling salesman problem over a street network. In: Golden BL, Raghavan S, Wasil EA (eds) The vehicle routing problem: latest advances and new challenges. Springer, Berlin, pp 487–501 es_ES


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

Mostrar el registro sencillo del ítem