枢纽机场停止准则

2019-09-11 275

      TSSPA算法痛过设定目标函数值持续未改善次数或运算达到预先设定的最 大选代次数来中止运算。 综上所述,求辩立MP五M”的启发式TSSPA算法的具体计算步骤如下。

      步骤1应用上述初始解的构造方法产生初始解,并设为当前解和当前最 

      步骤2依次将(加二P)个轮辐机场与当前枢组集中的力个枢组作单一交换: 产生p(m一力)个候选解集,可见个数小于枚举法的I1个解; 

      步骤3从候选解集中选择最好的候选解,此解若优于当前最好解,转步骤6, 否则执行步骤4。 

      步骤4判断此解是否为禁忌,若是则转步骤5,否则转步骤7。

      步骤5若所有候选解都禁忌,将最好候选解作为当前解,转步骤8,否则把非 禁忌的最好候选解作为当前解,转步骤8。 

      步骤6更新当前最好解。 

      步骤7更新当前解。

      步骤8更新禁忌名单。 

步骤9是否达到停止条件,若是则输出结果,计算结束;否则转步骤2。

        例3-7在例3-6的15个城市中再增加5个城市,共20个城市。在20个城 市的基础上构建枢纽航线网络。城市编号如表3-7所示。在本例中同样把距离直 接作为成本来看待。城市间距离数据和航空运输流量数据参见附表3-5和附表3- 6。折扣系数a分别取0.4、0.6、0.8,枢纽数目p分别取23、4 解利用上述TSSPA算法求解,用Matlab编程计算,算法的禁忌长度TL= 7,算法终止规则是:连续5次保持相同最好解或最大迭代次数达到30次即终止运 算。具体运算结果如 计算结果可以得出以下结论。 

     (1)利用启发式TSSPA算法均可在0.09s内求得所有问题的最优解,而利用 ILOG优化软件则计算时间较长。需要注意的是,由于计算机更新换代很快,这里 的计算时间本身已经没有参考价值,但用于比较计算效率还是有意义的。 

     (2)利用ILOG优化软件的求解时间随着问题规模的变大而快速增长,而利 用TSSPA算法的求解时间随着问题规模的变大增长较慢,因此TSSPA算法可用 来解决大型问题。 

    (3)TSSPA算法给出了与ILOG同样的最优解(除个别枢纽城市外,此时有 多个最优解,两种方法各获得了一个)。 由于算例是无容量限制的严格的枢纽航线网络优化问题,且算例的规模相对 较小,就这样ILOG的精确算法的运算时间也是禁忌搜索算法TSSPA的100倍 以上。对于大规模的网络优化问题,TSSPA算法的速度优势更明显,但不一定保 证能获得最优解。


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

QQ咨询

微信二维码

客户服务热线

18824138009