Top > JACIII > WIN Algorithm for Discrete Online TSP

single-jc.php

JACIII Vol.15 No.9 pp. 1199-1202
doi: 10.20965/jaciii.2011.p1199
(2011)

Paper:

Views over last 60 days: 718

WIN Algorithm for Discrete Online TSP

Yonghua Wu*, Guohun Zhu*,**, Huaying Chen***,
and Jucun Qin*

*School of Computer Science and Engineering, Guilin University of Electronic Technology, No.1 Jinji Road, Guilin 541004, China

**Department of Math and Computer, University of Southern Queensland, Toowoomba, QLD, Australia

***Graduate School of Science, Department of Information System, University of Melbourne, Melbourne, Australia

Received:
April 14, 2011
Accepted:
June 15, 2011
Published:
November 20, 2011
Creative Commons License
Keywords:
online TSP, metric TSP, competitive analysis, discrete metric space, Waiting-If-Necessary
Abstract
Traveling Salesman Problem (TSP) which is proved as an NP-Complete problem is solved by many algorithms. In this paper, we propose online TSP which is based on general discrete metric space. A Waiting-If-Necessary (WIN) algorithm is proposed that involves with increasing cost caused by zealous algorithms and unnecessary waiting caused by cautious algorithms. We measure the performance of the WIN algorithm using competitive analysis and found that it is a 2-competitive algorithm. The competitive ratio of theWIN algorithm can be improved by setting parameter T0.
Cite this article as:
Y. Wu, G. Zhu, H. Chen, and J. Qin, “WIN Algorithm for Discrete Online TSP,” J. Adv. Comput. Intell. Intell. Inform., Vol.15 No.9, pp. 1199-1202, 2011.
Data files:
References
  1. [1] G. Laporte, “A concise guide to the Traveling Salesman Problem,” J. of the Operational Research Society, Vol.61, pp. 35-40, 2010.
  2. [2] Y. Wu, G. Zhu, and T. Sang, “On Update Mechanism of Online Traveling Salesman Problems,” 2010 Int. Conf. on Intelligent Computing and Integrated Systems, pp. 53-56, 2010.
  3. [3] K. Zhou et al., “Algorithms for TSP,” Computer Engineering and Applications, Vol.43, No.29, pp. 43-47, 2007.
  4. [4] G. Ausiello et al., “Online Algorithms, Real time, the Virtue of Laziness, and the Power of Clairvoyance,” TAMC, pp. 1-20, 2006.
  5. [5] G. Ausiello et al., “Algorithms for the Online Quota Traveling Salesman Problem,” Information processing Letters, Vol.92, pp. 89-94, 2004.
  6. [6] G. Ausiello, E. Feuerstein, S. Leonardi, et al., “Algorithms for the Online Traveling Salesman,” Algorithmica, Vol.29, pp. 560-581, 2001.
  7. [7] M. Aprea et al., “Discrete Online TSP,” AAIM 2009, LNCS 5564, pp. 29-42, 2009.
  8. [8] V. Bonifaci, “Models and algorithms for online sever routing,” Ph.D. Thesis, Technische Universiteit Eindhoven, 2007.
  9. [9] P. Jaillet and M. R. Wagner, “Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses,” Operations Research, Vol.56, No.3, pp. 745-757, 2008.
  10. [10] V. Bonifaci, “An adversarial queueing model for online sever routing,” Theoretical Computer Science, Vol.381, pp. 280-287, 2007.
  11. [11] V. Bonifaci and L. Stougie, “Online k-Sever Routing Problems,” Theory Comput Syst, Vol.45, pp. 470-485, 2009.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Apr. 19, 2024