樊倩 熊雷鸣 邵晓根 孔亮
摘要:为了响应国家低碳经济的号召,为了降低物流行业的成本,提高商品配送的质量和效率,该文提出了基于遗传算法的生鲜配送的路径优化模型,并针对具体案例进行了仿真,初始的行驶距离为:210.76km,优化后行驶距离为:80.4964km。该文提出的模型具有较高参考性和可行性,具有实际应用的价值。
关键词:遗传算法;生鲜配送;路径优化
中图分类号:0229;F505;0224 文献标识码:A
文章编号:1009-3044()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结束语
本文所研究的生鲜配送问题,除了考慮到距离最小之外,还考虑了生鲜在配送过程中的制冷所产生的成本,使得问题更加贴近实际生活。优化现有的运输网络,降低成本,为企业的发展带来更好的收益。
如果觉得《matlab遗传算法配送路径 基于遗传算法的生鲜配送的路径优化问题》对你有帮助,请点赞、收藏,并留下你的观点哦!