Abstract: To transport emergency supplies to the crisis attacked locations fairly and quickly,aiming at the limited capacity and nomadic vehicle,the online traveling repairman problem with quotas was introduced and solved with online algorithm.Lower bounds of the problem on the positive half-line and general networks were proved.The Blindly Turn Left (BTL) algorithm was designed for metric space of positive half-line,and the inverse leverage algorithm was presented for metric space of general metric space.Then competitive ratio was given for the two algorithms respectively and competitive performance was analyzed.Compared with a paper which studied the online traveling repairman problem,the competitive performance of the inverse leverage algorithm was better.The sensitivity analysis for the scale of disaffected network,the number of disaffected points and the capacity of delivery vehicles was carried out by numerical simulation,and the result showed that the inverse leverage algorithm was more suitable under greater network,capacity of vehicles and disaster point density.

Key words: emergency rescue, online algorithm, competitive analysis, traveling repairman problem

摘要： 为了将应急物资公平且迅速地送往受灾点,本文提出救援车辆装载能力有限且不必返回出发点的在线旅行维修工问题。使用在线算法分析求解,证明了该问题在正半轴网络和一般网络上的下界。分别对正半轴网络上的情形设计了Blindly Turn Left(BTL)算法,对一般网络上的情形设计了逆杠杆算法,给出上述在线算法的竞争比并分析了其竞争性能,与前人研究的在线旅行维修工问题对比发现,逆杠杆算法的竞争性能更优。最后通过数值仿真对受灾网络规模、受灾点数量和配送车辆容量进行敏感性分析,研究得到逆杠杆算法更适用于网络规模、车辆容量和受灾点密度较大的情形。

关键词: 应急救援, 在线算法, 竞争分析, 旅行维修工问题