枢纽机场停止准则

      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算法的速度优势更明显，但不一定保 证能获得最优解。