CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Dynamic version of Traveling Salesman Problem

by Pawan Jindal, Amit Kumar, Shishir Kumar
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 19 - Number 1
Year of Publication: 2011
Authors: Pawan Jindal, Amit Kumar, Shishir Kumar
10.5120/2322-3010

Pawan Jindal, Amit Kumar, Shishir Kumar . Dynamic version of Traveling Salesman Problem. International Journal of Computer Applications. 19, 1 ( April 2011), 37-46. DOI=10.5120/2322-3010

@article{ 10.5120/2322-3010,
author = { Pawan Jindal, Amit Kumar, Shishir Kumar },
title = { Dynamic version of Traveling Salesman Problem },
journal = { International Journal of Computer Applications },
issue_date = { April 2011 },
volume = { 19 },
number = { 1 },
month = { April },
year = { 2011 },
issn = { 0975-8887 },
pages = { 37-46 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume19/number1/2322-3010/ },
doi = { 10.5120/2322-3010 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:05:54.443938+05:30
%A Pawan Jindal
%A Amit Kumar
%A Shishir Kumar
%T Dynamic version of Traveling Salesman Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 19
%N 1
%P 37-46
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In the classical version of Traveling salesman problem, the targets which have to be visited are stationary but in real life there are large numbers of instances where the targets are in motion. In this paper, Moving target TSP with resupply is being studied and new algorithm is designed for moving target TSP with resupply when all targets are moving away from the origin with positive constant velocity and the goal is to minimize the total intercepting time taken by the salesman. An algorithm is also designed When all targets are moving towards the origin with the positive constant velocity in a straight line and a single salesman (moving with the constant velocity) has to intercept these targets in a particular way with the constraint that after intercepting every target, salesman must come back to the origin for resupply and the goal is to minimize the total intercepting time taken by the salesman.

References
  1. C.S. Helving, Gabriel, and Alex Zelikovsky, The Moving-Target Traveling Salesman Problem, Journal of Algorithm, 2003, pp. 153-174.
  2. M. Hammar and B.J. Nilsson, Approximation Results for Kinetic Variants of TSP, International Colloquium on Automata, Languages, and Programming, 1999, in: Lecture Notes in Comput. Sci., Vol. 1644, 1999, pp. 392-401.
  3. E. Horowitz and S. Sahni, "Fundamental of Computer Algorithms", Computer Science Press, 1982.
  4. T. Cormen, C. Leiserson and R. Rivest, "Introduction to Algorithms", MIT Press, 1991.
  5. A.V. Aho, J.E. Hopcroft and J.D. Ullman, "The Design and Analysis of Computer Algorithms", Addison-Wesley, 1974.
  6. A.V. Aho, J.E. Hopcroft and J.D. Ullman, "Data Structures and Algorithms", Addison-Wesley,1984.
  7. U. Manber, "Introduction to Algorithms: A Creative approach", Addison-Wesley, 1989
  8. G. Tel, "Introduction to Distributed Algorithms" Cambridge Univ. Press 1995.
  9. G- Brassard, and P. Bratley, "Algorithmics: Theory and Practice", Prentice-Hall, 1988.
  10. E.M. Reingold, J. Nievergelt and N. Deo, "Combinatorial Algorithms: Theory and Practice", Prentice-Hall, 1977.
  11. N. Wirth, "Algorithms and Data Structures" Prentice Hall, 1986.
  12. A. Blum, S. Chawla, D. R. Karger, T. Lane, A. Meyerson and M. Minko, “Approximation Algorithms for Orienteering and Discounted-Reward TSP," SIAM Journal on Computing, vol. 37, no. 2, pp. 653-670, 2007.
Index Terms

Computer Science
Information Sciences

Keywords

Algorithm Traveling salesman problem Moving target traveling salesman problem with resupply

Powered by PhDFocusTM