Análisis de heurísticos para el problema del cartero rural
- Benavent López, Enric
- Campos Aucejo, Vicente
- Corberán Salvador, Ángel
- Mota Vidal, Enrique
ISSN: 0041-0241
Year of publication: 1985
Volume: 36
Issue: 2
Pages: 27-38
Type: Article
More publications in: Trabajos de estadística e investigación operativa
Abstract
In this paper we study the worst case performance of two heuristic algorithms proposed for the Rural Postman Problem on a non directed graph (RPP) and on a directed graph (DRPP). In both cases the worst case ratio is obtained; for the RPP this ratio is 3/2, whereas for the DRPP the ratio is unbounded. In order to obtain more significant bounds, this ratio has also been obtained as a function of certain parameters that can be computed from the particular data of each instance, thus producing a finite bound for the worst case ratio of the heuristic algorithm for the DRPP.