Abstract

In this paper, the Moving Target Travelling Salesman Problem (MTTSP) is described. In MTTSP, several sites are required to be visited which are moving with constant velocity in different directions. The distance of the sites from origin, velocity and the angle of movement are known in advance. The goal is to find the fastest tour starting and ending at the origin which intercepts all the sites. The method implemented using genetic algorithm approach on the various data sets and the results are compared with greedy approach.

References

• Horowitz E. , Sahani S, and Rajasekaran S, 2007. Fundamentals of Computer Algorithm, University Press.
• Rajesh Matai, Surya Singh and Murari Lal Mittal (2010). Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches, Traveling Salesman Problem, Theory and Applications, Prof. Donald Davendra (Ed. ), ISBN: 978-953-307-426-9, InTech, Available from: http://www. intechopen. com/books/traveling-salesman-problem-theory-and-applications/traveling-salesmanproblem an-overview-of-applications-formulations-and-solution-approaches.
• Schrijver, A. , 2005. On the History of Combinatorial Optimization (Till 1960). In K. Aardal, G. L. Nemhauser, & R. Weismantel (Eds. ), Handbooks in operations research and management science, 12, Amsterdam: Elsevier.
• Helvig C. S. , Gabriel Robins, and Alex Zelikovsky, 2003. The Moving-target travelling salseman problem, Journal of Algorithms 49 (2003), 153-174.
• Helvig C. S. Gabriel Robins, and Alex Zelikovsky, C. H. Helvig, G. Robins, and A. Zelikovsky. "Moving Target TSP and Related Problems", G. Bilardi et Al. (Eds. ): ESA'98, LNCS 1461, pp 435-1998.
• D. P. Guy, Evolutionary Computing as a Tool for Grammar Development, CNTS – Language Technology Group, UIA – University of Antwerp, Antwerp – Belgium, GECCO 2003 LNCS 2723, Springer-Verlag, Berlin, Heidelberg, 2003, pp. 549–560.
• J. H. Holland, Adoption in Natural and Artificial System, University of Michigan Press, Ann Arbor, MI, 1975.
• D. E. Goldberg, Genetic Algorithms in Search, Optimizations and Machine Learn-ing, Addison-Wesley, 1989.
• Jindal Pawan, Amit Kumar, and Shishir Kumar, 2011, "Dynamic Version of Travelling Salseperson Problem", International Journal of Computer Applications (0975 – 8887), Volume 19– No. 1, April 2011.
• Choubey Nitin S. , 2012, "Solving TSP using DARO", International Journal of Computer Applications (0975-8887), Volume 58-No. 9, November 2012.
• Potvin J. Y. , 1996, "Geneti Algorithms for the Travelling Salseman Problem", Annals of Operation Research, 339-370, 1996.
• Sivanandam, Deepa, 2008, "Introduction to Genetic Algorithm", Springer, 2008.
• Bartley Cristopher, 2004, "Closed Form Guidance Laws for Intercepting Moving Targets" Master's thesis, Rice University, Houstons, Texas, April 2004.
• Gabrial Jacob Diaz, Flip Phillips and Brett R. Fajen, 2009, "Intercepting Moving Targets: a Little Foresight Helps a Lot" Springer-Verlag 2009.
• Jason R. Looker, 2008, "Minimum Paths to Interception of a Moving Targets when Constrained by Turning Radius", DSTO Defence Science and Technology Organisation, Australia, December 2008.
• Jindal Pawan, Amit Kumar, and Shishir Kumar, 2011, "Multiple Target Intercepting Travelling Salseperson Problem", International Journal of Computer Science and Technology, (0976 – 8491), Volume 2– Issue 2, June 2011.