Abstract
In this paper, we consider the Online Traveling Salesperson Problem (OLTSP) where the locations of the requests are known in advance, but not their arrival times. We study both the open variant, in which the algorithm is not required to return to the origin when all the requests are served, as well as the closed variant, in which the algorithm has to return to the origin after serving all the requests. Our aim is to measure the impact of the extra knowledge of the locations on the competitiveness of the problem. We present an online 3/2-competitive algorithm for the general case and a matching lower bound for both the open and the closed variant. Then, we focus on some interesting metric spaces (ring, star, semi-line), providing both lower bounds and polynomial time online algorithms for the problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
We note that our 3/2-competitive algorithm for general metric spaces also works for discrete metric spaces (where you do not continuously travel from one point to another, but travel in a discrete manner from point x at time t to point y at time \(t+d(x,y)\)).
- 2.
Indeed, if \(OPT\) does not do this we can easily transform it into another optimal solution (with the same order of serving requests) that acts like this.
- 3.
Strictly speaking, if \(x \ge L\), all requests and thus [0, x] would be released. We will ignore this and only use half-open intervals to avoid technicalities.
References
Allulli, L., Ausiello, G., Laura, L.: On the power of lookahead in on-line vehicle routing problems. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 728–736. Springer, Heidelberg (2005). https://doi.org/10.1007/11533719_74
Ascheuer, N., Grötschel, M., Krumke, S.O., Rambau, J.: Combinatorial online optimization. In: Kall, P., Lüthi, H.J. (eds.) Operations Research Proceedings 1998, pp. 21–37. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-642-58409-1_2
Ausiello, G., Bonifaci, V., Laura, L.: The on-line asymmetric traveling salesman problem. J. Discrete Algorithms 6(2), 290–298 (2008)
Ausiello, G., Demange, M., Laura, L., Paschos, V.T.: Algorithms for the on-line quota traveling salesman problem. Inf. Process. Lett. 92(2), 89–94 (2004)
Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M.: Algorithms for the on-line travelling salesman. Algorithmica 29, 560–581 (2001)
Bampis, E., Escoffier, B., Hahn, N., Xefteris, M.: Online TSP with known locations. CoRR abs/2210.14722 (2022)
Bernardini, G., Lindermayr, A., Marchetti-Spaccamela, A., Megow, N., Stougie, L., Sweering, M.: A universal error measure for input predictions applied to online graph problems. In: Oh, A.H., Agarwal, A., Belgrave, D., Cho, K. (eds.) Advances in Neural Information Processing Systems (2022)
Bjelde, A., et al.: Tight bounds for online TSP on the line. ACM Trans. Algorithms 17(1), 3:1–3:58 (2021)
Blom, M., Krumke, S.O., de Paepe, W., Stougie, L.: The online TSP against fair adversaries. INFORMS J. Comput. 13(2), 138–148 (2001)
Chen, P., Demaine, E.D., Liao, C., Wei, H.: Waiting is not easy but worth it: the online TSP on the line revisited. CoRR abs/1907.00317 (2019)
Gouleakis, T., Lakis, K., Shahkarami, G.: Learning-augmented algorithms for online TSP on the line. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence (2023, to appear). CoRR abs/2206.00655
Hu, H., Wei, H., Li, M., Chung, K., Liao, C.: Online TSP with predictions. CoRR abs/2206.15364 (2022)
Jaillet, P., Wagner, M.: Online routing problems: value of advanced information as improved competitive ratios. Transp. Sci. 40, 200–210 (2006)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24777-7
Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley Series in Discrete Mathematics & Optimization (1991)
Psaraftis, H.N., Solomon, M.M., Magnanti, T.L., Kim, T.U.: Routing and scheduling on a shoreline with release times. Manage. Sci. 36(2), 212–223 (1990)
Acknowledgments
This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bampis, E., Escoffier, B., Hahn, N., Xefteris, M. (2023). Online TSP with Known Locations. In: Morin, P., Suri, S. (eds) Algorithms and Data Structures. WADS 2023. Lecture Notes in Computer Science, vol 14079. Springer, Cham. https://doi.org/10.1007/978-3-031-38906-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-38906-1_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-38905-4
Online ISBN: 978-3-031-38906-1
eBook Packages: Computer ScienceComputer Science (R0)