原文传递
基于遗传-蚁群二级嵌套混合算法的选址-路径规划方法研究
| 论文题名： | 基于遗传-蚁群二级嵌套混合算法的选址-路径规划方法研究 |
| 关键词： | 路径规划;选址策略;物流运输;遗传算法;蚁群算法 |
| 摘要： | 选址-路径规划问题(LRP:Location-RoutingProblem)是一类经典的物流运输优化问题，也是一类典型的NP-hard问题，它包含“选址分配”和“路径规划”这两个相互耦合、且具有不同优化特性的子问题：“选址分配”属于资源配置问题，“路径规划”属于路径优化问题。将两个子问题集成求解，由于紧密耦合导致问题复杂度很高，求解过程往往不收敛，且单一算法往往无法有效的解决两类子问题；将两个子问题分为两阶段独立求解，则由于过度解耦，导致解的优化程度较低。 针对以上问题，本文在考虑遗传算法求解“资源配置问题”和蚁群算法求解“路径优化问题”的优势的同时，也考虑“选址分配”和“路径规划”两个子问题的紧密耦合性，提出了一种集遗传算法与蚁群算法于同一循环体的二级嵌套混合算法，并且，针对算法流程中的核心环节：运输节点分配环节，提出一种邻接三点聚集度分析方法。通过标杆问题测试实验与算法比对实验论述了所提算法的有效性与优越性。在案例研究中，针对中药掺配车间物料中心定位与搬运路径规划问题，在考虑配送中心间的负载平衡的基础上，对所提方法及相关策略进行相应的拓展。本文研究内容与成果如下： (1)构建了LRP的二级优化数学模型，提出了求解LRP的遗传-蚁群二级嵌套混合算法，从而，既避免问题复杂度太高导致求解过程陷入局部最优或不收敛的情况，又避免简单解耦导致优化程度低的问题。 (2)针对LRP，提出了混合算法的实现过程和改进策略，如：编码策略、选址方案种群初始化方法、适应度值计算方法、精英保留策略、自适应随机互换的交叉与变异策略、选址分配方案确定时的车辆路径解码方法、考虑多因素的路径选择方法与信息素更新策略等，以提高算法效率。 (3)针对算法中运输节点分配这一主要环节，从经验设计角度出发，提出了一种面向路径优化的运输节点分配方法：基于邻接三点聚集度分析的分配方法，比对实验验证了这一方法的有效性与优越性。 (4)采用标杆算例，通过与文献的比对实验表明：结合邻接三点聚集度分析的遗传-蚁群二级嵌套混合算法，在求解选址-路径问题上具有可靠的收敛性和较优的求解能力。 (5)针对中药掺配车间物料中心定位与搬运路径规划这一现实案例，在遗传-蚁群二级嵌套混合算法框架下，对所提方法进行了拓展：提出了考虑负荷平衡的边缘点重分配方法，综合考虑了负荷平衡和路径优化两方面的指标。实验表明，该方法在不显著降低求解的优化程度的情况下，显著提升了求解的可靠性。 |
| 作者： | 余晗琳 |
| 专业： | 工业工程 |
| 导师： | 罗亚波 |
| 授予学位： | 硕士 |
| 授予学位单位： | 武汉理工大学 |
| 学位年度： | 2022 |
检索历史
应用推荐
