带有预知信息的在线Homing ATSP问题

被引：6

作者：

马军平 ^{[1
,2
,3
]}

徐寅峰 ^{[1
,3
]}

温新刚 ^{[1
,3
]}

张惠丽 ^{[1
,3
]}

机构：

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

[2] 西安工业大学经济管理学院

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

来源：

系统工程理论与实践 | 2015年 / 35卷 / 02期

关键词：

旅行商问题; 预知信息; 非对称网络; 在线算法;

D O I：

暂无

中图分类号：

TP393.01 [];

学科分类号：

081201 ; 1201 ;

摘要：

针对快递服务网络结构上的非对称性以及可提前获知待服务需求的位置和释放时间的特征,将预知信息引入可返回原点的非对称TSP问题中,提出以服务总成本最小为目标的带有预知信息的在线Homing ATSP问题.分析了该问题竞争比的下界,并且在一般网络图上设计了SSdd(α)算法和PAH-dd算法,分析了算法各自的竞争比.结果表明在线车采取适时等待策略比采取zealous策略更优;并且预知信息越多,在线算法的竞争性能越优.

引用

页码：381 / 387

页数：7

共 7 条

[1] 基于预知信息的占线Nomadic TSP问题 [J].

温新刚 ;

徐寅峰 ;

丁黎黎 .

系统工程理论与实践, 2013, 33 (11) :2845-2851

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

Wen, Xingang ;

Xu, Yinfeng ;

Zhang, Huili .

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

[3]

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)

[4]

Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses[J] . Jaillet,Patrick,Wagner,Michael R. Operations Research . 2008 (3)

[5]

The on-line asymmetric traveling salesman problem[J] . Giorgio Ausiello,Vincenzo Bonifaci,Luigi Laura. Journal of Discrete Algorithms . 2007 (2)

[6]

Algorithms for the On-Line Travelling Salesman1[J] . G. Ausiello,E. Feuerstein,S. Leonardi,L. Stougie,M. Talamo. Algorithmica . 2001 (4)

[7] The online TSP against fair adversaries [J].

Blom, M ;

Krumke, SO ;

de Paepe, WE ;

Stougie, L .

INFORMS JOURNAL ON COMPUTING, 2001, 13 (02) :138-148

← 1 →