枢纽航线网络三下模型

     前面建立的UMpHMP模型是NP-hard问题，目前没有有效的算法。为了减少计算时间，Ernst和Krishnamoorthy(1998a，1998b)为枢纽网络建立了三下标的 数学模型，大大减少了变量和约束的个数，提高了求解的效率。 这个模型不采用流量的比例作为流变量，而直接用流量为流变量，并对汇运、 转运和分运分别设置不同的变量。

     令Z4为OD流的汇运流变量，即从始发地机 场i到枢纽机场k的流量，Ya是从轮辐机场i运出的转运流量，X是O-D对(i，j) 从枢纽机场l分运到目的地j的流量，再令O是从始发地机场i运出的总流量， N={1,2,…，n}是机场集合，则三下标枢纽网络优化模型如下； minC[2xCaZx+22aCuYu+22oC,x, O.表示起始于机场i的流量，因此二W，=0；式（3-15)表示共有p个枢 纽；式（3-16）~式（3-18）是流量平衡方程，保证所有的O-D流全部由起始机场到目的地机场，其中式（3-16）表示从始发机场i出发，经过分配连接到各枢纽机场 的汇运流量之和必须等于O，式（3-17）表示O-D对（i，j）经过各枢组机场l中转 后分运到目的地机场j的流量之和必须等于W，，式（3-18）表示从始发地机场i运 出的流量，在枢纽机场k中转的运进流量必须等于运出流量；式（3-19）表示从始发 机场i出发，经航节i→k汇运时，k一定是枢纽城市，式（3-20）表示如果O-D对(i、 j)经过机场l中转分运到目的地机场j，l一定是枢纽；式（3-21）表示流变量是非 负变量，式（3-22）要求y；是0-1型变量。 这个模型尽管采用了三下标变量，但任一O-D对仍然至多经过汇运、转运和 分运等三个航节完成运输任务，因此最多两次中转。

     变量数从四下标的O（n1)个 减少为O（n3)个。如果n=100，那么流变量数从1亿个减少到100万个。约束条 件数从四下标模型的（2n3+n2+1）减少到三下标模型的(n3+3n2+n+1)，当n= 100时，四下标模型大约有201万个，三下标模型大约有103万个。可见，三下标 模型的规模确实下降不少。 例3-4在例3-3同样的条件下，采用三下标模型对枢纽航线网络进行优化 设计。构建三下标模型如下： 同样应用ILOG/CPLEX求解上述模型，得到的结果为：y2=y；=1，即以北京 和广州作为枢纽；最优的总成本是950364元，这与四下标模型得到的结果相同；流 变量的解如下：Z2=106，Z2=354,Z2=97，Za=46，Z46=22，Z4s=231，Z2=63， 模型中一共有331个约束条件和474个变量。与四下标模型比较可以发现， 无论是约束条件数、变量数还是运算时间，三下标模型都小于四下标模型。当问题 的规模进一步扩大后，这一点将会更加明显。