基于最短完成时间和动态可挽救性的应急车辆调度问题研究
|
摘要
突发的灾难性事件近期在世界范围内的频繁发生,给社会、经济等带来了严重的破坏和影响,造成了生命和财产的巨大损失。如何应对突发事件,是很多国家和社会组织都会面对的强有力的挑战。应急资源调度在处置突发事件中有着不可替代的重要作用。
鉴于此,本文选择研究运输应急资源的车辆调度问题,重点研究了基于最短完成时间和动态可挽救性的应急车辆调度模型及算法等问题。文章介绍了应急物流和车辆调度的相关知识以及国内外相关研究现状,强调了最短完成时间和动态可挽救性在应急车辆调度中的重要作用,并给出了应急车辆调度问题的模型和算法,并用实例进行了模型验证。在当前的研究中,大部分模型都无法准确体现应急救援时间第一的原则,也不能指导性的体现受灾地点的具体情况。鉴于此,本文首先提出了基于最短完成时间和最大可挽救性的双目标规划模型,使得模型的设计更加符合实际,模型中的双目标函数既体现了救援时间的重要性,又能较准确的体现受灾地点的实际情况。另一个方面,本文通过对模型和算法的研究解决了现有VRP算法中规模过大,计算运行时间过长的缺点,主要的工作有以下几个方面：
(1)对应急物流以及车辆优化调度等论文相关内容作了大体的介绍；根据前人的研究讨论了目前急需解决的一些问题,说明了本项研究的研究意义。
(2)结合相关研究人员的经验,总结出了基于最短完成时间的应急车辆调度问题。并结合前人的研究成果,建立了数学规划模型,给出了一个简洁易行的两阶段式算法。该算法有效地将物资储备中心与受灾地点构成的网络通过聚类分析,按照车辆的容量约束划分成若干子网络,使得每一个车辆对应一个子网络,然后就可以对子网络进行车辆路径安排,从而将车辆调度问题转化成寻找子网络各个节点的最优顺序问题,该算法有效地解决了一般算法中计算时间过长的缺点,具有较强的应用背景。
(3)结合第二章的研究,主要从寻找最优顺序方面考虑,讨论了在子网络中含有禁止时间窗的车辆路径安排问题。建立了以最快完成时间为目标函数的带禁止时间窗的应急车辆路径安排模型,并在禁忌搜索算法的基础上设计了该模型的求解算法,运用算例验证了这种方法的有效性。该模型将禁止时间窗应用于封闭式VRP问题中,具有实际应用价值。
(4)主要讨论了基于动态可挽救性的应急车辆调度问题。创造性的建立了以最短完成时间和最大可挽救性为目标的应急车辆调度模型。该模型将可挽救性的相关理论嵌入到规划模型之中,使得模型能结合受灾地点的具体情况提供相应的决策方案,并对基本的禁忌搜索算法进行了改进,给出了该模型的求解算法,并用算例分析了算法的有效性。
Emergency always brings serious destruction and bad influence. The various country governments have paid attention to the emergency management (EM). How to manage emergency is one of powerful challenges the whole world is facing.
For the vital role of the emergency resources in EM, this thesis mainly discussed the vehicle scheduling and the vehicle routing of the emergency resources dispatching problem with salvability and the shortest finished time. Vehicle routing problem is introduced shortly and the content of emergency resource management is analyzed. Secondly, on the basis of emergency resources allocation research, optimization models and the efficient algorithms of the emergency dispatching under time constraints are raised and a case is given. There are some results in this thesis:
(1) After an overview of recent researches of the emergency vehicle routing problem, some existence questions are found and the practical significance of the vehicle scheduling and the vehicle routing of the emergency resources dispatching problem with salvability and the shortest finished time is explained.
(2) After learning the experience of other researchers, summarize the vehicle scheduling and the vehicle routing of the emergency resources dispatching problem with salvability and the shortest finished time. on the basis of other people's research, optimization models and the efficient algorithms of this models are raised according to vehicle capacity constraints, This algorithm can be divided into several sub-networks by cluster analysis, so that each vehicle corresponds to a sub-network, then you can study the network traffic path arrangement about the vehicle scheduling problem, in order to find the optimal sequence of questions.
(3) Considering the vehicle routing problem of forbidding time windows, a optimization model under forbidding time windows in the emergency environment is given and the tabu search algorithm is discussed. Finally, the efficiency of the algorithm is given.
(4) Vehicle routing problem in emergency management with salvability is studied and the model of this problem is raised. Improvement tabu search algorithm is proposed and efficiency of algorithm is given through example.
鉴于此,本文选择研究运输应急资源的车辆调度问题,重点研究了基于最短完成时间和动态可挽救性的应急车辆调度模型及算法等问题。文章介绍了应急物流和车辆调度的相关知识以及国内外相关研究现状,强调了最短完成时间和动态可挽救性在应急车辆调度中的重要作用,并给出了应急车辆调度问题的模型和算法,并用实例进行了模型验证。在当前的研究中,大部分模型都无法准确体现应急救援时间第一的原则,也不能指导性的体现受灾地点的具体情况。鉴于此,本文首先提出了基于最短完成时间和最大可挽救性的双目标规划模型,使得模型的设计更加符合实际,模型中的双目标函数既体现了救援时间的重要性,又能较准确的体现受灾地点的实际情况。另一个方面,本文通过对模型和算法的研究解决了现有VRP算法中规模过大,计算运行时间过长的缺点,主要的工作有以下几个方面：
(1)对应急物流以及车辆优化调度等论文相关内容作了大体的介绍；根据前人的研究讨论了目前急需解决的一些问题,说明了本项研究的研究意义。
(2)结合相关研究人员的经验,总结出了基于最短完成时间的应急车辆调度问题。并结合前人的研究成果,建立了数学规划模型,给出了一个简洁易行的两阶段式算法。该算法有效地将物资储备中心与受灾地点构成的网络通过聚类分析,按照车辆的容量约束划分成若干子网络,使得每一个车辆对应一个子网络,然后就可以对子网络进行车辆路径安排,从而将车辆调度问题转化成寻找子网络各个节点的最优顺序问题,该算法有效地解决了一般算法中计算时间过长的缺点,具有较强的应用背景。
(3)结合第二章的研究,主要从寻找最优顺序方面考虑,讨论了在子网络中含有禁止时间窗的车辆路径安排问题。建立了以最快完成时间为目标函数的带禁止时间窗的应急车辆路径安排模型,并在禁忌搜索算法的基础上设计了该模型的求解算法,运用算例验证了这种方法的有效性。该模型将禁止时间窗应用于封闭式VRP问题中,具有实际应用价值。
(4)主要讨论了基于动态可挽救性的应急车辆调度问题。创造性的建立了以最短完成时间和最大可挽救性为目标的应急车辆调度模型。该模型将可挽救性的相关理论嵌入到规划模型之中,使得模型能结合受灾地点的具体情况提供相应的决策方案,并对基本的禁忌搜索算法进行了改进,给出了该模型的求解算法,并用算例分析了算法的有效性。
Emergency always brings serious destruction and bad influence. The various country governments have paid attention to the emergency management (EM). How to manage emergency is one of powerful challenges the whole world is facing.
For the vital role of the emergency resources in EM, this thesis mainly discussed the vehicle scheduling and the vehicle routing of the emergency resources dispatching problem with salvability and the shortest finished time. Vehicle routing problem is introduced shortly and the content of emergency resource management is analyzed. Secondly, on the basis of emergency resources allocation research, optimization models and the efficient algorithms of the emergency dispatching under time constraints are raised and a case is given. There are some results in this thesis:
(1) After an overview of recent researches of the emergency vehicle routing problem, some existence questions are found and the practical significance of the vehicle scheduling and the vehicle routing of the emergency resources dispatching problem with salvability and the shortest finished time is explained.
(2) After learning the experience of other researchers, summarize the vehicle scheduling and the vehicle routing of the emergency resources dispatching problem with salvability and the shortest finished time. on the basis of other people's research, optimization models and the efficient algorithms of this models are raised according to vehicle capacity constraints, This algorithm can be divided into several sub-networks by cluster analysis, so that each vehicle corresponds to a sub-network, then you can study the network traffic path arrangement about the vehicle scheduling problem, in order to find the optimal sequence of questions.
(3) Considering the vehicle routing problem of forbidding time windows, a optimization model under forbidding time windows in the emergency environment is given and the tabu search algorithm is discussed. Finally, the efficiency of the algorithm is given.
(4) Vehicle routing problem in emergency management with salvability is studied and the model of this problem is raised. Improvement tabu search algorithm is proposed and efficiency of algorithm is given through example.
引文
[1]赵新光,龚卫锋,张燕.应急物流的保障机制[J].中国物流与采购,2003,16(3)：24-27.
[2]高东椰,刘新华.浅论应急物流[J].中国物流与采购.2004,12(2)：22-23.
[3]Rathi,A.K.R.L.Church and R.S.Solanki. Allocating Resource to Support a Multi-commodity Flow with Time Windows [J]. Logistics and Transportation Review 1993. vol.28,167-188.
[4]Equi,L G. Gallo,S.Marziale,A.Weintraub. A Combined Transportation and Seheduling Problem[J]. working Paper, Pisa University, Pisa, Italy, vol.8,49-57.
[5]王文亮.应急物流中的信息系统建设[J].中国物流与采购,2003,24.30-34.
[6]卢安文等.紧急情况下的物流配送模型[J].西南石油学院学报.2003,25(1)：80-83.
[7]刘春林等.一类应急物资调度的优化模型研究[J].中国管理科学.2001,11(3)：29-36
[8]戴更新.多资源组合应急调度问题的研究[J].系统工程理论与实践.2000,12(9)：52-55.
[9]傅克俊.基于突发事件的物流配送过程建模构想[J].物流技术.2005,9(10)：263-266.
[10]Laporte G, Mercure H, Nobert Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem[J]. Networks,1986,16:33-46.
[11]Christofides N, Mingozzi A, Toth P. Exact algorithms for the vehicle routing problem based on spanning the shortest path relaxation[J]. Mathematical Programming,1981,20:255-282.
[12]Fisher M L. Optimal solution of vehicle routing problems using minimum k-trees[J].Operations Research,1994,42 (4):626-642.
[13]Balinski M, Quandt R. On an integer program for a delivery problem[J]. Operations Research,1962,12:300-304.
[14]Rao M R, Ziont S. Allocation of transportation units to alternative trips A column generation scheme with out2of2kilter sub problems [J]. Operations Research 1968,12:52-63.
[15]Fisher ML, Jaikumar R. A generalized assignment heuristic for vehicle routing[J]. Networks,1981,11:109-124.
[16]Laporte G, Nobert Y, Desrocher M. Optimal routing under capacity and distance restrictions[J]. Operations Research,1985,33:1050-1073.
[17]Clarke G, Wright J W. Scheduling of vehicles from a central depot to a number of delivery points[J].Operations Research,1964,12:568-581.
[18]Paessens H.The saving algorithm for the vehicle routing problem[J]. European Journal of Operational Research,1988,34:336-344.
[19]Gillett B, Miller L. A heuristic algorithm for the vehicle dispatch problem[J]. Operations Research,1974,22:340-349.
[20]Taillard E. Parallel, interative search method for vehicle routing problem[J]. Networks,1993,23:661-673.
[21]Wark P,Holt J. A repeated matching heuristic for the vehicle routing problem[J].Operations Research Socitey,1994,45 (10):1156-1167.
[22]李军.有时间窗的车辆调度问题的网络启发式算法[J].系统工程2006,10,66-71.
[23]樊建华.基于免疫遗传算法的车辆路径优化问题[J].计算机工程与应用,2006,10：210-213.
[24]李大卫.改进的遗传算法在车辆调度问题中的应用[J].系统工程学报,2006,(3)：28-34.
[25]刘云忠,宣慧玉.车辆路径问题的模型及算法研究综述[J].管理工程学报,2005,1：124-128.
[26]Kallehauge B. Formulations and exact algorithms for the vehicle routing problem with time window[J].Computers & Operations Research,2008.
[27]丁秋雷,胡祥培,李永先.求解有时间窗的车辆路径问题的混合蚁群算法[J].系统工程理论与实践,2007,(10).
[28]Osman IH. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem[J].Annals of Operations Research,1993,41
[29]GendreauM, HertzA, Laporte G. A tabu search heuristic for the vehicle routing problem[J]. Management Science,1994,40.
[30]王素云等.两阶段启发式算法在带时间窗的车辆路径问题中的应用[J].200711.114-115.
[3 1]陈安等.现代应急管理理论与方法[M].
[32]车颍涛.时间约束下的应急资源调度模型及算法研究[J].河南大学硕士毕业论文.7-16.
[33]张斌.应急物流配送车辆调度优化研究[J].大连海事大学硕士毕业论文..
[34]上官艳秋.突发事件应急管理中的“可挽救性”度量评价模型研究[J].中国软科学,2009(9),165-173.
[35]刘兴贺国光.车辆路径问题的禁忌搜索算法研究[J].计算机工程与应用2007,43(24),179-181.
[36]郎茂祥,胡思继.车辆路径问题的禁忌搜索算法研究[J].管理工程学报,2004,18(1).
[37]何正文.等基于禁止时间窗的应急物资调度车辆路径问题[J].运筹与管理,2009.4.2-6
[2]高东椰,刘新华.浅论应急物流[J].中国物流与采购.2004,12(2)：22-23.
[3]Rathi,A.K.R.L.Church and R.S.Solanki. Allocating Resource to Support a Multi-commodity Flow with Time Windows [J]. Logistics and Transportation Review 1993. vol.28,167-188.
[4]Equi,L G. Gallo,S.Marziale,A.Weintraub. A Combined Transportation and Seheduling Problem[J]. working Paper, Pisa University, Pisa, Italy, vol.8,49-57.
[5]王文亮.应急物流中的信息系统建设[J].中国物流与采购,2003,24.30-34.
[6]卢安文等.紧急情况下的物流配送模型[J].西南石油学院学报.2003,25(1)：80-83.
[7]刘春林等.一类应急物资调度的优化模型研究[J].中国管理科学.2001,11(3)：29-36
[8]戴更新.多资源组合应急调度问题的研究[J].系统工程理论与实践.2000,12(9)：52-55.
[9]傅克俊.基于突发事件的物流配送过程建模构想[J].物流技术.2005,9(10)：263-266.
[10]Laporte G, Mercure H, Nobert Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem[J]. Networks,1986,16:33-46.
[11]Christofides N, Mingozzi A, Toth P. Exact algorithms for the vehicle routing problem based on spanning the shortest path relaxation[J]. Mathematical Programming,1981,20:255-282.
[12]Fisher M L. Optimal solution of vehicle routing problems using minimum k-trees[J].Operations Research,1994,42 (4):626-642.
[13]Balinski M, Quandt R. On an integer program for a delivery problem[J]. Operations Research,1962,12:300-304.
[14]Rao M R, Ziont S. Allocation of transportation units to alternative trips A column generation scheme with out2of2kilter sub problems [J]. Operations Research 1968,12:52-63.
[15]Fisher ML, Jaikumar R. A generalized assignment heuristic for vehicle routing[J]. Networks,1981,11:109-124.
[16]Laporte G, Nobert Y, Desrocher M. Optimal routing under capacity and distance restrictions[J]. Operations Research,1985,33:1050-1073.
[17]Clarke G, Wright J W. Scheduling of vehicles from a central depot to a number of delivery points[J].Operations Research,1964,12:568-581.
[18]Paessens H.The saving algorithm for the vehicle routing problem[J]. European Journal of Operational Research,1988,34:336-344.
[19]Gillett B, Miller L. A heuristic algorithm for the vehicle dispatch problem[J]. Operations Research,1974,22:340-349.
[20]Taillard E. Parallel, interative search method for vehicle routing problem[J]. Networks,1993,23:661-673.
[21]Wark P,Holt J. A repeated matching heuristic for the vehicle routing problem[J].Operations Research Socitey,1994,45 (10):1156-1167.
[22]李军.有时间窗的车辆调度问题的网络启发式算法[J].系统工程2006,10,66-71.
[23]樊建华.基于免疫遗传算法的车辆路径优化问题[J].计算机工程与应用,2006,10：210-213.
[24]李大卫.改进的遗传算法在车辆调度问题中的应用[J].系统工程学报,2006,(3)：28-34.
[25]刘云忠,宣慧玉.车辆路径问题的模型及算法研究综述[J].管理工程学报,2005,1：124-128.
[26]Kallehauge B. Formulations and exact algorithms for the vehicle routing problem with time window[J].Computers & Operations Research,2008.
[27]丁秋雷,胡祥培,李永先.求解有时间窗的车辆路径问题的混合蚁群算法[J].系统工程理论与实践,2007,(10).
[28]Osman IH. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem[J].Annals of Operations Research,1993,41
[29]GendreauM, HertzA, Laporte G. A tabu search heuristic for the vehicle routing problem[J]. Management Science,1994,40.
[30]王素云等.两阶段启发式算法在带时间窗的车辆路径问题中的应用[J].200711.114-115.
[3 1]陈安等.现代应急管理理论与方法[M].
[32]车颍涛.时间约束下的应急资源调度模型及算法研究[J].河南大学硕士毕业论文.7-16.
[33]张斌.应急物流配送车辆调度优化研究[J].大连海事大学硕士毕业论文..
[34]上官艳秋.突发事件应急管理中的“可挽救性”度量评价模型研究[J].中国软科学,2009(9),165-173.
[35]刘兴贺国光.车辆路径问题的禁忌搜索算法研究[J].计算机工程与应用2007,43(24),179-181.
[36]郎茂祥,胡思继.车辆路径问题的禁忌搜索算法研究[J].管理工程学报,2004,18(1).
[37]何正文.等基于禁止时间窗的应急物资调度车辆路径问题[J].运筹与管理,2009.4.2-6