ICSC
interdisciplinary research

Fourth International ICSC Symposium on
ENGINEERING OF INTELLIGENT SYSTEMS (EIS 2004)
in collaboration with the University of Madeira
Island of Madeira, Portugal
February 29 – March 2, 2004

 
 

 

Session:

Hybrid System Applications
Sunday, February 29, 2004, 17.55 – 18.15

Session Chair:

Fikret Gürgen

   

Paper Title:

Heuristics and Metaheuristics Approaches used to Solve the Rural Postman Problem: A Comparative Case Study

   

Author(s):

M. Gulnara Baldoquín de la Peña, Prof. Dr. Dpto. Matemática General, Universidad
Técnica de La Habana (ISPJAE), Habana Cuba

   

Abstract:

The Rural Postman Problem (RPP) consists of determining a minimum cost tour of a specified arc set of a graph (G=(V,A)) with the particularity that only a subset T (T Í A) of arcs is required to be traversed at least once. The arcs can be directed, undirected or both. This problem appears in a variety of practical contexts like mail, fuel and newspaper deliveries, school bus routing, electrical lines inspection, etc. (Frederickson, 1979). RPP is a NP-hard problem, therefore it has been tackled with some heuristics and metaheuristics due to the difficulty of using exact approaches to global optimality. Up to now, and based in computational results using 26 instances described in Christofides et al. (1981) and in Corberán & Sanchis (1994), a heuristic algorithm for the RPP by Fernández de Córdoba et al. (1998) based on Monte Carlo method had obtained the best results. Baldoquín et al. (2002) developed a hybrid approach based on GRASP and Genetic Algorithm comparable with the above method testing the same instances. In this paper a new hybrid approach based on Simulated Annealing, GRASP and Genetic Algorithm is introduced to solve the Undirected Rural Postman Problem (URPP). We describe the design of a computational experiment to compare the performance of Monte Carlo and the two hybrid method mentioned before, using the same 26 instances. Computational results indicate that the new hybrid approach presented in this paper, and considering the instances tested, outperformed the other methods.

Key words: heuristics, metaheuristics, routing problems, GRASP, Genetic Algorithms, Simulated Annealing.

CD-ROM Produced by X-CD Technologies