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

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