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

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