论文部分内容阅读
相比于发达西方国家,我国物流业起步相对较晚。虽然近些年取得了长足发展,但是物流业整体运行效率偏低。据相关资料统计发现,在运输、配送、仓储、装卸搬运、流通加工和信息处理等这些物流作业活动中,配送作业成本占物流作业总成本的比例超过了50%,且一直高居不下。因此,如何进行配送线路和配送车辆的合理优化配置,实现配送作业在物流系统中的高效率、低成本运行一直是物流行业关注的重点。配送作业问题可以抽象成为容量约束的车辆路径问题,该问题是典型的NP-hard问题,也是一个组合优化问题,车辆路径问题求解的复杂程度会随着问题规模的增大呈指数级增长。对于车辆路径问题的求解方法,主要有精确算法、传统启发式算法及智能优化算法,本文采用遗传算法求解车辆路径问题。遗传算法由美国的J.H.Holland教授在1975年提出,该算法简单、易实现,具有并行、强鲁棒性等优点,是求解车辆路径这类问题的经典算法。在充分研究车辆路径特征及遗传算法优缺点后,本文设计三类改进遗传算法进行问题的求解,通过相关数据集的测试,证明了算法的有效性。主要工作如下:(1)传统遗传算法求解容量约束车辆路径时,染色体编码采用随机分割的策略,这种编码策略会产生大量的不可行解,缩小算法的搜索空间。因此,设计基于整数映射编码的遗传算法,使得每条染色体在解码后都产生可行解,保证算法解的空间在算法迭代过程始终保持多样性特征,提高算法求得最优解的概率。(2)验证可知,基于整数映射编码的遗传算法求解结果优于传统遗传算法,但该算法仍然存在早熟收敛、易陷入局部最优等问题,解严重依赖于初始化种群,特定的编码策略削弱了选择算子和交叉算子的搜索能力。因此,考虑将禁忌搜索算法的局部搜索能力同遗传算法的全局搜索能力相结合,设计遗传禁忌搜索混合算法求解容量约束车辆路径问题,通过全局搜索和局部搜索相结合的方式来提高算法搜索性能,提高算法求得最优解的概率。(3)验证可知,遗传禁忌搜索混合算法求解结果优于传统遗传算法和基于整数映射编码的遗传算法,但需要多次试算才可以得到比较满意的解,算法性能不稳定,解比较依赖于初始种群。为进一步提高算法求解稳定性及求解精度,设计了双种群混合遗传算法。种群I作为精英群体,采用扫描算法思想生产初始种群,使得种群I在迭代之初就处于一个较优状态。利用变邻域搜索策略进行局部搜索,提高算法搜索到最优解的概率。种群II作为劣势群体,进行全局开发,判断种群达到早熟收敛状态时,植入外部新个体,保证种群II的多样性。种群I和种群II通过移民算子进行种群间的协同优化,整体上提升算法稳定性和可行性。研究发现,双种群混合遗传算法在稳定性、求解精度等方面均优于传统遗传算法、基于映射编码的遗传算法及遗传禁忌搜索混合算法,这为容量约束车辆路径问题的求解提供一种新的思路。