内容提要：为进一步优化交通物流配送路径，提高物流配送效率，将多种路径优化算法相结合，提出改进的路径优化混合算法。首先利用遗传算法的随机搜索性、快速性和全局收敛性产生物流路径问题的初始信息素分布，然后充分利用蚁群算法的并行性、正反馈机制及求解效率高等特点求得较优解，最后利用爬山算法良好的局部收敛性求得最优解。实验结果证明，该混合算法与单一算法相比，其路径计算效果和计算效率都有比较明显的提高。

    关 键 词：物流配送/路径优化/算法

　　物流配送对物流系统的整体效率发挥着关键性作用，而物流配送路径的优化是提高效率的重要环节。为搜索最优的配送路径，目前已有多种精确算法和启发式算法，如分支定界算法、动态规划算法、节约法、扫描法、禁忌搜索算法、遗传算法、蚁群算法和爬山算法等。在分析上述算法利弊的基础上，将遗传算法、蚁群算法和爬山算法相结合，提出一种改进的路径优化混合算法。仿真实验结果表明，该算法相对于某种单一算法而言，其计算效果和计算效率都有比较明显的提高。

　　1 路径优化混合算法的提出与模型建立

　　遗传算法是一种有效的解决最优化问题的算法，有较强的全局搜索能力，但其局部搜索能力存在缺陷。蚁群算法具有随机性、正反馈性、并行性等特点，适用于并行计算和求解最优解问题，但是初始信息匮乏，求解速度慢。爬山算法运用了迭代改进技术，搜索空间的单个点，也即当前点。爬山算法具有快速局部收敛性，利用该特性与蚁群算法相结合，能较好地解决路径最优解问题。

　　将以上三种算法相互结合即可得到一种混合算法。首先利用遗传算法进行一定步数迭代求解并转化为网络的初始化信息素分布，再利用蚁群算法对遗传算法所得的初始结果进行精确、收敛，得到m个Hamilton圈。最后利用爬山算法，对当前路径反复进行局部搜索，直到无法改进Hamilton圈的质量为止。这样借用爬山算法的良好收敛性，能够较快地得到物流配送路径的最优解。

　　1.1 混合算法的模型结构设计

　　混合算法的模型结构见图1。
　　

　　图1 混合算法的模型结构

　　该模型结构主要包括两部分：利用遗传算法初始化信息素的分布；利用蚁群和爬山算法获取最优路径的解。

　　1.2 初始化信息素的分布

　　初始化信息素分布的算法流程见图2。
　　

　　图2 初始化信息素分布的算法流程

　　图3 获取最优解的计算流程

　　1.3 获取最优解

　　对遗传算法所得的初始结果进行收敛，选取Hamilton圈中的最短长度作为爬山算法计算的当前路径，对当前路径反复进行局部搜索，直到无法改进Hamilton圈的质量为止。获取最优解的计算流程见图3。

　　2 实验分析

　　为验证该混合算法对配送路径优化能力的提高效果，现采用文献[7]中的数据进行实验，即2台配送车，载重量均为8t，车辆每次配送最大行驶距离为50km，分别采用三种单一算法和混合算法对8个客户、16个客户、32个客户和64个客户四种情况进行求解，并假设客户的货物需求为已知。参数取值如下：群体规模20，进化代数25，交叉概率0.9，变异概率0.09，变异记忆换位次数为5；蚁群算法时的α=1，β=5，ρ=0.5，τ=0.00002，m=30，迭代次数为100；爬山算法次数为20次，随机求解取均值。8个客户时4种算法的计算结果比较见表1。

　　为了更加直观地对混合算法的计算效果和计算效率进行评价，将8个客户、16个客户、32个客户和64个客户4种情况下不同算法的计算结果进行比较（见图4、图5）。
　　
　　实验结果证明，该混合算法在路径优化的计算效果和计算效率方面都有一定的提高，并随着客户数量和配送数量的增加，其优势则更加明显。

　　3 结束语

　　混合算法将遗传算法、蚁群算法和爬山算法相结合，取长补短，使计算效果更优、性能更高。同时，结合生产生活实际，可将算法模型具体化。实验结果表明，该算法在物流配送路径优化方面具有较强的实用性。但是物流配送路径优化算法作为一个NP(Nondeterministic Polynomial)问题，有待进一步探索与改进。

    原文参考文献：
[1]张强，师军.基于遗传算法的分层路径寻优算法[J].计算机工程与设计，2008(16)
[2]刘勇，张晓红.遗传算法的多目标优化资源选择算法[J].火力与指挥控制，2008(2)
[3]王鸥，唐超礼，黄友锐.蚁群算法在求解TSP问题中的应用[J].科技情报开发与经济，2007(29)
[4]何军良，宓为建，严伟.基于爬山算法的集装箱堆场场桥调度[J].上海海事大学学报，2007(4)
[5]郏宣耀，滕少华.双种群改进蚁群算法[J].计算机辅助工程，2006(2)
[6]李明利，王选民，张利川，等.分区分层的动态最优行车路径算法[J].长安大学学报（自然科学版），2009(2)
[7]郎茂祥，胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学，2002(5)