在灾害辅助决策中，最重要的是在有限的撤离安置点和连通道路网中，生成受灾人口快速和安全撤离的应急预案，这是一个典型的优化问题，而影响决策的主要因素是受灾区面积、人口数、安置点容量、安置点数量和撤离路径等。解决最优路径的方法很多，如图论方法、动态规划法、A*算法、遗传算法和神经网络等。在图论中有几十种求解算法，其中Dijkstra算法是目前多数系统解决最优路径问题采用的理论基础，被GIS系统广泛采用。
单源最短路径问题是：给定带权的有向图G=（V，E）和图中节点s∈V，求从s到其余各节点的最短路径，其中s称为源点。路径长度是指路径上的边所带权值之和，而不是路径上的边的数目，并假定边上的权值为非负值。
从广义上讲，源点到某一个节点的任何一条路径可视为一个可行解，其中长度最短的路径是从源点到该节点的最短路径。从源点到其余每个节点的最短路径构成了单源最短路径问题的最优解。因此，问题解的形式可以认为是：L=（L1，L2，…，L-1），只要每个分量都是源点到某一个节点的路径，L就是问题的一个可行解。
Dijkstra算法提出了按路径长度的非递减次序逐一产生最短路径的算法：首先求得长度最短的一条路径，再求得长度次短的一条路径，依此类推，直到源点到其他所有节点之间的最短路径都已求得为止。
在风暴潮系统中，受灾区域的人员需要同时迅速撤离到多个安置点，而Dijkstra算法只方便用于求解单条最短路径，因此基于Dij kstra算法做了以下改进：①求出受灾区域到各个安置点的最短路径；②受灾人员多目标撤离。
图5-21 受灾养殖区到各安置点的路线
1）改进Dijkstra算法求最短路径问题
例：如图5-21所示，一受灾养殖区V1附近有5个节点V2、V3、V4、V5、V6，其中节点V3 、V5 、V6是安置点。现计算V1到3个安置点的最短路径。
按照Dijkstra算法计算最短路径的步骤如下：
（1）设V1为源点，则S=｛V1｝。可知：最短的那条最短路径是3条边＜V1，V2＞，＜V1，V4＞，＜V1，V5＞中权值最小的边＜V1，V2＞。所以第一条最短路径应为（V1，V2），即源点V1到节点V2的最短路径，其长度为10。
（2）将节点V2加入S中，得S=｛ V1，V2 ｝。在V2连通的两条边＜V2，V3 ＞，＜V2，V4＞中取得权值最小的边＜V2，V4＞，则最短路径为（V2，V4），对当前最短路径进行修正
(www.xing528.com)
即源点V1到节点V4的最短路径是（V1，V2，V4），其长度为25。
（3）将节点V4加入S中，得S= ｛V1，V2，V4｝，求下一条最短路径。从V4出发的边＜V4，V3 ＞，＜V4，V5＞和＜V4，V6＞中，最短的为＜V4，V5 ＞，则最短路径为（V4，V5）。对当前最短路径进行修正即源点V1到节点V5的最短路径是（V1，V2，V4，V5），其长度为35。同理，可求得：源点V1到节点V3的最短路径是（V1，V2，V4，V3），其长度为45；源点V1到节点V6的最短路径是（V1，V2，V4，V6），其长度为65。
2）基于受灾和安置点情况的算法优化
根据受灾的实际情况，包括受灾点需撤离的人数、受灾点到各个安置点的最短路径长度以及各个安置点的容量（即最多可容纳人数），需要对Dijkstra算法做以下改进：
（1）在人员撤离过程中，可能需要撤离到多个安置点，所以将受灾点到各个安置点的最短路径长度按降序排列。
根据以上例子求出的结果，将受灾点到各个安置点的最短路径按路径长度降序排列，见表5-8。
表5-8 受灾点到各安置点的最短路径
（2）人员优先撤离到路径长度最短的安置点，再撤离到次短的安置点，直到需撤离人员全部安置完。
每个安置点都有容量，撤离的过程中还要结合安置点的容量进行安排。最终的受灾人员安置情况见表5-9。
表5-9 根据安置点容量最终选择的最优路径
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
