Premium
Online traveling salesman problems with service flexibility
Author(s) -
Jaillet Patrick,
Lu Xin
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20454
Subject(s) - competitive analysis , travelling salesman problem , online algorithm , metric (unit) , computer science , time complexity , metric space , space (punctuation) , flexibility (engineering) , line (geometry) , pspace , mathematical optimization , mathematics , algorithm , upper and lower bounds , discrete mathematics , computational complexity theory , mathematical analysis , operations management , statistics , geometry , economics , operating system
The traveling salesman problem is a well‐known combinatorial optimization problem. We are concerned here with online versions of this problem defined on metric spaces. One novel aspect in this article is the introduction of a sound theoretical model to incorporate “yes‐no” decisions on which requests to serve, together with an online strategy to visit the accepted requests. To do so, we assume that there is a penalty for not serving a request. Requests for visit of points in the metric space are revealed over time to a server, initially at a given origin, who must decide in an online fashion which requests to serve to minimize the time to serve all accepted requests plus the sum of the penalties associated with the rejected requests. We first look at the special case of the non‐negative real line. After providing a polynomial time algorithm for the offline version of the problem, we propose and prove the optimality of a 2‐competitive polynomial time online algorithm based on reoptimization approaches. We also consider the impact of advanced information (lookahead) on this optimal competitive ratio. We then consider the generalizations of these results to the case of the real line. We show that the previous algorithm can be extended to an optimal 2‐competitive online algorithm. Finally we consider the case of a general metric space and propose an original c ‐competitive online algorithm, where \documentclass{article}\usepackage{mathrsfs, amsmath, amsfonts, amssymb}\pagestyle{empty}\begin{document} $c = \sqrt{({17+5})}/{4} \approx 2.28$ \end{document} . We also give a polynomial‐time (1.5ρ + 1) ‐competitive online algorithm which uses a polynomial‐time ρ ‐approximation for the offline problem. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011