下载掌阅APP，畅读海量书库
立即打开
对于任何启发式算法的评估都涉及对算法的表现等方面相关的一系列标准的比较。这些标准通常包括运行时间、最终解的质量、算法实现的难易程度、算法的稳定性，以及算法的灵活性（Barr等，1995；Cordea等，2002）。由于启发式算法最终的目的是用来求解实际运作当中所面临的问题，灵活性就成为一个非常重要的考量标准。一个较好的算法应该能够很好地应对实际运作中出现的种种变化，如不断出现的新的约束条件和目标函数。而算法的稳定性是指算法不应该对不同问题之间的特性差异过度敏感，也就是说算法对于所有的算例都应该表现出类似的作用，不能是在某一些算例中表现较好而在另外一些算例中表现较差。因此，一个好的算法需要在应用到每一个算例中都有较好的表现。这一点在路径优化算法中尤为重要，由于很多启发式算法是针对动态问题的，算法实现过程中涉及很多随机元素，如参数值的确定方法是随机的。因此，针对同一问题，算法在每次实现时其结果也是不相同的，这使得分析和判断结果的难度进一步增加。现有文献中，很多学者多采用所有实验结果中最好的结果，但这通常会对读者在算法优劣上的判断产生误导。因此，对于非确定性的启发式算法，我们一般应该采用所有实验结果的平均值作为比较不同的启发式算法的一个基准。同时，也需要报告实验结果中最差的情况。
在选择不同的启发式算法时，用来产生高质量的解的计算时间也是一个非常重要的评价标准。同样通常由目标函数的取值决定的最终解的质量，也是很重要的。由于启发式算法应用于那些通常不能用精确算法求解的大规模复杂问题，因此准确性度量是启发式算法所求解与最优解之间的差异。如果算法只是用来提供可行解的，那么启发式算法可以求得可行解的能力就是一个重要的衡量标准。
通常，计算时间和解的质量之间是此消彼长的关系，就像跷跷板的两头。因此，我们会在两者之间进行权衡。通常计算时间越长，启发式算法得到的最终解的质量也就越高。因此，我们的权衡结果应该是在一个较为合理的，并且可以接受的时间内找到一个质量较好的解。一般来说，计算时间和解的质量之间的权衡可以看成是多目标优化问题，即目标函数中包含两个相互矛盾的目标。较为直观的判断方式是通过在二维坐标系中进行描点来进行，其中横轴为启发式算法的计算时间，纵轴为解的质量。在这样的二维空间中，如果在两个维度上都不存在更好的点，那么现在的这个点就被称为帕累托最优（Pareto Optimal）。在多种启发式算法的选择过程中，帕累托最优的选择大多取决于决策者的偏好及对当前情况的判断。
当前，最为普遍的评估启发式算法中解的质量的方法是通过实证分析。其基本的思想是通过广泛的算例来对启发式算法进行全面的测试，从而得到一个对算法全面的评价。为了能够得到一个统计学上有意义的评价结果，实验设计需要能够覆盖不同类型的算例和算法的不同级别，从而能够对算法中参数的不同取值进行测试，并进行合理的比较。但是，在实际实现的过程中，我们可能会碰到各种各样的困难。其中，最重要的就是保证公平竞争。启发式算法实现所用的计算机不同将会导致不同的计算时间和解的质量。更加难以解决的问题是在编程过程中使用的不同技巧也将直接影响计算时间和解的质量。另一方面的困难就是我们前面提到的，通常作者会在文章中报告算法的最好结果。有些作者并不在文章中报告运行算法的次数及计算时间。在这些情况下，很难仅通过最好结果来判断启发式算法的效率和效果，从而也无法对多种启发式算法进行比较。
与多数启发式算法类似，求解路径优化问题的启发式算法的评价标准通常包括两个维度：准确性和速度。同时，文献中也经常把简单和灵活性作为评价路径优化问题启发式算法有效性的重要标准。下面分别对这4个属性进行分析。
由于启发式算法通常应用于不能用精确算法求解的大规模复杂问题，因此准确性度量是启发式算法所求解与最优解之间的差异。在路径优化问题中经常无法求得全局最优解或是较为准确的下界，多数算法准确性的度量需要通过与现有文献中提供的最好的解进行比较。综观现有文献，学者们通常会在文章中报告所有参数组合中最好的结果，或是基于不同初始解的所有解中最好的结果。此外，由于结果进位方法的不同，结果之间的比较很难得到较为可靠的准确性。与此相关的一个问题是一致性。一般认为好的算法是在任何情况和算例中都可以得到比其他算法更好的结果，而不是只在部分算例中取得较好的结果。
计算速度对于路径优化问题的重要性主要取决于该问题所对应的决策层级，以及对于结果准确性的要求。一个极端的情况是像快递送取包裹或者救护车的路径优化等实际应用问题都要求算法较快的得出结果，甚至需要得到实时结果。Gendreau等在其论文中描述了并行算法在救护车路径优化问题中的重要应用，因为这样的实际问题需要平均每3分钟求解一次。另一个极端情况是公司的长期计划中所涉及的决策，如车队规模。这样的决策通常每隔几个月才进行一次，这样我们就可以采用计算时间长达数小时甚至数天的算法。多数的实际应用介于这两种极端情况之间，一般来说，对于一个需要每天进行决策的问题投入10～20分钟的计算时间是较为合理的。
很多路径优化问题的启发式算法未得到广泛的应用和认可的一个重要原因是算法本身太复杂从而增大了理解和编程的难度。尽管要求文章提供算法所有的细节有些不切实际，但至少应该提供足够的信息使得程序员可以理解并对算法进行编程。但是很多算法的描述并不能提供足够的信息。经典的CW算法之所以得到较为广泛的实际应用主要由于其思想简单易懂且易于实现。因此，算法需要在保证较高质量结果的基础上尽量简单且易于理解和实现。
如果一个算法设计很多参数则不容易理解且不易被广泛利用。这是现有文献中的算法所存在的一个通病。为了获得更好的试验结果，学者们不断增加参数的数量，但有些参数并不是算法实现所必需的。因此，学界一直提出限制算法中参数的数量并且要求算法中的参数对终端客户有意义。例如，控制局部搜索改进算法迭代次数的参数是大家都较为容易理解的，而控制一个内部循环执行次数的参数则对终端客户意义不大。对于参数滥用问题有两个简单的解决方法：一是当算法中需要多次使用某一参数时，可以将参数设定为固定值；二是可以采用自适应的参数值设定方法。
一个好的路径优化启发式算法需要具有足够的灵活性来处理实际应用问题中所碰到的各种约束。文献中有些算法虽然主要是用来求解考虑时间窗的路径优化问题，但通常会对算法的扩展进行说明进而求解考虑其他约束的路径优化问题，然而所求得解的质量可能会由于其他约束的加入而大大下降。
对于多种约束的处理方法，通常可以将其作为惩罚项加到目标函数中。原本的目标函数F（x）为行驶成本，而新的目标函数F′（x）为F（x）和约束惩罚项之和。例如，Q（x）和D（x）分别为当前解x所对应的载重和路线总时长违反约束的程度，则新的目标函数可以定义为F′（x）=F（x）+αQ（x）+βD（x），其中α和β为自适应惩罚系数。α和β的初始值设定为1，随着搜索算法的进行，α和β的值会根据解的状态（可行与否）周期性地增加或减少。这样的算法设计使得搜索过程既包含可行解也包含不可行解，从而大大降低了最终收敛到局部最优解的可能性。同时，也使得我们可以采用较为简单的位置改变，如将一条路线上的一名客户从该条线路删除并添加到另外一条线路上。如果算法需要确保搜索过程中所有的解都可行，则会限制我们应用简单的位置改变，尤其是在其他附加约束较为严格的情况下。可行解的要求会迫使我们采用较为复杂的位置改变。从这个意义上来讲，简单的算法设计可以帮助我们达到更好的算法灵活性。