Online traveling salesman problem with deadline and advanced information

We consider the online version of the traveling salesman problem, where instances are not known in advance. Requests are released over time regardless whether the server is en route or not. This problem has been described as online TSP. Current literature about online TSP assumes that each request becomes known at its release time and will always remain active. We model the customers’ waiting psychology and service preparation time into the online TSP with the objective to serve as many requests as possible. More specifically, each request has a disclosure time before accepting service at its release time, and a deadline, which is no bigger than its release time plus the travel time from origin to its position. We give lower bounds for the competitive ratios, online algorithms, and quantify the influence of advanced information on competitive ratios.

► We model the customer waiting psychology into traveling salesman problem.
► Salesman is to serve as many requests as possible before their deadlines.
► Lower bounds and competitive algorithms are given on restricted metric spaces.
► No lower bound on general metric spaces.