（机械制造及其自动化专业论文）基于动态网络流的舰船人员疏散方法研究.pdf

基于动态网络流的舰船人员疏散方法研究 摘 舰船人员疏散问题因其在船员生命和财产安全等方面的重要意义而受到广泛的关 注。本文基于动态网络流理论研究“不含特殊要求”、“含禁行点禁行区段 、“含必 经点必经区段 以及“含对流”等多种情况下的舰船人员疏散方法。文中忽略个体的行 为，将每个经过良好训练的船员看作具有相同性质的“商品”，将他们有组织的移动看 作是受约束的“流动 。 本文首先对舰船人员疏散问题的特征进行了详尽的分析，并根据该问题需要考虑的 因素将其抽象为动态网络流模型，模型中节点、弧以及它们的属性可以准确且完整地体 现舰船的布局、船员的位置以及船员密度对其行走速度的影响等。然后通过分析目前已 有算法的思想，提出了可以解决不含特殊要求的舰船人员疏散问题的启发式算法。接着 以该算法为基础，分别提出解决“禁行点禁行区段 、“必经点必经区段”和“对流 的方法，并相应地为其设计了启发式算法。本文在一定程度上完善了舰船人员疏散的理 论与方法。 最后，本文采用在v i s u a lc h 中嵌入m a p x 组件的方式对舰船人员疏散系统进行了 开发，该系统运用a c c e s s 数据库存储数据，用户界面友好，实现了疏散路径的计算和 可视化，大大提高了应急方案制定的效率。 关键词：舰船人员疏散；动态网络流；禁行点禁行区段；必经点必经区段；对流 哈尔滨t 程大学硕+ 学位论文 ；i i i i 毫；昌宣昌昌宣昌j 暑暑昌；暑宣；昌；昌；暑；暑暑暑昌暑暑暑暑昌暑昌昌宣昌；暑暑；昌；暑宣i i i 置 a b s t r a c t s h i pe v a c u a t i o np r o b l e mi sw i d e l yc o n c e r n e dd u et oi t ss i g n i f i c a n c ei nc r e w sl i f ea n d p r o p e r t ys e c u r i t y i nt h i sp a p e r ，t h es h i pe v a c u a t i o nm e t h o d si nv a r i o u sc a s e ss u c ha s c o n t a i n i n gn os p e c i f i cr e q u i r e m e n t s ，i n c l u d i n gf o r b i d d e np a s s i n gn o d e s p a t h s ，i n c l u d i n g n e c e s s a r yp a s s i n gn o d e s p a t h s a n d i n c l u d i n gc o n v e c t i o n a r es t u d i e do nt h eb a s i so ft h e d y n a m i cn e t w o r kf l o wt h e o r y t h ei n d i v i d u a lb e h a v i o ri s i g n o r e di n t h i sp a p e r e a c h w e l l t r a i n e dc r e wi sc o n s i d e r e da sah o m o g e n e o u s “c o m m o d i t y ”，a n dt h e i r o r g a n i z e d m o v e m e n ti st r e a t e da sc o n s t r a i n e d “f l o w i n g ” f i r s t l y ，t h ec h a r a c t e r i s t i c so ft h es h i pe v a c u a t i o np r o b l e ma r ea n a l y z e di nd e t a i l t h e p r o b l e mc a n b ea b s t r a c t e di n t oa d y n a m i cn e t w o r kf l o wm o d e la c c o r d i n gt ot h ef a c t o r sw h i c h n e e dt ob et a k e ni n t oc o n s i d e r a t i o n t h en o d e s ，a r c s ，a n dt h e i rp r o p e r t i e si nt h i sm o d e lc a n a c c u r a t e l ya n dc o m p l e t e l yr e f l e c tt h el a y o u to ft h es h i p ，t h ec r e w sl o c a t i o n ，t h ee f f e c to ft h e c r e wd e n s i t y0 1 1t h e i rw a l k i n gs p e e d ，a n ds oo n t h e nah e u r i s t i ca l g o r i t h mw h i c hc a ns o l v e t h es h i pe v a c u a t i o np r o b l e mw i t h o u ts p e c i a lr e q u i r e m e n t si sp r o p o s e dt h r o u g ha n a l y z i n gt h e c u r r e n ta l g o r i t h m s t h o u g h t a f t e rt h a t ，b a s e do nt h i sa l g o r i t h m ，t h em e t h o d so fs o l v i n g “f o r b i d d e np a s s i n gn o d e s p a t h s ”，“n e c e s s a r y p a s s i n gn o d e s p a t h s a n d “c o n v e c t i o n a r e b r o u g h tf o r w a r dr e s p e c t i v e l y ，a n dt h ec o r r e s p o n d i n gh e u r i s t i ca l g o r i t h m sf o rt h e ma r e d e s i g n e d t os o m ee x t e n t ，t h es h i pe v a c u a t i o nt h e o r i e sa n dm e t h o d sa r ei m p r o v e di nt h i s p a p e r i i lt h ee n d ，t h ew a yo fe m b e d d i n gm a p xc o m p o n e n ti n t ov i s u a lc + + i sa d o p t e dt o d e v e l o pt h es h i pe v a c u a t i o ns y s t e m i nt h i ss y s t e m ，a c c e s sd a t a b a s ei su s e dt os t o r et h ed a t a a n dt h es y s t e mp o s s e s s e sau s e r - f r i e n d l yi n t e r f a c e o nt o po ft h a t ，t h e c o m p u t a t i o na n d v i s u a l i z a t i o no fe v a c u a t i o np a t h sa r ec a r r i e do u t t h i sw i l lg r e a t l yi m p r o v et h ee s t a b l i s h m e n t e f f i c i e n c yo fe m e r g e n c yp r o g r a m s k e y w o r d s ：s h i pe v a c u a t i o n ；d y n a m i cn e t w o r kf l o w ；f o r b i d d e np a s s i n gn o d e s l ：i a t h s ；n e c e s s a r y p a s s i n gn o d e s l ：i a t h s ；c o n v e c t i o n 第1 章绪论 1 1 课题的背景及意义 第1 章绪论 近百年来，海难频发。据m s n b c 新闻网报道，造成海难的事故种类很多，大致有 火灾、船舶搁浅、碰撞、触礁、爆炸、船舶失踪以及船舶主机和设备损坏而无法自修以 致船舶失控等。而发生海难事故的原因是多方面的，诸如天气条件、船员技术水平和工 作责任心、船舶技术状态、港口设施和管理水平等。 屡屡发生的海难给人们的生命、财产造成了巨大的损失。首先关注以下如图1 1 所 示的一组船舶失事图片和表1 1 所示的近百年来的海难数据1 。 这些惨不忍睹的图片和触目惊心的数据，无不让人扼腕叹息。可以看到，海难事故 带来的不仅仅是财产方面的严重损失，更可怕的是会让人们付出生命的高昂代价。而且， 如果海难造成了原油溢漏等事件，将会严重污染海洋环境，影响几代人甚至几十代人的 健康。 ( a ) 英国“路两塔尼亚号”被鱼雷击中 ( b ) 英国“羚羊号”爆炸 ( c ) 美国“科尔号”爆炸( d ) “玛丽亚悟梅拉号”发生火灾 图1 1 船舶失事图片 哈尔滨r 程大学硕十学位论文 表1 1 近卣年米的海难数据 时间船舶名称 事故原因造成的后果 1 9 1 2 年4 月泰坦尼克号撞上冰山沉没1 5 1 3 人遇难 1 9 1 4 年5 月皇后号 于圣劳伦斯河沉没1 0 1 2 人丧生 1 9 1 5 年5 月路两塔尼皿号被鱼雷击中沉没1 1 9 8 人葬身海底 1 9 3 3 年大西洋号 被不明原因大火烧毁9 名船员牺牲 1 9 4 0 年6 月兰开斯特里亚号 飞机轰炸约3 5 0 0 人遇难 1 9 4 5 年1 月威廉古斯特洛夫号 被潜艇鱼雷击中约9 0 0 0 人丧生 1 9 4 8 年1 2 月江亚号 撞上水雷；炸弹误炸3 0 0 0 多人遇难 1 9 5 6 年7 月安德烈弧多里哑号 与客船大雾中相撞4 6 人遇难 溢漏原油将当地海岸线 1 9 7 8 年3 月公迪司卡兹号 搁浅并断为两截 几乎全部污染 l1 0 0 万加仑原油溢漏至 1 9 8 9 年3 月 埃克森瓦尔迪兹号撞上岸礁 该水域 1 9 9 4 年9 月爱沙尼哑号沉没 死亡9 1 2 人 2 0 0 0 年8 月库尔斯克号携带的鱼雷发生故障 1 1 8 名艇载人员丧生 2 0 0 0 年1 0 月科尔号恐怖袭击 1 7 名船员遇难 2 0 0 2 年4 月玛丽亚r 梅拉号火灾 2 5 人丧生 2 0 0 2 年9 月乔拉号遭遇暴风雨 1 8 6 3 人死亡 2 0 0 3 年7 月塔斯曼精灵号搁浅 约1 2 4 0 0 吨原油漏进大海 超过5 万加仑燃油溢漏到 2 0 0 7 年1 1 月中远釜山号撞上海湾大桥的桥墩 旧金山湾 2 0 0 8 年6 月群晕公主号 风浪过人导致引擎故障停驶超过8 0 0 人丧生 因此，在舰船遭到意外破坏后，如何在尽量短的时白j 内顺利地完成疏散及救援工作， 以求保障船员的生命及财产安全，已经成为亟待解决的问题。 可以说，紧急疏散计划在灾难管理方面起着决定性的作用雎3 1 ，提供高效的疏散计划 能很大程度地减少灾难管理的风险。在船舶发生事故或遭到严重破坏而必须弃船时，我 们急需高效的产生疏散计划的工具将处于危险中的船员撤离到安全地带p j l ，以达到控制 和减少伤亡人数的目的。当然，当船舶遇到可以通过救援保全部分财产而无须弃船的紧 急情况时，如何保证疏散与救援同时安全进行( 即“对流) 也已经成为当务之急。 2 第1 章绪论 1 2 课题的研究方法 如今，为了能够改善上述严峻的现状，大量的疏散模型和最优化算法纷纷涌现，为 多种类型的紧急自然和人为灾难提供了疏散计划。目前，公认的疏散计划方法有以下三 种脚： ( 1 ) 警报系统 警报系统只是简单地传达可能造成威胁的事件，并且通过大量的媒体通讯工具( 如 电视、广播等) 向受到影响的人员传达疏散的必要性。这种系统可能会在疏散过程中引 发意料之外的后果。例如，1 9 9 2 年当飓风安德鲁到达福罗里达州和路易斯安那州时，受 到影响的人口只是被简单地告知要尽快离开该区域，结果造成了极其严重的高速公路交 通堵塞，导致了极度的混乱峥1 。 ( 2 ) 线性规划方法n 町 这种疏散规划采用网络流和线性规划的方法。运用线性规划方法( 如e v a c n e t i ) 产生最优解，但是它具有呈指数增长的运行时间，因此不能应用到大型运输网络中。 h o p p e 与t a r d o s 。坨1 给出了世界上第一个为疏散问题计算最优结果的多项式算法。然而， 他们的算法中采用了椭球法，具有很高的计算复杂度，因此不具有可执行性。 ( 3 ) 启发式方法 启发式算法可以得到较好的解并降低计算的复杂度，然而现有的单纯启发式算法仅 仅是计算一个源点到与其最近的出口的最短路径，并没有考虑到路径的容量限制、多个 源点或者突发状况对网络结构的影响等。这在疏散人数众多和路径网络比较复杂的情况 下不能产生高效的计划。 本文的研究对象是一类舰船人员疏散问题，具有网络结构庞大且复杂、路径容量有 一定限制、船员的行走速度与人员密度有关等特点。因此，需要设计一种新的启发式方 法以适应上述特点。 另外，对于任何结构( 如楼房、客轮、近海平台、飞机) 或者某个地理区域内的人员 疏散过程，有以下两种基本的建模方法； ( 1 ) 最优化模型体：在最优化模型中，每个被疏散者被看作是单一的、具有相同性 质的“商品 ，个体的行为被忽略。 ( 2 ) 离散事件仿真”羽 离散事件仿真考虑个体的移动和不确定行为，试图真实地表现疏散过程中的决策制 定。这种建模方法并不关注疏散区域内的整体疏散情况，而是着重于对个体行为的研究。 哈尔滨t 程大学硕十学何论文 本文采用最优化模型，因为舰船上训练有素的船员可以被认为是有组织的移动，也 就是说，可以看作是受约束的人“流动 。另外，最优化模型还可以很好地向船员提供 指定的逃生路线，为应急预案的制定提供参考。 综上所述，基本上可以确定本文的研究方法，即基于网络流模型设计有效的启发式 算法解决舰船人员疏散问题。 传统的静态网络流理论是很多年来关注的焦点，它们代表着组合最优化的一个很成 功的领域，发展了深厚的理论和高效的算、法l 例。在静态网络模型中，网络结构( 如节点的 存在性、节点间的连通关系等) 是固定不变的，网络中弧上的参数( 如长度、成本等) 均为 常值，是不随时间变化的。但在实际的舰船人员疏散问题中，某舱室或走廊路段可能突 然遭袭击而被禁行、船员的疏散速度会随着其密度的增大而减小，这些就意味着该问题 的网络流模型中，网络的结构和参数是随时间变化的。所以，静态网络无法反应实际疏 散过程中网络结构和参数与时间有关的特征，这大大影响了静态网络流理论运用于疏散 模型的效果。 可以说，经典的网络流理论已不能解决社会和管理实践中所遇到的一些新问题哪! ， 对更加实际可行的网络模型的需求引起了动态网络流理论的发展。动态网络是传统静态 网络在时间维的扩展b ，在动态网络流模型中，流通过弧不是瞬时而是需要花费时间的， 流可以被耽搁在节点处，网络参数可以随时间变化。因此，动态网络流模型中的参数可 以比静态网络更好地描述舰船人员疏散问题的特点。 然而，虽然动态网络流模型更接近现实，但它的发展远远不及经典的静态网络流模 型。这很大程度上是由于在静态流问题存在高效算法的同时，动态流问题却被证明更难 解决明。那么，本文的难点就在于设计出适用于该动态网络流模型的算法以解决舰船人 员疏散问题。 另外，由于舰船人员疏散问题具有其特殊性，目前针对它的研究还不多。所以，运 用动态网络流理论解决舰船人员疏散问题将是一个引人注目的研究领域。 1 3 课题的国内外研究现状 为了科学、及时并有效地应对各种突发的自然灾害或人为事故，减少生命和财产方 面的损失，国内外学者已经开展了大量卓有成效的研究。 对于应急疏散的研究起步较晚，一般认为开始于二十世纪六十年代伫2 1 。1 9 6 3 年， g i v e n s 1 率先探讨了疏散决策的基本概念和一般框架。此后，越来越多的学者运用不同 4 第l 章绪论 的方法从不同的侧面研究了应急疏散方法。 对疏散方法的研究可以分为微观和宏观两大类，其中微观模型主要考虑被疏散人员 的恐慌心理和行为等对疏散路径选择的影响，典型的微观模型有：元胞自动机模型陬2 ， 社会力模型1 以及概率模型2 7 1 等。本文的研究类型则属于宏观模型扭矧的范畴，即将舰船 上所有的被疏散船员和救援人员都看作有组织地移动，并不考虑他们之间的相互作用 ( 如摩擦力等) 。与微观模型相比，宏观模型可以更加完整地描述整个疏散过程，并且更 加明确地评估疏散方案、指导应急预案的制定。 基于宏观模型的上述优点，很多专家学者将精力倾注到对宏观模型的研究上来。 2 0 0 2 年，h w h a m a c h e r 和s a t j a n d r a 【如1 对疏散问题的宏观模型进行了综述，他们将 疏散过程中涉及到的时间参数作为最关键的因素，给出了疏散问题的最大流、最快流等 多个数学模型，这些模型主要用于陆上建筑物火灾事故的疏散。 网络流理论最初来源并应用于运输网络、供水电网络、通讯网络等实际的网络系统 中。由于在解决这些问题过程中表现出的优越性能，网络流理论的应用领域不断扩展， 许多表面上看似非网络的问题，通过将其抽象为网络问题求解都取得了良好的效果。 a h u j a 【3 u 指出，对于很多问题来说，运用网络流方法可以简化计算并快速地得到准确的结 果。因此，很多研究工作都是将紧急疏散问题建模成网络流问题来解决的p 到。 1 9 5 5 年，t e h a r r i s p 习在研究铁路最大通量时，首先提出在一个给定的网络上寻求 两点间最大运输量的问题。1 9 5 6 年，l r f o r d 和d r f u l k e r s o n p 卅给出了解决这类问题的 算法，从而建立了网络流理论。 动态网络流最早是在1 9 5 8 年由f o r d 和f u l k e r s o n 提出的p 邵卯，同时他们也提出了该 问题的第一个解决方法，其中最主要的发现就是时间扩展图( t i m e e x p a n d e dg r a p h s ) 。时 间扩展网络口6 3 刀模型是将动态网络扩展为静态网络的一种方法。该静态网络在时间范围 0 ，t ) 内的每个时间单位都有一个副本节点，并且动态网络中所有的弧都应该在这些 节点副本间重画以表达它们的运输时间。如图1 2 为 0 ，1 ) 时间范围的一个动态网络，弧 上的标号代表运输时间，运用时间扩展网络模型可以将其转化为在时间范围 0 ，4 ) 的 静态网络，如图1 3 所示。 t = 0t = l 图1 2 时间范围 o ，1 ) 的一个动态网络 哈尔滨i j 程人学硕十学位论文 图1 3 时i 司扩展图 利用时间扩展图的线性规划方法可以产生最优解，该模型对中小型疏散网络( 如陆 上楼房内的居民疏散) 比较适用。但是该方法仍然有局限性，从图1 3 中可以看出，若动 态网络中的节点个数为刀，疏散时间的上限为丁，那么时间扩展图中的节点数将是 ( 丁+ 1 ) 聆，也就是说，时间扩展网络的规模会随着丁和玎的增加而激增。因此，它并不一 定适合大型网络，例如舰船人员疏散网络。同时，为了产生时间扩展图，需要事先估计 疏散时间的上限丁，而实际上丁是很难预计的。低估了丁会造成仿真的重复运行，而高 估了丁就会增加不必要的内存使用和计算代价。 如今，动态网络在疏散规划方面已经得到了初步的应用拉”。2 0 0 2 年，h a m a c h e r 和 t j a n d r a t 蚓用动态网络流理论描述了疏散问题，为单源点疏散问题建立了最快流模型并给 出了疏散算法。2 0 0 3 年，q i n g s o n gl u 等人弘1 提出了容量限制路径方法c c r a ( c a p a c i t y c o n s t r a i n e dr o u t i n ga p p r o a c h ) ，它包含了基于动态网络流的两种新的启发式算法，分别 为单路径方法s r c c p ( s i n g l e r o u t ec a p a c i t yc o n s t r a i n e dp l a n n e r ) 和多路径方法m r c c p ( m u l t i p l e r o u t ec a p a c i t yc o n s t r a i n e dp l a n n e r ) 。2 0 0 5 年，他们对c c r a 方法进行了改进p 1 ， 引入了“超级源点 概念，提出了容量限制路径规划算法c c r p ( c a p a c i t yc o n s t r a i n e d r o u t ep l a n n e r ) ，得到了较优的结果。可以说，这是将动态网络流理论应用于人员疏散问 题的一个成功范例。 为了降低计算和储存方面的代价，g e o r g e ，k i m 和s h e k h a r t 3 卅又于2 0 0 7 年提出了解 决动态网络流问题的另一个方法时间聚合医 ( t i m e - a g g r e g a t e dg r a p h s ) 。在时间聚合网 络模型中，动态网络不需要在任意时刻都被复制。取而代之的是，它提出了两个新的参 数：“存在时间序y l j ( e x i s t e n c et i m es e r i e s ) 和“行走时间序? l j ( t m v e lt i m es e r i e s ) ”。其 中，前者用来表示在各时刻节点或弧的存在性，后者则用来表示在弧上不同的行走时问。 如图1 4 给出了图1 2 的时间聚合图，图中弧上圆括号内代表的是存在时间序列，方括 号内代表的是行走时间序列。 6 第l 章绪论 图1 4 时间聚合网络模型 可以看出，与时间扩展网络模型相比，运用时间聚合网络模型可以大大降低对储存 空间的需求，因此它更适用于大型网络的计算。 之后，r e n eb u s t a m a n t e m l 又基于时间聚合网络模型改进了q i n g s o n gl u 等人建立的 动态网络流模型，在节点和弧上都添加了相应的时间参数，并在c c r p 的基础上提出了 一种新的启发式算法( c c r pw i t hn e p t s ) 。 本文将在上述研究的基础上，借鉴前人解决问题的思想，针对要解决的舰船人员疏 散问题的具体特征，建立动态网络流模型并找到合适的算法。 1 4 论文的主要内容 本文研究的是“不含特殊要求 、“含禁行点禁行区段”、“含必经点必经区段 以及“含对流”等多种情况下的舰船人员疏散问题。为了能在尽量短的时间内获得较好 的疏散计划，以保障舰船上的生命财产安全，本文主要做了如下研究： ( 1 ) 由于动态网络流理论来源于经典的静态网络流理论，所以要在深刻了解后者的 基础上，通过比较二者在所含参数和应用场合等各方面的异同，深入思考如何将实际问 题转化为网络流模型中相应的结构和属性参数。 ( 2 ) 分析所要解决的舰船人员疏散问题，根据该问题的具体特征确定其中必须要考 虑、可以适当简化和可以忽略的因素以及疏散目标等。在此基础上，将疏散过程中涉及 到的各种结构设施等抽象成为具有多种属性的节点和弧，并且保证节点和弧上的参数能 正确且充分的描述舰船环境以及疏散过程。这样，就可以将实际的舰船人员疏散问题转 化为一个动态网络流模型。 ( 3 ) 深入研究目前已有的应用于动态网络流模型的各种算法，设计一种可以满足该 模型目标( 疏散和救援的时间最短) 的启发式算法。 ( 4 ) 找到处理“禁行点禁行区段 、“必经点必经区段 以及“对流”约束的方法， 进而设计出可以解决含这些特殊要求的舰船人员疏散问题的方法。 ( 5 ) 建立一个相对完整的舰船人员疏散系统，具体工作包括：为舰船人员疏散问题 哈尔滨一i ：稃人学硕十学何论文 设计并建立相应的a c c e s s 数据库，数据库的结构和其中的数据可以清晰、简洁且准确 的表达舰船的物理结构和环境参数等；将已经设计好的启发式算法用v i s u a lc + + 6 o 编 程实现；设计既合乎需求又方便美观的舰船人员疏散界面；通过具体算例分析多种因素 对舰船人员疏散的影响。 1 5 论文的结构安排 本论文共分为五章，具体章节安排如下： 第1 章为绪论部分，主要介绍本文研究的背景及意义，确定对舰船人员疏散问题的 研究方法，综述该问题的国内外研究现状，并指出论文的主要内容。 第2 章首先概述网络流理论的基本概念，然后分析舰船人员疏散问题的具体特征， 确定需要考虑的因素和疏散目标，最后为舰船人员疏散问题建立动态网络流模型。 第3 章为舰船人员疏散问题设计启发式算法，包括算法的基本流程及细节分析。 第4 章找到处理“禁行点禁行区段、“必经点必经区段”以及“对流”问题的 可行方法，从而设计出可以解决含特殊要求的舰船人员疏散问题的启发式算法。 第5 章进行舰船人员疏散系统的开发。包括设计与建立a c c e s s 数据库、设计系统 的各个模块、分析计算结果等。 8 第2 章舰船人员疏散问题的动态网络流模犁 第2 章舰船人员疏散问题的动态网络流模型 随着网络流理论应用领域的不断扩展，很多实际问题都可以被转化为网络流模型来 加以解决，本文要研究的舰船人员疏散问题也不例外。本章的目的在于通过分析舰船人 员疏散问题的基本特征，将现实中复杂的舰船人员疏散问题抽象成一个动态网络流模 型，为之后的算法设计和系统开发打下坚实的理论基础。 2 1网络流理论概述 网络流理论是图论的一个分支，最初用于研究网络中的最优化问题。它是一个引入 注目的研究领域，结合了数学、图形学和计算科学等多个领域的知识。网络流理论的应 用范围相当广泛，目前已成功应用于计算机网络、调度、路由、电信、运输以及制造等 领域。本节首先简要地回顾关于静态网络流的基本概念和重要结果，接着进一步探讨动 态网络流问题。 2 1 1 静态网络流基本概念 ( 1 ) 有向图和无向图。有向图g = ( n ，彳) 包括顶点集和弧集a ，其中弧集彳的每 条弧a 都由一组有序的顶点对( ，t ，) 表示。无向图与有向图类似，只是其弧集a 所包含 的弧中，顶点对是无序的，也就是说，弧既可以从吩指向刀，又可以从刀，指向n j 。 如图2 1 ( a ) 所示的就是一个有向图，其中顶点集n = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，弧集 a = ( 1 ，2 ) ，( 1 ，3 ) ，( 2 ，4 ) ，( 2 ，5 ) ，( 3 ，6 ) ，( 4 ，7 ) ，( 5 ，3 ) ，( 5 ，7 ) ，( 6 ，7 ) ) ，与其相对应的无向图如图 2 1 ( b ) 所示。 本文的舰船人员疏散问题中，在船员从事发地点向外疏散的同时，可能还需要救援 人员到事发地点进行救援。初步分析：这两组人员在同一区段内的运动方向可能是相 反的；两组人员在同一区段内的运动速度等参数值可能是不同的。而有向图中，两节 点间的运动方向是唯一的，无法满足要求；无向图中，虽然两节点间允许存在方向相 反的弧，但是两个方向上的权值是相同的，无法满足要求。因此，有向图和无向图都 无法满足舰船人员疏散问题的要求。 在这种情况下，本文提出双向图的概念，即两节点间存在方向相反的两条弧，并且 允许弧上的权值不同，如图2 1 ( c ) 所示。可以这样认为：单独进行疏散或救援时，其网 络模型可视为一个有向图；而在疏散和救援同时进行时，其网络模型就是一个双向图。 9 哈尔滨r ：程大学硕十学位论文 ( a ) 有向图 ( b ) 无向图 ( c ) 双向图 图2 1 有向图、无向图和双向图 ( 2 ) 网络p 。网络，简而言之，就是一个加权有向图。也就是说，使得某个简单的 有向图g = ( n ，a ) 的各节点和或弧与一些数值( 通常是容量、成本、供应量以及需求量等) 相联系。 通常在网络的顶点集中指定一个源节点，和一个汇节点s 。每条弧a a 的容量由 表示，弧口上每个单位流的成本为c a 。如果一条弧口从节点伟指向，l ，那么吩就称为 弧口的尾节点，玎，称为弧口的头节点，分别记为t a i l ( a ) = ，h e a d ( a ) = 刀，。而流入和离 开节点刀的弧集分别用矿( 拧) 和占一( 刀) 表示，并且扩( 刀) 和艿一( 刀) 中弧的条数分别称作节点 刀的入度和出度，它们的和称为度。如图2 2 所示，该网络的源节点为l ，汇节点为5 。 ( 2 0 ，3 5 ) ( 3 0 ，2 5 ) 少2 0 ，2 5 ) 函 2 5 ) i ( 1 5 3 5 ) g ( 1 5 ，4 0 ) 4 弋y 0 0 , 3 0 ) 图2 2 网络不例 ( 3 ) 静态网络流。一个静态流x ：aj 足将一个非负流值分配到a a 上。 一= 一d ( 2 1 ) d e 艿+ ( r )口占一( ，) 艺一= o v n n r ，s ( 2 2 ) l o 第2 苹舰船人员疏散问题的动态网络流模型 艺一艺- - d ( 2 - 3 ) a g 8 + ( j )a e 8 ( j ) 0 u a ( 2 - 4 ) 如果它满足流守恒规贝j j ( 2 - 2 ) ，那么可称为一个流。一个流如果服从容量约束( 2 4 ) ， 那么这个流是可行的。一个遵循约束( 2 - 1 ) 和( 2 3 ) 的值d 叫做流的值，通常表示为h 。 2 1 2 动态网络流基本概念 与静态网络流相比，动态网络流模型中有一个附加的参数l ，它指定弧a 上每个单 位流从弧的尾到弧的头所需要的时间，称为弧a 的行程时间。换句话说，一个，时刻从 弧a 的尾出发的单位流，需要到f + 乞时刻才能到达弧a 的头。因此，动态模型中的负荷 量与流量的概念是不同的。 ( 1 ) 弧的负荷量。顾名思义，f 时刻弧口的负荷量l ( t ) 就是指，时刻存在于弧a 上的 流的数量。 ( 2 ) 流量。，时刻弧a 的流量x o ( t ) 指的是，时刻已经进入弧a 的流的数量。流量是动 态网络流理论中研究的焦点问题，它经常被简称为“流 。 负荷量与流量均为时间的函数，而且：丁专r 和而：丁一r 这两个函数紧密相关。 在离散和连续模型中，二者关系分别如式( 2 5 ) 和( 2 - 6 ) 所示。 f l l ( t ) - - x ( t - o ) ( 2 - 5 ) 0 = 0 五( f ) = f 4 x ( 卜o ) a o( 2 - 6 ) ( 3 ) 吞吐量。吞吐量是指在给定的时间区间内可以从源点到汇点发送的流量，它是 动态网络流的一个最重要的衡量标准。 下面给出一个动态网络流的例子。考虑如图2 3 所示的动态网络，弧上的标号表示 弧的行程时间，并且假设每条弧的容量为2 。图2 4 则给出了一个在t = o ，l ，5 ) 内吞 吐量为8 的流。 图2 3 动态网络示例 哈尔滨r 1 ：程大学硕十学位论文 t 2 4 t = 5 图2 4 在时刻l 5 的动态流 另外，动态网络流模型中，弧上的参数可能不是固定而是随时间变化的，用函数 “。：r 一墨，c a ：r 专r 和l r 分别表示弧a 上不同时刻的容量、成本和行程时间。 下列约束( 2 7 ) ( 2 1 1 ) 定义了弧容量固定的情况下，离散时问模型中的可行动态流 集合。 r ( x o ( t - r o ) - x o ( t ) ) = - d ( 2 - 7 ) t = 0a e # + ( ，) a e 8 一( r l 口 ( x o ( t - r o ) - ( f ) ) o t = 0 a e 8 + ( n )骺，( 月) 滚激01 ：t k - 1 ， v p = ， 、 7 了 ( x o ( t - t o ) - 而( ，) ) = o ( 2 - 9 ) t = o 口e 矿( 月)a e r y - ( n ) 0 x o ( t ) u a v a a ，v t = o ，l ，t ( 2 一l o ) ( 2 - 1 1 ) 而在连续时间模型中，时间的和被积分代替。- f 歹u 约束( 2 1 2 ) 一( 2 - 1 6 ) 则定义了弧容 量随时间变化的情况下，连续时间模型中的可行动态流集合。 ( 。( x o ( t - r o ) - x o ( t ) ) d t = - d ( 2 - 1 2 ) 口e 矿( ，)a e $ 一( ，) 址；。、啪训- e 。、啪泐。孑n 州en 耐 r b - 砖( 2 1 3 ) 徙矿( 肝) 口e 打) v l v ，工， 1 2 d = ”o 川 口 一 毛 一 屹 o 引 ( 口r脚 第2 章舰船人员疏散问题的动态网络流模型 ( 。( x o ( t t o ) 一x o ( t ) ) d t = o * 矿( )a e 8 一( h ) = 。( x o ( t 一吃) 一屹o ) ) 出= d a e 8 + ( )a 8 一( s ) ( 2 - 1 4 ) ( 2 - 1 5 ) 0 x o ( t ) h a ( f ) v a a ，v t = 【o ，t 】 ( 2 - 1 6 ) 可以看出，离散时间模型的约束超过丁个，而连续时间模型有无穷个约束。因此， 用线性规划方法解决动态网络流问题不是多项式可解的方法。 2 2 舰船人员疏散问题分析 在将动态网络流理论应用于实际问题的过程中，模型的构造是比较关键的一步。原 因在于构造的过程没有现成的模式可依，只能根据问题的具体条件来分析。这不仅需要 对网络流理论有深入的了解，而且要求对实际问题了如指掌，然后在此基础上归纳积累 一些经验、发挥我们的创造性。因此，本节将着重分析舰船人员疏散问题的具体特征， 为建立动态网络流模型奠定基础。 2 2 1 问题假设 舰船人员疏散是一个非常复杂的问题，所以首先了解一下它与普通客船人员疏散的 相同点( 1 ) ( 2 ) 和不同点( 3 ) ( 5 ) ，以便在研究过程中对其进行适当的简化。 ( 1 ) 不论是普通客船还是舰船，影响人员疏散速度的因素都是错综复杂的，例如疏 散时人员的密集程度、船体运动以及当时的外界环境因素等。 ( 2 ) 普通客船与舰船都由舱室、走廊、公共区域、门、楼梯和电梯等结构组成。 ( 3 ) 普通客船上的乘客任务相对简单；舰船上船员的任务比较复杂。 ( 4 ) 普通客船上乘客的分布比较分散；舰船上船员的分布相对比较集中。 ( 5 ) 普通客船中的乘客有不同的文化背景、语言以及身体素质等，因此在遇到突发 紧急情况时，反应时间、惊慌程度等也会有所不同：而在舰船中，受过训练的船员的运 动可以被看作是受控制的“流 。 由此，对舰船人员疏散问题进行以下两点假设： ( 1 ) 鉴于影响船员疏散速度因素的复杂性，本文暂不考虑船体运动( 如纵摇、横摇) 及外界环境对疏散速度的影响。 ( 2 ) 假设船员都经过良好训练且熟悉舰船环境、有较好的组织性和纪律性，且不考 哈尔滨t 程大学硕十学位论文 虑船员个体之间的相互作用。 2 2 2 考虑因素 ， 针对舰船人员疏散问题的特殊性，解决该问题时需要考虑以下几个因素： ( 1 ) 舰船的布局及参数 包括舰船中设施( 舱室、门、走廊以及楼梯等) 的布局和位置，舱室及通道等的面积 和容量限制，门的宽度等等。这些参数是在突发状况发生之前就已知的。 ( 2 ) 舰船上船员的位置 在大多数情况下，舰船上船员的位置是非常精确地已知的。因此，突发危险状况时， 直接获知舰船上船员的位置分布是很容易做到的。 ( 3 ) 舱室及通道中船员密度对其行走速度的影响 在疏散过程中，船员的持续“流动”会导致其密度的不断变化，而船员的行走速度 与其密度有关，那么也就意味着船员在各条通道上的行走时间需要非常复杂的计算。为 了对该时间进行合理的简化，本文根据国际海事组织( i m o ) m s c 1 c i r c 1 2 3 8 ( 新建客船和 现有客船撤离分析指南) 给出的标准一2 删( 如表2 1 所示) 来确定相应密度下的船员行走速 度，然后行走时间就可以通过“行走时间= 行走距离行走速度 这一简单的公式计算得 到。 表2 1 船员密度对其行走速度的影响 初始密度oc p m 2 ) 初始船员速度s p ( m s ) o1 2 0 51 2 1 90 6 7 3 2o 2 0 芝3 50 1 0 ( 4 ) “禁行点禁行区段” 在舰船遭到意外破坏的情况下，需要对已破坏的区域或危险区域采取禁行的措施。 也就是说，根据舰船环境的变化考虑在疏散过程中不允许船员通过的区域( 如已毁的舱 室或走廊路段等) 。 ( 5 ) “必经点必经区段 在舰船人员疏散过程中，还有一种情况是有些地点或路段是“必经点必经区段 ， 例如船员在逃生过程中，必须要经过存放逃生设备的地点。 ( 6 ) “对流 1 4 第2 章舰船人员疏散问题的动态网络流模犁 意外突发时，并非每次都必须做出弃船的决定，大部分时候情况如下：船员疏散的 同时，还有救援人员前去事故发生地点执行救援任务。这时，就产生了所谓的对流问题。 在上述的六个因素中，因素( 1 ) ( 3 ) 中涉及的参数都是可以直接获得或是通过简单 的计算间接得到的，因此需要将这些参数合理地包含于动态网络流模型中。而对于因素 ( 4 ) 一( 6 ) 来说，需要在设计算法的过程中找到解决的方法。 2 。2 3 疏散目标 本文中，舰船人员疏散问题的目标为：完成疏散和救援工作的总时间最短。所谓疏 散时间，即从第一个被疏散者出发直至最后一个被疏散者到达安全聚集地为止的总时 间。同理，救援时间即为从第一个救援人员出发直至最后一个救援人员到达事发现场为 止的总时间。 该疏散目标的数学表达如公式( 2 一1 7 ) ( 2 - 1 8 ) 所示。 t 。= m i nt ( 2 1 7 ) r = i t l a x ( t a + y , ( t r a v e l f f m p ( p i p j + l ，t r , ) + d o o ，一f 砌p 所竹“) ) = m a x ( _ + 善k - i ( 面獗l p j p l + l 而+ 焘? 其中：，一最优目标函数值； b 一路径p 中的第f 个节点，i e l ，2 ，k ) ，p 。是网络的源点，鼠是网络的汇点： 一从节点易出发的时刻； 乞岛一弧只仍+ - 的长度； s p e e d ( p t p j + l ，_ ) 一_ 时刻经过弧只b + - 的速度； g 一某次疏散的人数； 厶- - 弧p , p , + - 的通量。 2 3 动态网络流模型建立 2 3 1 模型建立方法 要为舰船人员疏散问题建立动态网络流模型，首先要确定节点( 包括源点、中间节 哈尔滨t 程大学硕十学位论文 点和汇点) 和弧所代表的意义。 先来分析一下，本文的最终目的是找到意外事故发生后逃生船员( 或救援人员) 在舰 船中的疏散路线( 或救援路线) ，映射到动态网络流模型中，就是要找到“流”在动态网 络中的路径。前面已经说过，船员可以被看作是受约束的人“流 。那么，动态网络中 的节点和弧所代表的就应该是疏散过程中可能会涉及到的舰船上的各种设施，即舱室、 走廊、门以及楼梯等。 于是，很自然地想到，紧急情况发生时有船员的舱室应该建模成源点，因为这些舱 室就是船员疏散的起点。按照同样的逻辑，舰船上的安全聚集区域就可以建模成汇点， 因为这些区域可以看作是船员疏散的终点。此外，中间节点就应该代表疏散过程中船员 可能经过的舱室、走廊和楼梯。而在舰船上，舱室、走廊以及楼梯之间都是靠门连接起 来的，所以将节点连接起来的弧自然就代表门了。 这样，就得到了动态网络流模型中节点( 源点、汇点以及中问节点) 和弧代表的意义， 如表2 2 所示。 表2 2 动态网络流模型中节点和弧代表的意义 动态网络流模型代表的实际意义 源点紧急情况发生时有船员的舱室 节点中间节点疏散过程中经过的舱室、走廊和楼梯 汇点安全聚集区域 弧门 在确定了节点和弧所代表的实际意义之后，接下来就应该确定节点和弧的属性了。 首先，节点和弧需要有唯一的标识。那么，为节点设置唯一的标识节点编号， 同时弧就可以将其尾节点和头节点编号的组合作为唯一标识。 然后，根据前面2 2 2 节提出的舰船人员疏散问题需要考虑的前三个因素分别找出 其他必要的参数。 ( 1 ) 考虑“舰船的布局及参数 为节点设置3 个参数：节点面积、节点位置和节点容量，分别用来表示舱室或走廊 等的面积、位置和同时能容纳的人数； 为弧设置2 个参数：弧长度和弧通量，分别用来表示船员在舱室或走廊等中需要行 走的距离以及单位时间内可以同时通过门的人数。其中，弧通量只与门的宽度有关。 ( 2 ) 考虑“舰船上船员的位置” 1 6 第2 章舰船人员疏散问题的动态网络流模型 1 为节点设置1 个参数：人员占有量，用来表示当时在某位置的人数。 ( 3 ) 考虑“舱室及通道中