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.
Key words
quota TSP /
advanced information /
online algorithm
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
References
[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_en}}
Footnotes
{{custom_fn.content}}
PDF(441 KB)
