基于遗传算法的VRP扩展模型求解方法研究
发布时间：2021-06-01 01:25
车辆路径问题（Vehicle Routing Problem,VRP）是一种典型的组合优化问题,其具有广泛的应用背景。为了应对实际的需求,对VRP基本模型进行扩展,并提出有效算法是目前关于该问题的研究热点。本文就两类复杂的VRP扩展模型展开探索,（1）中心点的扩展,由单一中心扩展为多中心;（2）服务对象的需求由静态扩展为动态。结合实际问题,本文先分析了一种生活中复杂的垃圾收运问题——多回收站垃圾收运问题（Multi-station Refuse Collection Problem,MSRCP）,并将其映射为多中心车辆调度问题。建立了以最小车辆运输费用为目标的多回收站垃圾收运问题模型,设计了一种基于协同进化（Cooperative Co-evolutionary,CC）作为外部框架的问题求解方法。首先利用本文的聚类算法,对每个垃圾回收站进行垃圾收集点的分配操作,将多回收站的垃圾收运问题分解为多个单回收站的垃圾收运问题。再采用一种混合遗传算法对每个单回收站进行路径规划处理。最后,以安庆市大观区生活垃圾收运为例进行了上述模型及算法的验证,结果表明本文所提算法在降低复杂垃圾收运问题时,具有良...
【文章来源】：安庆师范大学安徽省
【文章页数】：54 页
【学位级别】：硕士
【部分图文】：
改进规则二应用说明图
路线，增大了该问题解的搜索范围，提高了种群的多样性。具体步骤如图 3.2 所示：第一步，在初始种群中随机选择两条父代染色体 P1、P2，即两种对垃圾收集点进行垃圾收集的服务顺序。染色体中单个基因代表单个垃圾收集点，基因片段代表多个有服务顺序的垃圾收集点集合。第二步，在 P1、P2 中随机选取相同位置的基因片段，分别记为change1 和 change2；第三步，按一定规律改变 P1、P2 中 change1 和 change2 的位置，再删去 P1 中与 change2 相同的基因，P2 中与 change1 相同的基因；第三步，按一定规律将 change2 放入删除后的 P1 中，将 change1 放入删除后的 P2 中，交叉操作完成生成子代 C1、C2。
18（4）局部搜索算子设计传统的遗传算法中初始化种群经过选择、交叉产生后代，进入变异操作，但是变异概率低，局部搜索能力差，有早熟收敛的风险。本章以一定变异概率对初始化种群的每一条染色体依次进行四种局部搜索，反映到MSRCP问题中，就是依次以不同的方法将一条服务顺序上的垃圾收集点变换位置，找到最合适的收集顺序。SingleInsertion（SI）单插入：在一条染色体中，依次将单个基因提取出来，插入到染色体的其他位置，每插入一个位置要记录解并与原解作比较，如果当前解要优于原来的解，那么将替换原解。这里考虑解是闭合曲线，为避免重复，单个基因插入的位置避开首基因的前一个位置和尾基因的后一个位置，如图3.3左所示。DoubleInsertion（DI）双插入：在一条染色体中，依次将两个连续的基因提取出来，插入到染色体的其他位置，每插入一个位置要记录解并与原解作比较，如果当前解要优于原来的解，那么将替换原解。同样这里考虑解是闭合曲线，为避免重复，基因插入的位置避开首基因的前一个位置和尾基因的后一个位置，如图3.3右所示。图3.3SI算子和DI算子示意图Swap交换算子：在一条染色体中，依次将每个基因与这条染色体上的其他基因互换位置，每换一个位置要记录解与原解相比，较优则替换原解，如图3.4所示。图3.4Swap算子示意图2-Opt：一条染色体转译成一个车辆路径方案，经常会出现路径与路径之间的交叉，这样必定会增加行驶距离，所以利用2-Opt方法来消除这个现象，如图3.5所示。2-Opt
本文编号：3209380
【文章来源】：安庆师范大学安徽省
【文章页数】：54 页
【学位级别】：硕士
【部分图文】：
改进规则二应用说明图
路线，增大了该问题解的搜索范围，提高了种群的多样性。具体步骤如图 3.2 所示：第一步，在初始种群中随机选择两条父代染色体 P1、P2，即两种对垃圾收集点进行垃圾收集的服务顺序。染色体中单个基因代表单个垃圾收集点，基因片段代表多个有服务顺序的垃圾收集点集合。第二步，在 P1、P2 中随机选取相同位置的基因片段，分别记为change1 和 change2；第三步，按一定规律改变 P1、P2 中 change1 和 change2 的位置，再删去 P1 中与 change2 相同的基因，P2 中与 change1 相同的基因；第三步，按一定规律将 change2 放入删除后的 P1 中，将 change1 放入删除后的 P2 中，交叉操作完成生成子代 C1、C2。
18（4）局部搜索算子设计传统的遗传算法中初始化种群经过选择、交叉产生后代，进入变异操作，但是变异概率低，局部搜索能力差，有早熟收敛的风险。本章以一定变异概率对初始化种群的每一条染色体依次进行四种局部搜索，反映到MSRCP问题中，就是依次以不同的方法将一条服务顺序上的垃圾收集点变换位置，找到最合适的收集顺序。SingleInsertion（SI）单插入：在一条染色体中，依次将单个基因提取出来，插入到染色体的其他位置，每插入一个位置要记录解并与原解作比较，如果当前解要优于原来的解，那么将替换原解。这里考虑解是闭合曲线，为避免重复，单个基因插入的位置避开首基因的前一个位置和尾基因的后一个位置，如图3.3左所示。DoubleInsertion（DI）双插入：在一条染色体中，依次将两个连续的基因提取出来，插入到染色体的其他位置，每插入一个位置要记录解并与原解作比较，如果当前解要优于原来的解，那么将替换原解。同样这里考虑解是闭合曲线，为避免重复，基因插入的位置避开首基因的前一个位置和尾基因的后一个位置，如图3.3右所示。图3.3SI算子和DI算子示意图Swap交换算子：在一条染色体中，依次将每个基因与这条染色体上的其他基因互换位置，每换一个位置要记录解与原解相比，较优则替换原解，如图3.4所示。图3.4Swap算子示意图2-Opt：一条染色体转译成一个车辆路径方案，经常会出现路径与路径之间的交叉，这样必定会增加行驶距离，所以利用2-Opt方法来消除这个现象，如图3.5所示。2-Opt
本文编号：3209380
本文链接：https://www.wllwen.com/shoufeilunwen/boshibiyelunwen/3209380.html
