时间约束下生鲜配送线路优化研究

秦诗寒　余小鹏　朱秀迪

[摘 要] 我国冷链物流起步较晚，导致生鲜品在配送、装卸、储存等环节的损失率较高，建立完善的冷链物流配送体系意义重大。根据生鲜品的特点，构建了包含运输成本、货损成本、能耗成本和惩罚成本的线路模型，并采用节约算法，对该模型进行了优化，以期在最大化节约成本和时间窗约束的条件下，确定合适的配送线路，最终通过相应实例，证明了该配送线路优化模型的有效性。

[关键词] 时间约束；生鲜配送路线；优化模型；节约算法

[中图分类号] F323.7 [文献标识码] A

Abstract： The cold chain logistics in China starts late， As a result， the distribution， loading and unloading， and storage of fresh food has high loss rate， so it is significant to establish perfect cold chain logistics distribution system.According to the characteristics of fresh food， the study build a line model in terms of transportation， cost of damage， energy consumption and penalty cost and optimized this model by means of saving algorithm， so as to determine appropriate distribution lines to maximize cost savings and time window constraints.Finally， this model is effective proved by the corresponding instance.

Key words： time constraint， fresh distri bution route，optimization models， saving algorithm

一、前言

发改委于2010年7月出台了首部《农产品冷链物流发展规划》，该规划提出到2015年，建成一批效率高、规模大、技术新的跨区域冷链物流配送中心，使流通环节产品腐损率分别降至15%、8%、10%以下[1]。为了完成该发展规划，需要整个冷链物流体系合理运作，以提升整体效益。而生鲜配送作为冷链物流系统中最重要的环节之一，对该环节中路径的优化不仅能提高配送的时效性，还能有效降低物流成本。目前，国内外关于配送线路优化问题的研究大多归为车辆路径问题（VRP），而VRP问题又可细分为带载重约束VRP问题、带时间窗VRP问题、带回程载货VRP问题等；而早在1959年，Dantzig和Ramser就首次提出了相应的VRP规划模型和求解算法，以解决需求已知情况下，不同种类的车辆的组成和配送线路，达到运输费用最少的目的[2]。在2012年Jun等人提出了改进后的经典启发式算法，通过路线构造、改造、干扰三阶段得出最优解[3]；同一年，庄景明等基于改进的遗传算法对车辆运行路线进行了优化[4]。在本文中，我们对具有时间约束的冷链车辆配送线路优化展开了相应研究。

二、模型提出

（一）问题描述

时间约束下生鲜品配送线路优化问题可描述如下：生鲜品配送中心VO接到各网点（Vi=1，2，···n）订单后，根据各网点订单量（Qi=1，2···n）和时间窗要求，安排冷链配送车辆依次进行货物配送。其中各配送点Vi与配送中心的距离（di=1，2···n）以及配送量（qi=1，2···n）已知，冷链配送车辆具有相同的载重量Q0；各网点都有配送时间约束，超过网点规定时间窗送达则需要承担延误成本，该成本与相应生鲜品的价格、数量以及延迟时间相关。本文的目的是在各网点时间约束的条件下，确定合理的配送路线、配送顺序、配送车辆数，从而有效降低配送总成本。

（二）数学模型

为了简化配送条件，以优化生鲜品的配送线路，我们做了如下假设：一是配送中心车辆能够满足配送需求；二是单一网点生鲜品需求量不超过每辆车的运载量；三是每个网点生鲜品由一辆车一次送达；四是各网点间以及各网点与配送中心距离已知；五是各网点生鲜品需求量已知；六是各网点间路况相同，配送车辆匀速行驶；七是各网点时间窗、可接受时间窗以及延误的惩罚系数已知。本文的目标是确定合理的生鲜配送路线、配送顺序以及配送车辆数，从而有效降低配送总成本；在本文中，配送总成本主要包括运输成本、货损成本、延误所致的惩罚成本以及车辆能耗成本。

1.运输成本。由于冷链配送车辆相同，因此运输成本主要与运输里程相关，用公式可表示为：

其中：C1为运输成本，c为单位里程运输成本，tij为运输车辆从网点Vi到Vj的运输时间，Xijk为0，1变量，若车辆经过网点Vi到Vj，则为1，反之为0。

2.货损成本。由于生鲜品具有易损、易腐特点，加上运输途中挤压、新陈代谢等问题，会造成生鲜品损耗；我们假定全程路况一致，则货损成本与车辆的运送时间相关，公式可表示为（假设车辆先到达Vi网点再到Vj网点）：

其中：C2为货损成本，α为货损系数，Pj为网点Vj货物的价格，ΔQjk为K车辆在Vi点卸货后车辆的剩余载货；Xijk同上，Si为配送中到Vi网点的距离，Sj为配送中心到Vj网点的距离，h为变量。

3.惩罚成本。首先，每个网点都有自身的时间窗约束，车辆未在指点时间范围内送达，则会影响网点日常经营情况，需要加入一定的惩罚成本，惩罚成本与货物量、货物价格以及延误时间相关；其次，我们假定了网点可接受的延误时间，若超过可接受的延误时间，则网点拒绝收货，公式表示为：endprint

其中，C3为惩罚成本，β为惩罚系数，Pj为Vj网点所需生鲜品的价格，Qj为Vj网点所需生鲜品的需求量，tjk为K车运送至Vj网点的时间，[tj～td]为Vj网点时间窗，[Ti～Tj]为Vj网点可接受的时间窗（包含了延误时间）。

4.能耗成本。冷链车辆相较于普通运输车辆而言，需要消耗更多的能源以保证生鲜品温度的要求；因此生鲜品配送过程中能耗与载货量、配送里程有关，可用公式表示如下：

其中：C4为能耗成本，γ为耗能系数，Pj为网点Vj货物的价格，ΔQjk为K车辆在Vi点卸货后车辆的剩余载货量，Xijk同上，Si为配送中到Vi网点的距离，Sj为配送中心到Vj网点的距离，h为变量。

因此，根据配送总成本最小的思想，建立了如下目标函数：

在该约束条件中，（1）表明每个网点仅配送一次货物；（2）表明每个网点都在配送范围内，不存在遗漏；（3）表明配送中心的冷链配送车辆均被利用，不存在闲置车辆；（4）表明每个网点的需求量小于每辆配送车辆的最大载重量；（5）表明每个网点的配送完成时间需在该网点可接受时间范围内。

三、算法设计

考虑到生鲜品的特点及配送的软时间窗约束，同时认识到上文建立的生鲜品配送模型求解问题属于非线性规划问题，我们因故采取启发式算法中的节约算法来进行求解。

（一）具体思路

当配送车辆由配送中心发出时，寻找“最邻近的网点”作为第一条配送线路上的第一个被服务的客户；随后，选择尚未被加入任何线路中的网点加入当前线路中；而且，在加入当前线路的网点选择中要遵守“综合成本最低”的原则。其次，运用节约算法求解时，需将可行的网点加入现有回路中，并计算相应的节约值，从而将节约值最多的网点加入到回路中，并不断重复这一过程直到所有网点纳入相应回路。因此，通过对第二节的模型进行优化，可以得到节约值最大化的配送线路模型，其目标函数如下：

其中，Yij为网点Vi到Vj的节约成本，c为单位运输成本，Wij为网点Vi到Vj的节约里程，h为变量，C3（tj）为Vj网点的惩罚成本，其他变量在第二章已提及，不再一一介绍。通过上述目标函数，发现添加新网点时应遵循时间约束为第一顺序（降低惩罚成本），各网点运输里程为第二顺序（降低运输成本、货损成本和能耗成本）。

（二）算法步骤

根据节约算法的思想和节约值最大化的配送线路模型，我们认为具体算法步骤包括：（1）按各网点时间窗约束进行排序；（2）计算各网点间的节约里程；（3）按节约算法中“最邻近网点”思想，在配送中心选择步骤1排序后网点中的“最邻近网点”为第一位配送网点；（4）按步骤3的思想逐个将满足条件的网点纳入当前线路，当超过可接受时间窗约束或达到车辆最大载货量时，则不再加入新的网点；（5）排除已选网点后，重复步骤3和4，直到所有网点均被纳入相应配送线路。

（三）实例分析

设某配送中心在约定时间范围内要向10个生鲜网点配送一批新鲜苹果，配送中心编号为V0，各网点编号为Vi=1，2···n；配送车辆运行速度为30km/h，载重量Q0为15吨，苹果的价格P为5000元/吨，生鲜品货损系数α为0.01%，超过时间窗的惩罚系数β为0.2%，车辆能耗系数γ为0.2%，单位运输成本c=1元/吨公里，各网点平均卸货时间为10分钟/网点。各网点货物需求量以及时间窗约束见表1，配送中心及各网点间距离见表2。

按照算法步骤对以上实例进行计算：首先，计算出每个网点的时间窗约束先后顺序以及各网点间的节约里程；随后得出第一条配送线路中的第一个网点P1；其次，对剩余网点的节约里程、节约运输成本、节约货损成本、节约能耗成本、惩罚成本进行计算，得出各个网点的总节约成本；因此，得到的第一条配送线路为P0-P1-P10-P2-P5-P0，其中载货量为14.5吨，小于最大载货量Q0。随后按以上步骤，计算出第二条配送线路为P0-P3-P4-P6-P0，载货量为13.5吨；第三条配送线路为P0-P7-P8-P9-P0，载货量为9.5吨。至此，所有的网点均被纳入相应线路。

四、结论

通过对生鲜品配送特点的认识，构建了包含运输成本、货损成本、能耗成本和惩罚成本的线路模型，并采用节约算法，对该模型进行了优化，以期在最大化节约成本和时间窗约束的条件下，确定合适的配送线路；最终通过相应实例，证明了该配送线路优化模型的有效性。

[参 考 文 献]

[1]国家发展改革委.国家发展改革委印发.农产品冷链物流发展规划[EB/OL]. http： // zys. ndrc. gov. cn / xwfb / 201007 / t20100728_363173.html.2010-7-28

[2] Dantzig G.B， Ramser J.H. The truck dispatching problem[J]. Management Science， 1959-6：80-91

[3] Jun Y， Kim B I. New best solutions to VRPSPD benchmark problems by a perturbation based algorithm[J]. Expert Systems with Applications，2012，39（5）： 5641-5648

[4]庄景明，彭昕昀.基于改进遗传算法的新鲜农产品配送路线优化研究[J].江西师范大学学报（自然科学版），2012，4（36）：399-402

[责任编辑：王凤娟]endprint