- -

A GRASP for the Mixed Postman Problem

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

  • Estadisticas de Uso

A GRASP for the Mixed Postman Problem

Show simple item record

Files in this item

dc.contributor.author Corberán, A. es_ES
dc.contributor.author Marti, R. es_ES
dc.contributor.author Sanchís Llopis, José María es_ES
dc.date.accessioned 2018-04-19T04:14:20Z
dc.date.available 2018-04-19T04:14:20Z
dc.date.issued 2002 es_ES
dc.identifier.issn 0377-2217 es_ES
dc.identifier.uri http://hdl.handle.net/10251/100592
dc.description.abstract [EN] Arc routing problems (ARPs) consist of finding a traversal on a graph satisfying some conditions related to the links of the graph. In the Chinese postman problem (CPP) the aim is to find a minimum cost tour (closed walk) traversing all the links of the graph at least once. Both the Undirected CPP, where all the links are edges that can be traversed in both ways, and the Directed CPP, where all the links are arcs that must be traversed in a specified way, are known to be polynomially solvable. However, if we deal with a mixed graph (having edges and arcs), the problem turns out to be,N P-hard. In this paper, we present a heuristic algorithm for this problem, the so-called Mixed CPP (MCPP), based on greedy randomized adaptive search procedure (GRASP) techniques. The algorithm has been tested and compared with other known and recent methods from the literature on a wide collection of randomly generated instances, with up to 200 nodes and 600 links, producing encouraging computational results. As far as we know, this is the best heuristic algorithm for the MCPP, with respect to solution quality, published up to now. es_ES
dc.language Inglés es_ES
dc.publisher Elsevier es_ES
dc.relation.ispartof European Journal of Operational Research es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Metaheuristics es_ES
dc.subject Routing es_ES
dc.subject Chinese postman es_ES
dc.subject GRASP es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title A GRASP for the Mixed Postman Problem es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1016/S0377-2217(01)00296-X 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.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1016/S0377-2217(01)00296-X es_ES
dc.description.upvformatpinicio 70 es_ES
dc.description.upvformatpfin 80 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 142 es_ES
dc.description.issue 1 es_ES
dc.relation.pasarela S\22199 es_ES


This item appears in the following Collection(s)

Show simple item record