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

Online TSP Problem with Service Time on the Ring Road Network

作　　者：樊相宇[1] 林小果 武小平[3] FAN Xiang-yu;LIN Xiao-guo;WU Xiao-ping(Postal Research Institute,Xi’an University of Posts and Telecommunications,Xi’an 710061,China;College of Economic and Management,Xi’an University of Posts and Telecommunications,Xi’an 710061,China;Modern Postal College,Xi’an University of Posts and Telecommunications,Xi’an 710061,China)

机构地区：[1]西安邮电大学邮政研究院,陕西西安710061 [2]西安邮电大学经济与管理学院,陕西西安710061 [3]西安邮电大学现代邮政学院,陕西西安710061

出　　处：《运筹与管理》2020年第6期139-144,共6页Operations Research and Management Science

基　　金：不确定视角下快递企业末端配送优化策略研究-以西安市为例(18JK0705);基于网络分区的物流配送碳足迹优化研究(2019JM-369);城市快递网络抗毁性研究—以西安市为例(XDWL1906)。

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

关 键 词：快递揽件 旅行商问题 服务时长 在线方法 竞争比 

分 类 号：F224.9[经济管理—国民经济]