考虑产品互斥和时效的多冷链产品车辆路径建模与仿真

陈淑童，王长军

(东华大学 旭日工商管理学院， 上海 200051)

近年来，随着生活水平的不断提高和电子商务的普及，我国民众对冷链产品及其运输的需求飞速增长。但相关资料[1]显示，我国冷链产品在物流各环节的损失率高达25%～30%，尤其是在运输阶段(例如，2015年果蔬、肉类、水产品运输腐损率分别为15%、8%和10%)。显然，现阶段低效的冷链运输加重了各方成本，也难以满足消费者对冷链产品新鲜度的要求。为改善现状，非常有必要对冷链运输进行科学化运营。

传统上通过优化配送路径来缓解成本与顾客需求间的冲突，其中的一个核心决策问题即车辆路径问题(vehicle routing problem，VRP)，由Dantzig等[2]于1959年提出。该问题旨在设计适当的路线，使车辆有序通过一系列需求点，在满足一定的约束条件(如货物需求量、交发货时间、车辆容量限制等)下，优化相应的经济性或服务性目标。此类研究成果颇丰，多针对普通货物，但其中考虑的一些因素与冷链产品的特征(如时效性要求强、产品类型多、能耗大等)也有一定关联。针对运输时效要求，最为典型的就是加入时间窗约束[3-5]。此外，也有文献研究了多产品下的VRP问题，均考虑了产品体积或重量间的不同[6-7]。Nalepa等[8]通过构建以燃油站收费和运输途中燃油成本总和最小为目标的模型，进一步拓展了对运输能耗的研究。

近年来，也有学者通过强化时间窗要求，或考虑与冷链相关的能耗等方法，进一步研究冷链环境下的VRP问题。例如，Wang等[9]在传统VRP模型的基础上，除考虑时间窗约束外，还将制冷成本、开关门能源损耗成本考虑在目标函数中，并用节约法进行求解。Hsu等[10]通过考虑能源损耗成本、与运输时间相关的货损率和较短的时间窗限制，体现冷链产品的特性，同时也顾及了配送时间和温度的随机性。大多数研究只针对一种冷链产品。Zhang等[11]考虑了多种冷链产品的VRP研究，但是，仅考虑了不同冷链产品具有的不同货损率、价格和需求，未考虑产品可否共运的限制。

随着电子商务的普及，我国的冷链运作(特别在B2C端)存在着多冷链产品的运输需求。而冷链产品与普货不同，存在互斥性。这种互斥性一方面源于部分冷链产品存储温度的不同；另一方面源于部分冷链产品共运过程中的相互影响。前者不难理解，有些产品仅需冷藏、而有些则需冷冻；后者则是由于存在串味、乙烯催熟等问题[12]。与现有文献中强调的时间窗、能耗等因素不同，冷链产品互斥性这一特征是冷链运作所特有的，但在以往研究中却没有被考虑。

为此，在现有研究基础上，构建以固定发车成本、配送成本、时间惩罚成本和能源损耗成本总和最小为目标，考虑多冷链产品特性的配送混合整数非线性规划模型。其中：针对冷链产品互斥性的特性，融入相关互斥性约束；考虑冷链产品时效性强、能耗大的特点，在目标函数中加入时效惩罚成本和能源损耗成本。以上海地区某运输任务为背景，采用ILOG CPLEX求解模型最优解，以此精确展现在产品互斥性约束下，时效惩罚斜率变化对运输批次划分和路径决策的影响。

1 模型构建

1.1 变量说明与基本假设

设有N个客户点，客户点i和j(=1， …，N)间的距离为dij。F种冷链产品，记客户点i的订单中产品f(=1，…，F)的需求量为qif，以0-1变量wif表示客户i的订单中是否有产品f，即当客户i订购产品f时，wif=1，否则，wif=0，显然qif>0时，wif= 1。针对冷链产品可能存在的不可共运的特点，构建0-1变量tpf表示产品p和f的互斥性，即若两种产品不互斥，tpf=1，否则tpf=0。常见的冷链产品互斥性(tpf值)如表1所示。

由于产品之间存在互斥性，则运输需分多个批次完成，记发车批次上限为B。用0-1变量xifb标记b(≤B)批次中是否包含客户i的产品f，xifb=1为是，xifb=0为否。由此，如客户i有产品f，则该产品必定在某个批次且仅在某个批次中运输，故有

(1)

继而，定义0-1变量kbi表示批次b是否包含客户i这个客户点，kbi=1表示包含，kbi=0表示不包含。显然，

(2)

表1 常见冷链产品互斥性示例表Table 1 Illustration of mutual exclusion among popular cold chain products

用0-1变量zijb表示客户i、j与b批次的关系，只有客户i、j的任意产品同时在批次b中，zijb=1，否则zijb=0。用决策变量rib表示第b个批次中车辆到达客户i的时间。由M种不同类型车辆进行运输，其中，车型的不同体现在装载质量与体积的不同，温度可由车辆温控设备根据需要调节。第m(=1， …，M)种车辆的最大容纳量为Lm。用0-1变量ybm标记批次b是否用m种车辆运输产品，即若批次b使用第m种车辆，则ybm=1，否则ybm=0。假设每批次用且仅用一种车型，则有

(3)

下面简述冷链物流中需侧重考虑的时效和能耗等要求。

首先，客户i对于所有产品的期望交付时间段均为[ai，bi]，若到达时间早或晚于该时间段，都将引发相应的时效惩罚(如式(4)所示)。其中，单位时间的时效惩罚斜率为ci；rib为第b个批次中车辆到达客户i的时间。

(4)

其次，能耗方面。本文考虑配送过程中车辆开关门和运输过程中能源损耗成本，分别与装卸货开关门时间和运输时间成线性关系。参照文献[11]，系数分别定义为单位时间的开关门损耗热电荷Xm(库仑，记为C)和运输损耗热电荷Ym(C)。其中，Xm的计算是基于车内外温差和开门程度等参数，表达式如式(5)所示。

Xm=(3.22+0.54Nm)·ΔT·β，m=1， 2， …，M

(5)

式中：ΔT为车内外温差(℃)；Nm为m型车辆的容积(m3)；β为开门程度系数，对应开门频率，取值参见表2。

表2 β系数与开门频率对照表Table 2 Relation between β and the frequency of opening doors

Ym由车厢内外温差的热传导所导致的热电荷损耗，与车厢内外温差、车厢材料、厚度有关，表示为

(6)

式中：λ为车辆折旧系数；U为车厢体的热传导率(KJ/(h·m2·℃))，Ainm、Aom为m型车辆的车厢体内、外表面积(m2)。

1.2 模型与说明

至此，构建模型如式(7)～(13)所示。

(7)

s.t. (1)～(3)

xipb·xjfb≤tpf，i，j=1， 2， …，N;p，f=1， 2， …，F;b=1， 2， …，B

(8)

(9)

(10)

(11)

(12)

(13)

式(7)为优化目标函数，包含4部分，依次是多车型车辆的固定发车成本(Rm为车型m的发车费用)、与运输距离线性相关的运输成本(u为单位里程运输成本系数，元/km)、时间惩罚成本和两项能耗成本(其中：v为平均时速，δ为单位电荷的制冷成本)。式(8)反映冷链产品互斥性约束，详见表1。式(9)为每批次下的承载能力约束。式(10)、(11)是VRP模型中常见的车辆行驶流量平衡。式(12)限定每个批次均由出发点发车，最终回到出发点，保证了线路的连通性。式(13)表示了每个批次中先后经过的两个客户之间交付时间的关系(其中h为每个客户点所需卸货时间)。

此模型决策变量共有6组，包括实际使用批次数、xifb、kbi、zijb、ybm和rib。其中，包含了整数、0-1整数和实数3类变量，为混合整数规划模型。

2 仿真研究与分析

2.1 求解方法

本文所讨论的问题为一个有多个回路的旅行商问题，且产品间存在互斥，其数学性质为强NP(non-deterministic polynomial)-hard。类似问题多采用启发式算法、遗传算法和混杂算法[3-5]进行求解。本文希望精确分析冷链要素，特别是互斥性和时效性对决策产生的影响。为避免次优解的影响，此处采用ILOG CPLEX[13]求解模型的最优解，且该方法已被用于相关物流优化问题的求解中[14]。

2.2 仿真背景

以上海某冷链物流企业为应用背景，该企业在上海市嘉定区马陆镇附近自有冷库及车场，常年供应果蔬类、肉类、水产类、冷饮等多种冷链产品，产品多且互斥性强。企业客户遍及上海各行政区，均有交付时间要求。其中，某次运输任务的客户点及所需产品如表3所示。

表3 客户需求表及需求交付起始时间Table 3 Customers’ needs and best delivery time

(续 表)

其中，由于存储温度不同的原因，苹果/梨不能与其他产品共运；同时，由于羊肉会串味影响冰淇淋品质，两者不能共运，详见表1。由百度地图查得各点间实际运输距离如表4所示(0代表车场)。

表4 客户点间行驶距离Table 4 Distances between customers km

本文选择载重为1.5 t的冷藏车，单位发车成本为150元/车，v=40 km/h，u=4.24元/km，参数如表5和6所示。

表5 运输当天不同产品的车内外温差Table 5 Temperature difference between internal and externalof vehicle according to different products ℃

表6 能耗系数表Table 6 Parameters of refrigeration cost

2.3 不考虑时效惩罚下的仿真

先不考虑时效要求，即假设式(4)中惩罚斜率ci均为0，给出运输批次上限为8，由ILOG CPLEX编程，得到了满足互斥性的最优决策方案。实际需5个运输批次，总成本为6 885.63元。其中，固定发车成本为750元，运输成本共1 687.1元，开关门与运输能耗费用分别为2 226.25和2 222.28元。每个批次的配送客户点及相应产品如表7所示，产品配送路径如图1所示，其中五角星处为车场，路径上数字对应表7中批次。

图1 配送路径图Fig.1 Illustration of the routing decision

表7 配送批次及产品Table 7 Batch of delivery and the corresponding products

2.4 时效惩罚斜率变化下的仿真

本节研究时效性对各项成本以及决策结果的影响，在2.3节数据的基础上，使惩罚斜率ci从0开始(即表7结果)，以4为幅度，增至44。由ILOG CPLEX编程计算，发现随着惩罚斜率的增加，总成本不断上升，但上升斜率却在不断减小(见图2)，这正是优化所导致各成本项互相协调的结果。

图2 成本趋势图Fig.2 Illustration of the trend of costs

具体来说，当惩罚斜率由0增至12时，批次与路径决策不变(见表7)，再增至16，原决策中冷藏批次1、2则发生如表8所示的变化。其中，运输路径变长，导致运输成本和运输能耗(与运输距离成线性关系)增加，但抑制了过快上涨的时效惩罚(见图2)。

表8 冷藏产品决策变化表(ci=16)Table 8 Changes of decisions on refrigerated products(ci =16)

当时效惩罚由28增加到32时，原先3个冷冻批次增至4个(见表9)。发车成本和运输长度均有增加，但由于批次的增加导致运输时效大幅改善(见图2)。同时，客户点3所需羊肉和速冻糕点在惩罚斜率为28的情况下，归属2个运输批次，而当惩罚斜率为32时，被集中到了1个批次中，继而减少了开关门的能耗(见图2)。

表9 冷冻产品决策变化表(ci =32)Table 9 Changes of decisions on frozen products (ci =32)

各项成本在总成本中的占比如图3所示。综合图2～3及以上分析，可得如下结论：(1)优化可通过协调各成本，达到抑制总成本快速上涨的目的，换言之，即便在互斥性约束存在的前提下，时效和能耗也能实现一定程度协调；(2)随惩罚斜率的增大，时效性被不断强调，虽可通过优化协调各成本，但总体上，时效惩罚值及其占比还是上升(从0增加到6.1%)；(3)随时效要求的加强，批次会增加，继而导致运输里程加长，所以会带来发车与运输成本及运输能耗的增加，但这些成本量增加趋势会逐渐趋缓，继而在总成本中的占比也会趋于下降。

图3 成本比例图Fig.3 Illustration of the proportion of costs

3 结 语

本文考虑了冷链产品互斥性要求，针对冷链物流时效性强、能耗大的特点，构建了包含时效惩罚、能源损耗和冷链产品互斥性约束在内的混合整数规划模型。通过ILOG CPLEX编程对模型进行求解，以上海某企业实际运输任务为背景，展示了互斥性约束下的决策结果，基于此，对时效要求加强导致决策结果变化的相关规律进行了分析和总结。研究发现，在时效惩罚率上升过程中，统一优化对于减缓总成本上升有着明显的作用，具体而言，随着惩罚率的上升，时效惩罚成本在总成本中的占比不断增加，而固定发车成本、运输成本、运输能耗成本的占比趋于下降。对决策者而言，可以通过优化运输路径与增加发车批次的方法，以适当增加的运输成本、运输能耗成本与发车成本来抑制时效惩罚成本的过快上涨，从而取得时效和成本间的协调。