6533b856fe1ef96bd12b2ed2
RESEARCH PRODUCT
Analisis de heuristicos para el problema del cartero rural
Enrique VidalAngel Corberán SalvadorVicente Campos AucejoEnric Benavent Lópezsubject
Statistics and ProbabilityStatistics Probability and Uncertaintydescription
En este articulo se estudia el comportamiento en el peor de los casos de dos algoritmos heuristicos 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 heuristicos estudiados, que para el RPP es 3/2, mientras que para el DRPP no esta acotado. Para conseguir cotas que sean mas significativas, se ha determinado tambien este radio en funcion de ciertos parametros 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 heuristico para el DRPP.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1985-03-01 | Trabajos de Estadistica Y de Investigacion Operativa |