Atlantis Press Journal style Received 3 December 2016 Accepted 12 December 2016 Path Optimization in Dynamic Adverse Weathers Mingkong Zhang1,2,3, Xiaobing Hu1,2,3, Jianqin Liao4 1State Key Laboratory of Earth Surface Processes and Resources Ecology (Beijing Normal University) Beijing 100875, China 2Key Laboratory of Environmental Change and Natural Disaster, Ministry of Education of China, Beijing Normal University, Beijing 100875, China 3Academy of Disaster Reduction and Emergency Management, Ministry of Civil Affairs & Ministry of Education the Peoples' Republic of China, Beijing Normal University, Beijing 100875, China 4MiidShare Technology Ltd, Chengdu, 610000, China Abstract As we all know, weather condition is constantly changing. Then, when an adverse weather event occurs during travelling period, path planning becomes a dynamic path optimization (DPO) problem. A common practice of DPO is to conduct real-time online path optimization based on the current weather condition. However, the result of online optimization under the current weather condition is rarely optimal for future weather conditions. We are concerned with how to achieve optimal actual travelling trajectory by just a single offline optimization, given the dynamics of weather conditions is pre-known. To this end, the concept of co-evolutionary path optimization (CEPO) is introduced, where the weather condition in a single run of offline optimization is not static, but keeps changing during the single run of offline optimization. Existing DPO methods can hardly address CEPO, because they do not allow the weather condition to change in a single run of online optimization. To address the CEPO in dynamical adverse weathers, this paper proposes a ripple-spreading algorithm (RSA), which can achieve optimal actual travelling trajectory by a single offline calculation. The reported CEPO and RSA are then tested on a typhoon scenario in Hainan Province of China, and the advantages against traditional DPO methods are clearly demonstrated. Keywords: Co-Evolutionary Path Optimization, Adverse Weathers, Ripple-Spreading Algorithm, Typhoon. 动态极端天气情况下的路径优化问题 张明空 1,2,3 ，胡小兵 1,2,3 ，廖建勤 4 1.北京师范大学地表过程与资源生态国家重点实验室，北京 100875 2. 北京师范大学环境演变与自然灾害教育部重点实验室，北京 100875 3. 北京师范大学，民政部/教育部减灾与应急管理研究院，北京 100875 4. 成都鸣先科技有限公司，成都，610000 摘要：众所周知，天气情况是实时变化的。所以，当旅途中遭遇极端天气时，路径规划问题就成为了动态路径 优化问题（Dynamic Path Optimization，DPO）。动态路径优化的普遍求解思路是：基于当前天气情况实时优化 路径。然而，虽然在线优化的结果对于当前天气情况而言是最优的，但对于未来天气情况而言不见得是最优的。 Journal of Risk Analysis and Crisis Response, Vol. 6, No. 4 (December 2016), 197-205 Published by Atlantis Press Copyright: the authors 197 M.K. Zhang et al. / Path Optimization in Dynamic Adverse Weathers 所以,基于当前天气情况而不断在线实时优化所得到的实际旅行路径一般都不是最优的。本文关心的问题是：假 定已知天气变化的动态规律，如何通过一次性的离线优化就能使实际旅行路径达到理论最优？为此，本文提出 了协同进化路径优化（Co-Evolutionary Path Optimization，CEPO）概念，它要求：在一次性的离线路径优化计 算中充分考虑天气的动态变化过程。目前已有的 DPO 方法很难解决 CEPO 问题，因为在 DPO 的每次在线优化 计算中，未来的天气变化情况并没有被考虑。本文提出了一种涟漪扩散算法（Ripple-Spreading Algorithm， RSA），通过一次性的离线优化就能找到动态变化天气情况下的最优实际旅行路径，从而解决 CEPO 问题。为 了验证 CEPO 和 RSA，本文以中国海南岛路网为背景，模拟海南岛台风登陆的动态过程，并在这种动态天气情 况下进行路径优化仿真实验。实验结果证明：本文所提出的基于 RSA 的 CEPO 方法较传统的 DPO 方法，不论 在计算时效还是在求解效果上，都更具优势。 关键词： 协同进化路径优化；动态路径优化；极端天气；涟漪扩散算法；台风 1. 前言 日常出行中的路径规划通常都需要考虑天气情 况。如果旅途中遇到恶劣天气，那么，不仅我们出 行的舒适性会受到影响（例如，极端天气造成的交 通拥堵）[1]-[2]，我们出行的安全性也会受到威胁 （例如，台风、龙卷风、暴风雨和暴风雪经常会引 起致命的交通事故）[3]-[4]，所以，在极端天气情 况下进行路径优化具有重要的现实意义。优化路径 一方面可以避开受极端天气影响的区域或道路，降 低气象灾害风险[5]，增加旅行的舒适性和安全性， 提高面对气象灾害时，降低应急时承灾体的脆弱性 [6]。另一方面也可以降低相关旅行成本。在一般的 路径优化问题中，旅行成本可以用距离、油耗和路 桥费等指标来衡量，然而，在极端天气情况下，旅 行时间通常会被作为优先考虑的指标，因为在极端 天气情况下，安全问题是重中之重，对于旅行者而 言，如何以最短的时间安全完成旅行任务才是最重 要的。而且，旅行时间最小化在自然灾害疏散、救 援和应急管理中也具有重要地位[7]。许多自然灾害 通常会伴随有极端天气情况发生（例如，灾难性的 地震之后很可能会伴随暴风雨）[8]。最小化旅行时 间就意味着尽可能缩短暴露在极端天气情况下的时 间，从而降低受灾风险。所以，在减灾和风险管理 研究领域中，极端天气情况下的路径优化问题具有 重要的研究价值[9]-[10]。 显然，极端天气情况下的旅行是一个动态路径 优化问题。例如，当台风中心随时间移动时，其经 过的区域就会有暴风雨，暴风雨将导致该区域的通 行条件恶化，只有等暴风雨过境后才能恢复有效通 行，从而在一定时间内对旅行造成影响。其实，动 态路径优化问题并不是一个新问题，国内外的学者 已经提出了很多求解方法。例如，文献[11]-[14]研 究了针对单一路网改变的动态路径优化问题；文献 [14]-[17]则研究了针对一系列路网改变的路径优化 问题。在文献[11]和[17]的方法中，基本上，原始 路网一旦有任何改变，优化算法就需要在线重新计 算以确定新的最优路径。事实上，每次在线路径优 化计算所求解的是一个基于当前路网的静态路径优 化问题（Static Path Optimization，SPO），因为单 次在线路径优化计算中所使用的路网都是静止不变 的。由于受在线计算时间的限制，文献[11]-[14]中 的动态路径优化方法的关注重点是：能否不进行完 全的重新计算，而是结合当前路网对以前的优化路 径进行恰当的改进就达到优化的效果？换句话说， 文献[11]-[14]中的动态路径优化方法强调在每次路 网发生改变时求解新 SPO 的速度。在线求解 SPO 的结果对于当前路网来说可能是最优的，但是在实 际旅行中，不断重复在线求解 SPO 所走出的实际 旅行路径，对于给定的路网动态变化规律而言，很 难保证最优性。图 1 展示了 DPO 的求解过程，以 及 DPO 所导致的实际旅行路径与理论最优的实际 旅行路径之间的差异。事实上，DPO 方法不能得 到理论最优的实际旅行路径，其主要原因是忽略了 路网未来变化的可预测性。在 DPO 的单次在线路 径优化计算中，动态变化的路网被简化成当前时刻 的路网（静态路网），因而单次在线路径优化的结 果对于未来的路网而言，一般很难是最优的。 图 1. 动态路径优化（DPO）不能实现最优实际旅行路径 Published by Atlantis Press Copyright: the authors 198 M.K. Zhang et al. / Path Optimization in Dynamic Adverse Weathers 事实上，得益于天气预报技术的快速发展，许 多由于天气原因对路网造成的改变或多或少是可以 预测的。例如，对台风中心的位置、移动轨迹、以 及暴风雨的持续时间，目前都可以提前几个小时准 确预报。显然，充分利用天气预报信息进行动态极 端天气情况下的路径优化，对于提升优化效果是非 常重要的。当前，对于灾害发生规律的研究已经有 相应基础，例如连续的 Markov 决策模型模拟灾害 随机发生过程 [18]和预测灾害的有效发生时间[19]； 对于社会灾害，城市火灾发生时蔓延的规律及模型 的研究也有不少相关报道[20]-[21]。这些研究都有 助于提高灾害预测技术的发展，帮助增强 CEPO 单 次离线路径最优结果的解算精度。 本 文 通 过 改 进 文 献 [22] 中 的 涟 漪 扩 散 算 法 （Ripple-Spreading Algorithm，RSA），提出了一 种解决动态极端天气情况下路径优化问题的新方法， 通过利用天气预报提供的未来天气变化信息，执行 一次性的离线优化，从而找到在所预报的天气动态 变化规律下的理论最优的实际旅行路径。为了实现 这个目标，就必须在一次性的离线路径优化过程中 把天气变化对路网的动态影响考虑进去。换句话说， 天气动态变化情况和离线优化过程必需协同进行。 由于天气情况和路径优化求解是一起协同进化的， 因此我们将此新方法称为协同进化路径优化方法 （Co-Evolutionary Path Optimization，CEPO）。传 统的 DPO 方法很难处理 CEPO，因为天气情况的 变化没有（事实上是没法）在 DPO 的单次在线优 化计算中得到考虑。文献[22]中的 RSA 区别于传统 路径优化算法的最大特点就是：RSA 实际上是一种 确定性的去中心化的多智体仿真模型，而不是传统 类型的集中式搜索算法。因为集中式搜索算法需要 进行全局比较，所以在算法的单次运行中，路网不 允许变化（否则全局比较就会失去意义和作用）， 因而在单次运行中无法考虑天气情况的变化。去中 心化的多智体仿真模型则不一样，对于仿真模型中 的单个智体而言，其行为只取决于当前该智体所处 位置的路网部分的情况，路网中其它部分的变化并 不会影响该智体的行为。因此天气情况的动态变化 可以自然而有机地整合到多智体仿真过程当中。正 是基于去中心化的多智体仿真模型的特点，本文通 过对 RSA 进行改进，从而可以有效解决 CEPO 这 一传统 DPO 方法所不可能完成的任务：即，通过 一次性的离线优化就能找到动态变化天气情况下的 最优实际旅行路径（而传统 DPO 方法需要不停地 重复在线实时优化，可是 DPO 方法下实际走出的 旅行路径却通常并不是最优的）。 2. CEPO 问题描述 用 G(V,E)来表示路径网络，V 表示结点集合， E 表示结点间的链接集合。V 有 NN 个不同的结点， 包括起点和终点，E 有 NE 条链接。路径网络可以 表示成 NN *NN 的邻接矩阵 M。矩阵 M(i, j)=1, i=1,…,NN，j=1,…,NN,表示结点 i 和 j 之间存在一条 链接，否则 M(i, j)=0，即结点 i 和 j 之间没有链接。 本文不考虑结点自我连接的情况，因而有 M(i,i)=0。 每条链接上的旅行速度 SL(i, j)与链接 M(i,j)有关。 C(i, j)为链接上的成本，也与 M(i, j)有关。不同等 级的链接分别有不同的旅行速度，根据链接 M(i, j) 的旅行速度 SL(i, j)，就可以计算从结点 i 到结点 j 的所用时间。 假设候选路径通过整数型向量 R 来记录，其元 素 R(i)=j 表示结点 j 是路径 R 中的第 i 个结点， i=1,…,NP, j=1,…,NN,NP 表示路径 R 中有多少个结点， 包括起点和终点。显然 R(1)是起点，R(NP)是终点。 本文研究中，不允许任何一结点在同一条路径 R 中 出现次数多于一次，即整数型向量 R 满足如下条件： R(i)≠R(j), 如果 i≠j, i=1,…,NP, j=1,…,NP. (1) 为了在 t=0 时刻计算出最优路径，需要基于已 知的天气预报信息，预测在未来各个时刻有多少结 点和链接会受到极端天气的影响，从而邻接矩阵 M 就会随时间发生改变。Mk|0 表示在当前时刻 t=0 所 预测的未来时刻 t=k 时的邻接矩阵。 基于上述数学符号定义，传统 DPO 在当前时 刻 t=0 的单次在线优化计算问题可以描述如下： 约束条件为：公式（1）和 ( )min ,DPO P R f R N ∈Ω (2) M0(R(i), R(i+1))=1, i=1,…,NP-1, (3) Ω 是所有可能连结起点与终点的路径集合, ( ),1 0DPOf R = (4) ( ) ( ) ( )( ), , 1 1 , ( )DPO DPOf R i f R i C R i R i= − + − 1 < i ≤ NP. (5) 如公式（3）所示，DPO 在当前时刻 t=0 的单 次在线优化计算中，路径网络固定不变的。一旦路 径网络在未来时刻 t=k>0 时刻发生改变，DPO 就需 要基于 Mk 重新在线优化计算一次（注意：时刻 t=k 的起点与时刻 t=0 的起点一般是不一样的）。 与 DPO 彻底不同的是，本文所提出的 CEPO 在其一次性的离线优化计算中，路径网络不是固定 不变的，而是随预测时间 k|0 而不断变化的。CEP O 问题的数学描述如下： Published by Atlantis Press Copyright: the authors 199 M.K. Zhang et al. / Path Optimization in Dynamic Adverse Weathers ))(,(min RLRfCEPOR Ω∈ , (6) 约束条件： 1))1(),((0| =+iRiRM k , 1,..., += ii kkk (7) 0)1,( =Rf CEPO , (8) ))1(),(()0|),,(max()1,( ++=+ iRiRCkiRfiRf iCEPOCEPO , 1 ≤i< NP -1, (9) fCEPO(R,i)是用来计算沿路径 R 到达结点 R(i)的 时间，ki|0 是当沿路径 R 到达结点 R(i)后，结点 R(i) 变为可以通行的预测时刻。换句话说，当沿路径 R 于时刻 fCEPO(R,i)到达结点 R(i)时，结点 R(i)并不一 定可以通行，因此需要在结点 R(i)处等待，预测需 要等到时刻 ki|0 结点 R(i)才变为可以通行，此时旅 行才得以继续。所以沿路径 R 通过结点 R(i)的预计 时间是 max(fCEPO(R,i),ki|0)。Mk|0(R(i), R(i+1))=1 表 示的意思是：根据在初始时刻 t=0 的预测，结点 R (i)和 R(i+1)之间在预测时刻 t=k|0 存在可通行的链 接。 公式(7)和公式(9)清楚的表示：在正在通过的 R 的一个子路径中，其连通性和预测旅行时间是相 互依赖的，这一点 DPO 并没有考虑。根据预测时 间 k|0 改变 Mk|0 是由动态变化的极端天气情况决定 的，公式如下： )( 0|0|1 kFAWDk MfM =+ , k≥0, (10) 约束条件是 M0|0=M0，fFAWD 是由天气预报的极端天 气动态变化规律所决定的函数，M0 是 t=0 时的邻接 矩阵。 从公式(6)和(7)对 CEPO 的数学描述可以看出， 如果 fFAWD 已经确定，即，极端天气情况的动态变 化过程能够预测，并且给定 t=0 时的 M0，那么我 们就能进行一次性离线优化来找到动态变化天气情 况下的最优实际旅行路线，而完全不需要像 DPO 那样不断在线重新计算 t=k>0 时的最优路径（仅仅 对于时刻 t=k 的路网 Mk 而言是最优的）。 比较 DPO 中的公式(3)和 CEPO 中的公式(7)， 我们能发现，在一次优化过程中，DPO 只关心两 个结点间是否有链接，而 CEPO 需要知道什么时候 哪些链接可以通过，即，需要预测某条链接是否在 恰当的时间变为可以通行。换句话说，在 DPO 中 的基本计算操作是分析链接，例如，一个链接需要 多长的旅行时间；而在 DEPO 中的基本计算操作是 分析各个预测时刻的仿真时间单位长度内的路网变 化和旅行行为，即，在模拟一个仿真时间单位长度 内，路径网络如何改变，然后基于这种改变，根据 公式(9)沿着某条链接的旅行时间可能就会受到什么 影响，例如， )0|),,(max( iCEPO kiRf 就意味着旅行 者在结点 R(i) 处可能需要等到时刻 0|ik （假设 fCEPO(R,i) 0 表示涟漪 i 是被涟漪 j 激活的。rR(i,:)是一个向量， 表示当前涟漪 i 的半径。SR(i)记录涟漪 i 的状态， SR(i)=0,1,2,3 表示涟漪 i 所处的状态，分别表示不活 跃、等待、活跃和消亡。 第 1 步，初始化，FR(i) = 0, SR(i)=0, rR(i,:) = 0， i = 1, …, NN。 第 2 步，k=0，当前时间 t=k|0。设 FR(1) = 1, SR(1)=2。 第 3 步，如果 FR(NN) = 0， 第 3.1 步，k=k+1,更新时间 t = k|0。 第 3.2 步，更新 Mk|0，即，根据预报的天气动 态变化规律，更新路网。 第 3.3 步，对于任一等待涟漪 i，即，SR(i)=1， 如果根据更新的 Mk|0，结点 i 变为可以通行，则涟 漪 i 的状态更新为活跃，即，设置 SR(i)=2。 第 3.4 步，对于任一活跃涟漪 i，即，SR(i)=2， 更新涟漪 i 沿着与结点 i 相连的链接扩散的半径， 例如，设结点 i 的第 l 条链结与结点 m 相连，那么， rR(i, l) = rR(i, l) + SL(i, m)。 第 3.5 步，根据 Mk|0 对于任意可通行的结点 n, Published by Atlantis Press Copyright: the authors 201 M.K. Zhang et al. / Path Optimization in Dynamic Adverse Weathers 如果 SR(n)=0，且它刚被至少一个活跃涟漪到达， 假设是激励涟漪 i，沿着与结点 i 相连的第 l 条链接 扩散第一个到达结点 n，那么根据涟漪 i 到达结点 n 的时间 tR 更新 rR(n,:)，例如：假设结点 n 的第 l 条链接与结点 m 相连，则 rR(n,l) = (k-tR)×SL(n, m)。 设置 FR(n) = i。设置涟漪 n 作为活跃涟漪，即， SR(n)=2。 第 3.6 步，根据 Mk|0，对于任意不可通行结点 n，如果 SR(n)=0，且它刚被至少一个活跃涟漪到达， 那么，假设是涟漪 i 第一个到达结点 n，则设置 rR(n)=0, FR(n) = i,同时设置涟漪 n 为等待涟漪，即， SR(n)=1。 第 3.7 步，对于任何一个涟漪 i，无论活跃还 是不活跃，如果对于每个具有 Mk|0(i, n) = 1 的结点 n，FR(n) > 0，那么设置 SR(i)=3，即，涟漪 i 消亡。 第 4 步，从 FR(NN)回溯，就可确定最优路径。 步骤 3.2 和步骤 3.4 很好地描述了路网和涟 漪的协同进化关系。根据步骤 3.5，一旦一个可 以通行的结点第一次被任何一个涟漪到达后，那 么在该结点就会立刻产生新的活跃涟漪。步骤 3.4 和步骤 3.5 允许不同的链接可以有不同的涟 漪扩散速度。步骤 3.6 定义了涟漪的等待行为， 一个不可通行结点第一次被任何一个涟漪到达后， 该结点的涟漪虽然会被激活，但会保持等待而不 扩散。根据步骤 3.7，如果与一个涟漪的波源结 点相连的所有结点都已被涟漪到达过（不管是被 哪个涟漪到达），则该涟漪就会消亡。 有了上述伪代码中所引入的协同进化的关系、 以及多涟漪扩散速度和等待行为，RSA 就可以有效 解决 CEPO 问题，即，通过一次性的离线优化就能 找到动态变化天气情况下的最优实际旅行路径。图 2 展示了涟漪扩散算法 RSA 是如何解决 CEPO 问题 的。简单起见，图 2 中所有链接具有相同的旅行速 度。从图 2 可以看到，由于天气的动态变化，随着 预测时间 k|0，k=1,…,5，路网变化与涟漪接力赛是 协同进行的。如果 DPO 方法运用于该情境中，它 的第一步是先走向结点 9，同时结点 4 在时间 1|0 成为不可通行结点；然而当到达结点 9 时，结点 9 已变成不可通行结点；于是在 4|0 时刻，DPO 方法 会返回结点 1。这就会使得实际旅行时间变长。而 根据本文提出的 CEPO, RSA 总是可以找到能够在 恰当的时间避开不可通行点的路径，因此成功地找 到图 2 所给的极端天气动态变化情况下的理论最优 实际旅行路径：1→2→4→5→7→10。 4. 实验结果 为了验证本文所提出的方法，在此，我们以中 国海南省路网为例来研究 CEPO。海南省是中国的 第二大岛屿，拥有相对现代化的路网，路网主要包 括 4 大类，环岛的高速网络、遍布全岛的国道、省 级道路和县/村级道路。省级道路连接着各个城市 和县，而县/村级道路连接着各个镇和村。图 3（a） 中给出了海南岛的路网图。由于这里并没有其他外 界路径可以利用，相对封闭，因此就构成了非常适 合路径优化仿真实验的案例路网。众所周知，海南 岛每年都会有台风登陆，所以，在台风季节里，通 过有效的路径优化方法可以合理规划出行路线，提 高旅行安全性、舒适性和旅行效率。 (a) 海南省路网 (b) 从万宁市和三亚市登陆的台风运动示意图 图 3. 海南省路网图和台风运动示意图 台风：三 亚 西北： 37° 台风：万 宁市 西北 45° 时速： Published by Atlantis Press Copyright: the authors 202 M.K. Zhang et al. / Path Optimization in Dynamic Adverse Weathers 在实验中，我们首先模拟了从万宁市登陆的台 风，台风中心以每小时 30 公里的速度向西北方向 移动穿过海南岛（图 3(b)模拟了从万宁市登陆的台 风的运动情况），假设所有的距离台风中心 50 公 里的道路都将受台风影响而关闭。假设旅行者在高 速公路上的旅行平均速度是 80km/h，国道的平均 速度是 60km/h，省道的平均速度是 40km/h，乡村 道路平均速度是 30km/h。实验中，从路网里随机 选择旅行起点和终点对，旅行者从所选的起点城市 出发到终点城市处理紧急事情，因而需要以最短的 时间到达目的地。仿真结果见表 1。 表 1：台风从万宁市登陆向西北方向运动情景下的两种 方法仿真结果（PL 单位：km; CT 单位：s； TT 单位：h） 起 点 和 终 点 916 和 274 664 和 436 190 和 576 299 和 464 DPO PL 320.00 344.90 312.30 282.30 TT 9.10 9.85 8.92 8.06 CT 3.81 6.58 5.07 2.70 CEPO PL 257.80 189.60 241.80 220.30 TT 7.36 5.41 7.30 6.43 CT 5.68 4.29 5.58 5.04 注：起点 916：莺歌海市 终点 274：琼海市 起点 664： 儋州市 终点 436：陵水市 起点 190：文昌市 终点 576： 乐东市 起点 299: 安定市 根据参考文献[25],海南岛的三亚市也是台风经 常登陆的地方（如图 3(b)，从三亚登陆的台风的运 动方向为西偏北 37°，时速 30km/h），因此本研究 又模拟了台风从三亚市和万宁市同时登陆的情况， 然后随机选取起点终点对进行路径优化，实验结果 如表 2。 表 2：台风从三亚市和万宁市同时登陆情景下的两种方 法仿真结果（PL 单位：km; CT 单位：s； TT 单位：h） 起点和终点 664 和 436 190 和 576 800 和 464 408 和 51 DPO PL 无解 无解 无解 122.90 TT 3.51 CT 4.91 CEPO PL 189.50 241.90 148.00 122.90 TT 5.41 7.30 4.22 3.51 CT 7.13 9.45 5.55 1.39 注：190：文昌市 结点 576：乐东市 结点 800：昌河市 结点 464：保亭市 结点 408：琼中市 结点 51：临高市； 为了更好评估本文提出的 CEPO 和 RSA 方法， 我们将其与传统的 DPO 方法做对比。在 DPO 方法 中，不断重复的在线优化需要在每个仿真时刻根据 当 前 旅 行 者 的 位 置 和 台 风 中 心 位 置 ， 应 用 Dijkstra’s 算法计算当前的最优路径。如本文一直所 强调的，基于天气预报的台风中心移动路径，本文 的 CEPO 和 RSA 方法，仅仅需要在起点进行一次 性的离线优化就能找到最优的实际旅行路径。模拟 台风从万宁市登录，随机选取四个起点终点对的仿 真实验结果如表 1。图 4 是台风从万宁市登陆，旅 行者从起点 664 儋州市和到终点 436 陵水市的仿真 路径结果示意图。 表 2 是台风从三亚市和万宁市同时登录时随机 选取四个起点终点对的仿真实验结果。表 1、2 中 的 PL、TT 和 CT 分别代表路径长度、旅行时间和 计算时间。从表 1、2 和图 4 中，有以下观测结果：  CEPO 的 PL 和 TT 都比 DPO 的方法短。尤其， CEPO 的真实路径长度相比 DPO 缩短 20%- 45%，CEPO 的实际旅行时间也比 DPO 减少 18%-45%，所以，在 TT 和 PL 上，CEPO 都比 DPO 更有明显优势。  图 4 展示了 CEPO 方法为何比 DPO 方法有更 短的 PL 和 TT。在图 4 的实验中，起初 DPO 运行结果是从东南方向行走，由于海南岛的东 南部遭遇台风，DPO 又准备绕西北部避开走， 一段时间过后，最初绕西北部走的计划又被移 动到西北部的台风打乱，所以，DPO 又返回 绕东南部走。不同的是，CEPO 的离线优化可 以直接找到最优路线，并且在合适的时间避开 台风中心，不仅节约了旅行成本，又满足了最 小化时间的要求。  表 2 展示的是台风从三亚市和万宁市同时登录 的仿真结果，表二中的第四组结果显示，DPO 和 CEPO 的仿真结果是一致的，这说明：如果 动态天气变化过程不影响 DPO 的最优性时， CEPO 的求解结果与 DPO 的一致，从而间接 证明了 CEPO 的最优性。  在两个台风同时登陆海南省的时候，表 2 中除 第四组数据，剩余的其它三组仿真结果说明： DPO 在面对更复杂的动态障碍区时（例如， 多个台风同时登录情景）常常无法找到可行解 （更不要说最优解），只能停止运动等待台风 过境，但是这种坐以待毙的方法并不是旅行者 所希望的。相反，CEPO 结合台风预报信息， 离线优化，引入结点等待行为使得 CEPO 在处 理多个台风同时登录情景时，优化路径能力更 有突出优势。 Published by Atlantis Press Copyright: the authors 203 M.K. Zhang et al. / Path Optimization in Dynamic Adverse Weathers 图 4. DPO 和 CEPO 结果仿真结果图  表 1 和表 2 就 CT 而言，CEPO 拥有和 DPO 相 似的计算效率。值得注意的是，CEPO 的 CT 是某个起点终点对下采用 CEPO 方法离线优化 所用的时间，而 DPO 的 CT 是旅行者到达终 点时所有在线优化所消耗的时间总和。在本次 实验中，所有的 DPO 和 CEPO 都是在同一计 算机上运行。事实上，CEPO 的离线优化可以 很容易的采用更多更强大的硬件系统，然而 DPO 却受各种在线优化环境条件的限制而很 难采用大型复杂的硬件系统。所以，在现实生 活中，CEPO 有更好的潜力去实现更短的 CT。 5. 结论 本文主要提出了协同进化路径优化（CEPO） 和涟漪扩散算法（RSA）在动态极端天气情况下路 径优化中的应用。与现有的动态路径优化（DPO） 方法不同，新方法不需要在线实时优化。由于天气 变化的同时也会影响路网中各个结点和链接的状态， CEPO 在一次性的离线优化过程中的每一个单位时 间内都会同时考虑该时刻天气对路网的影响，所以， 离线优化的结果就能保证实际旅行路径的最优性。 RSA 是实现这种离线优化的关键，涟漪扩散优化原 理保证了新方法的最优性。以中国海南省台风为背 景，我们进行了仿真实验，实验结果清晰的表明了 新方法在旅行时间和计算时间上相对 DPO 的优势。 未来的研究将会考虑更复杂的路径网络，同时考虑 更多真实的天气情景以便更好的了解和挖掘新方法 的优势和应用潜力。 参考文献 [1] Wolfgang W., Weisser, Volkl W., Hassell M., The Importance of Adverse Weather Conditions for Behaviour and Population Ecology of an Aphid Parasitoid. Journal of Animal Ecology, 1997, 66:386- 400. [2] William H., Lam K., Hu S. and Sumalee, A., Modeling impacts of adverse weather conditions on a road network with uncertainties in demand and supply. Transportation Research Part B : Methodological , 2008, 42:890-910. [3] Keay K. and Simmonds I., The association of rainfall and other eather variables with road traffic volume in Melbourne, Australia. ccident Analysis &Prevention, 2005, 37:109–12433. [4] Keay K. and Simmonds I., Road accidents and rainfall in a large Australia city. Accident Analysis &Prevention, 2006, 38:445–459. [5] Guo S.J. The meteorological disaster risk assessment based on the diffusion mechanism. Journal of Risk Analysis and Crisis Response, 2012（2）:124-130. [6] Jiang T.H. Assessment method of emergency preparedness system vulnerability based on the complex network theory. Journal of Risk Analysis and Crisis Response, 2012，2（3）:195-200. （a）DPO 的结果 PL: 344.90km； TT：9.85h； CT：6.58s （b）CEPO 的结果 PL：189.60km ；TT： 5.41h； CT: 4.29s Published by Atlantis Press Copyright: the authors 204 M.K. Zhang et al. / Path Optimization in Dynamic Adverse Weathers [7] Lakshay, Agarwal A., Bolia N. Route guidance map for emergency evacuation. Journal of Risk Analysis and Crisis Response，2016, 6(3): 135-144. [8] Maarten K, Aalst V., The impacts of climate change on the risk of natural disasters. Disaster, 2005, 30:5-18. [9] Quan C., Trani A., and Srinivas, S., Modeling the Economic Impact of Adverse Weather into Route Flights. Journal of the Transportation Research Board, vol. 1788, doi: 10.3141/1788-10. [10] Krozel J., Lee C.and Mitchell J., Estimating time of arrival in heavy weather conditions. Guidance, Navigation, and Control Conference and Exhibit, Guidance, Navigation, and Control and Co-located Conferences, http://dx.doi.org/10.2514/6.1999-4232. [11] Ramalingam G. and Reps T., On the computational complexity of dynamic graph problems. Theoretical Computer Science, 1996,158:233–277. [12] Frigioni D., Marchetti-Spaccamela A. and Nanni U., Fully dynamic algorithms for maintaining shortest paths trees. Journal of Algorithms,2000, 34:251–281. [13] Frigioni D., Marchetti-Spaccamela A. and Nanni U., Semidynamic algorithms for maintaining single-source shortest path trees. Algorithm- mica, 1998, 22:250–274. [14] Narvaez P., Siu K. and Tzeng H., New dynamic algorithms for shortest path tree computation. IEEE/ACM Transactions on Networking, 2000, 8:734– 746. [15] Ramalingam G. and Reps T., An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms, 1996, 21:267–305. [16] Bauer R. and Wagner D., Batch dynamic single-source shortest-path algorithms: An experimental study. Experimental Algorithms, 2009, 51–62. [17] Taoka S., Takafuji D., Iguchi T. and Watanabe T., Performance comparison of algorithms for the dynamic shortest path problem. IEICE Transactions on Fundamentals of Electronics, Communication and Computer Sciences, 2007,90. [18] 叶柳儿，黄香香.连续时间 Markov 决策过程的均值- 方 差 优 化 问 题 . 中 国 科 学 ： 数 学 , 2014 ， 44 （8）:883-898. [19] 李俊平，张利娜.带有灾难和依赖状态控制的成批到 达成批服务排队模型. 中国科学：数学, 2015，45 （5）:527-538. [20] 黄维章，张锁春，雷光耀.城市火灾蔓延的数学模型 和计算机模拟.计算物理, 1993，10（1） [21] 马鑫，黄全义，刘全义.基于物联网的建筑火灾动态 监测方法. 清华大学学报（自然科学版）, 2010，52 （11）. [22] Hu, X.B., Wang, M., M.S. Leeson, E.L. Hines, and E. Di Paolo, A Deterministic Agent-Based Path Optimization Method by Mimicking the Spreading of Ripples. Evolutionary Computation, 2016, 24:319-346. [23] Hu, X.B., Wang, M., D. Hu, M.S. Leeson, E.L. Hines, and E. Di Paolo, A Ripple-Spreading Algorithm for the k Shortest Paths Problem. 2012 the 3rd Global Congress on Intelligent Systems (GCIS 2012), Wuhan, China,2012:202-208. [24] Hu, X.B., Sun, Q., Wang, M.S. Leeson, and Paolo E., A Ripple Spreading Algorithm to Calculate the k Best Solutions to the Project Time Management Problem. 2013 IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2013), 16-19 April 2013, Singapore. [25] 张凯荣, 宋长远, 陈钰祥.近 50 年来海南岛台风记录 及 其 灾 害 性 评 价 . 安 徽 农 业 科 学 , 2010 ， 38 （23）:12280-12882. Published by Atlantis Press Copyright: the authors 205 1. 前言 2. CEPO问题描述 3. 涟漪扩散算法（RSA） 4. 实验结果 5. 结论 << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /LeaveColorUnchanged /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA /BGR /CHS /CHT /CZE /DAN /DEU /ESP /ETI /FRA /GRE /HEB /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN /ITA /JPN /KOR /LTH /LVI /NOR /POL /PTB /RUM /RUS /SKY /SLV /SUO /SVE /TUR /UKR /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice