带时间窗的冷链物流车辆路径优化问题研究

-精选财经经济类资料- -最新财经经济资料-感谢阅读- 1 带时间窗的冷链物流车辆路径优化 问题研究 摘 要：文章研究了带有硬时间 窗限制的超市速冻食品冷链配送车辆路 径优化问题，根据其配送批量小，配送 地点分散，时间要求高的特点建立了配 送成本最小的目标函数，以降低物流的 配送成本，提高其经济效益。该模型考 虑了配送过程中的固定成本、运输成本、 时间惩罚成本以及制冷成本，其配送车 数、每两个客户间的运输量、配送时间 以及卸货时间相互作用，共同影响总成 本，然后采用遗传算法求解，最后以一 个物流公司为算例，进行求解证明该模 型的可行性。 中国论文网 /8/view-13005116.htm -精选财经经济类资料- -最新财经经济资料-感谢阅读- 2 关键词：路径优化；冷链物流； 遗传算法 中图分类号：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 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 3 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 引 言 随着人们对新鲜食品的需求不断 增多，冷链物流配送得到急速发展，现 今我国很多中小城市的物流公司发展较 落后，专门提供冷链配送的企业较少， 大多物流企业将冷链配送作为副业，缺 少对冷链配送的详细规划，因而冷链物 流配送水平较低，降低配送成本与满足 客户要求很难同时兼顾，尤其在满足超 市冷鲜产品供应方面更加明显。冷链物 流的高成本源于运输设备价格较高，制 冷成本较高以及未按时到达产生的惩罚 成本三部分组成，所以选择合适的配送 路径可以满足客户的时间要求，最大限 度地降低配送成本，提高企业的竞争力 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 4 和经济效益。 1 国内外研究综述 目前国内外冷链物流配送研究可 分为对冷链物流的配送路径的模型研究 以及对冷链物流配送路径算法研究。冷 链物流配送路径模型方面：王淑云、孙 虹1探讨了顾客需求变动下的冷链配送 路径模型。潘东静2针对零售点农产品 需求模糊的情况进行分析，建立了适用 于模糊需求的冷链最小成本模型。石兆、 符卓3结合了配送网络时变特征对食品 冷链配送的易腐性进行行程时间分析， 通过建立时变条件下的仿真模型来求解 在配送网络体系下的最优路径。于坤4 研究了具有同时取送货特征的典型城市 冷链物流配送状况。王晓宁5以冷链物 流的高耗能和高排碳为研究的对象，主 要研究了在农产品的新型流通形式即农 超对接模式下的冷链物流碳排放。 冷链物流配送路径优化算法方面： 缪小红6运用了具有 GIS 功能的二次开 发软件Map Objects 控件和 VB 开发 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 5 平台来辅助解决路径优化问题。吕俊杰、 孙双双7用蚁群算法和 matlab 工具对 实例进行求解分析。杨玮等8用优化的 粒子群算法解决农产品冷链物流配送路 径优化问题。刘镇等9构建了冷链物流 配送车辆路径优化模型，利用粗粒度并 行遗传算法，在云计算环境下对模型求 解。邱荣祖等10 应用 GIS 与禁忌搜索 法集成技术对带时间窗的车辆路径问题 进行求解。 目前对于冷链物流配送路径优化 问题的研究大多是针对农产品以及生鲜 类食品长途跨市（省）运输，并在建模 中考虑到货损成本，以一种农产品（生 鲜品）单价作为参考数据求解模型，很 少有对市内超市速冻食品配送路径问题 的研究，况且农产品（生鲜品）的售价 差距较大，易受货损程度不一，以某种 农产品为例计算运输成本以及货损成本 不尽合理，实际效用不高。本文研究了 市内超市速冻食品配送问题，由于配送 一般要求当日送达，基本不存在货损成 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 6 本，从而可以以均价参数，提高模型的 精确度，具有较强实际应用价值。 2 问题描述及模型建立 2.1 问题描述 城市冷链物流配送除了要考虑传 统配送中的顾客需求量、顾客时间要求、 车辆限制以及车行驶里程外，还要考虑 到温度的控制，包括在运输途中产生的 制冷费用、在卸货时由于温差而a 生 的额外费用和制冷运输车的成本。由于 研究对象是市内超市配送，超市营业时 间相近，各超市的卸货时间时长不同， 导致在短时间内完成多点配送较为困难， 因而研究难点在于在降低配送里程的同 时，尽量满足顾客的时间要求，减少惩 罚成本。 本文研究一个配送中 心，多配送地点的超市速冻食品冷链物 流配送路径优化问题，客户地址与需求 量已知，同时考虑配送的时间惩罚成本 并做出如下假设：（1）配送同一种饮 料；（2）配送发生在早上，不会突然 产生交通拥堵；（3）配送时路面状况 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 7 良好；（4）每辆冷藏运输车只服务一 条路径；（5）每个客户都只被服务一 次。 2.2 数学模型 根据传统的车辆路径问题可设道 路网络图 GV，A 为完全对称网络，其 中集合 V=v，v，v 代表配送中心及 其客户地址，k=1，2，3，m 表示 某物流公司所拥有的车辆数目，d 为包 括配送中心在内的配送节点间的距离， i，j=0n。g 为第 k 辆车从 i 地到 j 地 的送货量。则 c 为运输成本，其单位为 吨公里。在时间窗限制条件下，冷链 配送成本主要由车辆固定成本、运输成 本、时间惩罚成本以及制冷成本组成。 其中固定成本是投入每辆车所需消耗的 必须成本，包括车辆维修以及操作人员 薪资等费用，该成本与运输里程无关。 运输成本与车辆行驶里程有关，时间惩 罚成本是当车辆早到或迟到时作为未按 规定时间到达所产生的费用。制冷成本 发生在车辆配送时用于保持车厢内食品 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 8 所需温度所花成本以及在卸货过程中车 厢内外冷热空气交替所产生的额外制冷 费用。 固定费用 fk=1，2， ，m，其 中 k 代表车辆，固定成本与配送车辆数 目呈正相关，即若最终结果使得配送车 辆减少则相应的固定成本也会降低。 假设车辆 k 将货物从 i 客户配送 至 j 客户，其配送成本为 dcgy，其 中 y 为 0-1 变量，当第 k 辆车将货物从 i 客户运往 j 客户时 y=1，当第 k 辆车没 有将货物从客户 i 送往客户 j 时，y=0。 由于本文为使计算精确并贴近实际单位 运价采用吨公里来度量，使得计算难 度加大，即 g 表示的为从客户 i 到客户 j 时车上的总货量，例如从配送中心出 发到第一个客户的货运量是第 k 辆车服 务的整条配送路径上的货运总量，当到 达第一个客户 i 并卸货后，从客户 i 到 下一个客户 j 的货运总量为除去客户 i 的需求量后余下的送货量，以此类推递 减，直到送完最后一个客户时，该车辆 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 9 应为空箱返回配送中心。即运输费用与 配送里程呈正相关，与配送量呈负相关。 传统的运输成本计算往往固定了节点间 的运输成本，使其采用统一价格，在实 际操作中并不可行，第一节点间的运输 费用是由车辆里程和运量共同决定的， 随着车辆的服务客户的增加，该费用也 会随之变化，因而固定节点间的运费本 身存在较大误差。第二传统的固定节点 间费用忽略了空车返回的成本，本文的 方法可以最大限度合理化配送次序，减 少空车行驶里程。 对于速冻食品来说，车辆配送过 程中车厢内应时刻保持低温状态，但在 卸货过程中由于车厢内外存在温差，为 了维持车内的平均温度，会产生更高的 制冷费用，当车厢内外的温差越大所需 的功率就越高，相应的制冷费用就越大， 为了简便计算，将卸货过程中的制冷成 本分为两部分：不考虑温差时，为维持 车内的温度所需的制冷费用以及由于车 厢内外温差所导致的额外的制冷费用， -精选财经经济类资料- -最新财经经济资料-感谢阅读- 10 总制冷成本不仅包括运输途中的费用也 包括装卸时的费用。无冷热空气对流的 制冷成本包括运输过程中的制冷费用以 及不考虑温差的卸货时产生的制冷成本， 由如下公式表示：d/s+g/？A 其中 ij。在本公式中 为不考虑温差的制冷 系数，代表每单位时间内所产生的制冷 费用，s 为冷藏车的运输时速，g 表示 第 j 个客户的需求量，？A 为在客户 j 处的卸货效率。运输到装卸地点后， 冷藏车厢内外温差，打开冷藏车门后由 于空气对流会导致车厢内的气温升高， 所以为了保持车内的温度不变，需要增 大功率，因增加的功率而产生的额外制 冷成本计算公式为： g/？A T，其中 为卸货时的气温每升高一度 单位时间内产生的成本，T 为车厢内外 温差。 时间惩罚成本遵循硬时间窗惩罚 成本，如图 1 所示，ES 与 KS 分别代表 着配送车辆早到时客户能够接受的最早 送货时间和配送车辆晚到时客户能够接 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 11 受的最晚送货时间，ES，KS 为客户可 以接受的送货时间，本文为方便计算以 某一时间点为基准，以分钟为单位来进 行计时以及时间限制。当配送车辆到达 客户 j 地的送货时间 t（即从客户 i 到客 户 j 的送货时间，包括在客户 j 处的卸 货时间）少于客户 j 的最早接货时间 ES 时，其产生的惩罚费用为 M；当配送车 辆到达客户 j 地的送货时间 t 超过客户 j 的最晚接货时间 KS 时，其产生的惩 罚费用为 M。在实际情况中，配送车辆 早到所产生的惩罚成本小于配送车辆晚 到所产生的惩罚成本，即 MM。 综上所述，超市冷链物流配送模 型为： minz=f+dcgy+d/s+g/？ A+g/？AT+M+M y5 i，j=0，1，2，n （1） y1 j，k=1，2，3，n （2） y1 i，j=0，1，2，n （3） y1 i，k=1，2，3，n （4） y=N k=1，2， m （5） -精选财经经济类资料- -最新财经经济资料-感谢阅读- 12 gQ k=1，2，m （6） 在上述模型中，约束（1）保证 实际配送车数量不超过该公司拥有车数， 约束（2）表示每一个出发地最多只有 一个接受地，约束（3）表示每个客户 最多只被一辆车服务，约束（4）表示 每个客户最多接受一次配送服务，约束 （5）所有客户都要被服务，约束（6） 每条配送路径的车载量不得超过该车最 大载重量。该模型共有三个 0-1 变量： y=代表车辆 k 是否服务点； =代表车辆早于客户 j 的要求时间到 达；=代表车辆晚于客户 j 的要求时 间到达。 3 物流配送模型算法以及案例求 解 3.1 遗传算法求解 求解步骤如图 2： 3.2 遗传算法设计 （1）问题编码。本文研究的问 题是冷链物流配送，首先就要问题的配 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 13 送中心和客户点进行编码。编码设计是 采用客户节点直接编码，并不将配送中 心编入其中，直接对 n 个客户节点进行 全排列，每一种排列方式就是一种解， 其中盗械乃承蚓褪桥渌统盗镜酱锏乃 承颍如：若随机产生一个染色体为 （3，4，2，5，8，9，7，1，6） ，则说 明该路径的配送顺序为 342589716，每一个 染色体代表一个配送方案，再在每个染 色体头尾添加 0 元素。 （2）初 始种群设定。初始化种群，随机产生对 33 个客户节点所进行的全排列的染色体， 这样的染色体共有 100 个，会形成 100 行 33 列的二位矩阵。 （3）适应度函数设定。适应度 函数为目标函数。找出第 i 染色体，获 取其配送客户顺序，先对每个客户的需 求量进行加总，使总重不超过车的载重 能力，再针对第一个客户的需求量进行 运输费用求解，并算出运输时间与装卸 时间，以便计算制冷费用以及时间惩罚 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 14 费用，然后再计算下一个客户的运输费 用，并在上一个客户运输时间和装卸时 间总和的基础上计算本客户的配送时间 是否符合本客户要求，从而判断是否产 生惩罚成本，但运输的制冷费用的时间 为本段路的运输时间和装卸时间，并依 此类推，完成配送。最后用 for 循环语 句找出配送总成本最小的车，这样一直 重复找，直至再找不出更小的配送成本 的车辆为止。 （4）选择算子。本文采用的是 轮盘赌法。将个体的适应度值比上总染 色体的适应度值，作为该个体所占概率。 随机选择轮盘旋转圈数，令 pick 为随机 数，再让 pick 减去第 i 个染色体所占概 率，对初始种群中的染色体全部进行该 项循环操作，总共会有 sizepop 次循环， 当 pick 为负数时，循环才会终止。 （5）交叉算子。本文采用的是 单点交叉的方法，即随机选择一个基因 位置将两个染色体的同基因位置上的基 因进行交换，以增加染色体的数目，增 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 15 加种群规模。 （6）变异算子。本文采用的变 异过程是将某一染色体的某两个基因位 做出交换，以改变其个体。随机选择一 个数，若该数字小于变异概率则不进行 变异操作，若该数字大于变异概率则进 行变异。变异位置也是随机选择的。 3.3 算例求解 赛嘉物流公司以长途运输大宗商 品为主，超市配送业