基于模因算法的带时间窗多车路径规划研究
发布时间：2022-01-21 08:32
物流行业发展面临着激烈的市场竞争压力和消费者服务要求不断升级的挑战。物流企业要在如此激烈的竞争环境中生存,提高企业的核心竞争力,物流车辆路径规划是物流管理中的关键环节之一,优化物流车辆路径规划对于减少运营成本和提高服务质量至关重要。由于车辆路径规划问题属于组合优化的NP难问题,该问题的求解存在诸多的困难,如算法的收敛速度慢,求解目标过多,问题约束苛刻等。为了平衡问题求解的时空复杂度,本文基于演化计算方法,对物流车辆路径规划问题进行研究。主要内容如下:（1）针对带时间窗多车辆路径规划问题,提出基于骨干链与大邻域局部搜索的多因子多目标模因算法,对路径长度、车辆使用数两个目标进行优化。在多因子算法的隐性信息交换的基础上,提出基于骨干链显性信息交换方法,通过对骨干链进行修复和拼接,将其重组成一个候选解并运用于大邻域局部搜索中。利用大邻域搜索的方法,对个体解进行深度搜索,加速算法的收敛并提高解的质量。利用Solomon的数据集进行测试,并将本文提出的算法与多因子模因算法（MFMA）、多因子进化算法（MFEA）以及多目标遗传算法（MOGA）算法进行对比,实验结果表明,骨干链和大邻域搜索的结合能够在...
【文章来源】：深圳大学广东省
【文章页数】：74 页
【学位级别】：硕士
【部分图文】：
18年中国社会物流总费用构成
基于模因算法的带时间窗多车路径规划研究16务间显性信息交换的方法——骨干链，并将得到的信息应用于大邻域局部搜索中，从而进一步加速算法的优化并提高解的质量。本章重点优化路径长度和车辆数两个目标。算法的有效性将利用Solomon的数据集进行测试。3.3问题定义与数学建模本节对带时间窗的车辆路径规划问题进行定义，如图2所示，一个多车带时间窗的车辆路径规划问题是在某一特定区域，多辆具有相同载重的运输车从一个仓库出发，对该区域内的所有服务点进行服务，为每辆运输车规划出一条成本最低并且合法的服务路径，最后返回原仓库。在规划的过程中，每个服务点都具有一个开始服务时间1和结束服务时间2，运输车辆只有在规定的时间窗[1，2]内进行服务才是合法的。每一个服务点有且仅有一辆车对其服务，同时每一辆车所服务的节点都是不重复的。图2.带时间窗多车辆路径规划图示在求解带时间窗的车辆路径规划问题前，需要对问题进行数学定义。描述如下：集合={1,2,3,…,}表示载重为的辆运输车，无向图=(，)表示某一特定区域，由服务节点和节点间的连线组成的网络，集合={1,2,3,…,}表示个顾客和一个仓库，集合={1,2,3,…,}表示节点间连线所形成的边。车速为1。服务节点由一个三元组(，，)组成，分别代表服务节点的坐标，坐标以及货物重量。服务节点和的距离通过两者的坐标(,)和(,)进行计算。每个服务节点的时间窗为[,]，是开始服务时间，是结束服务时间。车辆到达服务节点的时间为。候选路径表示为={,+1,+2,…,+}，表示节点的数量。问题求解的目标分别是总的
基于模因算法的带时间窗多车路径规划研究18公式(14)表示运输车辆必须在服务节点规定的时间窗内进行服务。A表示车辆到达服务节点的时间。该约束针对硬时间窗函数而言。()={(A)0(AO),A≤,≤A≤O,O≤A(15)其中()表示惩罚函数，和分别表示单位时间早到和晚到的惩罚系数，若运输车辆按时到达服务节点进行服务则惩罚成本为0。在规定的时间内对节点进行服务既是客户的需求，同时也能为物流公司节约成本。因此，若在服务的过程中运输车存在早到或晚到的现象，则会产生一定的惩罚成本。由于车辆早到而导致需要等待服务点开始服务，因此降低了物流公司的配送效率，但没有影响到服务点的服务质量，因此惩罚系数只针对物流公司本身，所以取值较校而对于车辆晚到而导致服务节点无法及时进行服务，从而影响了客户的服务质量，同时也影响了物流公司的配送效率和信誉，因此惩罚系数既针对了物流公司本身，同时物流公司也要支付一定的损失给客户，所以取值较惩罚系数大。3.4基于骨干链与大邻域搜索的多目标多因子模因算法框架本小节将着重介绍基于骨干链与大邻域局部搜索的多目标多因子模因算法框架（multi-objectivemulti-factorialmemeticalgorithm,MOMFMA）。流程简述如图3所示。图3.基于骨干链与大邻域搜索的多目标多因子算法框架
【参考文献】：
期刊论文
[1]基于实时信息的取送货动态车辆路径问题研究[J]. 孙宝凤,史俊妍,杨雪,郑再思. 宁波大学学报(理工版). 2019(03)
[2]基于改进蜂群算法的工业机器人路径规划研究[J]. 吴方圆. 电子测量技术. 2019(07)
[3]改进粒子群算法的三维空间路径规划研究[J]. 杨超杰,裴以建,刘朋. 计算机工程与应用. 2019(11)
[4]基于工作流网的应急资源配置与路径规划集成优化[J]. 傅惠,陈恺宇. 工业工程. 2018(05)
[5]基于VRP模型城市共享单车的优化调配研究[J]. 王嘉薇,朱家明,祁浩宇,李瑞新. 沈阳理工大学学报. 2018(01)
[6]考虑时间窗因素的物流配送车辆调度优化[J]. 初良勇,孟聪,阮志毅. 集美大学学报(自然科学版). 2017(06)
[7]求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法[J]. 李阳,范厚明. 控制与决策. 2018(07)
[8]基于改进遗传算法的移动机器人路径规划[J]. 郭首亮,孙海洋,陈珍. 电子世界. 2017(06)
[9]考虑供给商品价格的多车场车辆路径问题[J]. 鲁建厦,洪欢蕾,陈青丰. 浙江工业大学学报. 2016(05)
[10]市区小范围多车辆低碳VRP:以珠海速递公司区域收件网络为例[J]. 马秋卓,王健,宋海清. 管理工程学报. 2016(04)
硕士论文
[1]基于模因算法的物流车辆路径规划问题求解及实现[D]. 杨彦明.深圳大学 2018
本文编号：3599936
【文章来源】：深圳大学广东省
【文章页数】：74 页
【学位级别】：硕士
【部分图文】：
18年中国社会物流总费用构成
基于模因算法的带时间窗多车路径规划研究16务间显性信息交换的方法——骨干链，并将得到的信息应用于大邻域局部搜索中，从而进一步加速算法的优化并提高解的质量。本章重点优化路径长度和车辆数两个目标。算法的有效性将利用Solomon的数据集进行测试。3.3问题定义与数学建模本节对带时间窗的车辆路径规划问题进行定义，如图2所示，一个多车带时间窗的车辆路径规划问题是在某一特定区域，多辆具有相同载重的运输车从一个仓库出发，对该区域内的所有服务点进行服务，为每辆运输车规划出一条成本最低并且合法的服务路径，最后返回原仓库。在规划的过程中，每个服务点都具有一个开始服务时间1和结束服务时间2，运输车辆只有在规定的时间窗[1，2]内进行服务才是合法的。每一个服务点有且仅有一辆车对其服务，同时每一辆车所服务的节点都是不重复的。图2.带时间窗多车辆路径规划图示在求解带时间窗的车辆路径规划问题前，需要对问题进行数学定义。描述如下：集合={1,2,3,…,}表示载重为的辆运输车，无向图=(，)表示某一特定区域，由服务节点和节点间的连线组成的网络，集合={1,2,3,…,}表示个顾客和一个仓库，集合={1,2,3,…,}表示节点间连线所形成的边。车速为1。服务节点由一个三元组(，，)组成，分别代表服务节点的坐标，坐标以及货物重量。服务节点和的距离通过两者的坐标(,)和(,)进行计算。每个服务节点的时间窗为[,]，是开始服务时间，是结束服务时间。车辆到达服务节点的时间为。候选路径表示为={,+1,+2,…,+}，表示节点的数量。问题求解的目标分别是总的
基于模因算法的带时间窗多车路径规划研究18公式(14)表示运输车辆必须在服务节点规定的时间窗内进行服务。A表示车辆到达服务节点的时间。该约束针对硬时间窗函数而言。()={(A)0(AO),A≤,≤A≤O,O≤A(15)其中()表示惩罚函数，和分别表示单位时间早到和晚到的惩罚系数，若运输车辆按时到达服务节点进行服务则惩罚成本为0。在规定的时间内对节点进行服务既是客户的需求，同时也能为物流公司节约成本。因此，若在服务的过程中运输车存在早到或晚到的现象，则会产生一定的惩罚成本。由于车辆早到而导致需要等待服务点开始服务，因此降低了物流公司的配送效率，但没有影响到服务点的服务质量，因此惩罚系数只针对物流公司本身，所以取值较校而对于车辆晚到而导致服务节点无法及时进行服务，从而影响了客户的服务质量，同时也影响了物流公司的配送效率和信誉，因此惩罚系数既针对了物流公司本身，同时物流公司也要支付一定的损失给客户，所以取值较惩罚系数大。3.4基于骨干链与大邻域搜索的多目标多因子模因算法框架本小节将着重介绍基于骨干链与大邻域局部搜索的多目标多因子模因算法框架（multi-objectivemulti-factorialmemeticalgorithm,MOMFMA）。流程简述如图3所示。图3.基于骨干链与大邻域搜索的多目标多因子算法框架
【参考文献】：
期刊论文
[1]基于实时信息的取送货动态车辆路径问题研究[J]. 孙宝凤,史俊妍,杨雪,郑再思. 宁波大学学报(理工版). 2019(03)
[2]基于改进蜂群算法的工业机器人路径规划研究[J]. 吴方圆. 电子测量技术. 2019(07)
[3]改进粒子群算法的三维空间路径规划研究[J]. 杨超杰,裴以建,刘朋. 计算机工程与应用. 2019(11)
[4]基于工作流网的应急资源配置与路径规划集成优化[J]. 傅惠,陈恺宇. 工业工程. 2018(05)
[5]基于VRP模型城市共享单车的优化调配研究[J]. 王嘉薇,朱家明,祁浩宇,李瑞新. 沈阳理工大学学报. 2018(01)
[6]考虑时间窗因素的物流配送车辆调度优化[J]. 初良勇,孟聪,阮志毅. 集美大学学报(自然科学版). 2017(06)
[7]求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法[J]. 李阳,范厚明. 控制与决策. 2018(07)
[8]基于改进遗传算法的移动机器人路径规划[J]. 郭首亮,孙海洋,陈珍. 电子世界. 2017(06)
[9]考虑供给商品价格的多车场车辆路径问题[J]. 鲁建厦,洪欢蕾,陈青丰. 浙江工业大学学报. 2016(05)
[10]市区小范围多车辆低碳VRP:以珠海速递公司区域收件网络为例[J]. 马秋卓,王健,宋海清. 管理工程学报. 2016(04)
硕士论文
[1]基于模因算法的物流车辆路径规划问题求解及实现[D]. 杨彦明.深圳大学 2018
本文编号：3599936
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/3599936.html
