5.5.3　两阶段启发式算法的计算结果

表5-4列出了两阶段启发式算法的性能特征。性能特征包括：①问题的规模（列数、行数和0-1变量数）；②DM的计算结果（整数解、最优线性上界、最优差值、运算时间）；③受限BM的计算结果（两阶段算法的第二阶段）。从表5-4可以看出，列数、行数和0-1变量数都要比BM少得多。在第一阶段通过求解DM可以得到18个算例中的10个算例的最优解。但是，运算时间会随着阶段数量的增加而急剧上升。只能得到132个阶段的算例的近似最优解，却无法在给定的时间内得到它的最优解。132个阶段的平均最优差值3.33%。在启发式算法的第二个阶段中，所有的受限BM都能在5分钟内得到最优解。第一阶段的DM的目标值和第二阶段的受限BM的目标值差值约为5%。这可能是因为网络效应的影响：在第一阶段，所有的旅程都被分解为路段，DM的解比BM有更多的可售座位数。在BM中，如果一个旅程的任一个路段到达了其座位容量，整个这一旅程就不能再售，但是在DM中，即使一段旅程中的一段路段售完，但其他路段依然可售。

表5-4　两阶段启发式算法的计算结果(https://www.daowen.com)