第3方冷链物流配送路径优化研究.pdf

第2 0 卷第4 期 2 0 1 1 年8 月 运筹与管理 O P E R A T I O N SR E S E A R C HA N DM A N A G E M E N TS C I E N C E V 0 1 2 0 ，N o 4 A u g 2 0 1 1 第3 方冷链物流配送路径优化研究 缪小红1 ，周新年2 ，林森2 ，方万春2 ，王秀明2 ，林丽娟2 ( 1 福建对外经济贸易职业学院，福建福州3 5 0 0 1 6 ；2 福建农林大学交通学院，福建福州3 5 0 0 0 2 ) 摘要：根据冷链物流配送具有的特殊性，进一步探索冷链物流配送优化研究的方案。在保证货物不超载的情 况下，建立以一个冷链配送中心、多个顾客的冷链物流的配送数学模型，用改进遗传算法加以分析求解，并采用 M a t l a b 软件对算法进行编程，最后通过算例进行验证。得到如下结论：利用改进遗传算法得到的最优配送路线 优于标准遗传算法求解结果。 关键词：管理运筹学；配送路径优化；遗传算法；冷链物流；配送数学模型 中图分类号：C 9 3 1 1文章标识码：A文章编号：1 0 0 7 3 2 2 1 ( 2 0 1 1 ) 0 4 - 0 0 3 2 0 7 S t u d yo nR o u t i n gO p t i m i z a t i o nf o rC o l d c h a i nL o g i s t i c sD i s t r i b u t i o no f3P L M I A OX i a o h o n 9 1 ，Z H O UX i n n i a n 2 ，L I NS e n 2 ， ( 1 F u f i a nI n t e r n a t i o n a lB u s i n e s s & E c o n o m i cC o l l e g e ， F o r e s t r yU n i v e r s i t y ，F u z h o u3 5 0 0 0 2 ，C h i n a ) F A N GW a n c h u n 2 ，W A N GX i u m i n 9 2 ，L I NL i - j u a n 2 F u z h o u3 5 0 016 ；2 r r n f f i eC o l l e g e ，F u j i a nA g r i c u l t u r ea n d A b s t r a c t ：A c c o r d i n gt ot h es p e c i f i c i t yo fc o l d - c h a i nl o g i s t i c s ，w ee x p l o rt h eo p t i m a lp r o g r a m so fc o l d c h a i nl o g i s t i c sd i s t r i b u t i o n I na d e q u a t el o a d i n gc a p a c i t y ，w ee s t a b l i s ham a t h e m a t i c a lm o d e lf o rap a t t e r na so n ed e p o tt o m a n yc u s t o m e r s ，u s i n gg e n e t i ca l g o r i t h m sa n dM a t l a bs o f t w a r et oa n a l y z ea n ds o l v ei t F i n a l l y ，t h er e s e a r c hi si l l u s t r a t e db ya ni n s t a n c ea n dt h ef o l l o w i n gc o n c l u s i o ni so b t a i n e d ：t h eo p t i m a ld e l i v e r yr o u t eo b t a i n e df r o mt h ei m p r o v e dg e n e t i ca l g o r i t h mi ss u p e r i o rt ot h er e s u l t so fs t a n d a r dg e n e t i ca l g o r i t h m K e yw o r d s ：m a n a g e m e n to fo p e r a t i o n sr e s e a r c h ；t h eo p t i m a lr o u t i n go fd i s t r i b u t i o n ；g e n e t i ca l g o r i t h m s ；c o l d - c h a i nl o g i s t i c s ：m a t h e m a t i c a lm o d e lo fd i s t r i b u t i o n 0 引言 我国是一个食品生产和消费大国，大众消费的食品安全和卫生一直都是值得特别关注的问题。要保 障食品安全，就必须发展生鲜食品冷冻、冷藏供应链，将易腐、生鲜食品从产地收购、加工、贮藏、运输和销 售，直到消费的各个环节都处于适当的低温环境之中，以保证食品的质量，减少食品的损耗，防止食品的变 质和污染，以实现食品质量安全的有效控制目标- 。冷链应运而生，企业利用自己所持有的冷链运作设 备进行运作管理，或外包给第3 方冷链外包企业。运用冷链设备进行生鲜食品的运输、储存，在保持商品 鲜度的同时还可以减少由于商品鲜度下降、变色、变质和腐烂等带来的损耗，降低经营成本。 配送是冷链物流中一个极其重要的环节，生鲜易腐食品从生产者到最终消费者的过程中，有8 0 以 上的时间在配送运输上嵋1 。由于生鲜食品易腐变质的特性，食品必须在流通的全过程中持续保持适宜的 温度，并迅速周转，因此冷链物流必须使加工、运输、仓储和销售等所有环节紧密衔接，并配以合适的设备， 收稿日期：2 0 0 9 0 7 0 4 基金项目：福建省自然科学基金资助项目( 2 0 0 8 J 0 3 2 7 ) 作者简介：缪小红( 1 9 8 5 ) ，女福建福鼎人，助教从事现代物流管理研究；用新年( 1 9 5 1 ) ，男通讯作者，福建浦城人，教授，博士生导 师，从事交通运输、现代物流技术和工程索道研究等。 万方数据 第4 期缪小红，等：第3 方冷链物流配送路径优化研究 3 3 统一的管理，方能确保生鲜产品的质量。基于配送在冷链物流运营中的重要性，因此，研究如何合理安 排车辆调度，缩短货物在途时间，减少货损，从而降低冷链物流运营成本，提高顾客满意率，是具有重大意 义的。第3 方冷链物流配送是由食品的供应方和需求方以外的物流企业提供冷链物流服务，目前食品 贸易中大部分采用第3 方物流配送模式。鉴于冷链物流配送具有的特殊性，在研究第3 方冷链物流配送 路径优化问题中，除要考虑常温物流的运输成本以外，还需考虑配送过程中的生鲜食品损耗和配送时间窗 限制等因素。 1 第3 方冷链物流配送路径优化研究方案 1 1第3 方冷链物流多目标配送问题描述 由于多目标配送问题的不同目标之间相互制约，使其建模和求解具有一定的难度。因此在研究多目 标配送路径优化问题时，只考虑那些对最优路径的选取影响较大的目标。路径优化最实质的问题是要缩 减配送运输时间降低配送成本。对生鲜易腐化食品来说，配送时间的长短影响着产品的质量。对此，时间 成了企业竞争优势的一种新资源。按客户对货物取( 送) 时间的要求，物流配送调度问题分为无时限和有 时限2 种“ 】。这里将带有时间窗的配送路径问题中的时间变量引入目标函数，建模时重点考虑运输成本 和路径最短，且满足时间准时的目标，将时间约束作为目标转化成成本函数。兼顾“冷链物流配送”中的 “冷链”，即考虑到配送过程中车厢的温度控制和能量损耗问题，实现了将多目标问题分别转化成3 个单 目标问题求解。 1 2 多目标第3 方冷链物流配送模型建立 1 2 1 配送问题假设 冷链物流配送的模型为一个冷链配送中心为多个顾客( o n eD e P o tt oM a n yC u s t o m e r s ) 派送货品的配送 模型，配送的生鲜食品类型单一，同时满足以下条件： ( 1 ) 物品流向为单向，即纯送货； ( 2 ) 运输工具为K 辆汽车，每辆车都有一定的装载能力限制，满足单车的容量大于运输路线上客户的 总需求量； ( 3 ) 每个客户的需求量是已知的，所需货物只能由一辆汽车完成，且所有客户都应该得到服务； ( 4 ) 每条线路的开始和结束位置都在配送中心，所有车辆必须在规定的时间内返回配送中心； ( 5 ) 每个客户都有一个指定的服务时间窗，送货必须在此时间范围内进行； ( 6 ) 目标为多目标，车辆运输费用最小、车辆运输时间及全部客户的等待时间最短； ( 7 ) 配送中心与客户之间，以及两两客户之间的最优配送线路已知。 1 2 2 配送模型建立 根据决策目标。模型以综合成本最低作为目标函数。综合成本包括：配送车辆的运输成本和生鲜食品 在配送途中腐坏所造成的货损成本，以及超出客户时间窗的惩罚成本。 ( 1 ) 配送车辆的运输成本 配送车辆运输成本包括固定成本和变动成本2 部分。其中固定成本为常数，与运输里程和客户数量 都没有直接关系】。因此，为了计算方便，在这里不考虑。主要考虑配送车辆的变动成本。包括油耗、维 修和保养等成本，配送车辆的变动成本与车辆所行驶的里程数呈正比。对于配送车辆运输成本，采用公式 ( 1 ) 来计算。 Z l = g i Y q i t 0 荟y 诗= 二 茗班= i - 0 石驰= Y 诖 ，= o c 毋 i = 0 = 0 = 0 k = 1 ，2 ，A ，m f = 1 ，2 ，A ，m f = 0 = 0 ，1 ，A ，n ；k = 1 ，2 ，A ，m i = 0 。1 ，A ，l ( 1 ) ( 1 a ) ( 1 b ) ( 1 e ) ( 1 d ) 万方数据 3 4 运 筹与管 理 2 0 1 1 年第2 0 卷 茗珊= 0 或i ，- = 0 ，1 ，A ， t ；蠡= 1 ，2 ，A ，m ( 1 e ) Y 诸= 0 或i ，= 0 ，l ，A ，n ；后= 1 ，2 ，A ，m ( 1 f ) 其中：c 啦为第k 部车在路段( 移；，吩) 的运输成本，且c 班= ；菇 ； 为0 ，1 变量，若第k 部车行经( q ，印) 路段，则 戈涵为1 ，否则为0 ；) ，让为0 ，l 变量，若客户i 的任务由第后部车完成，则y 谙为1 ，否则为0 。目标函数( 1 ) 要求 合理安排车辆路径，使运输成本最小，运输式( 1 8 ) 为汽车容量约束，式( 1 b ) 保证了每个客户点的运输任务 仅由m 辆车来完成，而所有的运输任务由m 辆车协同完成，式( 1 c ) 和式( 1 d ) 限制到达和离开某一客户的 汽车有且仅有1 辆。 为了安排路线，需要对使用的汽车数m 有一个估计。在现实情况中，货物装( 卸) 车越复杂，约束条件 越多，一辆车的实际载货量就会越小。可以使用文献 7 l 的公式来确定需要的汽车数：m = g ；a q + l ， 其中m 取整，口为参数，0 口 I ，约束条件越多，货物装( 卸) 车越复杂，口值越小。 ( 2 ) 超出客户配送时间的惩罚成本 用s i 表示车辆到达客户；的时刻，t ；表示车辆在客户i 停留的时间，t 。，表示车辆由客户f 行驶到客户_ 的时间一般有以下的关系式 5 0 = 0 髫班2l j s i + t i + f 口。勺 i , j = 0 ，I ，A ，l ，i _ E f s f t J = 0 ，1 ，A ，r t t = m a x E i s f ，0 采用软时间窗的做法，即如果某项任务不能在要求的时间范围内完成，则给予一定的惩罚。如果车辆 在E ，之前到达客户，则车辆在此等待( 因为客户可能还没有准备好存放该物品的仓库) ，发生机会成本的 损失，此时t ；大于0 ；若车辆在r ，之后到达客户_ ，则配送任务被延迟，实际中肯定要支付一定的罚金。以 d 和e 分别表示车辆等待和迟到带来的单位损失成本，若车辆在E ，之前到达客户，则产生成本为d ( E ，一 s f ) ，若车辆在t 之后到达客户_ ，则产生的惩罚成本为e ( s ，一巧) ，从而生鲜货物配送过程中的时间窗惩罚 成本可以表示为 z ：= d m a x ( E j 一，o ) + e m a x ( s j 一巧，o ) ( 2 ) ( 3 ) 配送过程中的货损成本 生鲜食品属于易腐( P e r i s h a b l e ) 性食品，影响生鲜食品腐坏的因素很多，假定生鲜食品运送过程中能 保持在固定的运送温度下，不考虑其它的影响因素的条件，则配送时生鲜食品的腐坏仅与运送时间有关； 另一方面，由于服务顾客时，后车厢门开启，会加剧生鲜食品腐坏的速度。随着开启时间的长短与开启频 率不同，会对生鲜食品品质造成不同程度的影响哺1 。故分为2 种情况对生鲜食品的腐坏进行分析：一类为 运送途中因运送时间累积，生鲜食品腐坏所造成的货损损失；另一类则是在服务顾客时，因车辆车厢门的 开启造成空气的对流，车厢内的冷空气流出外界热空气流入，使得车厢内的温度上升，造成生鲜产品品质 急速下降而造成货损。这2 部分成本可用公式( 3 ) 计算。 z ，= P A 庐( a t 勺+ 口：岛) ( 3 ) 其中：p 为生鲜产品单价；A 雄为0 ，l 变量，若第k 部车辆服务客户，则A 雄= 1 ，否则，A 砖= 0 ；t t 。为运送过程 中生鲜食品货损比例；口：为装卸操作过程中生鲜食品货损比例；= ；，为服务完i 客户后前往_ 客户的里程；卢， 为客户的货物数量。 1 2 3 配送优化模型 冷链物流配送优化模型如下 r a i nz = 三c 咖+ d m a x ( E j i ；OJ = oI = lj ；I s t =，2，At g l Y l l q k12A ，m s 乞 2， i = 0 一巧，o ) + P A 辟( 口。勺+ 口：岛) - I = I ( 4 ) ( 4 a ) ，L Xam 。 e+ 、， O 一 万方数据 第4 期缪小红。等：第3 方冷链物流配送路径优化研究 3 5 = 1 _ = 0 ，1 ，A ，死( 4 b ) 茗，= 凡 ( 4 c ) 1 。u u 埘 = I = 0 ，I ，A ，厅 ( 4 d ) 易s t ，= o ，1 ，A ，n ( 4 e ) 其中：式( 4 a ) 表明每辆车的载货量不超过自身最大载货量q ；式( 4 b ) 表明每个客户只被服务一次，不存在 重复服务；式( 4 c ) 表明所有的客户都被服务到，没有遗漏；式( 4 d ) 表明每个客户只被1 辆车服务；式( 4 e ) 表明客户的服务时间须在客户可接受的范围内。 2 改进遗传算法求解冷链配送问题 2 1 遗传算法的基本原理 遗传算法是一种“生成+ 检测”的迭代搜索算法。它以种群中的所有个体为操作对象、每个个体对应 问题的一个解。选择、交叉和变异是其3 个主要操作1 。应用M a t l a b7 0 ，编制适合该算法模型的计算机 程序，完成对配送问题的求解过程，求得最优路径，实现对实际问题的指导。 该算法包括以下6 个基本要素： ( I ) 编码：遗传算法不能直接对空间的数据进行处理，必须通过编码将它们表示成基因型串数据。 ( 2 ) 生成初始种群：初始种群的个体通过随机方法产生，且对应研究问题的一个解。 ( 3 ) 评估适应度：遗传算法在搜索过程中用适应度来评估个体的优劣，并把它作为遗传操作的依据。 适应度函数常取非负数，且适应度增大的方向与目标函数的优化方向一致。 ( 4 ) 选择：根据“适者生存”的选择原理，从当前种群中选择生命力强的个体( 即适应度高的个体) 产 生新的种群。适应度越高的个体，被选择的机会就越大，但并不意味着适应度高的个体一定会被选择。 ( 5 ) 交叉：将选择出的个体存入配对库，用随机的方法进行配对，以产生新一代的个体0 。 ( 6 ) 变异：在交叉过程中可能丢失一些重要的遗传信息，必须引人适度的变异，即按一定的概率改变 染色体基因位。 2 2 遗传算法的操作实现 2 2 1 编码方式设计 采用自然数编码方法，构造易腐货物即时配送路线优化问题解向量的染色体结构。把数学模型中的 解向量编成一条长度为n + m + 1 的染色体，表示一条可行配送路线，即：G = ( 1 ，i 儿，i A i ，I ，f ：。，i ：，A ， 1 ，i ：。，I A ，1 ，i 。，i 。：，A ，i 。I ) 1 1 。可将其理解为：第1 辆配送车从“0 ”出发，完成任务“i i 。：，A ，i 。”后，又 回到“0 ”，形成子路径l ；第2 辆配送车再从“0 ”出发，完成以前未访问过的任务“i ：。，i ：，A ，f ：。”后，也回到 “0 ”，形成子路径2 ；如此反复直到完成全部任务。 如染色体0 2 3 0 1 4 5 0 6 7 8 0 表示行车路线： 子路径l ：配送中心0 一客户2 一客户3 一配送中心0 子路径2 ：配送中心0 一客户1 一客户4 一客户5 一配送中心0 子路径3 ：配送中心0 一客户6 一客户7 _ + 客户8 一配送中心0 这种染色体结构子路径的内部是有序的，若子路径1 中的任务点1 、2 相互交换位置，会使目标函数值 改变；而子路径之间是无序的，若子路径1 和2 之间交换位置，不会改变目标函数值。 2 2 2 遗传算子设计 在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体的概率。个体的适应度越大， 该个体被遗传到下一代的概率也越大；反之。个体的适应度越小，该个体被遗传到下一代的概率也越小，并 要求所有个体的适应度必须为非负2 。对于求该最短路径的优化问题，适应度函数取目标值的倒数，即 疋= 1 z Io 万方数据 3 6运 筹 与 管 理 2 0 1 1 年第2 0 卷 选择算子 选择算子一般有轮转法、最优保存方法和期望值选择方法等，遗传算法的理论已经证明轮转法选择算 子不能收敛到全局最优解，而最优保存方法能收敛到全局最优解3 1 。这里，采用轮转法对遗传算子进行 选择，选择概率为P 。= 以Z ，L 为染色体个数。 不五 交叉算子 采用用O X 法实施交叉操作引，具体操作举例如下：随机在父代个体中选择一个交配区域，如路线 A = 4 7 8 5 6 3 9 2 ，B = 8 3 4 6 9 1 2 5 ；将B 的交配区域加到A 的前面，A 的交配区域加到B 的前面，得 A = 4 6 9 1 4 7 8 5 6 3 9 2 B = 8 5 6 3 8 3 4 6 9 1 2 5 在A ，曰中自交配区域后依次删除与交配区相同的自然数，最终个体为 A = 4 6 9 1 7 8 5 2 3 B = 8 5 6 3 4 9 1 2 这种交叉操作的优点在于：在2 个父代个体相同的情况下，仍能产生一定的变异效果，这对维持群体的多 样性有较好的作用。 变异算子 采用均匀变异法，选取0 0 2 的变异概率对父代染色体进行变异，即有2 的染色体发生变异，且每条 染色体发生变异的机率是均等的，随机确定染色体中发生变异的基因位及其个数。染色体的变异操作完 成后，重新判断s 的适应度值，若其大于原染色体的适应度值，则此次变异成功，将后代染色体s 作为新的 染色体加入到子代中；否则为变异失败，将父代染色体加入到子代中引。通过染色体变异能够将可变性 引入群体，从而提供了跳出局部最优解的一种手段，进而有机会继续寻找问题的全局最优解。 3 算例分析 3 1 算例验证 为验证改进遗传算法的有效性，以福州国运通冷藏运输有限公司为市区内客户的配送过程为例。配 送中心编号为“0 ”，对市区内的1 0 个顾客点进行配送服务。据第3 方冷链物流配送商提供的资料，配送 货物为超市每天出售的白菜，上海青，番茄和土豆等鲜蔬类，并保证不串味。保存时限为1 2 小时。当外界 温度超过2 0 时，配送冷藏车内温度控制在2 一1 5 ，外界温度低于2 0 。C 时，采用常温运输。 各配送点的坐标值( 坐标系采用北京坐标系) ，时间窗约束和服务时间，以及各配送点的需求量，见表 2 ；各点之间的配送距离见附表3 。采用的小型货车的运输能力为4 I ，假设所有路段均为非禁行路段，且配 送车辆在配送过程中平均行驶速度为3 5 k m h ，单位里程的运输成本为2 元公里。在满足不超过车辆载 量约束的同时，合理安排配送路线。 表l 配送距离及各配送点的需求量 配送点至各配送点距离k i n需求量t 0 5 0 0 6 5 O 3 0 2 3 O 5 0 O 5 5 0 4 2 0 5 l 0 4 0 O 3 5 m 埒m M m 8坶8：”O 9 9 6 ：“挎m 9 婚9 O 坩 0硌堪n”n埒n”O 9 心 7 悖u 9 m 坫8 O ：2 b 8 6：2：坫：他7 O 8 9 均 5 m M n 坞0 7 培m 0 4 儿m 8 9 O 埔! ：2 n 悖m ，”7O 9 ”j m ：2 U M 2 眨H O 8 H 圩9 儿! m ：2 O H 7 m屹U堪6：2 O 0临也好儿m：2挎巧9 M O l 2 3 4 5 6 7 8 9 m 万方数据 第4 期缪小红，等：第3 方冷链物流配送路径优化研究 3 7 3 2 结果分析 根据蔬菜产品配送的具体要求，对该问题进行求解。设定参数口= 0 8 5 ，确定需要的汽车数：m = g a q + 1 = 4 g I O 8 5 4 + 1 = 2 。利用所提出的改进遗传算法，设定指定种群个数儿= 1 0 0 ，最 大进化代数C = 1 0 0 ，交叉概率P 。= 0 9 ，变异概率P 。= 0 2 ，借助M a t l a b7 0 实现迅速搜索，得到最优配送 路线为：0 9 一l 一3 4 2 0 ，0 8 6 7 一1 0 5 0 计算得相应配送里程为l O g k m 。 表3 基于改进遗传算法的配送时问窗核对 核对表3 中的每一配送任务，上述1 0 个配送点的配送时间均在配送时间窗内，故此处不存在惩罚成 本。由于生鲜食品腐坏因素由运送时间和服务客户时车厢开启时间来决定，已知蔬菜的单价P 为4 0 0 0 元t ，运输过程中货损系数为0 1 ，装卸过程中的货损系数为0 2 ，运输里程l O g k m ，货物数量4 4 1 t ，根 据公式( 3 ) 进行计算，得到货损成本为5 1 6 元。 在相同控制参数条件下，利用标准遗传算法，针对该问题进行搜索。搜索过程中的种群代数、染色体 个数和变异概率等控制参数与上述改进遗传算法中的完全相同，但得到最优配送路线如表4 。 表4 基于标准遗传算法的配送时间窗核对 由此可见，利用改进遗传算法得到的最优配送路线，能够充分满足各连锁店的时间窗约束及配送车辆 的容量限制约束；标准遗传算法只考虑配送车辆的容量限制约束，并未考虑到各连锁店的时间窗约束，导 致时间惩罚成本高，客户满意度下降，而且计算时间复杂度大。因此，研究所采取的这种改进遗传算法，在 求解冷链货物配送路线优化问题时明显优于标准遗传算法。 4 结束语 根据冷链物流的特殊性研究冷链物流的配送管理，以软时间窗限制下的车辆路径问题为基础，分析生 鲜产品路线配送特性并构建相关成本函数，包括因产品腐坏所造成的货损成本、违反顾客需求时间窗所造 成的惩罚成本，以及传统车辆路径问题中的运输成本等。以上述各项成本的总和最小为目标，构建冷链物 万方数据 3 8运 筹与管 理2 0 11 年第2 0 卷 流配送路径的基本模型。考虑到冷链物流与常温物流、冷链物流配送与常温物流配送在运作过程中的特 殊性，但是把模型定在一个相对狭小的范围内，对能耗的分析相对薄弱。如运输距离或时间较短，冷藏车 打冷与不打冷对运输货物的温度变化大与否，冷链效果明显与否；如果能计算出在什么样的时间范围内冷 藏车车载冷冻机没必要打冷，而超出这一时间范围就必须打冷的界限等问题，这将对第3 方冷链物流企业 降低运营成本，确保冷链物流质量和食品安全等具有重大意义。 参考文献： 9 l O 1 1 1 2 1 3 1 4 1 5 邓汝春我国的冷链物流市场及其发展策略 J 商场现代化，2 0 0 8 ，( 2 ) ：8 - 1 4 缪小红，周新年，巫志龙生鲜食品冷链物流研究进展探讨 J 物流技术，2 0 0 9 ，2 8 ( 2 ) ：2 4 - 2 7 S u nY a n ，C a iH u a w e i ，Z h c n gL i m i n ，e ta 1 D e v e l o p m e n ta n dc h a r a c t e r i z a t i o no fan e wa m y l a s et y p et i m e t e m p e r a t u r ei n d i c a t o r J F o o dc o n t r o l ，2 0 0 8 ，1 9 ( 3 ) ：3 1 5 3 1 9 汪祖柱，程家兴。方宏兵等车辆路径问题的混合优化算法 J 运筹与管理，2 0 0 4 ，1