Improving the Performance of Multi-start Search on the Traveling Salesman Problem - Developing Concepts in Applied Intelligence - page 81

still provides a significant performance improvement. Thus, regardless of the
complexity of a TSP configuration and memory limits, even a small cache is useful.
This work has applications in the study of the traveling salesman problem and in
combinatorial optimization problems in general.
Future work involves further investigation of redundancy in the construction
algorithms. We plan to investigate stochastic mechanisms to minimize redundancy
and study its affects on algorithm performance and quality of the generated tours.
References
1. Cormen, T.H., et al.: Introduction to Algorithms. MIT Press, Cambridge (2001)
2. Johnson, D., McGeoch, L.: The Traveling Salesman Problem: A Case Study. In: Local
Search in Combinatorial Optimization, pp. 215-310. John Wiley & Sons, Chichester
(1997)
3. Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-
completeness. W.H. Freeman, New York (1979)
4. Karhi, D., Tamir, D.E.: Caching in the TSP Search Space. In: Chien, B.-C., Hong, T.-P.,
Chen, S.-M., Ali, M. (eds.) IEA/AIE 2009. LNCS, vol. 5579, pp. 221-230. Springer,
Heidelberg (2009)
5. Allen, D., Darwiche, A.: Optimal Time-Space Tradeoff in Probabilistic Inference. In:
Proceedings of the 21st International Joint Conference on Artificial Intelligence (2003)
6. Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publishers, Dordrecht (1997)
7. Glover, F., Taillard, E., de Werra, D.: A User's Guide to Tabu Search. Annals of
Operations Research 41(1-4), 3-28 (1993)
8. King, C.R.: Improving the performance of constructive multi-start search using record
keeping. In: Computer Science. Texas State University, San Marcos (2010)
9. Dawson, E., Wong, D.: Information Security Practice and Experience. Springer,
Heidelberg (2007)
10. Applegate, D.L., et al.: The Traveling Salesman Problem, A Computational Study.
Princeton University Press, Princeton (2006)
11. Ambite, J., Knoblock, C.: Planning by Rewriting. Journal of Artificial Intelligence
Research, 207-261 (2001)
12. Pitsoulis, L.S., Resende, M.G.C.: Greedy Randomized Adaptive Search Procedures. In:
Handbook of Applied Optimization, pp. 168-183. Oxford University Press, Oxford (2001)
13. Hennessy, J.L., Patterson, D.A.: Computer Architecture. In: A Quantative Approach.
Morgan Kaufmann Publishers, Inc., San Francisco (2007)
14. Reinelt, G.: TSPLIB -A traveling salesman problem library. ORSA Journal on
Computing 3(4), 376-384 (1991)