带时间窗的生鲜冷链物流配送车辆路径问题研究.pdf

带时间窗的生鲜冷链物流配送车辆路径问题研究樊兵鹏(广东松山职业技术学院广东韶关:)摘要以生鲜冷链物流配送问题为研究对象,提出带有时间窗的生鲜冷链物流配送车辆路径问题,综合考虑了车辆固定成本、运输成本、货损成本(包括损耗费用和制冷成本)、违反时间窗惩罚成本等多种成本要素,构建出求解最优配送路径和配送成本最小化的目标函数,建立了带有时间窗的生鲜冷链物流配送模型.最后,通过实证仿真验证了模型的可靠性、实用性.关键词生鲜冷链;D V R P TW;遗传算法;配送成本;物流配送;时间窗;车辆路径中图分类号:U 文献标识码:A 文章编号:()收稿日期:修回日期:作者简介:樊兵鹏(),男,硕士,助教 E m a i l:q q c o m 引言近年来,随着电子商务的迅速发展及人民生活水平的不断提升,消费者更加关注生鲜冷链食品的质量与安全.生鲜冷链产品在运输流通过程中存在着运输成本高、货损率大、客户满意度低等问题,这些因素在一定程度上制约着生鲜冷链物流运输的长远发展.本文以生鲜品物流运输为研究对象,通过构建带时间窗的车辆路径问题(D y n a m i cV e h i c l eR o u t i n gP r o b l e mw i t hT i m eW i n d o w s,D V R P TW),优化了物流配送路径、降低了配送成本、节约了配送时间,在客户满意的时间窗内完成生鲜冷链物流配送.车辆路径问题(V e h i c l eR o u t i n gP r o b l e m s,简称V R P)这一概念最早由D a n t z i n g和R a m s e r基于卡车配送汽油的背景下所提出,对于V R P问题的求解主要包括精确算法和启发式算法两种.由于V R P属于NP h a r d问题,精确算法在求解的过程中存在局部最优、应用范围有限等局限性,本文采用启发式算法对模型进行求解,启发式算法主要包括遗传算法、蚁群算法、禁忌搜索算法、领域搜索算法等.国内外学者对V R P进行了很多研究与分析,S o n g y iW a n g等基于碳税政策影响下研究带时间窗的生鲜冷链物流配送车辆路径优化问题,利用循环遗传算法对模型进行求解,并为物流企业在生鲜冷链物流配送过程中碳排放控制提出可行性建议;万玲通过研究发现D V R P TW能够有效促进生鲜物流配送路径的优化,实现配送资源的合理利用和配送成本的有效控制,提升了生鲜物流整体配送效率;葛显龙等通过构建包含各种生鲜物流配送成本的目标函数模型,但在模型构建过程中没有考虑到客户满意度这一影响因素对于生鲜物流配送的影响;段雪凝指出D V R P TW是组合优化问题研究的重点,同时考虑运输成本、冷链运输特点等要素,构建出带有多目标要素的目标函数模型,对于带有多目标的车辆路径问题研究具有很好的借鉴价值;王维军等根据冷链物流的特性构建了成本函数模型,用于求解综合配送成本最低的车辆路径,并通过智能滴水算法对模型进行求解;王淑云等研究分析了顾客需求不确定情况下冷链物流配送的路径规划问题,建立了具有随机需求的模型,更好的满足了顾客多样化和个性化的冷链商品需求.综合以上内容,发现大多数学者主要研究生鲜配送或者冷链配送的路径问题,而对于生鲜冷链物流配送路径研究的相对较少,本文研究了带时间窗的生鲜冷链物流车辆路径问题.针对生鲜品冷链配送的特点,在比较系统考虑各种配送成本低的基础上,构建了带有生鲜品货损成本的目标函数,用于求解配送成本最小化和配送路径最优化的车辆路径问题.本文选用了具有很强计算能力和全局搜索能力的自适应遗传算法,并通过MAT L A P数据分析软件对模型进行求解,通过仿真分析,验证了遗传算法在求解路径规划和配送成本问题上具有很好的实用价值.配送成本构成因素分析 配送车辆的固定成本配送车辆固定成本是相对于变动成本来说,是指在进行物流配送的过程中不随着客户量、载货量、配送距离等因素的影响而保持不变情况下所发生的成本.T CMkP其中,T C配送车辆的固定成本;M配送车辆总数;P单配送车辆的固定成本.配送车辆的运输成本运输成本是指运输车辆在提供货物运输服务过程中所产生的如燃料费、维修与折旧费等所产生各项费用的总和,运输成本是衡量企业运输管理水平和运输质量的重要考核指标.T CNiNjMkxi j kdi j其中,T C配送车辆的运输成本;xi j k第k辆车从i点行驶至j点取值为,否则取值为;di j第i点至第j点之间的距离;配送车辆单位行驶距离的运输成本.生鲜配送的货损成本货损成本主要包括两种:一种是生鲜品在配送的过程中随着时间的延长而产生的货物损耗费用,另一种是对车厢内温度进行恒温控制而产生的制冷成本.T CNiNjMkxi j k(ti jqi j)其中,T C生鲜品货物损耗费用;生鲜品单位商品价格;运输过程中的货损系数;装卸过程中的货损系数;q销售商生鲜品需求量.T CcNiNjMkxi j kti jcNiNjMkxi j kti k其中,T C制冷成本;c单位运输时间所产生的制冷成本;c单位装卸时间所产生的制冷成本;ti j配送车辆从i点到j点所消耗的时间;ti k配送车辆从i点到k点所消耗的时间.违反时间窗惩罚成本配送车辆必须在客户约定的时间窗内到达,违反时间窗惩罚成本主要包括三种情况:生鲜品在规定的时间窗内送达,不产生惩罚成本;早于时间窗送达需要等待,并产生早到惩罚;晚于时间窗送达客户可能会拒收,并产生一定的延迟惩罚.T CpNim a x(Eiti,)pNim a x(tiLi,)其中,T C违反时间窗惩罚成本;p早到惩罚成本系数;p晚到惩罚成本系数;(Ei,Li)与客户约定的配送时间窗.问题描述及模型构建 问题描述某生鲜品冷链物流企业通过建立N个配送中心,向N家销售商(,N)配送生鲜品,配送中心共配置M辆(,M)相同类型的冷藏车,每辆冷藏车容量为q.为了便于模型计算,现对目标函数做以下的假设:()配送中心的地理坐标为已知;()每位客户的基本信息(包括时间窗、需求量、配送距离)均已知;()在客户要求的时间窗内货物必须送达;()配送中心的所有冷藏车在完成配送后必须返回配送中心;()剔除交通、自然等条件限制,配送过程中所有冷链车均匀速行驶;()配送中心的配送车辆为同一车型;()整个配送服务过程需在与客户约定的时间窗内完成.模型构建根据配送成本构成要素和问题描述可知,最终构建带有成本函数的目标函数模型:m i nZMkPNiNjMkxi j kdi jNiNjMkxi j k(ti jqi j)cNiNjMkxi j kti jcNiNjMkxi j kti kpNim a x(Eiti,)pNim a x(tiLi,)()S T NiMkqiyi j kQ,i,j,N;k,M()NiMkxi j k,i,j,N;k,M()NjMkxi j k,i,j,N;k,M()樊兵鹏:带时间窗的生鲜冷链物流配送车辆路径问题研究EitiLi,i,N()NiMkdi jxi j kLk,i,j,N,K,M()Ni,ijxi j kyj k,i,j,N,k,M()Nj,ijxi j kyi k,i,N,k,M()xi j k,i,N,k,M()上述约束条件所指的含义为:式()表示目标函数;式()表示每条路径上所有客户的需求总量之和恒小于等于冷链车辆的最大载重量;式(),()表示保证每位客户在时间窗内仅被一辆车服务;式()表示时间窗约束,即车辆需在时间窗关闭之前到达客户点i;式()表示确保在最大行驶距离内完成配送任务;式(),()表示两变量之间的关系;式()表示决策变量变量.遗传算法的模型求解 染色体编码本文采用基于车辆路径行驶顺序的自然数编码方式,一条行驶路径表示一条染色体,用(,s,s,sp,;,spst;,sk t,sk n,)表示染色体Ss;s;sk,如其中sp表示为第辆冷链车为客户点p进行服务.上述染色体S中将配送中心进行编码为i,配送中心冷链车共有k辆,对销售商即客户点编码为i,N.冷链车从配送中心出发,完成一条行驶路径后需返回配送中心,进行下一条行驶路径的物流配送工作,在染色体中加入的目的是为了区分不同冷链车各自的行驶路径,直到所有客户的配送任务完成编码工作结束.假如三辆冷链车的条行驶路径为();();(),则可编码为(,;,;,).适应度函数适应度函数能够筛选出具有优良性的染色体,即评价行驶路径的好坏程度,通常取值目标函数值的倒数,设适应度函数:f/m i nZ.一般情况下适应度函数越大,则染色体的优良性越好,其保留到下一代的概率也越高,经过不断的迭代求值,选取那些适应度函数值较大的染色体作为线性加权函数的可行解.交叉与变异算子 交叉算子为了保证父代中优良基因得到传承和子代基因的多样性,本文采用交叉操作算子将父代中的部分基因通过交叉交换的方法遗传到子代基因中.具体操作步骤:第一,随机选择两个去除带配送中心编码为的染色体A和B作为父代染色体;第二,在染色体A和B中随机选择一个位置作为交叉点;第三,从父代染色体A和B中选取合适的染色体链条,并通过部分交叉位移的方法产生新的子代染色体A和B;第四,删除子代染色体A和B中重复的基因,得到新的子代染色体A和B.遗传算法中的交叉算子操作有效防止了遗传算法局部最优问题,提高了算法的全局搜索能力和质量.交叉算子具体操作示例步骤如图所示.图交叉算子操作示意图 变异算子在染色体遗传进化的过程中部分基因会发生破碎、突变即基因变异现象,但发生基因变异的概率很小,一般变异概率在 范围内.变异算子通过模仿自然基因变异现象,通过变异操作弥补染色体基因变异的不足,从而保证染色体个体的完整性、多样性.变异操作和交叉操作一样能够增强遗传算法的全局搜索能力.变异算子具体操作步骤:首先,选择任意一条父代染色体,在染色体上随机选取一个数作为交叉变异点;然后,从销售商编码i,N 之间任意选择一个数作为交叉变异点并进行变异操作;最后,验证新生成的子代染色体是否符合变异操作算法规则,符合的保留否则舍去.变异算子具体操作示例步骤如图所示.图变异算子操作示意图武汉工程职业技术学院学报 算法终止条件通过遗传算法迭代次数做为算法的终止条件,当迭代次数达到所规定的迭代次数则终止遗传算法操作.染色体通过交叉和变异算法操作,保留性能最好的染色体组成一个集合体,做为生鲜冷链物流配送路径的最优解集,最后输出这个最优解集.实证及仿真分析 算例描述某一生鲜品配送物流企业通过建立单一配送中心,使用相同类型的冷链车分别向 家零销店铺配送生鲜品,已知每辆冷链车的最大载重量为t,车辆平均行驶时速为 k m/h.配送中心第一辆冷链车每天早上:准时发车,前一趟冷链车完成本次配送任务并返回配送中心后下一趟冷链车方可发车,假设冷链车发车时已经装车完毕.已知配送中心的坐标为(,),家零销店铺需求量、地理坐标、服务时间及时间窗如表所示,其他相关参数值设置如表所示.算例求解与分析根据上文对问题的描述以及约束条件、模型的构建,本文选用MAT L A B数值分析软件对带有加权线性函数的自适应遗传算法模型进行求解,通过将上文提到的客户相关信息数据、加权线性公式、相表客户基本信息数据编号坐标时间窗需求量/t服务时间/h(,)(:)(,)(:)(,)(:)(,)(:)(,)(:)(,)(:)(,)(:)(,)(:)(,)(:)(,)(:)(,)(:)(,)(:)(,)(:)(,)(:)(,)(:)表相关参数值设置参数符号参数名称及单位参数值V单位行驶距离(千米/小时)单位商品价格(元/吨)运输货损系数()装卸货损系数()c单位运输时间制冷成本(元/小时)c单位装卸时间制冷成本(元/小时)p早到惩罚系数(元/小时)p迟到惩罚系数(元/小时)关参数设置等输入程序中,得到生鲜品物流配送的最优配送路径时间信息、最优配送路径的相关成本数据如表、表所示.表最优配送路径及时间信息配送路径运输时间到达时间离开时间等待或延迟时间/m i n配送路径运输时间到达时间离开时间等待或延迟时间/m i n:表最优配送路径的相关成本数据车辆编号访问次序装载量/t固定成本/元运输成本/元货损成本/元惩罚成本/元总成本/元 总计 计算结果表明路径、路径、路径、路径等条路线在冷链车配送时出现车辆早到的现象,需要支付一定的等待费用,只有路径出现了配送延迟的问题,需要接受延迟惩罚,其樊兵鹏:带时间窗的生鲜冷链物流配送车辆路径问题研究他配送路径都在与客户所要求的时间窗内到达,无需支付等待费用或者延迟惩罚.在配送成本方面,计算结果表明完成此次生鲜品配送任务共需要使用辆冷链车,配送总成本为 元,其中货损成本(包括损耗成本和制冷成本)为 元,占总配送总成本的,需要物流配送企业通过改进生鲜品包装、冷藏保鲜技术、装卸搬运工具等措施降低生鲜品配送的货损成本,从而提升整体生鲜配送效率并有效降低货损成本.本文通过算例分析的方式验证了自适应遗传算法在配送方案优化和配送成本合理化方面具有明显的效果,表明遗传算法模型具有很好的实际应用价值.结论如何寻求最优配送方案和配送成本最小化问题,一直是物流配送企业关注的焦点.本文通过构建带有时间窗的车辆路径模型,研究分析了生鲜品冷链配送的路径与成本问题,综合考虑了车辆固定成本、货损成本、违反时间窗惩罚成本等多种成本因素,设计了具有加权性质的线性目标函数.最后通过实例进行验证,运用MAT L A P数据分析软件对带有时间窗约束的目标函数进行求解,得出生鲜品最优配送路径方案和配送成本合理化结果,在帮助企业提高生鲜冷链物流整体配送效率的同时降低了配送成本,验证了模型在求解路径和成本问题中具有很强的实用性和有效性.参考文献W a n gSY,T a oFM,S h iY H,e t a l O p t i m i z a t i o no fV e h i c l eR o u t i n gP r o b l e mw i t hT i m eW i n d o w s f o rC o l dC h a i nL o g i s t i c sB a s e do nC a r b o n T a xJ S u s t a i n a b i l i t y,():万玲带时间窗的冷链物流配送车辆路径优化研究 以D生鲜为例D成都理工大学,葛显龙,孔阳带有时间窗的生鲜物流配送路径优化研究J数学的实践与认识,():段雪凝带时间窗的冷链物流车辆路径多目标优化问题研究D东北大学,王维军,罗伟基于改进智能水滴算法的冷链物流配送路径优化问题研究J经营与管理,():王淑云、孙虹需求变动下的冷链品配送路径规划J公路交通科技,():俞武扬,杨沈记带软时间窗的冷链物流配送路径优化研究J生产力研究,():封学军,杨义林,蒋柳鹏,等硬时间窗约束下集装箱甩挂运输网络的车辆路径问题J长沙理工大学学报,():宋志兰,黄欢,张壮时间窗约束下带逆向物流的冷链物流车辆路径优化研究J物流技术,():侯玉梅,贾震环,田歆带软时间窗整车物流配送路径优化研究J系统工程学报,():朱长征,李艳玲碳排量最小的车辆路径优化问题研究J计算机工程与应用,():胡剑玫带时间窗的医药物流配送路径优化问题研究D江西财经大学,S t u d yo nF r e s hC o l dC h a i nL o g i s t i c sV e h i c l eR o u t i n gP r o b l e mw i t hT i m eW i n d o wF a nB i n g p e n g(G u a n g d o n gS o n g s h a nP o l y t e c h n i c,S h a o g u a n ,G u a n g d o n g)A b s t r a c t:T h i sp a p e rt a k e st h ef r e s hc o l dc h a i nl o g i s t i c sd i s t r i b u t i o np r o b l e ma st h er e s e a r c ho b j e c t,p r o p o s e s t h e f r e s hc o l dc h a i nl o g i s t i c sd i s t r i b u t i o nv e h i c l er o u t i n gp r o b l e m w i t ht i m ew i n d o w I tc o m p r e h e n s i v e l yc o n s i d e r s t h ev e h i c l e f i x e dc o s t,t r a n s p o r t a t i o nc o s t,f r e i g h t d a m a g e c o s t(i n c l u d i n g l o s s c o s t a n dr e f r i g e r a t i o nc o s t),v i o l a t i o no f t i m ew i n d o wp e n a l t yc o s t a n do t h e r c o s t f a c t o r s,a n dc o n s t r u c t s t h eo b j e c t i v e f u n c t i o no fs o l v i n gt h eo p t i m a ld i s t r i b u t i o np a t ha n dd i s t r i b u t i o nc o s tm i n i m i z a t i o n,a n dt h u saf r e s hc o l dc h a i n l o g i s t i c sd i s t r i b u t i o nm o d e lw i t ht i m ew i n d o wi se s t a b l i s h e da n dt h e r e l i a b i l i t ya n dp r a c t i c a b i l i t yo f t h em o d e l a r ev e r i f i e db ye m p i r i c a l s i m u l a t i o n K e yw o r d s:f r e s hc o l dc h a i n;D V R P TW;g e n e t i ca l g o r i t h m;d i s t r i b u t i o nc o s t;l o g i s t i c sd i s t r i b u t i o n;t i m ew i n d o w;v e h i c l er o u t i n g(责任编辑:李文英)武汉工程职业技术学院学报