| 标题 | 带时间窗的冷链物流车辆路径优化问题研究 |
| 范文 | 徐松梅 摘 要：文章研究了带有硬时间窗限制的超市速冻食品冷链配送车辆路径优化问题，根据其配送批量小，配送地点分散，时间要求高的特点建立了配送成本最小的目标函数，以降低物流的配送成本，提高其经济效益。该模型考虑了配送过程中的固定成本、运输成本、时间惩罚成本以及制冷成本，其配送车数、每两个客户间的运输量、配送时间以及卸货时间相互作用，共同影响总成本，然后采用遗传算法求解，最后以一个物流公司为算例，进行求解证明该模型的可行性。 关键词：路径优化；冷链物流；遗传算法 中图分类号：U116.2 文献标识码：A Abstract： In this paper， we study the optimization of the problem of the cold chain distribution of the frozen food in the supermarket with the hard time window. According to the characteristics of the small batch distribution， the scattered distribution time and the high time requirement， the objective function of the minimum distribution cost is established to reduce the distribution of the logistics cost， improve its economic efficiency. The model takes into account the fixed costs， transportation costs， time penalty costs and cooling costs in the distribution process， the number of dispatch vehicles， the amount of traffic between each two customers， the delivery time， and the time of unloading， which together affect the total cost and then using genetic algorithm to solve， and finally to a logistics company as an example， to prove the feasibility of the model. Key words： path optimization； cold chain logistics； genetic algorithm 0 引 言 随着人们对新鲜食品的需求不断增多，冷链物流配送得到急速发展，现今我国很多中小城市的物流公司发展较落后，专门提供冷链配送的企业较少，大多物流企业将冷链配送作为副业，缺少对冷链配送的详细规划，因而冷链物流配送水平较低，降低配送成本与满足客户要求很难同时兼顾，尤其在满足超市冷鲜产品供应方面更加明显。冷链物流的高成本源于运输设备价格较高，制冷成本较高以及未按时到达产生的惩罚成本三部分组成，所以选择合适的配送路径可以满足客户的时间要求，最大限度地降低配送成本，提高企业的竞争力和经济效益。 1 国内外研究综述 目前国内外冷链物流配送研究可分为对冷链物流的配送路径的模型研究以及对冷链物流配送路径算法研究。冷链物流配送路径模型方面：王淑云、孙虹[1]探讨了顾客需求变动下的冷链配送路径模型。潘东静[2]针对零售点农产品需求模糊的情况进行分析，建立了适用于模糊需求的冷链最小成本模型。石兆、符卓[3]结合了配送网络时变特征对食品冷链配送的易腐性进行行程时间分析，通过建立时变条件下的仿真模型来求解在配送网络体系下的最优路径。于坤[4]研究了具有同时取送货特征的典型城市冷链物流配送状况。王晓宁[5]以冷链物流的高耗能和高排碳为研究的对象，主要研究了在农产品的新型流通形式即农超对接模式下的冷链物流碳排放。 冷链物流配送路径优化算法方面：缪小红[6]运用了具有GIS功能的二次开发软件——Map Objects控件和VB开发平台来辅助解决路径优化问题。吕俊杰、孙双双[7]用蚁群算法和matlab工具对实例进行求解分析。杨玮等[8]用优化的粒子群算法解决农产品冷链物流配送路径优化问题。刘镇等[9]构建了冷链物流配送车辆路径优化模型，利用粗粒度并行遗传算法，在云计算环境下对模型求解。邱荣祖等[10]应用GIS与禁忌搜索法集成技术对带时间窗的车辆路径问题进行求解。 目前对于冷链物流配送路径优化问题的研究大多是针对农产品以及生鲜类食品长途跨市（省）运输，并在建模中考虑到货损成本，以一种农产品（生鲜品）单价作为参考数据求解模型，很少有对市内超市速冻食品配送路径问题的研究，况且农产品（生鲜品）的售价差距较大，易受货损程度不一，以某种农产品为例计算运输成本以及货损成本不尽合理，实际效用不高。本文研究了市内超市速冻食品配送问题，由于配送一般要求当日送达，基本不存在货损成本，从而可以以均价参数，提高模型的精确度，具有较强实际应用价值。 2 问题描述及模型建立 2.1 问题描述 城市冷链物流配送除了要考虑传统配送中的顾客需求量、顾客时间要求、车辆限制以及车行驶里程外，还要考虑到温度的控制，包括在运输途中产生的制冷费用、在卸货时由于温差而產生的额外费用和制冷运输车的成本。由于研究对象是市内超市配送，超市营业时间相近，各超市的卸货时间时长不同，导致在短时间内完成多点配送较为困难，因而研究难点在于在降低配送里程的同时，尽量满足顾客的时间要求，减少惩罚成本。 本文研究一个配送中心，多配送地点的超市速冻食品冷链物流配送路径优化问题，客户地址与需求量已知，同时考虑配送的时间惩罚成本并做出如下假设：（1）配送同一种饮料；（2）配送发生在早上，不会突然产生交通拥堵；（3）配送时路面状况良好；（4）每辆冷藏运输车只服务一条路径；（5）每个客户都只被服务一次。 2.2 数学模型 根据传统的车辆路径问题可设道路网络图GV，A为完全对称网络，其中集合V=v，v，…，v代表配送中心及其客户地址，k=1，2，3，…，m表示某物流公司所拥有的车辆数目，d为包括配送中心在内的配送节点间的距离，i，j=0…n。g为第k辆车从i地到j地的送货量。则c为运输成本，其单位为吨·公里。在时间窗限制条件下，冷链配送成本主要由车辆固定成本、运输成本、时间惩罚成本以及制冷成本组成。其中固定成本是投入每辆车所需消耗的必须成本，包括车辆维修以及操作人员薪资等费用，该成本与运输里程无关。运输成本与车辆行驶里程有关，时间惩罚成本是当车辆早到或迟到时作为未按规定时间到达所产生的费用。制冷成本发生在车辆配送时用于保持车厢内食品所需温度所花成本以及在卸货过程中车厢内外冷热空气交替所产生的额外制冷费用。 固定费用fk=1，2，…，m，其中k代表车辆，固定成本与配送车辆数目呈正相关，即若最终结果使得配送车辆减少则相应的固定成本也会降低。 假设车辆k将货物从i客户配送至j客户，其配送成本为d×c×g×y，其中y为0-1变量，当第k辆车将货物从i客户运往j客户时y=1，当第k辆车没有将货物从客户i送往客户j时，y=0。由于本文为使计算精确并贴近实际单位运价采用吨·公里来度量，使得计算难度加大，即g表示的为从客户i到客户j时车上的总货量，例如从配送中心出发到第一个客户的货运量是第k辆车服务的整条配送路径上的货运总量，当到达第一个客户i并卸货后，从客户i到下一个客户j的货运总量为除去客户i的需求量后余下的送货量，以此类推递减，直到送完最后一个客户时，该车辆应为空箱返回配送中心。即运输费用与配送里程呈正相关，与配送量呈负相关。传统的运输成本计算往往固定了节点间的运输成本，使其采用统一价格，在实际操作中并不可行，第一节点间的运输费用是由车辆里程和运量共同决定的，随着车辆的服务客户的增加，该费用也会随之变化，因而固定节点间的运费本身存在较大误差。第二传统的固定节点间费用忽略了空车返回的成本，本文的方法可以最大限度合理化配送次序，减少空车行驶里程。 对于速冻食品来说，车辆配送过程中车厢内应时刻保持低温状态，但在卸货过程中由于车厢内外存在温差，为了维持车内的平均温度，会产生更高的制冷费用，当车厢内外的温差越大所需的功率就越高，相应的制冷费用就越大，为了简便计算，将卸货过程中的制冷成本分为两部分：不考虑温差时，为维持车内的温度所需的制冷费用以及由于车厢内外温差所导致的额外的制冷费用，总制冷成本不仅包括运输途中的费用也包括装卸时的费用。无冷热空气对流的制冷成本包括运输过程中的制冷费用以及不考虑温差的卸货时产生的制冷成本，由如下公式表示：αd/s+g/？覣其中i≠j。在本公式中α为不考虑温差的制冷系数，代表每单位时间内所产生的制冷费用，s为冷藏车的运输时速，g表示第j个客户的需求量，？覣为在客户j处的卸货效率。运输到装卸地点后，冷藏车厢内外温差，打开冷藏车门后由于空气对流会导致车厢内的气温升高，所以为了保持车内的温度不变，需要增大功率，因增加的功率而产生的额外制冷成本计算公式为：θ·g/？覣·T，其中θ为卸货时的气温每升高一度单位时间内产生的成本，T为车厢内外温差。 时间惩罚成本遵循硬时间窗惩罚成本，如图1所示，ES与KS分别代表着配送车辆早到时客户能够接受的最早送货时间和配送车辆晚到时客户能够接受的最晚送货时间，ES，KS为客户可以接受的送货时间，本文为方便计算以某一时间点为基准，以分钟为单位来进行计时以及时间限制。当配送车辆到达客户j地的送货时间t（即从客户i到客户j的送货时间，包括在客户j处的卸货时间）少于客户j的最早接货时间ES时，其产生的惩罚费用为M；当配送车辆到达客户j地的送货时间t超过客户j的最晚接货时间KS时，其产生的惩罚费用为M。在实际情况中，配送车辆早到所产生的惩罚成本小于配送车辆晚到所产生的惩罚成本，即M minz=f+d×c×g×y+αd/s+g/？覣+θ×g/？覣×T+M×δ+M× y≤5 i，j=0，1，2，…，n （1） y≤1 j，k=1，2，3，…，n （2） y≤1 i，j=0，1，2，…，n （3） y≤1 i，k=1，2，3，…，n （4） y=N k=1，2，…，m （5） g≤Q k=1，2，…，m （6） 在上述模型中，约束（1）保证实际配送车数量不超过该公司拥有车数，约束（2）表示每一个出发地最多只有一个接受地，约束（3）表示每个客户最多只被一辆车服务，约束（4）表示每个客户最多接受一次配送服务，约束（5）所有客户都要被服务，约束（6）每条配送路径的车载量不得超过该车最大载重量。该模型共有三个0-1变量： ①y=代表车辆k是否服务点；②δ=代表车辆早于客户j的要求时间到达；③=代表车辆晚于客户j的要求时间到达。 3 物流配送模型算法以及案例求解 3.1 遗传算法求解 求解步骤如图2： 3.2 遗传算法设计 （1）问题编码。本文研究的问题是冷链物流配送，首先就要问题的配送中心和客户点进行编码。编码设计是采用客户节点直接编码，并不将配送中心编入其中，直接对n个客户节点进行全排列，每一种排列方式就是一种解，其中數列的顺序就是配送车辆到达的顺序，如：若随机产生一个染色体为（3，4，2，5，8，9，7，1，6），则说明该路径的配送顺序为3—4—2—5—8—9—7—1—6，每一个染色体代表一个配送方案，再在每个染色体头尾添加0元素。 （2）初始种群设定。初始化种群，随机产生对33个客户节点所进行的全排列的染色体，这样的染色体共有100个，会形成100行33列的二位矩阵。 （3）适应度函数设定。适应度函数为目标函数。找出第i染色体，获取其配送客户顺序，先对每个客户的需求量进行加总，使总重不超过车的载重能力，再针对第一个客户的需求量进行运输费用求解，并算出运输时间与装卸时间，以便计算制冷费用以及时间惩罚费用，然后再计算下一个客户的运输费用，并在上一个客户运输时间和装卸时间总和的基础上计算本客户的配送时间是否符合本客户要求，从而判断是否产生惩罚成本，但运输的制冷费用的时间为本段路的运输时间和装卸时间，并依此类推，完成配送。最后用for循环语句找出配送总成本最小的车，这样一直重复找，直至再找不出更小的配送成本的车辆为止。 （4）选择算子。本文采用的是轮盘赌法。将个体的适应度值比上总染色体的适应度值，作为该个体所占概率。随机选择轮盘旋转圈数，令pick为随机数，再让pick减去第i个染色体所占概率，对初始种群中的染色体全部进行该项循环操作，总共会有sizepop次循环，当pick为负数时，循环才会终止。 （5）交叉算子。本文采用的是单点交叉的方法，即随机选择一个基因位置将两个染色体的同基因位置上的基因进行交换，以增加染色体的数目，增加种群规模。 （6）变异算子。本文采用的变异过程是将某一染色体的某两个基因位做出交换，以改变其个体。随机选择一个数，若该数字小于变异概率则不进行变异操作，若该数字大于变异概率则进行变异。变异位置也是随机选择的。 3.3 算例求解 赛嘉物流公司以长途运输大宗商品为主，超市配送业务为副业，该公司共有5辆冷藏配送车，配送网点18个，目前5辆车全部投入配送业务中，车速限定为40公里/小时，即0.75km/分。每台配送车的最大车载量为5t。为方便计算本文以某天的气温为参考，车厢内外温差为10℃，速冻食品单价为6～10元，取均数8元。卸货效率为45斤/min，不考虑车厢内外温差的制冷系数α为20元/时，额外制冷系数θ为5元/时，早到的时间惩罚系数M为50元，迟到的时间惩罚系数M为100元。每车的固定费用为120元/车。具体配送情况如表1至表4所示： 遗传算法的参数为：染色体长度=33×2；种群规模=100；迭代次数=1 000；交叉概率=0.8；变异概率=0.2。运行结果为：2。运行图如图3所示： 通过运算得到配送方案如表5所示： 相比较原来配送方案，该配送方案少用了一辆运输车，总运输费用下降到1 281.738元，说明该模型有效。 4 结 论 本文针对带时间窗的超市速冻品冷链配送问题进行了研究，基于城市配送的批量小、地点分散、时间要求高的特点，建立了以最小配送成本为目标函数的模型，从而进行路径的选择，进一步提高配送效率，降低配送能耗和最大化配送效益。本文的單位运输成本取均值来计算，在实际生活中，每个路段的单位运输成本不可能一成不变，因而可以考虑构建物流配送系统，实时记录配送的单位成本的变化，可以进一步提高模型的精确度。 参考文献： [1] 王淑云，孙虹. 需求变动下的冷链品配送路径规划[J]. 公路交通科技，2014（8）：144-150. [2] 潘东静. 具有模糊需求的农产品冷链物流车辆配送路径优化研究[J]. 安徽农业科学，2015（5）：334-336. [3] 石兆，符卓. 时变网络条件下带时间窗的食品冷链配送定位——运输路径优化问题[J]. 计算机应用研究，2013（1）：284-288. [4] 于坤. 基于VRPSDP问题的城市冷链物流配送路径优化研究[D]. 大连：大连海事大学（硕士学位论文），2014：1-52. [5] 王晓宁. 农超对接模式下生鲜农产品冷链物流车辆配送路径研究——基于碳减排视角[D]. 南昌：华东交通大学（硕士学位论文），2014：1-60. [6] 缪小红. 基于GIS的生鲜食品冷链物流配送路径优化研究[D]. 福州：福建农林大学（硕士学位论文），2010：1-77. [7] 吕俊杰，孙双双. 基于鲜活农产品冷链物流配送的车辆路径优化研究[J]. 广东农业科学，2013（9）：178-181. [8] 杨玮，李国栋，张倩. 基于粒子群算法的农产品冷链物流配送路径优化研究[J]. 陕西科技大学学报，2013（3）：150-153. [9] 刘镇，徐优香，王译. 基于云计算的冷链物流配送路径优化方法研究[J]. 电子设计工程，2013（17）：122-127. [10] 邱荣祖，钟聪儿，修晓虎. 基于GIS和禁忌搜索集成技术的农产品物流配送路径优化[J]. 数学的实践与认识，2011（10）：145-152. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。