应急设施布局优化理论与应用-基于轴辐网络的模型改进

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

【摘要】：Campbell提出的MAHSCP模型有n4+n个变量、2n4+n2个约束式，属于复杂的混合整数规划模型，当节点数超过一定数量时，模型求解面临很大问题。翁克瑞[107]根据MAHSCP模型进行了改进，提出了有n2+n个变量、3n2个约束式的新的多分配枢纽覆盖模型。相对Campbell的MAHSCP模型，MAHSCP2模型减少了输入变量，从而以减少问题的输入规模，节约计算内存和时间。

多分配枢纽站集合覆盖问题的模型最初由Campbell（1994）[104]提出，该模型是一个由O（n4）个变量与约束式组成的混合整数规划模型。

在构建的模型中设给定的网络中G（N，A），A为所有边集合，N={1，…，n}为所有节点的集合；令cij表示节点i和j之间的直通成本，hij表示从节点i到节点j的客运流量；J={（i，j）|hij＞0，i，j∈N}表示所有的OD点对的集合；βij表示从i到j的流动成本限制，再令，表示从i到j经枢纽站k，m所花费的成本、时间和距离，其中，α（0≤α≤1）表示枢纽之间流动所产生的规模效益或折扣，若k=m，单点中转。

表示流i-j能否被备选枢纽站k和m所覆盖。再令表示流i-j经过枢纽站k和m的流量占hij的比例，当k=m时，表示单点中转。再令Fk表示k点的建造成本。同时，另二进制变量Xk=1表示在k点选址，否则Xk=0。则多分配枢纽集合覆盖模型（Multi-Allocation Hub Set Covering Problem，MAHSCP）如下：

目标函数式（5-9）寻求建站成本最小，约束条件式（5-10）确保所有的O-D流都被服务，约束条件式（5-11）、式（5-12）表示只有当k、m被选中时才能允许流i-j被k、m覆盖，约束条件式（5-13）是0-1整数约束。

Campbell提出的MAHSCP模型有n4+n个变量、2n4+n2个约束式，属于复杂的混合整数规划模型，当节点数超过一定数量时，模型求解面临很大问题。翁克瑞[107]根据MAHSCP模型进行了改进，提出了有n2+n个变量、3n2个约束式的新的多分配枢纽覆盖模型（记为MAHSCP2）。

在MAHSCP2中去掉了变量，引入0-1变量Zij，当Zij=1表示流i-j被所选的枢纽站所覆盖，否则，Zij=0。引入变量0-1变量Wkm，当Wkm=1表示点k，m同时被选中为枢纽点，否则Wkm=0。构建新的MAHSCP2模型如下：

目标函数式（5-14）表示建枢纽站的费用最小；约束条件式（5-15）保证至少有一个或者有一对枢纽站能够覆盖流i-j；约束条件式（5-16）、式（5-17）的作用是定义变量Wkm，确保只有当Xk与Xm都等于1的时候才能允许Wkm=1。

相对Campbell的MAHSCP模型，MAHSCP2模型减少了输入变量，从而以减少问题的输入规模，节约计算内存和时间。

上述多分配枢纽覆盖模型，是以总成本最小为目标函数，没有体现时间约束性，本节在有绕道约束的单分配枢纽覆盖模型的基础上，借鉴MAHSCP2模型，构建了有绕道约束的多分配应急枢纽集合覆盖选址模型（γ-MAHSCP），来优化枢纽网络中的拥堵、破坏等问题。

应急设施布局优化理论与应用-基于轴辐网络的模型改进

相关推荐