交通物流配送路径优化算法的研究

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

      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)问题，有待进一步探索与改进。