New genetic local search operators for the traveling salesman problem

1. K. Boese, “Cost versus Distance in the Traveling Salesman Problem,” Tech. Rep. TR-950018, UCLA CS Department, 1995.

   Google Scholar 

2. K.D. Boese and S. Muddu, “A New Adaptive Multi-Start Technique for Combinatorial Global Optimizations,” Operations Research Letters 16, pp. 101–113, 1994.

   Article  Google Scholar 

3. B. Freisleben and M. Schulte, “Combinatorial Optimization with Parallel Adaptive Threshold Accepting,” in Proceedings of the 1992 European Workshop on Parallel Computing, Barcelona, pp. 176–179. IOS Press, 1992.

   Google Scholar 

4. B. Freisleben and P. Merz, “A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems,” in Proc. 1996 IEEE Int. Conf. on Evolutionary Computation, Nagoya, Japan, pp. 616–621, 1996.

   Google Scholar 

5. D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.

   Google Scholar 

6. M. Gorges-Schleuter, “ASPARAGOS: An Asynchronous Parallel Genetic Optimization Strategy,” in Proc. of the 3rd Int. Conf. on Genetic Algorithms, Morgan Kaufmann, 1989.

   Google Scholar 

7. M. Gorges-Schleuter, “Explicit Parallelism of Genetic Algorithms through Population Structures,” in Parallel Problem Solving from Nature, (H. Schwefel and R. Männer, Eds.), pp. 150–159, Springer-Verlag, 1991.

   Google Scholar 

8. J. J. Grefenstette, “Incorporating Problem Specific Knowledge into Genetic Algorithms,” in Genetic Algorithms and Simulated Annealing, (L. Davis, ed.), pp. 42–60, Morgan Kaufmann, 1987.

   Google Scholar 

9. J. Grefenstette, R. Gopal, B. Rosimaita, and D. van Gucht, “ Genetic Algorithms for the Traveling Salesman Problem,” in Proc. of an Int. Conf. on Genetic Algorithms and their Applications, pp. 160–168, 1985.

   Google Scholar 

10. L. Homaifar, C. Guan, and G. Liepins, “A New Approach to the Traveling Salesman Problem by Genetic Algorithms,” in Proc. of the 5th Int. Conf. on Genetic Algorithms, pp. 460–466, Morgan Kaufmann, 1993.

    Google Scholar 

11. P. Jog, J. Y. Suh, and D. van Gucht, “The Effects of Population Size, Heuristic Crossover and Local Improvement on a Genetic Algorithm for the Travelling Salesman Problem,” in Proc. of the 3rd Int. Conf. on Genetic Algorithms, pp. 110–115, Morgan Kaufmann, 1989.

    Google Scholar 

12. D. S. Johnson, “Local Optimization and the Traveling Salesman Problem,” in Annual Int. Colloquium on Automata, Languages and Programming, 1990.

    Google Scholar 

13. D. S. Johnson and L. A. McGeoch, “The Traveling Salesman Problem: A Case Study in Local Optimization,” in (E. H. L. Aarts and J. K. Lenstra, eds.) Local Search in Combinatorial Optimization, Wiley & Sons, New York, to appear.

    Google Scholar 

14. P. van Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory and Applications. Kluwer Academic Publ., 1987.

    Google Scholar 

15. E. L. Lawler, J. K. Lenstra and D. B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley and Sons, New York, 1985.

    Google Scholar 

16. S. Lin, “Computer Solutions of the Travelling Salesman Problem,” Bell System Tech. Journal, Vol. 44, pp. 2245–2269, 1965.

    Google Scholar 

17. S. Lin and B. Kernighan, “An Effective Heuristic Algorithm for the Traveling Salesman Problem,” Operations Research, Vol. 21, pp. 498–516, 1973.

    Google Scholar 

18. K. Mathias and D. Whitley, “Genetic Operators, the Fitness Landscape and the Traveling Salesman Problem,” in Parallel Problem Solving from Nature, (R. Männer and B. Manderick, Eds.), pp. 219–228, Elsevier, 1992.

    Google Scholar 

19. H. Mühlenbein, “Parallel Genetic Algorithms, Population Genetics and Combinatorial Optimization,” in Proc. of the 3rd Int. Conf. on Genetic Algorithms, (J. D. Schaffer, ed.), pp. 416–421, Morgan Kaufmann, 1989.

    Google Scholar 

20. H. Mühlenbein, “Evolution in Time and Space — The Parallel Genetic Algorithm,” in Foundations of Genetic Algorithms, (G. J. E. Rawlins, ed.), M. Kaufmann, 1991.

    Google Scholar 

21. H. Mühlenbein, M. Gorges-Schleuter, and O. Krämer, “Evolution Algorithms in Combinatorial Optimization,” Parallel Computing, Vol. 7, pp. 65–88, 1988.

    Article  Google Scholar 

22. M. Padberg and G. Rinaldi, “Optimization of a 532-city Symmetric Traveling Salesman Problem by Branch & Cut,” Operations Research Lett. 6, pp. 1–7, 1987.

    Article  Google Scholar 

23. G. Reinelt, “TSPLIB — A Traveling Salesman Problem Library,” ORSA Journal on Computing, Vol. 3, No. 4, pp. 376–384, 1991.

    Google Scholar 

24. G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications. Vol. 840 of Lecture Notes in Computer Science, Springer-Verlag, 1994.

    Google Scholar 

25. J. Y. Suh and D. van Gucht, “Incorporating Heuristic Information into Genetic Search,” in Proc. of the 2nd Int. Conf. on Genetic Algorithms, pp. 100–107, Lawrence Erlbaum, 1987.

    Google Scholar 

26. A. Y. C. Tang and K. S. Leung, “A Modified Edge Recombination Operator for the Travelling Salesman Problem,” in Parallel Problem Solving from Nature, (H.-P. Schwefel and R. Männer, Eds.), pp. 180–188, Springer-Verlag, 1994.

    Google Scholar 

27. N. L. J. Ulder, E. H. L. Aarts, H. J. Bandelt, P. J. M. van Laarhoven, and E. Pesch, “Genetic Local Search Algorithms for the Traveling Salesman Problem,” in Parallel Problem Solving from Nature, (H. P. Schwefel and R. Männer, Eds.), pp. 109–116, Springer-Verlag, 1991.

    Google Scholar 

28. M. Wall, “GALIB 2.3.2,” http://lancet.mit.edu/ga, 1995.

    Google Scholar 

29. D. Whitley, T. Starkweather, and D. Fuquay, “Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator,” in Proc. of the 3rd Int. Conf. on Genetic Algorithms, pp. 133–140, Morgan Kaufmann, 1989.

    Google Scholar 

Download references