Analysis of heuristics for the Rural Postman Problem.

Enrique Benavent; Vicente Campos; Angel Corberán; Enrique Mota

Trabajos de Estadística e Investigación Operativa (1985)

  • Volume: 36, Issue: 2, page 27-38
  • ISSN: 0041-0241

Abstract

top
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.

How to cite

top

Benavent, Enrique, et al. "Análisis de heurísticos para el problema del cartero rural.." Trabajos de Estadística e Investigación Operativa 36.2 (1985): 27-38. <http://eudml.org/doc/40800>.

@article{Benavent1985,
abstract = {En este artículo se estudia el comportamiento en el peor de los casos de dos algoritmos heurísticos propuestos para el Problema del Cartero Rural definido sobre un grafo no dirigido (RPP) y sobre un grafo dirigido (DRPP). En ambos problemas se determina el radio del peor caso de los heurísticos estudiados, que para el RPP es 3/2, mientras que para el DRPP no está acotado. Para conseguir cotas que sean más significativas, se ha determinado también este radio en función de ciertos parámetros que se pueden calcular a partir de los datos particulares de cada ejemplo, lo que ha permitido obtener una cota finita para el comportamiento en el peor caso del algoritmo heurístico para el DRPP.},
author = {Benavent, Enrique, Campos, Vicente, Corberán, Angel, Mota, Enrique},
journal = {Trabajos de Estadística e Investigación Operativa},
keywords = {Heurística; Circuitos eulerianos; Algoritmos; Caso peor},
language = {spa},
number = {2},
pages = {27-38},
title = {Análisis de heurísticos para el problema del cartero rural.},
url = {http://eudml.org/doc/40800},
volume = {36},
year = {1985},
}

TY - JOUR
AU - Benavent, Enrique
AU - Campos, Vicente
AU - Corberán, Angel
AU - Mota, Enrique
TI - Análisis de heurísticos para el problema del cartero rural.
JO - Trabajos de Estadística e Investigación Operativa
PY - 1985
VL - 36
IS - 2
SP - 27
EP - 38
AB - En este artículo se estudia el comportamiento en el peor de los casos de dos algoritmos heurísticos propuestos para el Problema del Cartero Rural definido sobre un grafo no dirigido (RPP) y sobre un grafo dirigido (DRPP). En ambos problemas se determina el radio del peor caso de los heurísticos estudiados, que para el RPP es 3/2, mientras que para el DRPP no está acotado. Para conseguir cotas que sean más significativas, se ha determinado también este radio en función de ciertos parámetros que se pueden calcular a partir de los datos particulares de cada ejemplo, lo que ha permitido obtener una cota finita para el comportamiento en el peor caso del algoritmo heurístico para el DRPP.
LA - spa
KW - Heurística; Circuitos eulerianos; Algoritmos; Caso peor
UR - http://eudml.org/doc/40800
ER -

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.