基于预知信息的占线Nomadic TSP问题

被引：12

作者：

温新刚 ^{[1
,2
]}

徐寅峰 ^{[1
,2
]}

丁黎黎 ^{[3
]}

机构：

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

[2] 西安交通大学智能网络与网络安全教育部重点实验室

[3] 山东科技大学经济管理学院

来源：

系统工程理论与实践 | 2013年 / 33卷 / 11期

关键词：

旅行商问题; 预知信息; 占线路径选择; 竞争分析;

D O I：

暂无

中图分类号：

O242.1 [数学模拟];

学科分类号：

070102 ;

摘要：

自然灾害的频繁发生使得应急减灾倍受关注,尤其有效的应急救援车辆调度对应急减灾非常重要.针对受灾点被提前获知但是不能立即接受救援服务的情形,通过将受灾点(需求)的揭露时间和释放时间引入Nomadic TSP模型中构建了预知信息的占线Nomadic TSP问题,并分别给出了问题的下界,直线网络结构下的ENO-dd算法,和一般网络结构下的GTR-dd算法,并对算法进行了竞争性能分析.结果表明两个算法随着预知信息的增多会有明显改进.更为一般的预知信息结构以及最优的算法设计是下一步研究的方向.

引用

页码：2845 / 2851

页数：7

共 8 条

[1]

A logistics model for emergency supply of critical items in the aftermath of a disaster[J] . Yen-Hung Lin,Rajan Batta,Peter A. Rogerson,Alan Blatt,Marie Flanigan. Socio-Economic Planning Sciences . 2011 (4)

[2]

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)

[3] Routing for relief efforts [J].

Campbell, Ann Melissa ;

Vandenbussche, Dieter ;

Hermann, William .

TRANSPORTATION SCIENCE, 2008, 42 (02) :127-145

[4]

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

[5]

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

[6] 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

[7] AMORTIZED EFFICIENCY OF LIST UPDATE AND PAGING RULES [J].

SLEATOR, DD ;

TARJAN, RE .

COMMUNICATIONS OF THE ACM, 1985, 28 (02) :202-208

[8]

Stochastic vehiclerouting problem for large-scale emergencies .2 Shen,Z.H,Dessouky,M,Ordoez,F. Technical Report 2005 -06,Department of Industrial and Systems Engineering,University of Southern California . 2005

← 1 →