下载掌阅APP，畅读海量书库
立即打开
在对上述用爬山算法求解无时限单向配送车辆优化调度问题而设计的各种解的表示和评价方法、邻域选点方法以及算法终止准则进行综合分析比较的基础上，作者在设计该问题的爬山算法时，具体采用了以下算法策略。
（1）解的表示方法：采用客户直接排列的表示方法。
（2）生成初始解的方法：采用由计算机随机生成的方法。
（3）解的评价方法：采用公式（2.12）对解进行评价，即首先根据无时限单向配送车辆优化调度问题的约束条件，将解中的客户依次纳入到各台车辆的配送路径中，并得该解对应的配送路径方案的不可行路径条数M和目标函数值Z；将M和Z代入公式（2.12），即可计算出该解的评价值E。
（4）邻域操作方法：采用两交换法实施邻域操作。
（5）终止准则：采用迭代指定步数的终止准则。
根据上述无时限单向配送车辆优化调度问题的爬山算法策略，作者设计了该算法的结构（见算法2.1）。
算法2.1 无时限单向配送车辆优化调度问题的爬山算法的结构
{输入无时限单向配送车辆优化调度问题的已知条件；
输入算法的运行参数，如终止迭代步数T、对不可行路径的惩罚权重P w 等；
随机产生一个初始解，将其作为当前解S，迭代步数t=0；
利用解的评价方法计算解S的评价值；
根据上述无时限单向配送车辆优化调度问题的爬山算法的结构，作者编制了实现该算法的C语言程序，该程序的模块结构如图2.2所示。
图2.2 无时限单向配送车辆优化调度问题的爬山算法的模块结构图
各模块的作用如下。
（1）主控模块。该模块通过调用录入原始数据模块、产生初始解模块、爬山模块和计算结果输出模块，实现全部算法功能。
（2）录入原始数据模块。该模块用于输入问题的已知条件和算法运行参数，问题的已知条件包括客户总数、配送车辆总台数、配送中心与客户之间及客户相互之间的距离、各客户的货物需求量、车辆的最大载重量、车辆一次配送的最大行驶距离等；算法的运行参数包括终止迭代步数、对不可行路径的惩罚权重等。
（3）产生初始解模块。用于按照客户直接排列的解的表示方法，随机产生1个1～L间的L个互不重复的自然数的排列，该排列即为一个初始解，将该初始解作为当前解。该模块还要调用解的评价值计算模块以计算当前解的评价值。
（4）爬山模块。该模块首先要用两交换法对当前解实施邻域操作，从而得当前解的一个邻居，然后通过调用解的评价值计算模块计算该邻居的评价值，若该邻居的评价值小于当前解的评价值，则用该邻居代替当前解，并用该邻居的评价值代替当前解的评价值。
（5）计算结果输出模块。该模块用于输出程序的计算结果，即算法求得的最终解所对应的配送路径方案和目标函数值。
（6）解的评价值计算模块。该模块的作用是根据问题的已知条件，得到待评价解所对应的配送路径方案，进而得到该方案的不可行路径条数和目标函数值，并利用公式（2.12）计算出该解的评价值。
作者利用无时限单向配送车辆优化调度问题的爬山算法C语言程序，对参考文献中的一个实例（见实例2.1）和两个由计算机随机生成的实例（分别见实例2.2和实例2.3），利用主频为133MHz，内存为16MB的计算机（如无特别说明，本书的实验计算结果均是采用该配置的计算机得到的）进行了实验计算。
【实例2.1】某配送中心有2台配送车辆，其载重量均为8t，车辆每次配送的最大行驶距离均为50km，配送中心（其编号为0）与8个客户之间及8个客户相互之间的距离d ij 、8个客户的货物需求量q j （i、j=1，2，…，8）均见表2.1所示。要求根据以上条件合理安排车辆配送路线，使配送总里程最短。
表2.1 实例2.1的已知条件表
根据实例2.1的特点，在用爬山算法对其求解时采用了以下运行参数：对不可行路径的惩罚权重取100km，算法的终止迭代步数取200。对实例2.1随机求解10次，得到的计算结果见表2.2。
表2.2 实例2.1的爬山算法计算结果表
由表2.2可以看出：用爬山算法对实例2.1的10次求解中，每次都在200步之内得到了问题的最优解或近似最优解，这些解的质量均优于节约法所得的结果（79.5km），其配送总里程的平均值为69.55km，比节约法的计算结果少12.5%，其中有3次计算还得到了该问题的最优解67.5km，所对应的配送路径方案为：路径1∶0-4-7-6-0；路径2∶0-2-8-5-3-1-0。从计算效率看，10次求解的平均计算时间（该计算时间包括将中间计算结果存入文本文件和在屏幕上显示的时间，即纯计算时间比该时间还要少）仅为0.05s，首次搜索到最终解的平均迭代步数仅为61.5。可见，对于规模不大（客户数小于10）的无时限单向配送车辆优化调度问题，利用爬山算法可在很短的计算时间内用很少的迭代步数得到问题的最优解或近似最优解。
【实例2.2】设配送中心和20个客户分布在一个边长为20km的正方形地域内，每个客户的货物需求量都在2t及其以下，配送中心有5台配送车辆，车辆的最大载重量均为8t，车辆一次配送的最大行驶距离均为50km。作者利用计算机随机产生了配送中心和20个客户的位置坐标以及各客户的货物需求量，其中配送中心的坐标为（14.5km，13.0km），20个客户的坐标及其货物需求量见表2.3。要求合理安排配送车辆的行车路线，使配送总里程最短。为简便起见，本书设各客户相互之间及配送中心与客户之间的距离均采用直线距离，该距离可根据客户和配送中心的坐标计算得到。
该问题包括20个客户，其规模比实例2.1大了许多，由于客户的全排列数多达2.433×10 18 个，受计算时间的限制，该问题用穷举法根本无法求解。根据该问题的特点，在用爬山算法对其求解时采用了以下运行参数：对不可行路径的惩罚权重取300km，终止迭代步数取2000。对实例2.2随机求解10次，得到的计算结果见表2.4。从表2.4可以看出：用爬山算法对实例2.2的10次求解中，都在2000次迭代之内得到了问题的可行解，其配送总里程的平均值为128.0km，平均使用的车辆数为3.9辆，比已知条件平均节省1.1辆车。其中第6次求解得到的解的质量最高，其配送总里程为118.7km，仅需用3台车辆配送，对应的3条配送路径分别为：路径1∶0-13-6-11-20-17-3-0；路径2∶0-8-19-16-15-9-7-0；路径3∶0-1-12-2-14-5-4-10-18-0。从解的质量看，尽管用爬山算法可以求得实例2.2的可行解，但总体上解的质量不是很高，作者运用其他算法得到的实例2.2的最好解的配送总里程为101.9km，爬山算法求得的平均配送总里程要比该最好解多25.6%，爬山算法求得的最好解的配送总里程也比该最好解多16.5%。另外，爬山算法的计算结果也不太稳定，10次求解中，最差的解的配送总里程比最好的解多出24.6km，达20%。从计算效率看，10次求解的平均计算时间仅为0.33s，首次搜索到最终解的平均迭代步数仅为893.5。可见，对于规模较大（客户数为20左右）的无时限单向配送车辆优化调度问题，利用爬山算法也可在很短的计算时间和较少的迭代步数内得到问题的可行解，但总体上解的质量不是很高，且计算结果不太稳定。
表2.3 实例2.2的已知条件表
表2.4 实例2.2的爬山算法计算结果表
【实例2.3】设配送中心和100个客户分布在一个边长为20km的正方形地域内，每个客户的货物需求量都在2t及其以下，配送中心有20台配送车辆，其中10台车辆的最大载重量均为8t，车辆一次配送的最大行驶距离均为50km；另10台车辆的最大载重量均为10t，车辆一次配送的最大行驶距离均为60km。利用计算机随机产生了配送中心和100个客户的位置坐标及各客户的货物需求量，设配送中心的坐标为（10.18km，8.08km），100个客户的坐标及其货物需求量见表2.5。要求合理安排配送车辆的行车路线，使配送车辆的总吨位公里数最少。为简便起见，仍设各客户相互之间及配送中心与客户之间的距离采用直线距离，该距离可根据客户和配送中心的坐标计算得到。
表2.5 实例2.3的已知条件表
续表
实例2.3中包括100个客户、有两种车型，是一个规模很大的多车型配送车辆优化调度问题，且该实例的目标函数是使取配送车辆的总吨位公里数最少。根据实例2.3的上述特点，作者在用爬山算法对其求解时，采用了以下运行参数：对不可行路径的惩罚权重取12000 t·km，终止迭代步数取80000。对实例2.3随机求解10次，得到的计算结果见表2.6。
表2.6 实例2.3的爬山算法计算结果表
从表2.6可以看出：用爬山算法对实例2.3的10次求解中，都在80000次迭代内得到了问题的可行解，其配送总吨位公里数的平均值为4250.6 t·km，平均使用了6.8辆8t车和7.1辆10t车，比已知条件平均节省6.1辆车。其中第3次计算得到的解的质量最高，其配送总吨位公里数为3920 t·km，需用7台10t车和7台8t车，其中7台10t车的配送路径分别为：路径1∶0-63-32-77-23-88-2-84-90-16-46-0，路径2∶0-34-62-13-56-1-5-9-0，路径3∶0-44-51-76-58-40-14-86-0，路径4∶0-45-99-85-97-93-55-69-73-0，路径5∶0-82-79-64-60-0，路径6∶0-43-67-33-42-92-26-80-0，路径7∶0-71-11-91-29-22-70-28-75-49-47-100-37-25-0；7台8t车的配送路径分别为：路径8∶0-21-60-89-31-68-3-0，路径9∶0-12-35-52-48-96-0，路径10∶0-95-30-17-59-10-94-66-39-0，路径11∶0-50-57-41-27-98-38-0，路径12∶0-54-7-74-20-4-53-0，路径13∶0-72-24-15-87-83-18-78-36-0，路径14∶0-65-8-81-6-19-0。从解的质量看，尽管用爬山算法可以求得实例2.3的可行解，但总体上解的质量不是很高，作者运用其他算法得到的实例2.3的最好解的配送总吨位公里数为3491t·km，爬山算法求得的平均配送总吨位公里数要比该最好解多21.8%，爬山算法的最好解的配送总吨位公里数也比该最好解多12.3%。另外，爬山算法的计算结果也不太稳定，10次求解中，最差的解的配送总吨位公里数比该最好解多21.6%。从计算效率看，10次求解的平均计算时间为13.86s，首次搜索到最终解的平均迭代步数为53500。可见，对于规模很大（客户数为100左右）的无时限单向配送车辆优化调度问题，利用爬山算法也可在较短的计算时间和较少的迭代步数内得到问题的可行解，但总体上解的质量不是很高，且计算结果不太稳定。
通过以上实验计算，可以总结出爬山算法的以下特点：
（1）爬山算法具有很高的收敛速度，该算法可在较短的计算时间和较少的迭代步数内得到问题的最优解、近似最优解或可行解。
（2）对于规模较小的无时限单向配送车辆优化调度问题，爬山算法的寻优效果较好，可以求得问题的最优解或近似最优解；而对于规模较大或很大的无时限单向配送车辆优化调度问题，爬山算法的寻优效果较差，其解的质量与问题的最优解相比尚存在一定的差距，这是由于爬山算法全局搜索能力不强造成的。
（3）受初始解选取的随机性和邻域选点的随机性的影响，爬山算法的计算结果不太稳定，这说明爬山算法的稳健性较差。
针对爬山算法在寻优性能方面的不足，可以采用以下几种方法提高最终解的质量：
（1）对大量初始解执行爬山算法，再从中选优，但该方法会受到计算时间的限制。
（2）引入更复杂的邻域结构，使算法能对解空间的更大范围实施搜索。2.6.2节的实验计算结果表明，在爬山算法中通过采用逆转法实施邻域操作，可以有效地提高最终解的质量。
（3）改变爬山算法只接受优化解的迭代准则，在一定限度内接受恶化解。本书下一章研究的禁忌搜索算法和模拟退火算法都是基于这种思想提出的。