（模式识别与智能系统专业论文）灾害应急救助物资调度系统研究.pdf

摘耍 摘要 2 0 世纪9 0 年代以来中国进入新的灾害多发期，每年自然灾害的直接经济损 失有明显增大趋势，自然灾害已经严重威胁了我国经济的可持续发展。在自然灾 害发生以后，救灾是最急迫的减灾措施。在救灾过程中，紧急救援物资的及时到 达，可以很大程度上减轻自然灾害造成的损失，甚至能挽救很多宝贵的生命。但 救灾物资往往是有限的，一个物资储备仓库通常无法满足灾害发生地对紧急救援 物资的迫切需求。因此，需要研究出一个较优的物资调度方案以满足灾害发生地 对应急物资的数量和时限的要求，为救灾工作提供支持。在国家减灾委“环境与 灾害监测预报小卫星星座减灾应用系统工程项目”以及国家科技支撑计划子课题 “灾害应急决策支持与远程会商协同技术研究 ( 2 0 0 8 b a k 4 9 8 0 5 ) 的支持下， 本文围绕该课题的核心内容一自然灾害应急救助相关的物资调度活动开展深入 研究。 本文在介绍有无运力限制的单物资调度模型及有运力限制的多物资调度模 型的基础上，描述了一种满足连续应急物资消耗的多出救点、多物资应急调度算 法，设计了一个从灾害发生地到各物资储备仓库最短路径的求解方法，并给出了 从各物资储备仓库调度物资到灾害发生地的优化调度方案，最后给出了实例分 析，验证了陔方法的可行性。 在灾害发生地对应急救灾物资的需求确定后，制定应急物资配送计划实际上 就是制定车辆调度计划，车辆调度包括所需要调度的车辆的数量和其行驶路线。 在救灾行动进行当中，车辆必须在一个给定的时间点之前把物资送到灾害发生 地。本文在对车辆路径问题的一般模型和求解算法的研究基础上，重点研究了自 然灾害应急救助物资调度带时间窗的车辆路径规划问题。 物资调度环境的复杂化直接导致了物资调度决策过程的复杂化，引入地理信 息系统相关的技术可以较好的改善物资调度系统决策的可视化、效率和可靠性这 三个方面的性能。本文围绕基于g i s 技术的物资调度系统优化方法开展深入研 究，并设计了一个基于g i s 的物资调度系统，该系统实现了本文所述的物资调 度的相关算法，经反复测试，系统的功能正确、性能稳定，达到实际应用要求。 关键词：物资调度最短路径车辆路径问题地理信息系统 a 8 s t r a c t ab s t r a c t s i n c et h e19 9 0 s ，c h i n ah a se n t e r e dan e wp e r i o do ft h ed i s a s t e r - p r o n e i tw o u l d b e c o m eat r e n dt h a tt h ed i r e c te c o n o m i cl o s so fn a t u r a ld i s a s t e r sp e ry e a rh a s o b v i o u s l yi n c r e a s e d n a t u r a ld i s a s t e r sh a sb e e nas e r i o u st h r e a tt ot h es u s t a i n a b l e d e v e l o p m e n to fc h i n a se c o n o m y a f t e rt h eo c c u r r e n c eo fn a t u r a ld i s a s t e r s ，r e s c u ei s t h em o s tu r g e n tm i t i g a t i o nm e a s u r e s d u r i n gt h ep r o c e s so fr e s c u e ，i ft h ee m e r g e n c y r e l i e fs u p p l i e s w o u l da r r i v ei nt i m e ，c a l ll a r g e l yr e d u c et h el o s s e sc a u s e db yn a t u r a l d i s a s t e r sw o u l dh a v eb e e nd e c r e a s e d ，s o m e t i m e si tc o u l de v e ns a v em a n yp r e c i o u s l i v e s h o w e v e r , r e l i e fs u p p l i e sa r ef r e q u e n t l yl i m i t e d ，s ot h em a t e r i a lr e s e r v e di no n e w a r e h o u s ei su s u a l l yu n a b l et om e e te m e r g e n c yd i s a s t e rr e l i e fs u p p l i e so ft h eu r g e n t n e e d sf o r t h ep l a c ew h e r et h ed i s a s t e ro c c u r s t h e r e f o r e ，i ti sn e c e s s a r yt oc o m eu p w i t hab e t t e rs c h e d u l i n go fm a t e r i a l s ，w h i c hc a l lm e e tt h en e e d so fd i s a s t e re m e r g e n c y s u p p l i e si nt h er e q u i r e m e n t so ft h eq u a n t i t ya n dt i m el i m i t u n d e rt h es u p p o r to f t h e e n v i r o n m e n ta n dd i s a s t e rm o n i t o r i n ga n d f o r e c a s t i n ga p p l i c a t i o no fs m a l l s a t e l l i t e sf o rd i s a s t e rr e d u c t i o ns y s t e m p r o j e c to ft h en a t i o n a ld i s a s t e rr e d u c t i o n d e p a r t m e n ta n dt h es u b p r o je c t “r e s e a r c ho nd i s a s t e re m e r g e n c yd e c i s i o n - m a k i n g s u p p o r ta n dr e m o t ec o n s u l t a t i o nt e c h n o l o g y ( 2 0 0 8 b a k 4 9 8 0 5 ) o ft h en a t i o n a l s c i e n c ea n dt e c h n o l o g ys u p p o r t i n gp l a no fc h h a a , t h em a t e r i a ld i s p a t c h i n ga c t i v i t y , w h i c hi sr e l a t e dt ot h ee m e r g e n c yr e l i e ff o rn a t u r a ld i s a s t e r s ，i st ob ef u r t h e rs t u d i e d t h e s i n g l e m a t e r i a ld i s p a t c h i n g m o d e lw i t h w i t h o u t t r a n s p o r tc a p a c i t y r e s t r i c t i o n sa n dm u l t i - m a t e r i a ld i s p a t c h i n gm o d e lw i t ht r a n s p o r tc a p a c i t yr e s t r i c t i o n s a r ei n t r o d u c e d o nt h eb a s i s ，t h ea l g o r i t h mo fam u l t i - d e p o ta n dm u l t i m a t e r i a l d i s p a t c h i n gm o d e l ，i sg i v e nt om e e tt h ec o n t i n u o u sc o n s u m p t i o no ft h ee m e r g e n c y m a t e r i a l s as o l u t i o ni sd e s i g n e dt os o l v et h es h o r t e s tp a t hp r o b l e mb e t w e e nt h ep l a c e w h e r ed i s a s t e r so c c u r sa n dt h e m a t e r i a lr e s e r v ew a r e h o u s e a tt h es a m et i m et h e o p t i m i z a t i o nd i s p a t c h i n gs c h e m ei sa l s og i v e n u l t i m a t l y , a ne x a m p l ei su t i l i z e dt o v e r i f yt h ef e a s i b i l i t yo ft h ea l g o r i t h m ，a f t e rt h ee m e r g e n c ym a t e r i a lo ft h ep l a c ew h e r et h ed i s a s t e ro c c u r si sf i x e d ，t h e d e v e l o p m e n to fe m e r g e n c y m a t e r i a l sd i s t r i b u t i o np l a ni si nf a c tt od e v e l o pt h ev e h i c l e r o u t i n gp l a n t h ev e h i c l es c h e d u l i n gi n c l u d e st w op r o b l e m s ，h o wt o d e t e r m i n et h e n u m b e ro fn e c e s s a r yv e h i c l e sa n dt h e i rt r a v e l i n gr o u t e s d u r i n gt h ed i s a s t e rr e l i e f p r o c e s s i n g ，t h ev e h i c l em u s tc o m p l e t ei t st a s kt h a ti st ot r a n s p o r tt h em a t e r i a l st ot h e p l a c ew h e r et h ed i s a s t e ro c c u r si nag i v e nt i m e b a s e do nt h er e s e a r c ho ft h em o d e l i i a n dt h es o l u t i o no ft h eg e n e r a lv e h i c l er o u t i n gp r o b l e m ，t h ev e h i c l er o u t i n gp r o b l e m w i t ht i m ew i n d o w s ，w h i c hi st h em o s ta p p r o p r i a t ev e h i c l er o u t i n gp r o b l e mf o rt h e m a t e r i a ld i s p a t c h i n go f t h en a t u r a ld i s a s t e r s e m e r g e n c yr e l i e f , i sm a i n l ys t u d i e d t h ec o m p l e x i t yo ft h em a t e r i a ld i s p a t c h i n ge n v i r o n m e n td i r e c t l yr e s u l t si nt h e c o m p l e x i t yo ft h ed e c i s i o n m a k i n gp r o c e s sf o rm a t e r i a ld i s p a t c h i n g t h ei n t r o d u c t i o n o ft h eg e o g r a p h i ci n f o r m a t i o ns y s t e mt e c h n o l o g y , c a ni m p r o v et h r e ep e r f o r m a n c e so f t h ed e c i s i o nf o rm a t e r i a ld i s p a t c h i n gs y s t e m ：v i s u a l i z a t i o n ，e f f i c i e n c ya n dr e l i a b i l i t y i nt h i sp a p e r t h eo p t i m i z a t i o nm e t h o df o rm a t e r i a ld i s p a t c h i n gs y s t e mb a s e do ng i s t e c h n o l o g yi sd i s c u s s e di nd e p t h f i n a l l y , ag i s - b a s e dm a t e r i a ld i s p a t c h i n gs y s t e mi s r e a l i z e d t h es y s t e mr e a l i z e dt h e r e l a t e di d e a so ft h em a t e r i a ld i s p a t c h i n gt h a t d e s c r i b e di nt h ea r t i c l e t h er e p e a t e dt e s t i n gs h o w st h a tt h es y s t e mm e e t st h en e e do f c o r r e c t n e s sa n ds t a b i l i t yf o r t h ep r a c t i c a la p p l i c a t ! o n k e yw o r d s ：m a t e r i a ld i s p a t c h i n g ，t h e s h o r t e s tp a t h ，t h ev e h i c l er o u t i n gp r o b l e m ， g e o g r a p h i ci n f o r m a t i o ns y s t e m i i i 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 吣t 譬 作者签名：缒 1 年川日 第1 章绪论 1 1 选题的背景和意义 1 1 1 选题的背景 第1 章绪论 自然灾害是一种给人类生存带来危害或损害人类现有生活环境的自然现象， 包括洪涝、干旱灾害，台风、冰雹、雪、沙尘暴等气象灾害，火山、地震灾害， 山体崩塌、滑坡、泥石流等地质灾害，风暴潮、海啸等海洋灾害，森林草原火灾 和重大生物灾害等自然灾害。 我国是世界上自然灾害最严重的国家之一，我国自然灾害的特点主要体现在 以下四个方面： 灾害种类多 我国的自然灾害种类众多，覆盖了包括洪涝灾害、气象灾害、地震灾害、地 质灾害、海洋灾害、农业生物灾害和森林草原火灾等在内的全部的七大类自然灾 害( 佚名，1 9 9 4 ) 。 分布地域广 我国幅员辽阔导致各地自然地理环境各异，全国各地自然灾害的种类和受到 自然灾害的威胁程度都不同，有些省市会集中发生某种特定类型的自然灾害，有 些省市则可能同时面对多种自然灾害。 发生频率高 我国自然灾害发生频率非常高，特别是在夏秋季节的时候，洪涝和台风等灾 害尤为集中。仅2 0 0 6 一年民政部启动国家级自然灾害应急响应的次数就达四十 次之多。 造成损失重 上述我国自然灾害种类多、地域广、频率高的三大特点，导致我国每年的因 灾直接经济损失和间接经济损失都极为严重。近几年来，在最严重的情况下受灾 人口接近5 亿，紧急转移安置人口1 5 0 0 万，直接经济损失高达2 0 0 0 亿元。 根据民政部2 0 0 7 年年初的统计报表显示，自1 9 9 7 年至2 0 0 6 年间，我国平 均每年因各种自然灾害所造成的直接经济损失高达2 0 1 1 7 9 亿元，约相当于流失 了我国国民生产总值2 的财产。1 9 9 7 年至2 0 0 6 年十年间我国的自然灾害及经 济损失情况具体如表1 1 所示： 第1 章绪论 表1 11 9 9 7 2 0 0 6 年全国自然灾害及经济损失情况 泌 死亡人紧急转移安农作物受灾农作物绝收倒塌房屋( 万直接经济损 口( 人)置人口( 万面积( 千公面积( 千公间)失( 亿元) 人)顷)顷) 1 9 9 7 壬e3 2 1 25 l l5 4 3 4 06 4 2 02 8 71 9 7 5 1 9 9 8 笠5 5 l l2 0 8 2 45 0 1 4 57 6 1 48 2 1 4 3 0 0 7 4 1 9 9 9 年2 9 6 66 6 4 84 9 9 8 0 ， 6 7 9 71 7 4 51 9 6 2 2 0 0 0 年3 0 1 44 6 7 15 4 6 9 01 0 1 5 0 1 4 7 32 0 4 5 3 2 0 0 1 焦2 5 3 82 1 1 15 2 1 5 08 2 1 59 2 21 9 4 2 2 2 0 0 2 笠2 3 8 44 7 1 84 5 2 1 46 4 3 31 8 9 51 6 3 7 2 2 0 0 3 矩2 2 5 97 0 7 35 4 3 8 6 38 5 4 6 43 4 3 0 1 8 8 4 2 2 0 0 4 生2 2 5 05 6 3 33 7 1 0 64 3 6 0 01 5 5 01 6 0 2 3 2 0 0 5 芷2 4 7 5 1 5 7 0 3 3 8 8 1 8 24 5 9 7 42 2 6 42 0 4 2 1 2 0 0 6 生2 3 7 61 3 3 1 54 1 0 9 l5 4 0 91 4 8 12 0 2 0 2 我国幅员辽阔，全国各地经济发展不平衡，农村市场信息基础建设水平不一 ( 郭作玉，2 0 0 8 ) ，许多地方灾害发生时信息不通达导致灾害损失变相增大。据 统计表明：2 0 世纪9 0 年代以来，我国年均受灾人口近四亿人，农作物受灾面积 近五千多万公顷，因灾倒塌房屋约五百万间，紧急转移安置人口也至少有四百万 人，直接经济损失超过千亿元，灾害损失情况比八十年代严重得多。2 0 世纪9 0 年代以来，尤其是最近几年以来，中国进入新的灾害多发期，新的重大灾害事件 不断出现，我国每年自然灾害的直接经济损失有明显增大趋势，几乎每年的直接 经济损失均要超过两千亿人民币。并且自然灾害损失随着国民经济持续的高速发 展、生产规模的不断扩大和社会财富的逐渐积累，有愈演愈烈的趋势。截至2 0 0 6 年1 1 月3 0 同，2 0 0 6 年全年全国各类自然灾害共造成了2 3 7 6 人死亡，失踪5 6 8 人，紧急转移安置1 3 3 1 5 万人，倒塌房屋1 4 8 1 万间，因灾直接经济损失2 0 2 0 2 亿元。灾害发生地分布在全国十六个省份，国家减灾委、民政部根据灾情，紧急 启动救灾应急响应共四十次，应急时间达到1 3 3 天，其中仅三级响应就启动了八 次，三级响应时间多达二十二天。 综上所述，自然灾害已经严重威胁了我国经济的可持续发展，如果不注意减 轻自然灾害损失，就会影响全面建设小康社会战略目标的实现。为了保障社会经 济建设和可持续发展，必须采取综合措施，增强减灾能力，减灾已经成为了维护 国家安全和社会稳定的重要工作之一。如何解决好发展中的减灾问题，加强减灾 领域的科技水平和能力建设，一直是国家减灾部门所面l 临的首要问题。经国务院 批准，从2 0 0 9 年起，我国将每年的5 月1 2 日定为全国“防灾减灾日”，今年5 月7 日至5 月1 3 日为全国防灾减灾周。国家设立“防灾减灾日”，既体现了国家 对防灾减灾工作的高度重视，也是落实科学发展观，推进经济社会平稳发展，构 2 第1 章绪论 建和谐社会的重要举措。 在自然灾害突发事件发生以后，救灾是最急迫的减灾措施。进行紧急救助时 需要调用大量的救灾物资。在救灾过程中，紧急救援物资的及时到达，可以很大 程度上减轻自然灾害造成的损失，甚至能挽救很多宝贵的生命。但救灾物资往往 是有限的，一个物资储备仓库通常无法满足灾害发生地对紧急救援物资的迫切需 求。因此，需要研究得出一个相对较优的物资调度方案，该方案应该能在满足灾 害发生地对物资数量及时限的要求下，尽可能地减少所消耗的物资以及运送物资 所产生的费用。如上所述，灾害应急救助过程中的应急物资调度问题能产生巨大 的社会效益和经济效益。 另一方面，地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，g i s ) 作为地理 学、地图学、测量学、计算机科学等多门学科综合的交叉学科，近年来发展特别 迅速，应用范围也在逐渐扩大。g i s 除了兼备信息系统的各种优点外，还能够进 行相关的空间数据可视化操作，并可以在此基础上进行更为复杂的空间分析，这 些优点对于应急物资调度路径的优化和可视化都非常有意义，因此g i s 技术的 快速发展和广泛应用给应急物资的优化调度技术提供了新的思路。由于传统的物 资调度系统的规划局限于单一的数据处理和表现，缺乏直观性和可视化，而g i s 能够帮助人们将电子表格和数据库中无法看到的数据之间的模式和发展趋势以 图形的形式清晰直观地表现出来，实现数据可视化，并进行地理空间信息的相关 分析，实现地理空间分析与调度模型的集成，从而满足物资调度决策优化的需求。 因此，从某种意义上讲，g i s 是一种决策支持系统，g i s 技术的应用可以给物资 调度优化系统提供一种较优的可视化决策方案( 胡志杰，2 0 0 5 ) 。 正是在这样的背景下，本文选取了一种典型的应急物流一灾害应急救助的物 资调度作为研究的对象，研究了针对各种自然灾害、人为灾害和突发性安全事故 救助相关的物资调度活动。 l 。1 2 选题的意义 我国自然灾害频发，历次地震和洪水等灾害造成了建筑损毁、人员死伤、交 通中断等巨大损失，每年处理应急事件时所花的物流成本巨大。目前，我国的救 灾物流处于分散管理的状态，缺乏整体的规划和统一的指挥和协调部门。因而， 我国在全面推进现代化建设的进程中，迫切需要强有力的灾害应急管理体系，为 发展国家经济和保障人民安全保驾护航。在灾害应急管理中，物流管理是其中非 常重要的一部分，可以为灾区民众的提供切实的物资保障。尽管中国政府及相关 组织有减灾防灾的预案，但目前所支出的物流成本是巨大的。在突发性自然灾害 和人为灾害造成的巨大人员伤亡和财产损失中，由于应急物流造成的损失约占总 3 第1 章绪论 损失的1 5 至2 0 ，如s a r s 造成的损失总额达1 7 6 亿美元，其中应急物流的 损失约3 0 亿美元( 高东椰等，2 0 0 4 ) 。这是因为在灾难发生时，不可避免地需 要大量的救援车辆的派遣，用以完成应急物资调运、发放等。因此，如何建立起 一个救灾应急物资调度系统，把有限的资源规划出一个最佳的调运流程和策略， 以最短的时间、运用相对经济的方式，准确地把救援物资调运到灾区，成为我国 救灾工作研究的一项重要内容。现代物流学科的发展，为解决这一问题提供了良 好的理论基础。所以，研究应急物资调度的问题不仅具有重大的社会意义，而且 具有良好的研究基础。 由于救灾工作具有很强的实效性和重要性，这对救灾物资调度提出了很高的 要求。从“非典”的案例，我们对自然灾害和突发性公共事件对物资调度的需求 可见一斑。如2 0 0 3 年4 月下旬，北京急需十万套医用防护服，但是定单发出后， 只有远在安徽阜阳的外资企业杜邦公司可满足供应，而从阜阳运到北京需要四天 的时间。在当时的情形下，时间就是生命，快速物资调度是惟一选择，因此，北 京市委求助国家民航总局，用了两架专机将7 万套防护服当天运达北京。由此， 我们可以从中体会到物资调度在救灾和应对突发事件中的关键性。 应急物资调度信息量的急剧膨胀和物资调度环境的复杂化造成了物资调度 决策过程的复杂化。引入g i s 技术可以使物资调度系统的决策结果在可视化、 效率和可靠性这三个方面得到较好的改善，具体可以从以下三个方面来阐述： 1 ) 传统物资调度系统只限于单纯的数据处理和表现，引入g i s 技术可以有 效提高决策的直观性和可视化程度，能非常直观地了解具体的决策结果并判断该 结果是否满足要求； 2 ) 由于应急物资调度信息量极大，各种道路网络极其复杂，对于一般的信 息系统来讲，对大量与物资调度相关的空间数据进行高效操作和分析处理实现起 来非常困难，而利用g i s 强大的空间数据处理能力则可以迅速地提高物资调度 决策的效率； 3 ) 应急物资调度的复杂性使得仅依赖于传统的运筹学方法无法得出令人满 意的调度方案，借助g i s 的空间分析功能，能提高决策结果的可靠性，使得调 度结果更符合实际要求。 因此，利用g i s 空间分析相关技术，结合物资调度优化方法，对物资调度 方案中的车辆调度路径选择进行优化，为减灾救灾提供支持，是本文研究的目的 和意义所在。其具体表现在三个方面：一是寻求提高物资调度决策可视化程度的 途径；二是要解决由于海量信息引起空间数据处理能力不足的问题，提高决策的 效率：三是要找到g i s 与物资调度模型更好的结合方法，提高决策的可靠性。 本文根据物资调度的道路网络信息具有较强的空间地域性的特点，探讨将g i s 4 第l 章绪论 技术应用于物资调度路径优化中的技术和方法，以提高应急救助物资调度管理的 可视化程度、决策的科学性和决策的效率。因而本课题研究具有重要的理论意义 和实际意义。 在国家减灾委环境与灾害监测预报小卫星星座减灾应用系统工程项目以及 国家科技支撑计划子课题“灾害应急决策支持与远程会商协同技术研究” ( 2 0 0 8 b a k 4 9 8 0 5 ) 的支持下，本文围绕该课题的核心内容自然灾害应急救助 相关的物资调度活动，深入研究了紧急状态下的物资调度模型以满足灾区救灾物 资调度的需求，结合g i s 可视化显示物资调度的决策结果，为国家防灾和减灾 提供参考，并为增强我国应对突发性自然灾害的应急响应能力和提高我国在减灾 领域的国际地位贡献自己的力量。 1 2 国内外相关研究综述 应急物资调度作为一种典型的应急物流，其研究具有重要的社会意义和应用 价值。针对应急物资调度方案的制定问题，l i n e to z d a m a r 等( 2 0 0 4 ) 研究了应 急情况下的物资运输调度，该研究假定现在和未来一段时间内可供应的物资数量 有限，当前的物资需求已知，将来的物资需求也是可以预测的。设车辆无需回到 物资库存点，车辆的分配命令是一系列的“断点 路线，其目标是在请求的时间 里最大化满足救援中心的需求，该文中模型分解为两个多物品网络流问题，其中 p 1 是线性的，使得需求点的物品满足最大化，p 2 是整数的，使车辆最大可能的 满足p 1 ，可由l a g r a n g e a n 松弛迭代联立求解这两个模型。根据对19 9 9 年土耳其 伊兹米特地震的应用对所提出的模型和算法进行了测试。舢ih a g h a n i 等( 1 9 9 6 ) 将应急物资调度问题描述为有时间窗限制的多物品、多模式网络流问题，该研究 假定可供应的物资和车辆能完全满足需求，目标是最小的运输成本，作者给出了 两种求解方法：基于l a g r a n g e a n 松弛的启发式算法和交互式f i x a n d r u n 启发式 算法，对具体案例的应用结果表明第二种算法更准确和快速。 针对单灾体的物资调度问题，f i e d r i c h 等( 2 0 0 0 ) 探讨了在资源和时间的数 量及质量有限的情况下，如何通过有效利用资源以提高救援质量，使死亡人数最 小，并给出了地震后向多个灾害发生地分配和运输救灾物资的最优计划模型。 k o n s t a n t i n o sgz o g r a f o s 等( 2 0 0 2 ) 研究了一种基于适时决策支持系统的公路网 事故响应模型，其目标是使响应时间最短。j a ey o u n gc h o i ( 2 0 0 3 ) 研究了如何 在路网情况不确定的时候分配有限的资源( 如救护车或其它应急救灾车辆) 将受 伤人员送到医院，其目标是使尽可能多的受伤人员存活下来。 针对选用具体的交通运输方式进行应急救助问题，g u l a y 等( 2 0 0 0 ) 提出了 5 第l 章绪论 一种采用分层多标准方法解决救灾中直升机的调度问题，其目标是在满足需求的 情况下使得派遣的直升机和飞行员数目最少。s y o z ok u b o 等( 2 0 0 3 ) 提出了一个由 一定数量的气垫船组成的灾后急救运输系统，并采用该系统对1 9 9 5 年的神户地 震进行了救援仿真。 多年来，国内外学者对紧急情况下的物资调度问题进行了深入地探讨，作了 许多有意义的研究。对于应急系统的物资调配，许多国内学者都进行了深入的研 究，其中东南大学的刘春林教授( 1 9 9 9 ) 对此类问题研究得比较透彻且全面，但 是他是以时间最短和出救点最少为目标，并没有直接考虑到运输成本的大小。另 外，戴更新、达庆利( 2 0 0 0 ) 根据多应急资源多点出救问题的特点，建立了一种多 资源应急问题数学模型，并通过引入连续可行方案的概念，并求解了该模型。 对于救灾物资的调度问题，刘北林等( 2 0 0 7 ) 建立了以时间最短，成本最小 为目标函数的多目标数学模型，并利用理想点法对此问题进行优化求解，算法简 便且运算结果令人满意，但是对于突发事件为多个发生地的救灾物资调度问题还 需进一步研究。 实际上，关于应急物资调度的研究成果大致可以分为以下两类： 一类是把紧急状态下的物资调度问题转变为对网络最短路的求解问题。因为 应急物资的调度问题最显着的特点表现为时间的紧迫性，所以要求决策者在尽量 短的时间内完成物资调度方案，该方案应使得车辆在尽可能短的时间内到达物资 需求点为其服务。但是现代交通系统是一个十分复杂的网络系统，物资储备仓库 到物资需求点之间往往存在许多复杂的通路，许多路径问题已被证明是n p 完全 问题( n o n d e t e r m i n i s t i cp o l y n o m i a l ，不确定型多项式算法) 。对于这类问题，y a k e o y a m a d a l 把应急问题转变为对网络最短路径的求解，在有容量限制的情况下，李 帮义等将该问题理解为网络流算法问题，在给定限制期的情况下，用赋权图最小 风险路径的选取算法将问题转化为最短路径的变权迭代问题。近期许多其他方法 如遗传算法和模糊算法等，也被用来求解路径问题，其求解效果还比较不错。 另二类则是把应急物资调度问题转变为对应急物资储备仓库的选择问题，也 就是针对多个应急物资储备仓库，在物资数量供求关系的约束下，考虑对应急物 资储备仓库的组合优化问题。对于这种紧急状态下的组合优化问题，何建敏等人 探讨了在连续消耗系统中满足应急物资连续供应的约束条件下，提出以“应急开 始时间最早”为目标的数学模型及其解法，并在此基础上进一步讨论了以“时间 最短”和“应急出救点数目最少 为目标的多目标问题及其算法，其仿真算例及 实际应用的效果比较令人满意。本文主要采用的是第二种方法，即将物资调度实 现的问题转化为对应急物资储备仓库的选择问题。 综上所述，由于应急物资调度研究具有紧迫性且意义重大，学术界和政府部 6 第1 章绪论 门对研究的广度和深度都不断加大，国内外对应急物资调度的模型及实现算法都 进行了相应的研究。但是，对实际中需要的有多种应急物资需求且需要从多个物 资储备仓库派送物资的调度问题研究较少，本文将在现有救灾物流研究的基础 上，借鉴应急物资调度模型研究的成果，对物资调度所需的车辆调度算法进行研 究，开发出一个能实际应用的基于g i s 的应急物资调度系统。 1 3 本文研究的方法和内容 1 3 1 本文研究的方法 本文中所用到的具体的理论和方法如下： 现代物流学：现代物流学的主要就是运用系统的观点，结合信息技术对物流 中涉及的各个环节进行统一规划和管理。物流学的研究对象是整个物流系统，包 括物流系统的输入、输出、转换、反馈、影响和干扰等等。本文所研究的救灾物 资调度系统也是物流系统的一种，它具备一般物流系统的基本特征，本文关于物 资调度的研究大量运用了现代物流学的先进思想和技术。 数学规划t 数学规划是运筹学的一个重要分支，它研究的内容包括线性规划、 非线性规划、整数规划、目标规划和动态规划等等，本文主要应用的是线性规划 和多目标规划，对应急条件下仅以时间最短为目标和考虑多目标的情况分别建立 其物资调度模型。 组件式g i s ：组件式g i s ( c o m g i s ) 是面向对象技术和组件式软件在g i s 软件开发中的应用。c o m g i s 的基本思想是把g i s 的各大功能模块划分几个控件， 每个控件完成不同的功能。各个g i s 控件之间，以及g i s 控件与其他非g i s 控 件之间，可以方便地通过可视化的软件开发工具集成起来，形成最终的g i s 应 用( 刘仁义等，2 0 0 6 ) 。本文主要应用的是采用c o m o l s 开发技术，嵌入通用的 开发环境( 如v i s u a lc + + ) 中实现g i s 功能，可视化显示物资调度的运送路线。 1 3 2 本文研究的内容 我国属于自然灾害频发的国家，每年为救灾所进行的物流活动花费了大量的 社会财富，其中有些是必要的，有些却是可以节省的。本文从我国自然灾害应急 救助和应对突发性公共事件对物资调度的需求出发，指出了研究应急物资调度的 必要性和重要性。本文主要所研究的是应急物资调度过程中，最关键的一个阶段 一应急物资调度及其车辆调度优化问题。本文以应急物资调度环境为背景，在对 车辆调度算法进行研究的基础上，结合应急物资调度的实际特点，结合g i s ，寻 7 第1 章绪论 求解决该问题的优化调度模型，并在此基础上编制程序，开发出一个基王g i s 的灾害应急救助物资调度系统。 1 4 章节安排 第l 章，介绍了灾害应急救助物资优化调度的研究背景和意义，重点指出了 国内外相关研究的现状，给出了本文主要的研究方法和内容。 第2 章，介绍了相关的物资调度算法，在此基础上提出了一种改进的多物资、 多出救点的应急物资调度算法，并结合一个实例分析了该算法。 第3 章，分析了应急物资调度的决策过程，讨论了自然灾害应急物资调度决 策中最典型也是最重要的问题一车辆路径问题。介绍了一般车辆路径问题的数学 模型及求解算法，构建了针对应急物资调度的带时间窗的车辆路径问题的模型。 第4 章，针对基于g i s 技术的物资调度系统优化方法进行探讨，具体说明 了g i s 在应急物资调度系统决策中的巨大作用，以及灾害应急物资调度系统的 地理要素及特点，并研究了应急物资调度路网的g i s 模型的建立方法。 第5 章，设计并实现了一个灾害应急救助的物资调度系统，详细说明了系统 的开发平台、开发流程、关键技术，在此基础上给出了系统的测试结果。 第6 章，全文总结及有待深入研究的工作。 8 第2 章应急物资调度算法 第2 章应急物资调度算法 在自然灾害或其他突发性事件发生以后，需要调用大量的救灾物资进行紧急 救援，对于这种应急物资调度问题，最大的特点就是时间的紧迫性，时间效益远 远高于经济效益，但是物资储备仓库的应急救援物资通常是有限的，无法从同一 仓库及时有效地调度足够的物资到灾害发生地。因此，需要研究得出一个相对较 优的物资调度方案，该方案应该能在满足灾害发生地对物资数量及时限的要求 下，尽可能地减少所消耗的物资以及运送物资所产生的费用，这对于我们的生产 生活意义非常重大，也正是应急物资调度问题所要研究解决的重点。因此本章将 详细讨论应急物资调度的模型以及具体的调度算法。 2 1 单物资调度模型 由于灾害应急救助的特殊性，应急物资调度与普通的物资调度区别较大。应 急物资调度不是以总的物流费用成本最低作为唯一的决策目标，而是优先考虑调 度的时效性，在满足灾害发生地对物资需求的时间限制的情况下，以物流费用作 为第二决策目标。并且自然灾害发生后当地的道路可能被破坏，物资需求也可能 因为某一突然事件的发生而突变，因此应急物资调度的可变因素较多，需要动态 地研究相应的物资调度模型( 王杏，2 0 0 7 ) 。本节将研究应急条件下单物资、单 一运输方式下的物资调度模型，包括无运力限制和有运力限制的情况。 2 1 1无运力限制的调度时间最短的单物资调度模型 发生自然灾害或其它突发性事件时，需要进行大量的物资调度，在物资调度 过程中，对急需物资的需求明确后，最通常的应急调度思路就是让最近的物资储 备仓库进行应急物资供应，这种情况下只需研究物资运输的路径问题即可，目前 已有较多国内外学者针对路径问题对应急物资调度系统进行了深入研究( n o b u o s a n n o m i y ae t c ，1 9 9 6 ) ( t a k e oy a m a de t c ，1 9 9 6 ) ( j a c q u e sr e n a u de t c ，1 9 9 6 ) 。然 而在重特大灾害发生时，仅动用一个物资储备仓库往往不能完全满足灾害发生地 的应急物资需求。于是便提出了多个物资储备仓库进行物资供应的组合优化问 题。由于灾害应急救助的特殊性，时间最短成为了应急调度的第一目标，在实际 的应急物资调度中，往往规定一个物资应急调度的时间限制，在限制期内完成的 调度方案才是有效的，若应急调度时间超过限制期，则这种物资调度方案肯定是 无效的。 9 第2 章应急物资调度算法 无运力限制的调度时间最短的单物资调度问题描述如下： 设4 ，a ”a 。为m 个物资储备仓库( 可出救点) ，s 为灾害发生地，即应 急物资需求点，只( p o ) 为仓库4 ( f = l ，2 ，m ) 的应急物资储备量，p 为s 地对 应急物资的需求量，且满足y p p 。设从物资储备仓库a i 到灾害发生地s 所 公 需要的时间为，l ( o ) ，f _ 1 ，2 ，m ；t ( t o ) 为应急状态下给定的应急物资调 度时间的限制期。由于超过限制期的调度方案无法满足灾害应急救助的需求，所 以要求给出一个应急物资调度方案，在满足限制期的条件下使得调度时间最短。 设万为任意选择应急物资储备仓库的调度，其中4 ，a ：，a 。为所选的应急物资 储备仓库，l if 2 ，t k 为相应仓库的应急调度时间，丑，罡，最为相应的应急物资 贮存量，其中1 ，2 ，k 为l ，2 ，m 的一个子排列。对某个调度方案7 ， 其应急物资的调度时间记为丁仿) ，该应急物资调度时间是指从应急物资调度指 令下达开始，到物资调度完成之间所经历的时间。称调度方案万可行是指该调度 k 方案中各物资储备仓库的应急物资储备量满足：p 。 百 在此假设各物资储备仓库的应急调度是同步进行的，则对于这种多出救点参 与应急救助的组合调度方案万，应急调度时间应满足丁( 石1 = m a xf 。，即最后一 i = l 一2 t 个到达灾害发生地的车辆所经历的时间为整个应急物资调度方案完成的时间。根 据应急物资调度的目标和约束条件，可以构造一个以应急调度时间最短为唯一目 标的单物资调度的数学模型： m i n r ( 7 r ) = m i n 川m 五a x 。t , 舭 善牡尸， q j h t 若记q 为所有调度方案的集合，所有可行调度方案的集合记为q ，则显然有 dc q ，上述模型可以简化为：m 肥i n 。t ( n ) 。因此只要得出一个满足约束条件的 方案万，能使得丁( 石) = m i n 丁( q ) ，则该方案万为最合适的物资调度方案。 2 1 2 有运力限制的调度时间