基于轴辐网络的重大突发事件应急设施布局优化算法

2023-09-19 理论教育版权反馈

【摘要】：对于γ-MAHSCP模型，仍属于NP-Hard问题，可采用启发式算法进行模型求解。本书采用分散搜索算法进行求解，分散搜索算法是一种进化算法，依靠类似遗传算法的进化机制，通过迭代向最优解收敛。通过上述分散搜索算法，能够很好地求解γ-MAHSCP模型。该模型得出的结果与γ-SHSCP模型求解不同，因为非枢纽点的分配方式不同，枢纽点的布局也不尽相同。

设给定的完全网络G，N={1，…，n}为网络中所有节点集合；J=[（i，j）|i，j∈N]表示所有的O-D对的集合。应对重大突发事件的枢纽集合覆盖选址模型是在节点集合N中，存在枢纽候选集合H（H⊆N），从H中选择一定数量的节点作为枢纽点，将其余的非枢纽点以多分配方式分配给枢纽点。模型中tij、Xkk、α、rk、T、rk、fk、γ*等参数、变量的假设意义同前文所界定，同时重新定义变量：

如果k=m表示单点中转。则构建的γ-MAHSCP模型如下：

目标函数式（5-19）表示设立的枢纽点的数量最少，保证具有重要程度的候选枢纽点越易成为枢纽点；约束条件式（5-20）表示保证所有的O-D流至少被一对或一个枢纽站覆盖；约束条件式（5-21）定义变量Wkm；约束条件式（5-22）说明变量是0-1变量。

对于γ-MAHSCP模型，仍属于NP-Hard问题，可采用启发式算法进行模型求解。本书采用分散搜索算法进行求解，分散搜索算法是一种进化算法，依靠类似遗传算法的进化机制，通过迭代向最优解收敛。从一组初始解中按照一定标准选择一组参考解，在每一次迭代中，分散搜索算法在参考解中选择一对解作为子集，通过对子集的组合操作产生新解，若解的质量有所改善，则用其替换参考解中的最差解，其流程如下：

（1）按照多样化生成算法与改进算法产生q个不同的初始解集Q。

（2）在初始解中选择b个“最好”的解构成参考解集Θ。“最好”的解是指目标值最好，且要求选择的参考解服从多样化原则，尽量分散以期望其后代能覆盖解的全局空间，避免陷入局部困境。将参考解根据目标函数值从小到大成x1，x2，…，xb排列。

（3）令Θ0=Θ，在参考解Θ中产生一组子集，每个子集包括两个解。对所有的子集进行组合操作产生新解y；对y进行一次改进算法计算，将计算结果添加到新解集Ψ中。

（4）对所有的x∈Ψ，如果f（x）小于f（xb），则将x替换参考解集中的xb，每替换一次即更新Θ中的xb与x1。

（5）如果Θ=Θ0，算法结束，最终解为Θ中的x1；否则返回步骤（3）。

通过上述分散搜索算法，能够很好地求解γ-MAHSCP模型。该模型得出的结果与γ-SHSCP模型求解不同，因为非枢纽点的分配方式不同，枢纽点的布局也不尽相同。通过多分配枢纽覆盖选址模型得出的布局方案能够有效解决枢纽拥堵问题。但是该策略的缺点是：由于实施布局属于中长期战略，布局完成后很难重新改动，即使能够改动，也需要很大费用。如果开始就按照多分配方式进行布局，则潜在的枢纽点必须建成具有枢纽功能的设施点，但由于重大突发事件的概率较低，经济预算也非常高，容易造成很大的资源浪费。解决轴辐网络拥堵问题也可以不调整枢纽点布局，只需增加非枢纽点的分配方式即可，这就是本书针对拥堵问题提出的第二种解决策略。

基于轴辐网络的重大突发事件应急设施布局优化算法

相关推荐