生鲜农产品带越库配送的车辆路径问题

申聪 董明

摘 要： 越库（Cross-docking）作为一种高效的配送策略，具有降低库存成本、加快商品转运速度的特点，尤其适用于具有易腐特性的生鲜农产品。将车辆调度与车辆路径问题集成为一个模型来考虑生鲜农产品的配送问题。以越库中心转运成本、存储成本、车辆配送成本和货损成本的总成本为优化目标建立模型，设计了遗传算法对模型求解，并进行数值实验分析结果，验证了模型和算法的可行性，得到了最优的车辆与库门的分配策略以及出庫车的的最优配送路径。

关键词： 生鲜农产品;越库中心;车辆调度;车辆路径;遗传算法

中图分类号： F 50   文献标志码： A

Abstract： As an efficient distribution strategy， cross-docking has the characteristics of reducing inventory costs and speeding up the transshipment speed of goods， especially for fresh agricultural products with perishable characteristics. This paper integrates vehicle scheduling and vehicle routing issues into a model to consider the distribution of fresh products. The model is established to minimize the total cost including the transshipment cost， the storage cost， the vehicle distribution cost and the corruption cost. Genetic algorithm will be designed to solve the model. Through the analysis of the example， the feasibility of the model and the algorithm is verified， and the optimal allocation strategy of the vehicle and the warehouse door and the optimal distribution path of the delivery vehicles are obtained.

Key words： fresh agricultural products; cross-docking center; vehicle scheduling; vehicle routing; genetic algorithm

随着人们生活水平的提高，消费者对生鲜农产品的需求日益加大，对生鲜农产品配送的质量也提出了更高的要求。生鲜农产品主要指初级农畜产品，主要包括蔬菜水果、鲜肉蛋奶等产品。由于生鲜农产品具有易腐的特性，配送过程中的环境和时间会影响生鲜农产品的品质。提高生鲜农产品的物流效率和品质是零售企业抢占市场份额的必要手段。

越库配送（cross-docking）是一种可以降低库存和运输流通时间的有效的配送策略，尤其适用于保质期短的生鲜农产品。实施越库配送可以有效提高产品流动性，以达到降低库存成本、减少存储空间以及传输时间的目的，同时越库配送也可以利用整车运输来降低运输成本。

回顾生鲜农产品以及越库配送的相关文献，Nahmials和Raafat研究了固定保质期以及随机保质期的易腐产品的生产和库存基础系统。Zhang等人研究了在满足产品质量的要求下最小化库存与运输成本的问题。Rong等人提出了一个食品生产与分配规划的混合整数线性规划模型，侧重于供应链温控对产品质量的研究。Zanoni 和 Zavanella构建了一个评估食品供应链和食品物流的概念框架，来控制在整个食品供应链中的产品质量、安全、持续性和物流效率。杨华龙等人结合了生鲜农产品的敏感特征，考虑产品因腐烂变质造成的成本损失，建立了基于生鲜农产品物流网络布局的非线性规划模型。陈杰等人研究了不确定环境下基于两台机器的越库调度模型。Dwi等人研究了带越库中心的食品供应链车辆调度与车辆路径混合整数线性规划模型。麦家骥等人研究了考虑时间不确定环境下的循环取料情况，并建立了混合整数规划的越库调度模型。强瑞等人研究了转运仓门的分配问题，并设计了高效的启发式算法进行求解。缪朝炜等人研究了带有时间窗和车辆容量限制的车辆调度问题并用遗传算法进行求解，旨在合理分配仓门和越库内部货物来达到高效运作的目标。李敬峰等人将粒子群算法与改进粒子群算法还有遗传算法进行对比，对仓门分配和货车排序的问题进行了优化。葛显龙等人研究了供应商、零售商与一个配送中心还有多个配送中心的城市物流协同配送网络，建立了车辆路径模型，并设计了改进遗传算法进行求解。侯宇超等人建立多目标路径优化模型，考虑客户满意度并利用了精英蚁群算法进行优化。Dondo等人研究了越库配送中心仓门分配以及车辆的排序问题。汪涛等人研究了基于改进人工蚁群算法对构建的生鲜农产品配送路径模型进行优化。

本文主要考虑产品为生鲜农产品，研究带有越库配送的车辆路径问题（Vehicle Routing Problem with Cross-Docking， VRPCD），旨在通过车辆与库门的合理分配，以及车辆配送路径的研究，在考虑硬时间窗和生鲜农产品易腐特点的情况下，最小化以转运成本、存储成本、运输成本、货损成本组成的总成本，建立模型进行算法优化，实现越库中心内部的最优调度与供应链的高效运作。

1 生鲜农产品带越库配送的车辆路径问题模型构建

1.1 问题描述

本文研究的生鲜农产品带越库配送的车辆路径问题的结构如图1所示，由入库车辆和入库门、越库操作中心、出库门和出库车辆，以及客户所在节点组成。初始时刻，所有入库车与出库车均已到达越库中心等待分配库门，入库车分配到入库门后进行货物卸载，通过重新分配，将订单转运到停靠在相应出库门的出库车上。出库车装载完毕后再根据订单信息将其配送到客户手中。

1.2 模型假设

本文的生鲜农产品带越库配送的车辆路径模型是由一个越库中心向多个客户节点进行配送。为简化模型，对问题做如下假设：

（1）初始时刻，所有入库车和出库车均到达越库中心等待调度;

（2）所有客户订单信息已知，订单种类相同、数量不同;

（3）不考虑单一货物体积，只考虑货物重量;

（4）所有车辆均为同一类型，且容量已知;

（5）所有车辆与库门必须都参与调度;

（6）越库中心临时存储区域无限大;

（7）货物在越库中心转运操作时，从入库门到出库门的操作时间与其距离成正比，且单位转运成本相同;

（8）每辆出库车都开始并结束于越库中心;

（9）考虑货物的腐败率;

（10）每个客户节点的需求仅由一辆出库车完成配送。

1.3 模型构建

1.3.1 参数符号

D={0，1，2，…，n，n+1}：表示越库中心及客户集，其中1，2，…，n表示客户，0表示越库中心，n+1可以看成越库中心的复制点，即出库车均从配送中心出发，并且最终回到配送中心。

l={1，2，…，L}：入库车辆集合。

f={1，2，…，F}：越库中心的入库门集合。

k={1，2，…，K}：出库车辆集合。

h={1，2，…，H}：越库中心的出库门集合。

tupload：每个订单卸载的时间。

tload：每个订单装载的时间。

atl：入库车辆l到越库停车区域的时间（初始时刻都为0）。

uil：如果订单i在入库车l上为1，否则为0。

[eti，lti]：表示客户i可接受的时间窗。

qi：表示订单i的大小。

tij：表示从节点i到节点j的行驶时间。

Q：表示出库车辆k的最大载重量。

cfh：表示订单从入库门f转运到出库门h所用的操作时间。

B0：货物初始状态。

p：单位货物的价格。

α：表示订单从入库门运送至出库门的单位运输成本。

β：表示在越库配送中心的单位存储成本。

γ：表示出库车的单位运输成本。

μ：货物的腐败率。

T：时间维度。

M：一个大数。

决策变量：

rtl：入库车l分配给入库门并且订单开始卸载的时间。

Atk：出库车辆k分配给出库门的时间。

dtl：入库车辆l完成卸载的时间。

Rtk：出库车辆k离开越库配送中心的时间。

vik：如果订单i分配给出库车辆k则为1，否则为0。

sik：出库车辆k完成订单i的时间。

wifh：如果订单i从入库门f转运到出库门h则为1，否则为0。

xlf：如果入库车l分配给入库门f则为1，否则为0。

Xll′f：如果入库车l和l′都停靠在入库门f，且入库车l′离开后接着入库车l停靠则为1，否则为0。

ykh：如果出库车k分配给出库门h则为1，否则为0。

Ykk′h：出库车k和k′都停靠在出库门h，且出库车k′离开后接着出库车k停靠则为1，否则为0。

zijk：如果出库车k从节点i直接到达节点j则为1，否则为0。

1.3.2 成本分析

越库中心操作成本： COST（operation）= ∑ni=1∑Ff=1∑Hh=1αqi cfh wifh。

越库中心存储成本：COST（inventory）= ∑i=1∑Ff=1∑Kk=1βqi uil vik （Rtk-rtl）。

配送运输成本：COST（transportation）= ∑ni=0∑n+1j=1，j≠i∑Kk=1γtij zijk。

货损成本：生鲜农产品在存储运输过程中，品质会随着时间的增加而下降，这里采用易腐品的腐败函数：B（t）=B0·e-μt。其中，B0表示貨物初始状态，μ表示为腐败率，腐败率与环境温度和产品自身特性等有关。本文假设整个过程中只考虑时间为产品腐败带来的影响，腐败率相同为μ，进而获得整个过程中的货损成本。

COST（corruption） = ∑ni=1∑Ll=1∑Kk=1pqi B0 （1-e-μuil vik （Rtk-rtl）-μvik （sik-Rtk））

2.3.3 建立模型

在上述模型中：（1）表示入库车辆开始卸载的时间不早于入库车辆到达入库的时间;（2）和（3）表示入库车和出库车离开越库中心的时间限制;（4）表示订单i在且仅在一辆入库车上;（5）表示订单i在且仅在一辆入库车上;（6）表示订单能且仅能从一个入库门转运到一个出库门;（7）和（8）表示每辆车只可以分配到一个库门;（9）和（10）表示所有库门必须参与调度;（11）规定了在同一入库门分配的挨着的两辆入库车前车的离开时间等于后车的卸载时间;（12）规定了在同一出库门分配的挨着的两辆出库车前车的离开时间等于后车的停靠的时间;（13）和（14）表示车辆在库门停靠的时间顺序关系;（15）表示出库车的载重限制;（16）表示所有入库车订单总量等于所有出库车订单总量;（17）表示每一辆出库车都必须从越库中心发;（18）表示每一辆出库车都必须回到越库中心点;（19）表示每一辆出库车都不能回到越库中心0点;（20）表示每一辆出库车都不能从越库中心n+1点离开;（21）表示恰好有一辆出库车为每个客户提供服务;（22）表示每个订单仅且仅被一辆出库车送达;（23）表示限制出库车辆的配送路径;（24）表示s0k的初始值;（25）表示每个订单必须在T时段配送完毕;（26）表示每个顾客订单完成时间的关系;（27）和（28）表示订单i的到达时间必须在要求的时间窗之内;（29）表示整数化约束条件。

2 算法设计

2.1 解结构设计

根据对生鲜农产品带越库配送的车辆路径问题的描述，其对应的解可以分为两部分：第一部分表示车辆与库门的分配策略，第二部分表示出库车辆的路径分配。第一部分可以描述为In_x1，…，In_xL，Out_x1，…，Out_xK，长度为L+K（入库车数目+出库车数目）。设定变量中有车辆对应库门的顺序，因此其中In_xl只表示为入库车L对应的入库门，Out_xk只表示出库车k对应的出库门;第二部分可以描述为Out_11，…，Out_21，…，Out_K1，…，长度为需求点的总数目n，其中Out_k1，…代表出库车k对应的路径。因此问题的解的结构可以表示为

{In_x1，…，In_xL，Out_x1，…，Out_xK，Out_11，…，Out_21，…，Out_K1，…}。

2.2 编码设定

本文根据解结构的设计，对其组成的两部分分别进行编码。解结构的第一部分是车辆与库门的分配问题，由于每个库门可以对应多辆车，因此这部分染色体编码可以相同，本文采用整数编码（自变量取整操作），例如1 2 2 1 2;第二部分是车辆路径问题，涉及顺序问题，染色体编码不能相同，这里采用序列编码，例如4 3 1 2 5。

假设有1辆入库车、1个入库门、2个出库车、2个出库门、10个需求点，则染色体编码可以为以下形式：

1 1 2 4 9 10 8 7 2 1 6 3 5

解码后结果可能形式如下：

入库车门1停靠入库车1;

出库车门1停靠出库车1;

出库车门2停靠出库车2;

出库车1配送路线：0-4-9-10-8-7-0;

出库车2配送路线：0-2-1-6-3-5-0。

2.3 初始解的生成

根据参数设置，初始解第一部分为随机产生的（L+K）个整数，要求前L个整数取值为[1∶F]，后K个整数取值为[1∶H];初始解的第二部分为序数整数，要求数量为需求点个数n，且数字为1～n的某个顺序，不存在重复数字。

2.4 适应度函数

遗传算法通过适应度函数联系需要解决的具体问题。适应度值是种群中个体对环境的适应程度。适应度函数与优化目标存在一种对应关系，也是将具体问题抽象化成数学模型的过程。考虑到本文模型，需要目标函数总成本最小化，这里采取总成本的倒数表示适应度函数。个体的适应度值越大，表示目标函数总成本越小，个体适应环境的程度越好。

Fitness= 1COST

2.5 选择

选择是优胜劣汰的一种操作，目的是把优秀的解直接遗传到下一代或者通过配对交叉产生新的个体再遗传到下一代，整个操作是基于群体中适应度评估基础上的。

这里采用随机遍历抽样法，具体操作如下：

1）计算种群中每个个体的适应度;

2）计算个体遗传到下一代的概率：

P（xi）=f（xi）∑nj=1f（xj）

3）计算累计函数：

qi=∑ij=1P（xj）

4）设n为需要选择的个体数目，等距离选择个体，选择指针的距离为1/n，第一个位置为[0，1/n]的均匀随机数决定，以此类推得到所有需要选择得个体。

2.6 交叉操作

第一部分：单点交叉，是指只在个体的编码串中随机取一个交叉点，然后两条染色体在这个交叉点互相交换基因片段。 第二部分：部分映射交叉，是指对父代中的两个交叉点所属的部分基因互相建立的一种映射关系。在基因交换后，根据所建立的映射关系将冲突的基因消除。交叉过程如图2所示。

2.7 变异操作

第一部分：单点变异，根据变异概率在基因串中选取一位进行变异，数值变异范围为自变量取值范围。第二部分：互换变异。变异过程如图3所示。

2.8 逆转操作

只针对第二部分：被选择两个位置之间所有数字逆转，如图4所示。

2.9 重插入子代的新种群

父代经由交叉产生子代，根据代沟设置，将子代适应度最差部分丢弃，将同等数量父代适应度值最高种群插入子代，获得新種群。过程如图5所示。

2.10 算法步骤

步骤1：参数设置，包括种群规模大小、交叉概率、变异概率和最大迭代次数。

步骤2：初始种群的生成，根据问题描述和解结构的设计，将其分为第一部分整数编码，第二部分序数编码，并生成初始种群。

步骤3：适应度函数设置，这里将总成本的倒数作为适应度函数，计算种群中个体的适应值。

步骤4：选择，根据随机遍历选择法，从种群中选取进入下一代的个体。

步骤5：按照交叉概率，对种群进行交叉操作，其中解结构中第一部分种群进行单点交叉，第二部分进行部分映射交叉。

步骤6：根据变异概率，对种群进行第一部分单点变异及第二部分进行互换变异。

步骤7：没有满足迭代次数，转回进行步骤2直到达到设置的迭代次数为止。

步骤8：输出种群中满足条件的最优个体作为问题的解。

遗传算法流程如图6所示。

3 数值实验

3.1 算例设计

参考文献的数据，设计算例。某生鲜农产品越库配送中心，收到了16个来自其覆盖范围的订单。入库车根据订单信息已经取货，并到达越库中心，配送中心入库车、出库车载重限制均为1500kg，车辆单位时间配送成本为1.3元/min。入库车共7辆，入库门3个，出库车5辆，出库门3个，入库门到出库门的单位时间转运成本为0.01元/min，对应转运时间如表1所示。入库车负载订单情况如表2所示。16个需求点、客户订单时间窗、配送需求量如表3所示。越库中心点到客户需求点的配送时间如表4所示。其他参数如表5所示。

3.2 算法求解

遗传算法参数如表6所示，运行10次结果如表7所示。

从遗传算法运行结果可以得出，平均总成本为4031.712，最小总成本为3628.23，此时车辆与库门的分配方案如下：

入库门1：5->6;

入库门2：1->7;

入库门3：3->4->2;

出库门1：5;

出库门2：3;

出库门3：1->2->4。

出库车配送方案如下：

第 1 辆车路径：0->10->8->1->0;

第 2 辆车路径：0->7->5->4->0;

第 3 辆车路径：0->14->9->15->0;

第 4 辆车路径：0->6->11->12->0;

第 5 辆车路径：0->16->13->2->3->0。

数值实验结果表明本文模型可以应用于生鲜农产品带越库配送问题中，遗传算法可以得出越库配送中心车辆与库门的有效分配，以及出库车的最优配送方案。

4 结论

本文同时考虑了越库中心车辆调度问题和车辆配送路径问题，基于客户订单的时间窗，考虑到生鲜农产品的腐败率，以越库中心转运的操作成本、库存成本、交通运输成本、货损成本总成本最小化为目标，构建了复合模型。设计遗传算法求解，同时应用了两种解码方式构建初始解。数值实验表明，生鲜农产品在越库配送模式下能够更好地整合供应链上的各种资源，能够合理分配越库中心车辆与库门的调度，给出在最低总成本下的车辆与库门的分配方案和合理的车辆配送路径，对于现实应用具有很大的参考价值。

此外，本文的研究还有不足之处，可以考虑在冷链物流、取送货过程与多配送中心三个方面进行下一步的深入研究。

参考文献：

[1] 陈军， 但斌. 基于实体损耗控制的生鲜农产品供应链协调[J]. 系统工程理论与实践， 2009， 29（3）.

[2] LEE Y H， JUNG J W， LEE K M. Vehicle routing scheduling for cross-docking in the supply chain[J]. Computers and Industrial Engineering， 2006， 51（2）：247-256.

[3] NAHMIAS， STEVEN. Perishable inventory theory： a review[J]. Operations Research， 1982， 30（4）：680-708.

[4] RAAFAT F. Survey of literature on continuously deteriorating inventory models[J]. The Journal of the Operational Research Society， 1991， 42（1）：27-37.

[5] ZHANG G， HABENICHT W， SPIE W E L. Improving the structure of deep frozen and chilled food chain with tabu search procedure[J]. Journal of Food Engineering， 2003， 60（1）：67-79.

[6] RONG A， AKKERMAN R， GRUNOW M. An optimization approach for managing fresh food quality throughout the supply chain[J]. International Journal of Production Economics， 2011， 131（1）：421-429.

[7] ZANONI S， ZAVANELLA L. Chilled or frozen？ Decision strategies for sustainable food supply chains[J]. International Journal of Production Economics， 2012， 140（2）：731-736.

[8] 楊华龙， 计莹峰， 刘斐斐. 生鲜农产品物流网络节点布局优化[J]. 大连海事大学学报， 2010， 36（3）：47-49.

[9] 陈杰， 陈峰. 不确定环境下的越库调度的模型及算法[J]. 工业工程与管理， 2010， 15（1）：97-102.

[10] AGUSTINA D， LEE C K M， PIPLANI R. Vehicle scheduling and routing at a cross docking center for food supply chains[J]. International Journal of Production Economics， 2014（152）：29-41.

[11] 麦家骥， 陈峰. 基于循环取料的不确定越库调度模型与算法[J]. 上海交通大学学报（自然科学版）， 2011， 45（2）： 159-0163.

[12] 强瑞， 缪朝炜， 吴为民. 供应网络中越库转运中心仓门分配问题研究[J]. 管理工程学报， 2011， 25（1）：209-215.

[13] 缪朝炜， 苏瑞泽， 张杰. 越库配送车辆调度问题的自适应遗传算法研究[J]. 管理工程学报， 2016， 30（4）， 166-171.

[14] 李敬峰， 叶艳， 傅惠. 面向货物装卸需求的越库仓门分配和货车排序[J]. 工业工程， 2016， 19（2）：112-120.

[15] 葛显龙， 邹登波. 供应链环境下带越库配送的车辆路径问题[J]. 计算机工程与应用， 2018（24）：252-259.

[16] 葛显龙， 邹登波. 供应链环境下带越库配送的多配送中心车辆路径问题[J]. 控制与决策， 2018， 33（12）：60-67.