摘要
针对城市快递揽件服务过程中,需求事先无法预知并且每个需求服务时长不确定的情形,提出具有服务时长的在线TSP问题.分别在一般网络图上和直线上证明了此问题的竞争比下界进而在一般网络上给出PAH-ST算法,在直线上给出PQR-ST算法,并对算法进行了竞争性能分析.本文提出模型是在线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.
出处
《系统工程理论与实践》
EI
CSSCI
CSCD
北大核心
2015年第11期2832-2839,共8页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(61221063)
长江学者和创新团队发展计划(IRT1173)
关键词
旅行商问题
服务时长
在线算法
竞争比
traveling salesman problem
service time
online algorithm
competitive ratio
