关键词: 旅行商问题, 线性惩罚, 在线算法, 需求点, 应急车辆

Abstract: For delivering relief supplies to affected area by emergency vehicles as soon as possible after the natural disasters,aiming at the problem that the penalty would be generated caused by the affected area's request could not be served immediately,the online Traveling Salesman Problem (TSP) with linear penalty was introduced.Through designing the worst sequence,the circumstance that no deterministic or randomized online algorithms under general metric space could achieve constant competitive ratio was proved.While on truncated line segment,lower bound was presented,CM algorithm was designed,and optimum of this algorithm was prove when the maximal penalty value of a single request was greater than 8.

Key words: traveling salesman problem, linear penalty, online algorithm, request, emergency vehicles