The Undirected Rural Postman Problem Solved by the MAX-MIN Ant System

1. Deneubourg, J.L., Aron, S., Goss, S., Pasteels, J.M.: The self-organizing exploratory pattern of the argentine ant. J. Insect Behav. 3, 159–168 (1990)

   Article  Google Scholar 

2. Dorigo, M.: Optimization, learning and natural algorithms. Ph.D. thesis, Dip. Elettronica, Politecnico di Milano, Italy (1992)

   Google Scholar 

3. Dorigo, M., Blum, C.: Ant colony optimization: a survey. Theorical Computer Science 344, 243–278 (2005)

   Article  MATH  MathSciNet  Google Scholar 

4. Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)

   MATH  Google Scholar 

5. Orloff, C.S.: A fundamental problem in vehicle routing. Networks 4, 35–64 (1974)

   Article  MATH  MathSciNet  Google Scholar 

6. Lenstra, J.K., Rinnooy-Kan, A.H.G.: On general routing problems. Networks 6(3), 273–280 (1976)

   Article  MATH  MathSciNet  Google Scholar 

7. Eiselt, H.A., Gendreau, M., Laporte, G.: Arc routing problems, part II: The rural postman problem. Oper. Res. 43(3), 399–414 (1995)

   Article  MATH  MathSciNet  Google Scholar 

8. Christofides, N., Campos, V., Corberán, A., Mota, E.: An algorithm for the rural postman problem. Tech. Rep. IC-O.R.-81-5, Imperial College, London, UK (1981)

   Google Scholar 

9. Corberán, A., Sanchís, J.M.: A polyhedral approach to the rural postman problem. Eur. J. Oper. Res. 79, 95–114 (1994)

   Article  MATH  Google Scholar 

10. Letchford, A.N.: Polyhedral results for some constrained arc routing problems. Ph.D. thesis, Lancaster University, Lancaster (1996)

    Google Scholar 

11. Ghiani, G.: A branch-and-cut algorithm for the undirected rural postman problem. Math. Programming 87(3), 467–481 (2000)

    Article  MATH  MathSciNet  Google Scholar 

12. Chistofides, N., Campos, V., Corberán, A., Mota, E.: An algorithm for the rural postman problem on a directed graph. Math. Programming Stud. 26, 155–166 (1986)

    Google Scholar 

13. Chistofides, N., Mingozzi, A., Toth, P.: Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxations. Math. Programming 20(1), 255–282 (1986)

    Article  Google Scholar 

14. Fernández, E., Meza, O., Garfinkel, R., Ortega, M.: On the undirected rural postman problem: Tight bounds based on a new formulation. Oper. Res. 51(2), 281–291 (2003)

    Article  MathSciNet  Google Scholar 

15. Fernández, P., García, L.M., Sanchis, J.M.: A heuristic algorithm based on Monte Carlo methods for the rural postman problem. Comput. Oper. Res. 25(12), 1097–1106 (1998)

    Article  MATH  Google Scholar 

16. Frederickson, G.N.: Approximation algorithms for some postman problems. J. ACM 26(3), 538–554 (1979)

    Article  MATH  MathSciNet  Google Scholar 

17. Ghiani, G., Laganà, D., Musmanno, R.: A constructive heuristic for the undirected rural postman problem. Comput. Oper. Res. 33(12), 3450–3457 (2006)

    Article  MATH  Google Scholar 

18. Groves, G.W., van Vuure, J.H.: Efficient heuristics for the rural postman problem. Orion 21(1), 33–51 (2005)

    Google Scholar 

19. Hertz, A., Laporte, G., Nanchen-Hugo, P.: Improvement procedures for the undirected rural postman problem. INFORMS J. Comput. 11(1), 53–62 (1999)

    Article  MATH  MathSciNet  Google Scholar 

20. Pearn, W.L., Wu, T.C.: Algorithms for the rural postman problem. Comput. Oper. Res. 22(8), 819–828 (1995)

    Article  MATH  Google Scholar 

21. Baldoquín, M.G.: Heuristics and metaheuristics approaches used to solve the rural postman problem: a comparative case study. In: Proc. Fourth Internat. ICSC Symposium on Engineering of Intelligent Systems (EIS 2004), Maderia, Portugal (2004)

    Google Scholar 

22. Baldoquín, M.G., Ryan, G., Rodriguez, R., Castellini, A.: Un enfoque híbrido basado en metaheurísticas para el problema del cartero rural. In: Proc. of XI CLAIO, Concepci’on de Chile, Chile (2002)

    Google Scholar 

23. Kang, M.J., Han, C.G.: Solving the rural postman problem using a genetic algorithm with a graph transformation. Tech. rep., Dept. of Computer Engineering, Kyung Hee University (1998)

    Google Scholar 

24. Pérez-Delgado, M.L.: A solution to the rural postman problem based on artificial ant colonies. In: Borrajo, D., Castillo, L., Corchado, J.M. (eds.) CAEPIA 2007. LNCS (LNAI), vol. 4788, pp. 220–228. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

25. Pérez-Delgado, M.L., Matos-Franco, J.C.: Self-organizing feature maps to solve the undirected rural postman problem. In: Moreno Díaz, R., Pichler, F., Quesada Arencibia, A. (eds.) EUROCAST 2007. LNCS, vol. 4739, pp. 804–811. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

26. Rodrigues, A.M., Ferreira, J.S.: Solving the rural postman problem by memetic algorithms. In: MIC 2001 - 4TH Metaheuristics Internat. Conf., Porto, Portugal (2001)

    Google Scholar 

27. Stützle, T., Hoos, H.: The MAX-MIN Ant System and local search for the traveling salesman problem. In: Bäck, T., Michalewicz, Z., Yao, X. (eds.) Proc. IEEE Internat. Conf. on Evolutionary Computation, pp. 309–314 (1997)

    Google Scholar 

28. Stützle, T., Dorigo, M.: A short convergence proof for a class of ant colony optimization algorithms. IEEE Trans. Evol. Comput. 6(4), 358–365 (2002)

    Article  Google Scholar 

Download references