环形路网上带有服务时长的在线TSP问题

为了提高快递揽件的时效性,需要对快递车辆进行有效调度。针对环形路网上服务时长以及需求无法预知的揽件问题,本文提出了以服务总时间尽可能短为目标的环形路网上带有服务时长的在线旅行商问题。用在线算法分析了此问题竞争比的下界,设计了两个在线算法并分析了各自的竞争比,结果表明服务时长可以改善在线车的性能。最后通过简单算例对两个算法进行说明,本文研究结论可以为环形路网上的快递车辆实时调度提供指导。

Online TSP Problem with Service Time on the Ring Road Network

In order to improve the timeliness of courier services, it is necessary to dispatch the express vehicles effectively. In order to solve the problem of service time and unpredictable demand on the ring road network,this paper proposes an online traveling salesman problem with service time on the ring road network with the aim of providing the total service time which should be as short as possible. The lower bound of competition ratio of this problem is analyzed by the online algorithm,two online algorithms are designed and their respective competition ratio is analyzed,and the results show that the service time can improve the performance of the online vehicle. At last, the two algorithms are illustrated by a simple example. The conclusions of this paper can provide guidance for the real-time scheduling of express vehicles on the ring road network.