预知信息和有限运载能力下应急车辆路径选择问题

由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了人们的广泛重视.针对应急物资车辆装载能力有限和受灾点被提前获知但是不能马上被服务的情形,提出了具有预知信息的在线配额旅行商(quota TSP)问题,分析了该问题的下界,针对受灾点仅在正半轴上的情形设计了MLIB算法和SW算法,对于一般网络设计了Greedy算法,分别分析了三种算法的竞争性能.结果表明算法的竞争性能会随着预知信息的增加而得到改善.

The emergency vehicle routing problem with capacity constraint and advanced information

Due to the frequent occurrence of natural disasters, routing of the emergency vehicles after disaster is gaining extensive attention. This paper considers the situation that emergency vehicle has finite capacity and the affected points can be informed in advance but can't be served immediately, and introduces disclosure date and release date into quota TSP model with advanced information, and gives the lower bound. When metric space is positive half-line, MLIB algorithm and SW algorithm are presented. For general metric space, greedy algorithm is presented, competitive analysis is given for these three algorithms respectively. The results show that with more advanced information, the performance of the three algorithms will be better.