具有服务时长的在线 TSP 问题.

Based on the situation in which the requests could not be predicted in advance and the service time of each request is uncertain, this paper proposes the online traveling salesman problem with service time. A lower bound and PAH-ST algorithm are presented for general metric space. Moreover, a lower bound and PQR-ST algorithm are presented for real line. Competitive analyses are given to the two algorithms respectively. The model proposed in this paper is the general form of the traveling salesman problem. The conclusion can provide the basis of real-time scheduling for delivery vehicles. [ABSTRACT FROM AUTHOR]