We study the online traveling salesman problem on a semi-line, where a server (salesman) starts from the origin point of the semi-line and moves either at unit speed or ‘waits’ (with zero speed) at somewhere, so as to serve the requests that are released online along the semi-line. The objective is to minimize the time for serving all requests. We distinguish the homing version and the nomadic version by whether the server is required to return to the origin point or not. When no information of the requests is disclosed, the best online algorithms for two versions are \(\frac{3}{2}\) - and 2-competitive respectively. When the locations of all requests are known in advance, the online algorithm for the homing version could be 1-competitive. We present a \(\frac{10}{7}\) -competitive algorithm for the nomadic version, improving the previous \(\frac{13}{9}\) -competitive algorithm. We also improve the lower bound of this version from \(\frac{4}{3}\) to 1.356. If machine-learned predictions are adopted for the locations, then we introduce learning-augmented algorithms that have competitive ratios of \(\min \{1+\eta , 2\}\) and \(\min \{\frac{3}{2}+\frac{\eta }{2}, 2\}\) for the homing version and the nomadic version respectively, where \(\eta \ge 0\) denotes the prediction error, i.e., the maximum deviation between the predicted location and the real location normalized by the length of the shortest path serving all requests.
