三下标模型的求解算法

2019-09-10 1169

      三下标模型的规模比四下标模型小,因此这里以三下标模型的求解为例,讨论精确算法。四下标模型的求解算法可以仿照这里的算法进行设计。由于各 0-D对的运输路线最多有2次中转3个航节组成,在选定了枢组机场后,可以首 先构建一个四层网络G’,如图3-18所示,该网络很适合计算O-D对(i,j)之间的 最短路。 四层网络(/按下述方式构造:对于ViEN,在第一层用i表示,在第二层用i 表示,在第三层用”表示,在第四层用”表示。第一、第四层包含了网络G=(N, A)所有n个城市的节点,第二、第三层仅包含候选枢纽机场集合M的节点。各层 同层内的点不连接,只有相邻两层之间的点才用边连接。

      具体的连接方式为,层与层之间对应相同的城市直接连接,边长(航线运输成本)为0;第一层的非枢纽城市和第二层的所有枢纽城市都连接,为汇运边,边长为XC,;第一 层的枢纽城市只与第二层相同的枢纽城市连接,边长为0;第二层的枢纽城市和编 三层的枢纽城市分别连接,为转运边,边长为aCm;第三层与第四层的连接方式与 第一层及第二层的连接方式类似,只是边长变为Cm。给出了G在INl三 7时的连接示意图,其中城市2、6、7已选为枢组,并给出了以城市1为起始城市的 连接方式,其他城市的连接情况类似。这样就得到了一个四层网络,其中O-D对 (i,j)的运输路线将是>k’一m”一”,令C一表示i到j”的最短路长度,则对应的 最短路径就是最优运输路径,所有O-D对的最优运输路径构成了该组枢纽机场情 况下的航线网络。第一层的i和第四层的”表示同一个机场,因此不允许组成O-D 对(i,i")。 当四层网络G'中p个枢纽选定时,可用Floyd-Warshall最短路算法求解O-D 流间的最短路,具体步骤如下。 

     步骤1计算C·=mig{aCu+aC,},VkEH,jEN,Cw=0,VkEH,式中只包含分运,没有汇运的路径,其中H是已选为枢纽的力个机场组成的集合。 

     步骤2计算C·=2ip(xCa+Cx·},Vi,jEN,其中j”、”、”均对应N中的 j。

     这个由网络G求得的C,即网络G中从i到j的最短路。 利用四层网络最短路算法,可以找到任意给定的枢纽机场集合HCM情况下 的最优航线网络。下面给出求解无容量限制的枢组航线网络优化模型的计算 步骤。 步骤1选取合适的城市属性指标体系和指标权重,通过多属性决策方法对 各城市进行排序。 步骤2根据对各城市的排序结果,选出候选枢组城市集M。 步骤3从城市集M中任选力个作为枢纽集H,利用上述Floyd-Warshall最 短路算法求解相应的最短路问题,如此反复计算,则共得到Ci1个解,其中目标 函数值最小的解即为所求(当|Ml很小时,也可借助优化软件直接求解)。 步骤4对最优解进行必要的评估,给出枢纽航线网络的设计方案。 以上给出的算法是枚举法。由于枢纽机场候选集较小(通常10个左右),其可 能的组合也是有限的(三枢纽时不超过120个),采用Floyd-Warshall最短路算法 对每个枢纽组合情况进行网络计算也是很有效的。因此,枚举法能够在较短时间 内求得最优解,这个最优解是精确的全局最优解。


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

QQ咨询

微信二维码

客户服务热线

18824138009