交通物流配送路径优化算法的研究王鹏：张旭：马丽：习媛媛：长春＞－－ｙ．－ｒ＿大学计算机科学技术学院，讲师，吉林长春，１５００２２吉林交通职业技术学院道路与桥梁系，讲师，吉林长春，１５００１２长春理工大学计算机科学技术学院，硕士研究生，吉林长春，１５００２２长春理工大学计算机科学技术学院，硕士研究生，吉林长春，１５００２２摘要：为进一步优化交通物流配送路径，提高物流配送效率，将多种路径优化算法相结合，提出改进的路径优化混合算法。首先利用遗传算法的随机搜索性、快速性和全局收敛性产生物流路径问题的初始信息素分布，然后充分利用蚁群算法的并行性、正反馈机制及求解效率高等特点求得较优解，最后利用爬山算法良好的局部收敛性求得最优解。实验结果证明，该混合算法与单一算法相比，其路径计算效果和计算效率都有比较明显的提高。关键词：物流配送；路径优化；算法优化混合算法。仿真实验结果表明，该算法相对于某种单一算法而言，其计算效果和计算效率都有比较明显的提高。１路径优化混合算法的提出与模型建立遗传算法是一种有效的解决最优化问题的算法，有物用，而物流配送路径的优化是提高效率的重要环节。为搜索最优的配送路径，目前已有多种精确算法和启发式算法，如分支定界算法、动态规划算法、节约法、扫描法、禁忌搜索算法、遗传算法、蚁群算法和爬山算法等。在分析上述算法利弊的基础上，将遗传算法、蚁群算法和爬山算法相结合，提出一种改进的路径流配送对物流系统的整体效率发挥着关键性作较强的全局搜索能力，但其局部搜索能力存在缺陷。蚁群算法具有随机性、正反馈性、并行性等特点，适用于并行计算和求解最优解问题，但是初始信息匮乏，求解速度慢。爬山算法运用了迭代改进技术，搜索空间的单个点，也即当前点。爬山算法具有快速局部收敛性，利用该特性与蚁群算法相结合，能较好地解决路径最优解基金项目：国家科技部国际合作重大项目基金支持（ＤＦＡ０２９００）一３２—万方数据交通物流配送路径优化算法的研究王鹏等问题。将以上３种算法相互结合即可得到一种混合算法。首先利用遗传算法进行一定步数迭代求解并转化为网络的初始化信息素分布，再利用蚁群算法对遗传算法所得的初始结果进行精确、收敛，得到用个Ｈａｍｉｌｔｏｎ圈。最后利用爬山算法，对当前路径反复进行局部搜索，直到无法改进Ｈａｍｉｌｔｏｎ圈的质量为止。这样借用爬山算法的良好收敛性，能够较快地得到物流配送路径的最优解。１．１混合算法的模型结构设计混合算法的模型结构见图１。图１混合算法的模型结构该模型结构主要包括两部分：利用遗传算法初始化信息素的分布；利用蚁群和爬山算法获取最优路径的解。１．２初始化信息素的分布初始化信息素分布的算法流程见图２。１．３获取最优解对遗传算法所得的初始结果进行收敛，选取Ｈａｍｉｌｔｏｎ圈中的最短长度作为爬山算法计算的当前路径，对当前路径反复进行局部搜索，直到无法改进Ｈａｍｉｌｔｏｎ圈的质量为止。获取最优解的计算流程见图３。２实验分析为验证该混合算法对配送路径优化能力的提高效果，现采用文献【７】中的数据进行实验，即２台配送车，载重量均为８ｔ，车辆每次配送最大行驶距离为５０ｋｍ，分别采用３种单一算法和混合算法对８个客户、１６个客户、３２个客户和６４个客户４种情况进行求解，并假设客万方数据圈２初始化信息素分布的算法流程图３获取最优解的计算流程－３３—户的货物需求为已知。参数取值如下：群体规模２０，进化代数２５，交叉概率０．９，变异概率０．０９，变异记忆换位次数为５；蚁群算法时的口＝１，卢＝５，ｐ＝０．５，ｒ＝Ｏ．００００２，ｍ＝３０，迭代次数为１００；爬山算法次数为２０次，随机求解取均值。８个客户时４种算法的计算结果比较见表１。表Ｉ单一算法与混合算法求解比较（８个客户）为了更加直观地对混合算法的计算效果和计算效率进行评价，将８个客户、１６个客户、３２个客户和６４个客户４种情况下不同算法的计算结果进行比较（见图４、图５）。图４４种算法计算效果比较曲线图５４种算法计算效率比较曲线．．３４．．万方数据交通物流配送路径优化算法的研究王鹏等实验结果证明，该混合算法在路径优化的计算效果和计算效率方面都有一定的提高，并随着客户数量和配送数量的增加，其优势则更加明显。３结束语混合算法将遗传算法、蚁群算法和爬山算法相结合，取长补短，使计算效果更优、性能更高。同时，结合生产生活实际，可将算法模型具体化。实验结果表明，该算法在物流配送路径优化方面具有较强的实用性。但是物流配送路径优化算法作为一个ＮＰ（Ｎｏｎ－ｄｅｔｅｒｍｉｎｉｓｔｉｃＰｏｌｙｎｏｍｉａｌ）问题，有待进一步探索与改进。参考文献计算机工程与设计，２００ａｏ６）法【Ｊ】．火力与指挥控制，２００８（２）［３】王鸥，唐超札，黄友锐．蚁群算法在求解ＴｓＰ问题中的应用［Ｊ】．科技情报开发与经济，ｚｏｏＴ（ｚ９）场场桥调度［Ｊ】．上海海事大学学报，２００７（４）辅助工程，ｚ００６（２）优行车路径算法［Ｊ】．长安大学学报（自然科学版），２００９（ｚ）［７】郎茂祥，胡思继．用混合遗传算法求解物流配送路径优化问题的研究［Ｊ】．中国管理科学，２００ｚ（５）责任编辑卢敏收稿日期２００９—０８—１６【１】张强，师军．基于遗传算法的分层路径寻优算法【Ｊ】．【２】刘勇，张晓红．遗传算法的多目标优化资源选择算【４】何军良，宓为建，严伟．基于爬山算法的集装箱堆［５】郏宣耀，滕少华．双种群改进蚁群算法【Ｊ】．计算机［６】李明利，王选民，张利川，等．分区分层的动态最
