针对现实快递服务网络结构上的转向限制及待服务需求出现后不能立即接受服务的特征，将预知时间引入到在线旅行商问题中，提出以服务总时间最小为目标的转向限制网络中基于预知时间的快递车辆在线揽件路径选择问题.在半路径上提出了WBR-dd策略，在路径上提出了REP-dd略，在一般网络上提出了PAH-dd策略，证明了上述在线策略的竞争比，分析了该问题竞争比的下界.结果表明预知信息越多，在线算法将获得更优的竞争性能.
Abstract
Based on the turn restriction of network and the situation in which requests could not be serviced until its release time, this paper introduces the advanced information into online traveler salesman problem, proposes the online routing of express pick-up vehicles with advanced information on the turn restriction network. WBR-dd algorithm, REP-dd algorithm and PAH-dd algorithm are presented on half-path, path and general metric space. Competitive analysis is given respectively. The lower bounds are given. The results indicate that the more advanced information, the better online algorithms perform.
关键词
在线旅行商问题 /
预知信息 /
转向限制网络 /
在线算法 /
竞争比
{{custom_keyword}} /
Key words
online travelling salesman problem /
advanced information /
turn restriction network /
online algorithm /
competitive ratio
{{custom_keyword}} /
中图分类号：
C935
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Ausiello G, Feuerstein E, Leonardi S, et al. Algorithms for the on-line travelling salesman[J]. Algorithmica, 2001, 29(4):560-581.
[2] Lipmann M. The online traveling salesman problem on the line[D]. Amsterdam, Netherland:University of Amsterdam, 1999.
[3] Blom M, Krumke S O, De-Paepe W E, et al. The online TSP against fair adversaries[J]. Informations Journal on Computing, 2001, 13(2):138-148.
[4] Allulli L, Ausiello G, Bonifaci V, et al. On the power of lookahead in on-line server routing problems[J]. Theoretical Computer Science, 2008, 408(2):116-128.
[5] Jaillet P, Wagner M. Online routing problems:Value of advanced information as improved competitive ratios[J]. Transportation Science, 2006, 40(2):200-210.
[6] Jaillet P, Lu X. Online traveling salesman problems with service flexibility[J]. Networks, 2011, 58(2):137-146.
[7] Jaillet P, Lu X. Online traveling salesman problems with rejection options[J]. Networks, 2014, 64(2):84-95.
[8] 温新刚, 徐寅峰, 丁黎黎. 基于预知信息的占线Nomadic TSP问题[J]. 系统工程理论与实践, 2013, 33(11):2845-2851.Wen X G, Xu Y F, Ding L L. Online nomadic TSP based on advanced information[J]. Systems Engineering-Theory & Practice, 2013, 33(11):2845-2851.
[9] Wen X G, Xu Y F, Zhang H L. Online traveling salesman problem with deadline and advanced information[J]. Computers & Industrial Engineering, 2012, 63(4):1048-1053.
[10] 马军平,徐寅峰,温新刚,等. 带有预知信息的在线Homing ATSP问题[J]. 系统工程理论与实践, 2015, 35(2):381-387. Ma J P, Xu Y F, Wen X G, et al. Online homing asymmetric TSP with advanced information[J]. Systems Engineering-Theory & Practice, 2015, 35(2):381-387.
[11] 吴腾宇,徐寅峰,温新刚. 预知信息和有限运载能力下应急车辆路径选择问题[J]. 系统工程理论与实践, 2015, 35(5):1224-1229. Wu T Y, Xu Y F, Wen X G. The emergency vehicle routing problem with capacity constraint and advanced information[J]. Systems Engineering-Theory & Practice, 2015, 35(5):1224-1229.
[12] 廉文琪,徐寅峰. 基于预知信息和实时服务选择的在线TSP问题[J]. 系统工程理论与实践, 2016, 36(1):86-93. Lian W Q, Xu Y F. The online traveling salesman problem with real-time rejection options and advanced information[J]. Systems Engineering-Theory & Practice, 2016, 36(1):86-93.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金（71601152）；中国博士后科学基金（2016M592811）；陕西省自然科学基础研究计划（2015JM7372）；重庆市社会科学规划博士项目（2016BS085）
{{custom_fund}}
PDF(802 KB)
