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

被引：10

作者：

吴腾宇 ^{[1
,2
,3
]}

余海燕 ^{[4
]}

机构：

[1] 重庆邮电大学经济管理学院

[2] 西安交通大学管理学院

[3] 西安交通大学机械制造系统工程国家重点实验室

[4] 重庆交通大学管理学院

来源：

计算机集成制造系统 | 2017年 / 23卷 / 04期

关键词：

旅行商问题; 线性惩罚; 在线算法; 需求点; 应急车辆;

D O I：

10.13196/j.cims.2017.04.027

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

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

引用

页码：913 / 920

页数：8

共 8 条

[1]

基于预知信息和实时服务选择的在线TSP问题 [J].

廉文琪 ;

徐寅峰 .

系统工程理论与实践, 2016, (01) :86-93

[2]

基于k-中心点法的改进粒子群算法在旅行商问题中的应用 [J].

张旭梅 ;

邱晗光 .

计算机集成制造系统, 2007, (01) :99-104

[3]

Online traveling salesman problem with deadline and advanced information [J].

Wen, Xingang ;

Xu, Yinfeng ;

Zhang, Huili .

COMPUTERS & INDUSTRIAL ENGINEERING, 2012, 63 (04) :1048-1053

[4]

The online Prize-Collecting Traveling Salesman Problem [J].

Ausiello, Giorgio ;

Bonifaci, Vincenzo ;

Laura, Luigi .

INFORMATION PROCESSING LETTERS, 2008, 107 (06) :199-204

[5]

Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines.[J].Ann Melissa Campbell;Barrett W. Thomas.Computers and Operations Research.2008, 4

[6]

On the power of lookahead in on-line server routing problems.[J].Luca Allulli;Giorgio Ausiello;Vincenzo Bonifaci;Luigi Laura.Theoretical Computer Science.2008, 2

[7]

How to whack moles.[J].Sandra Gutiérrez;Sven O. Krumke;Nicole Megow;Tjark Vredeveld.Theoretical Computer Science.2006, 2

[8]

Algorithms for the On-Line Travelling Salesman<Superscript> <Emphasis Type="Italic">1</Emphasis> </Superscript>.[J].G. Ausiello;E. Feuerstein;S. Leonardi;L. Stougie;M. Talamo.Algorithmica.2001, 4

← 1 →