Abstract: Due to the frequent occurrence of natural disasters, routing of the emergency vehicles after disaster is gaining extensive attention, and emergency vehicles transporting emergency materials to affected points as soon as possible seem very important. This paper considers the situation that the emergency vehicle has finite capacity and the emergency vehicle is nomadic. We analyze online quota nomadic TSP. We give the lower bounds of the problem, when metric space is positive half-line, and WTAIB algorithm is presented. For general metric space, WSB algorithm is presented, and competitive analysis is given for these two algorithms respectively.

Key words: quota traveling salesman problem, online algorithm, competitive analysis

摘要： 由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了社会的广泛重视,而应急车辆尽快地将应急物资送到受灾点显得尤为重要。针对应急车辆装载物资能力有限和应急车辆不必返回出发点的情形,提出了带有配额的在线Nomadic旅行商问题。分析了该问题在正半轴和一般网络上的下界,针对受灾点仅在正半轴上的情形设计了WTAIB算法,针对受灾点在一般网络上设计了WSB算法,并进一步分析了两个算法的竞争性能。

关键词: 配额旅行商问题, 在线算法, 竞争性分析