基于遗传算法的生鲜配送的路径优化问题

来源:用户上传      作者:樊倩 熊雷鸣 邵晓根 孔亮

　　摘要：为了响应国家低碳经济的号召，为了降低物流行业的成本，提高商品配送的质量和效率，该文提出了基于遗传算法的生鲜配送的路径优化模型，并针对具体案例进行了仿真，初始的行驶距离为：210.76km，优化后行驶距离为：80.4964km。该文提出的模型具有较高参考性和可行性，具有实际应用的价值。
　　关键词：遗传算法;生鲜配送;路径优化
　　中图分类号：0229;F505;0224 文献标识码：A
　　文章编号：1009-3044（2020）01-0213-03
　　1背景
　　为了响应国家低碳经济的号召，各行各业都在最大限度地减少能源的使用。特别是物流行业，随着社会经济的不断发展，物流配送业务也随之提高，但是大量的能源在运输过程中被消耗，运输成本不断上升。如何能够在保证配送成本和消耗能源最小的情况下，提高商品配送的质量和效率，缩短生鲜在途时间是本文研究的主要内容。
　　2生鲜配送问题描述
　　目前生鲜配送主要由自营配送和建设配送网络两种构成。自营配送会产生成本的大量投入;建设配送网络容易出现地区发展不协调的问题。
　　没有做到合理的配送计划，易造成配送成本得虚高。借助先进的物流管理理念、技术，建立合适的配送路径优化模型是目前配送系统面临的主要问题。
　　考虑到这个问题，本文主要研究如何优化现有的同城配送运输网。优化运输网，可以缩减成本，以下是该研究问题的示意图：
　　3生鲜配送问题的模型的建立
　　如果要解决生鲜的配送路径优化问题，则该模型描述为：
　　1）车辆从暂存点出发，送至客户点，再返回暂存点;
　　2）满足路径上的需求量要求、车辆容载限制的约束;
　　与以往的车辆路径问题不同的是，生鲜在配送的过程中，将会产生制冷成本，本文在研究这个优化问题的时候需要将其考虑在内。
　　生鲜的配送问题，可以看作是一个多商旅问题（MTSP），可将其分成M个商旅问题（TsP）。
　　3.1模型的假设
　　在对生鲜的配送问题建模的过程中，为了保证模型准确性，运算的简便性，本文做出以下几点假设：
　　1）客户的需求量已知;
　　2）配送车辆匀速行驶，行驶路径固定;
　　3）在运输范围内不考虑生鲜腐坏的问题;
　　4）配送车辆的载重量一定，且能够满足客户的需要量。
　　3.2模型的描述
　　生鲜暂存点，为n个客户点提供生鲜配送服务;pi（i=1，2，…n）为第i个客户的需求量;运送车的规定载重为O。
　　3.3模型的目标函数
　　配送车辆从暂存点出发，送至多个客户点，最后再返回暂存点。
　　1）配送车辆的运输成本
　　运输成本主要由以下两个方面组成：一方面，固定成本co，这成本与行驶的距离无关;另一方面，变动成本c，这成本与行驶的距离有关：
　　4基于遗传算法的生鲜配送问题的模型的求解
　　车辆路径问题属于NP-hard问题，参考文献，本文选择遗传算法对问题进行求解。遗传算法全局搜索能力强、求解时间少，避免了逐次逼近算法效率低下的问题，也避免了陷入局部最优解。步骤如下：
　　4.1染色体编码
　　编码采用十进制的方式。采用一个随机数列表示种群中的一个个体，作为染色体。
　　4.2初始种群设定
　　采用改良圈算法，解得一个初始种群。产生M个染色体（即可行解）。把这些可行解转换成染色体编码。这个初始种群规模应适当：规模太大，会影响搜索效果;规模太小，会容易陷入局部最优解。
　　4.3适应度函数
　　适应度函数是一个有关目标函数的函数，其目的是用来判断个体的优劣：
　　4.4遗传操作
　　4.4.1选择
　　在父代、子代种群中选择适应度大的个体。适应度大的个体，将会被不断被选中、进化到下一代。
　　4.4.2交叉
　　使用单点交叉的方式。在新的种群中随机地选择两个个体，再随机地选择一个位置，两者进行交叉互换。
　　4.4.3变异
　　按照给定的变异率，选择发生变异的个体。随机地选取该个体的一个基因段，将其随机地插入余下的一个基因段中间，从而产生新的个体。
　　4.5终止原则
　　当算法迭代到指定的代数之后，停止运行，并将当前的最优染色体作为最优的解输出。
　　5生鲜配送问题的模型的仿真
　　为了验证本文所提出的算法是有效的，基于江苏省徐州市的生鲜超市进行配送模拟仿真。
　　stepl：获取生鲜商店的位置
　　首先，借助百度地图的坐标拾取器，获得徐州市130余家售卖生鲜食品的商店的地址及经纬度。然后，将获取的数据进行筛选，剔除数据缺失的项。同时，根据商店的实际经营情况，选择需要生鲜配送的大型商店。最终，选取了39家适合商店作为客户点，其中包括：爱客来、悦客等连锁便利店。将其绘制在地图中，如下图2所示：
　　step2：经纬度转换为距离
　　将经纬度的单位为角度，利用Matlab中distance函数计算两点与地心连线的夹角，再将角度乘以地球半径6370km，即为徐州市客户点之间的距离。
　　step3：对配送问题进行模拟仿真
　　根据客户点地地理位置及城区规划范围，将MTSP问题转化为3个TSP问题。求解该遗传算法问题，将参数设定如下，种群的大小为M=19;最大的迭代次数G=1000;为保证种群能够充分进化，交叉概率pc=1;一般来说，变异发生的可能性比较小，变异概率pm=0.1。最终，通过建立的模型，经过Matlab计算得到结果，绘制出配送的初始路径图和配送的路径优化图。
　　初始时行驶距离为：210.76km。由结果图可以看出优化过后的路径更短，行驶的距离为：80.4964km。
　　6结束语
　　本文所研究的生鲜配送问题，除了考慮到距离最小之外，还考虑了生鲜在配送过程中的制冷所产生的成本，使得问题更加贴近实际生活。优化现有的运输网络，降低成本，为企业的发展带来更好的收益。
转载注明来源:https://www.xzbu.com/8/view-15144818.htm