由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了人们的广泛重视.针对应急物资车辆装载能力有限和受灾点被提前获知但是不能马上被服务的情形,提出了具有预知信息的在线配额旅行商(quota TSP)问题,分析了该问题的下界,针对受灾点仅在正半轴上的情形设计了MLIB算法和SW算法,对于一般网络设计了Greedy算法, 分别分析了三种算法的竞争性能.结果表明算法的竞争性能会随着预知信息的增加而得到改善.
Abstract
Due to the frequent occurrence of natural disasters, routing of the emergency vehicles after disaster is gaining extensive attention. This paper considers the situation that emergency vehicle has finite capacity and the affected points can be informed in advance but can't be served immediately, and introduces disclosure date and release date into quota TSP model with advanced information, and gives the lower bound. When metric space is positive half-line, MLIB algorithm and SW algorithm are presented. For general metric space, greedy algorithm is presented, competitive analysis is given for these three algorithms respectively. The results show that with more advanced information, the performance of the three algorithms will be better.
关键词
配额旅行商问题 /
预知信息 /
在线算法
{{custom_keyword}} /
Key words
quota TSP /
advanced information /
online algorithm
{{custom_keyword}} /
中图分类号：
C935
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Jotshi A, Gong Q, Batta R. Dispatching and routing of emergency vehicles in disaster mitigation using data fusion[J]. Socio-Economic Planning Sciences, 2009, 43: 1-24.
[2] 石彪, 池宏,祁明亮,等. 应急物资运输的两阶段车辆调度模型[J].系统工程, 2012, 30(7): 105-111.Shi Biao, Chi Hong, Qi Mingliang, et al. A two-stage vehicle scheduling model of transportation of emergency resources[J]. Systems Engineering, 2012, 30(7): 105-111.
[3] 詹沙磊,刘南. 基于灾情信息更新的应急物资配送多目标随机规划模型[J]. 系统工程理论与实践, 2013, 33(1): 159-166. Zhan Shalei, Liu Nan. Multi-objective stochastic programming model for relief allocation based on disaster scenario information updates[J]. Systems Engineering - Theory & Practise, 2013, 33(1): 159-166.
[4] Beamon B M. Humanitarian relief chains: Issues and challenges[C]// 34th International Conference on Computers and Industrial Engineering, San Francisco, 2004. http://faculty.w ashington.edu/benita/sfpaper.pdf.
[5] Ausiello G, Feuerstein E, Leonardi S, et al. Algorithms for the on-line traveling salesman[J]. Algorithmica, 1998, 29(4): 560-581.
[6] Ausiello G, Demange M, Laura L, et al. Algorithms for the on-line quota traveling salesman problem[J]. Information Processing Letters, 2004, 92(2): 89-94.
[7] Jaillet P, Wagner M. Online routing problems: Value of advanced information as improved competitive ratios[J]. Transportation Science, 2006, 40(2): 200-210.
[8] 温新刚,徐寅峰,丁黎黎.基于预知信息的占线Nomadic TSP问题[J].系统工程理论与实践, 2013, 33(1): 1-7. Wen Xingang, Xu Yinfeng, Ding Lili. Online nomadic TSP based on the advanced information[J]. Systems Engineering - Theory & Practice, 2013, 33(1): 1-7.
[9] Borodin A, El-Yaniv R. Online computation and competitive analysis[M]. Cambridge: Cambridge University Press, 1998.
[10] Psaraftis H, Solomon M, Magnanti T, et al. Routing and scheduling on a shoreline with release times[J]. Management Science, 1990, 36(2): 212-223.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金(61221063);长江学者和创新团队发展计划(No.IRT1173)
{{custom_fund}}
PDF(441 KB)
