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

被引：7

作者：

廉文琪 ^{[1
,2
]}

徐寅峰 ^{[1
,2
]}

机构：

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

[2] 机械制造系统工程国家重点实验室

来源：

系统工程理论与实践 | 2016年 / 01期

关键词：

旅行商问题; 预知信息; 实时服务选择; 在线算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论]; F724.6 [电子贸易、网上贸易]; F719.3 [餐饮业];

学科分类号：

081202 ; 1201 ; 120203 ;

摘要：

现实生活中,提供外送服务的快餐店为了降低成本、提高效率,在接到顾客的订餐信息时,可能会因为距离等因素拒绝一些顾客的送餐要求,而拒绝顾客需求会带来一定的惩罚(如丧失部分客户).针对快餐店选择性提供送餐服务,同时送餐点信息被提前获知但是不能马上被服务的情形,提出了基于预知信息和实时服务选择的在线旅行商问题(traveling salesman problem,TSP).针对需求点在正半轴和直线上的情形分析了问题的下界,并设计了相应的算法,同时分析了每个算法的竞争性能.结果表明,算法的竞争性能会随着预知信息的增加而得到改善.

引用

页码：86 / 93

页数：8

共 9 条

[1] 预知信息和有限运载能力下应急车辆路径选择问题 [J].

吴腾宇 ;

徐寅峰 ;

温新刚 .

系统工程理论与实践, 2015, (05) :1224-1229

[2] 带有预知信息的在线Homing ATSP问题 [J].

马军平 ;

徐寅峰 ;

温新刚 ;

张惠丽 .

系统工程理论与实践, 2015, 35 (02) :381-387

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

温新刚 ;

徐寅峰 ;

丁黎黎 .

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

[4] Online Traveling Salesman Problems with Rejection Options [J].

Jaillet, Patrick ;

Lu, Xin .

NETWORKS, 2014, 64 (02) :84-95

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

Wen, Xingang ;

Xu, Yinfeng ;

Zhang, Huili .

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

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

Ausiello, Giorgio ;

Bonifaci, Vincenzo ;

Laura, Luigi .

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

[7]

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

[8] Algorithms for the on-line Quota Traveling Salesman Problem [J].

Ausiello, G ;

Demange, M ;

Laura, L ;

Paschos, V .

INFORMATION PROCESSING LETTERS, 2004, 92 (02) :89-94

[9]

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

← 1 →