枢纽航线网络三下模型

2019-09-09 1162

     前面建立的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个变量。与四下标模型比较可以发现, 无论是约束条件数、变量数还是运算时间,三下标模型都小于四下标模型。当问题 的规模进一步扩大后,这一点将会更加明显。


电话咨询
咨询留言
在 线 客 服 X

QQ咨询

微信二维码

客户服务热线

18824138009