- -

A metaheuristic for the min-max Windy Rural Postman Problem with K vehicles

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

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

A metaheuristic for the min-max Windy Rural Postman Problem with K vehicles

Mostrar el registro sencillo del ítem

Ficheros en el ítem

Thumbnail
Nombre: Metaheuristic_MM_ ...
Tamaño: 284.7Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir
[Cerrado]
Nombre: CompManagScience2 ...
Tamaño: 334.6Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor
dc.contributor.author Benavent, Enrique es_ES
dc.contributor.author Corberán, Angel es_ES
dc.contributor.author Sanchís Llopis, José María es_ES
dc.date.accessioned 2018-04-21T04:16:00Z
dc.date.available 2018-04-21T04:16:00Z
dc.date.issued 2010 es_ES
dc.identifier.issn 1619-697X es_ES
dc.identifier.uri http://hdl.handle.net/10251/100790
dc.description.abstract [EN] In this paper we deal with the min¿max version of the windy rural postman problem with K vehicles. For this problem, in which the objective is to minimize the length of the longest tour in order to find a set of balanced tours for the vehicles, we present here a metaheuristic that produces very good feasible solutions in reasonable computing times. It is based on the combination of a multi-start procedure with an Iterated Local Search. Extensive computational results on a large set of instances with up to 50 vertices, 184 edges and 5 vehicles are presented. The results are very good, the average gaps with respect to a known lower bound are less than 0.40% for instances with 2 or 3 vehicles and up to 1.60% when 4 or 5 vehicles are considered. es_ES
dc.description.sponsorship Authors wish to thank the Ministerio de Educación y Ciencia of Spain (projects MTM2006-14961-C05-02 and MTM2009-14039-C06-02) for its support. es_ES
dc.language Inglés es_ES
dc.publisher Springer-Verlag es_ES
dc.relation.ispartof Computational Management Science es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Rural postman problem es_ES
dc.subject Windy rural postman problem es_ES
dc.subject Metaheuristics es_ES
dc.subject Multivehicles es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title A metaheuristic for the min-max Windy Rural Postman Problem with K vehicles es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s10287-009-0119-2 es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MEC//MTM2006-14961-C05-02/ES/OPTIMOS: OPTIMIZACION PARA LA MOVILIDAD SOSTENIBLE/ 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.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, E.; Corberán, A.; Sanchís Llopis, JM. (2010). A metaheuristic for the min-max Windy Rural Postman Problem with K vehicles. Computational Management Science. 7(3):269-287. https://doi.org/10.1007/s10287-009-0119-2 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1007/s10287-009-0119-2 es_ES
dc.description.upvformatpinicio 269 es_ES
dc.description.upvformatpfin 287 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 7 es_ES
dc.description.issue 3 es_ES
dc.relation.pasarela S\39756 es_ES
dc.contributor.funder Ministerio de Educación y Ciencia es_ES
dc.contributor.funder Ministerio de Ciencia e Innovación es_ES
dc.description.references Ahr D (2004) Contributions to multiple postmen problems, PhD Thesis. University of Heidelberg, Germany, September es_ES
dc.description.references Ahr D, Reinelt G (2002) New heuristics and lower bounds for the min–max k-Chinese postman problem. In: Möring R, Raman R (eds) Algorithms-ESA 2002, 10th Annual European symposium, Rome, Italy, September 2002 Proceedings, Lecture Notes in Computer Science, vol 2461. Springer, Berlin, pp 64–74 es_ES
dc.description.references Ahr D, Reinelt G (2006) A Tabu search algorithm for the min–max k-Chinese postman problem. Comput Oper Res 33: 3403–3422 es_ES
dc.description.references Applegate D, Cook W, Dash S, Rohe A (2002) Solution of a min–max vehicle routing problem. INFORMS J Comput 14: 132–143 es_ES
dc.description.references Assad A, Pearn WL, Golden B (1987) The capacitated Chinese postman problem: lower bounds and solvable cases. Am J Math Manag Sci 7: 63–88 es_ES
dc.description.references Barahona F, Grötschel M (1986) On the cycle polytope of a binary matroid. J Comb Theory 40: 40–62 es_ES
dc.description.references Belenguer JM, Benavent E, Labadi N, Prins C (2009) Reghioui M Split delivery capacitated arc routing problem: lower bound and metaheuristic. Submitted to Transport Sci es_ES
dc.description.references Benavent E, Corberán A, Piñana E, Plana I, Sanchis JM (2005) New heuristic algorithms for the windy rural postman problem. Comput Oper Res 32: 3111–3128 es_ES
dc.description.references Benavent E, Carrotta A, Corberán A, 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 A, Plana I, Sanchis JM (2009) Min–Max K-vehicles windy rural postman problem. Networks 54: 216–226 es_ES
dc.description.references Benavent E, Corberán A, Plana I, Sanchis JM (2010) New facets and an enhanced branch-and-cut for the min–max k-vehicles windy rural postman problem (submitted) es_ES
dc.description.references Christofides N, Campos V, Corberán A, Mota E (1981) An algorithm for the Rural Postman Problem, Report IC.O.R.81.5. Imperial College, London es_ES
dc.description.references Christofides N, Campos V, Corberán A, Mota E (1986) An algorithm for the rural postman problem on a directed graph. Math Program Study 26: 155–166 es_ES
dc.description.references Corberán A, Plana I, Sanchis JM (2008) The windy general routing polyhedron: a global view of many known arc routing polyhedra. SIAM J Discret Math 22: 606–628 es_ES
dc.description.references Corberán A, Plana I, Sanchis JM (2007) A branch & cut algorithm for the windy general routing problem and special cases. Networks 49: 245–257 es_ES
dc.description.references Delgado C, Pacheco J (2001) Minmax vehicle routing problems: application to school transport in the Province of Burgos. Lecture notes in economics and mathematical systems, vol 505, pp 297–317 es_ES
dc.description.references Eiselt HA, Gendreau M, Laporte G (1995) Arc-routing problems, Part 2: the rural postman problem. Oper Res 43: 399–414 es_ES
dc.description.references Frederickson G, Hecht M, Kim C (1978) Approximation algorithms for some routing problems. SIAM J Comput 7: 178–193 es_ES
dc.description.references Lacomme P, Prins C, Ramdane-Chérif W (2002) Fast algorithms for general arc routing problems. IFORS, Edinburgh, 8–12 July 2002 es_ES
dc.description.references Lacomme P, Prins C, Ramdane-Chérif W (2004) Competitive memetic algorithms for arc routing problems. Ann OR 131: 159–185 es_ES
dc.description.references Lourenço HR, Martin O, Stützle T (2002) Iterated local search. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. Kluwer’s International Series, pp 321–353 es_ES
dc.description.references Minieka E (1979) The Chinese postman problem for mixed networks. Manage Sci 25: 643–648 es_ES
dc.description.references Mladenovic N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24: 1097–1100 es_ES
dc.description.references Or I (1976) Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. PhD Dissertation, Northwestern University, Evanston, USA es_ES
dc.description.references Pearn WL (1994) Solvable cases of the k-person Chinese postman problem. Oper Res Lett 16: 241–244 es_ES
dc.description.references Raghavachari B, Veerasamy J (1998) Approximation Algorithms for the Mixed Postman Problem. In: Bixby RE, Boyd EA, Ríos-Mercado RZ (eds) Proceedings of 6th Integer programming and combinatorial optimization. LNCS, vol 1412. Springer, pp 169–179 es_ES
dc.description.references Ramdane-Chérif W (2002) Problémes de Tournées sur Arcs. PhD thesis, University of Troyes, France [in French] es_ES
dc.description.references Win Z (1989) On the windy postman problem on eulerian graphs. Math Program 44: 97–112 es_ES


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

Mostrar el registro sencillo del ítem