- -

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

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

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

Show full item record

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. doi:10.1007/s10287-009-0119-2

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/100790

Files in this item

Item Metadata

Title: A metaheuristic for the min-max Windy Rural Postman Problem with K vehicles
Author:
UPV Unit: Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada
Issued date:
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 ...[+]
Subjects: Rural postman problem , Windy rural postman problem , Metaheuristics , Multivehicles
Copyrigths: Reserva de todos los derechos
Source:
Computational Management Science. (issn: 1619-697X )
DOI: 10.1007/s10287-009-0119-2
Publisher:
Springer-Verlag
Publisher version: https://doi.org/10.1007/s10287-009-0119-2
Thanks:
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.
Type: Artículo

References

Ahr D (2004) Contributions to multiple postmen problems, PhD Thesis. University of Heidelberg, Germany, September

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

Ahr D, Reinelt G (2006) A Tabu search algorithm for the min–max k-Chinese postman problem. Comput Oper Res 33: 3403–3422 [+]
Ahr D (2004) Contributions to multiple postmen problems, PhD Thesis. University of Heidelberg, Germany, September

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

Ahr D, Reinelt G (2006) A Tabu search algorithm for the min–max k-Chinese postman problem. Comput Oper Res 33: 3403–3422

Applegate D, Cook W, Dash S, Rohe A (2002) Solution of a min–max vehicle routing problem. INFORMS J Comput 14: 132–143

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

Barahona F, Grötschel M (1986) On the cycle polytope of a binary matroid. J Comb Theory 40: 40–62

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

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

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

Benavent E, Corberán A, Plana I, Sanchis JM (2009) Min–Max K-vehicles windy rural postman problem. Networks 54: 216–226

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)

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

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

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

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

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

Eiselt HA, Gendreau M, Laporte G (1995) Arc-routing problems, Part 2: the rural postman problem. Oper Res 43: 399–414

Frederickson G, Hecht M, Kim C (1978) Approximation algorithms for some routing problems. SIAM J Comput 7: 178–193

Lacomme P, Prins C, Ramdane-Chérif W (2002) Fast algorithms for general arc routing problems. IFORS, Edinburgh, 8–12 July 2002

Lacomme P, Prins C, Ramdane-Chérif W (2004) Competitive memetic algorithms for arc routing problems. Ann OR 131: 159–185

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

Minieka E (1979) The Chinese postman problem for mixed networks. Manage Sci 25: 643–648

Mladenovic N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24: 1097–1100

Or I (1976) Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. PhD Dissertation, Northwestern University, Evanston, USA

Pearn WL (1994) Solvable cases of the k-person Chinese postman problem. Oper Res Lett 16: 241–244

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

Ramdane-Chérif W (2002) Problémes de Tournées sur Arcs. PhD thesis, University of Troyes, France [in French]

Win Z (1989) On the windy postman problem on eulerian graphs. Math Program 44: 97–112

[-]

This item appears in the following Collection(s)

Show full item record