下载掌阅APP，畅读海量书库
立即打开
爬山算法，也称局部搜索算法，是一种基于邻域搜索技术的、沿着有可能改进解的质量的方向进行单方向搜索（爬山）的搜索方法。该方法的局部搜索能力很强，是一种常用的寻找局部最优解的方法。作者通过文献检索，发现有关用爬山算法求解配送车辆优化调度问题的研究成果很少。
用爬山算法求解组合优化问题时的步骤如下（以目标函数求最小为例）。
第一步：选定一个初始解x 0 ；记录当前最优解x best =x 0 ，令P=N（x best ）（表示x best 的邻域）。
第二步：当P=φ时，或满足其他停止运算准则时，转第四步；否则，从N（x best ）中按某一规则选一个解x now ，转第三步。
第三步：若x now 的目标函数值f（x now ）小于 x best 的目标函数值f（x best ），则令x best =x now ，P=N（x best ），转第二步；否则，P=P-x now ，转第二步。
第四步：输出计算结果，停止。
在爬山算法中，第一步的初始解可以采用随机方法产生，也可用一些经验方法得到，还可采用其他算法得到初始解。在第二步中，其他停止运算准则是指除P=φ以外的其他准则，这些准则一般取决于人们对算法的计算时间、计算结果的要求。第二步中在N（x best ）中选取x now 的规则可以采用随机选取的规则。
可见，爬山算法从解空间中的一个点出发，通过不断迭代，最终可达到一个局部最优点。算法停止时得到的解的质量依赖于算法的初始解的选取、邻域选点的规则和算法终止条件等。