带有线性惩罚的在线旅行商问题

来源：计算机集成制造系统杂志2017年第4期北京时间：

作者：吴腾宇,余海燕4

单位：1.重庆邮电大学经济管理学院2.西安交通大学管理学院3.西安交通大学机械制造系统工程国家重点实验室4.重庆交通大学管理学院

摘要：为了在自然灾害之后通过应急车辆尽快地将应急物资送到受灾点,针对每个受灾点在发出需求信号后,不能尽快被应急车辆服务,从而导致受灾点的情形进一步恶化的情形,提出了带有线性惩罚的在线旅行商问题。通过设计最坏序列证明了该问题在一般网络上不存在确定性和随机性的在线算法。针对需求点仅在线段上的情形,分析了问题的下界、设计了推测后再移动策略,并证明了当单个需求点的最大惩罚值大于等于8时,该算法为最优算法。

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

基金资助：重庆市社会科学规划博士基金资助项目(2014BS108,2016BS085);重庆市教委科技基金资助项目(KJ1600525);陕西省自然科学基础研究计划资助项目(2015JM7372);重庆邮电大学文峰创新创业基金资助项目(WF201406)。