- -

A Heuristic Algorithm Based on Monte Carlo Methods for the Rural Postman Problem

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

  • Estadisticas de Uso

A Heuristic Algorithm Based on Monte Carlo Methods for the Rural Postman Problem

Show simple item record

Files in this item

dc.contributor.author Fernández de Córdoba, Pedro es_ES
dc.contributor.author García-Raffi, L. M. es_ES
dc.contributor.author Sanchís Llopis, José María es_ES
dc.date.accessioned 2018-01-02T09:44:08Z
dc.date.available 2018-01-02T09:44:08Z
dc.date.issued 1998 es_ES
dc.identifier.issn 0305-0548 es_ES
dc.identifier.uri http://hdl.handle.net/10251/93709
dc.description.abstract [EN] The Rural Postman Problem (RPP) consists of finding a minimum cost traversal of a specified are subset of a graph. Given that the RPP is a NP-hard problem, heuristic algorithms are interesting both to handle large size instances and to provide upper bounds that could be used in branch and cut procedures. In this paper we propose a heuristic algorithm for the RPP based on Monte Carlo methods. We simulate a vehicle travelling randomly over the graph, jumping from one node to another on the basis of certain probabilities. Monte Carlo methods provide a simple approach to many different Routing Problems and they are easily implemented in a computer code. The application of this algorithm to a set of RPP instances taken from the literature demonstrates that, using the appropriate probabilities, they are also efficient. (C) 1998 Published by Elsevier Science Ltd. All rights reserved. es_ES
dc.language Inglés es_ES
dc.publisher Elsevier es_ES
dc.relation.ispartof Computers & Operations Research es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Rural postman problem es_ES
dc.subject Routing problems es_ES
dc.subject Monte Carlo methods es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title A Heuristic Algorithm Based on Monte Carlo Methods for the Rural Postman Problem es_ES
dc.type Artículo es_ES
dc.rights.accessRights Cerrado 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 Fernández De Córdoba, P.; García-Raffi, LM.; Sanchís Llopis, JM. (1998). A Heuristic Algorithm Based on Monte Carlo Methods for the Rural Postman Problem. Computers & Operations Research. 25(12):1097-1106. http://hdl.handle.net/10251/93709 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://www.journals.elsevier.com/computers-and-operations-research es_ES
dc.description.upvformatpinicio 1097 es_ES
dc.description.upvformatpfin 1106 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 25 es_ES
dc.description.issue 12 es_ES
dc.relation.pasarela S\15967 es_ES


This item appears in the following Collection(s)

Show simple item record