装载弱异性货物入厂物流的车辆路径方案优化决策*

伊俊敏 苏志雄

(厦门理工学院经济与管理学院 厦门 361024)

0 引 言

入厂物流是将不同供应商的货物通过集约运输送到工厂指定地点存储等使用的过程，其中车辆装载和路线设计是二个关键点，这首先是带容量限制的车辆路径问题(CVRP)，其次是装车装箱问题[1].CVRP几十年来一直是运筹学的热点研究问题之一，但传统的CVRP模型并未考虑装车，入厂物流需要综合考虑路径和装箱这两个相互制约、不可分割的过程，不考虑装箱，车辆优化路线上的货物无法全部装车；忽视路径优化，车厢装得再满成本也降不下来[2].

Gendreau等[3]从家具配送实践中提出了带三维装箱约束的车辆路径问题(3L-CVRP)的研究，引起国内外[4-6]学者的不断关注.带装箱约束的车辆路径问题将装箱作为CVRP新的约束条件，来保证路线上各节点的货物能够装入车厢空间，并满足不同客户货物的装卸货要求.这类问题将原本两个NP-难的运筹学问题集成考虑，模型与算法更加复杂.带装箱约束的路径复合问题主要包括二维、三维装载约束的(2L-CVRP, 3L-CVRP)、多叠车辆路径问题(MP-VRP[7])、托盘装箱车辆路径问题(PPVRP[8])等.

由于带装箱约束路径类问题的多重复杂性，它们的求解方法集中在启发式算法和混合算法.而装箱约束方面，借助已有装箱问题的研究成果和容器、单品、装载和货物相关的四类装载约束划分，具体问题结合装载实践要求相应考虑其中的几个方面.对于中小尺寸的弱异性货物(即每品种均有一定数量)，装载之前还存在是否先托盘装箱的问题.托盘装箱问题(MPLP)考虑一批等同货物如何装入尽量少的托盘中，现在已经得到较好解决.这样，等同货物托盘单元化之后，就是PPVRP的简单情况，用常规CVRP就可以求解.

另一方面，装载相关的约束还涉及到同一客户的货物是否分批装车，打破CVRP“客户唯一拜访”的假设就是需求可拆分的车辆路径问题(SDVRP)[9].SDVRP对一些线路总成本有显著降低，但拆分会额外增加物流作业交易和管理成本.物流实践中部分客户节点的需求量大于车辆容量(称为大节点)的现象也比较常见，对我们涉及大量装载装箱作业的问题，要考虑SDVRP以前很少考虑的三维装载约束.

本文针对某公司大量弱异性货物入厂物流问题，考虑需求拆分、托盘装箱、分类堆码等多方面实际装载可能性，建立不同的装载约束CVRP复合问题模型，并进行实例数据算法求解和物流综合成本比较分析，不仅必要而且有现实意义.

1 入厂物流货物装车决策

装配型工厂生产经常需要批量采购多种不同的货物，对于中小尺寸货物每品种都有不菲的数量，即弱异性货物.它们的装载及运输集约决策问题，首先是货物要否托盘化以及托盘类型选择决策；非托盘化时则有装车方式的选择：是分类堆码装车还是三维优化装车.决策方案包括：①货物先托盘化，再装车；②包装货物在车厢内分类堆码装车1L；③采用3L-CVRP的三维优化装车，总的决策树见图1.对应托盘类型、装车方式和a,b两种车型最终形成8个决策分枝.然后就是不同方案的建模、求解和结果比较分析.

图1 入厂物流优化决策树

2 三种方案的模型与求解

2.1 基本假设

1) 各取货节点i(i=0, 1, 2, …,n，其中i=0表示工厂)间的距离cij均已知且对称.

2) 货物包装的长、宽、高分别是li,wi,hi，所需数量为qi，装箱装车时hi不能倒置.

3) 对同一个实例，容器、车辆都是同质的，即对任一车k(k=1, 2, …,m)，容量为Q，车厢内尺寸长、宽、高分别是L,W,H；对任一托盘p(p=1,2,…,r)，托盘尺寸长、宽分别是B,D.

4) 每一车辆从工厂出发并回到工厂，中间经若干个节点装取货物，并且尽可能一次取完，需求拆分除外.

5) 一条路线一辆车，每条路线所取货物不超过车辆容量限制.

2.2 托盘化装车路径方案

这一方案实际上就是MPLP和CVRP的先后实施.首先要考虑托盘化MPLP问题，即寻求托盘单元内正交摆放同尺寸箱子(B,D,l,w)实例下最大数量的问题.按照文献[11]的算法，针对中小尺寸数据不超过托盘底面尺寸，分别得到每种货物在两种国标托盘(国际I、日式T)上的单层装码样式和各自需要的托盘单元数量，见图2.

图2 MPLP结果示例：290 mm×210 mm尺寸货物依次在国际和日式托盘上，单层18和20个

这些限定尺寸的托盘单元在车辆上的装载数量确定，又是一个MPLP的(L,W,B,D)实例，最终有了各节点的托盘单元数量qi和车辆的托盘单元容量Q，形成常规的CVRP问题如下所示的三指数流动模型.

(1)

(2)

(p=1,2,…,n,∀k)

(3)

(4)

(5)

(∀k,S⊆V{0},|V|>2)

(6)

(7)

式(2)保证每一节点仅由一辆车拜访一次；式(3)为节点流量守恒约束，每节点流入与流出的交通量相等；式(4)～(5)保证每台车在各节点只被使用一次，m台车辆均从工厂出发并回到工厂；式(6)为子回路消除约束，采用集合的形式表示；式(7)保证所取货物不超过车辆的容积.

2.3 1L-CVRP方案

包装货物在货车车厢内分类堆码的传统装车方式实际上就是一维堆码装车(1L-CVRP)[10].通常货物装箱优化涉及到三维容器装箱问题，但对于本问题弱异性小尺寸货物，采用三维容器装箱问题的砌墙法，可以近似算出每种货物在车厢内同方向堆码的墙厚ti(包装箱长或宽的整数倍)[11].这种近似算法设定每堵墙在车厢内垂直于车辆L方向，且横贯整个车厢宽度，不考虑不同墙在车厢宽度方向的拼接，在CVRP的基础之上增加了装车长度一维装载约束，即在2.2节CVRP模型的基础之上，增加下式可以建立1L-CVRP模型.

(8)

式(8)保证装入车辆中的每种货物的分类堆码的墙厚ti合计不超过车厢总长，这也是该方案的特殊之处，装箱约束条件简化为一维线性约束.

求解时将不同货物作为单独的节点来处理，解决了通常需要需求可拆分路径问题才能解决的、节点需求量大于车辆容量的难题.这一模型求解采用遗传算法实现.

2.4 3L-CVRP方案

3L-CVRP主要是在式(7)的基础之上增加三维装箱诸约束.问题的不同之处在于存在超过车辆容量的大节点，基于文献[12]所提出的带需求拆分的3L-CVRP，在模型的基础之上放松对车辆唯一访问的限制(式(2)的=1改为≥1)，来解决大节点问题.该方案的基本思路是重点考虑那些接近或超过车辆容量的节点，先构造这类节点的装车方式；于是剩余节点的问题则是3L-CVRP所能解决的.该方案求解的具体步骤如下.

步骤1由容器装箱问题的遗传算法来产生每个节点的装车计划.先对一个客户的箱子采用建墙法生成若干“墙”.这里墙与一维优化的主要区别是可以由不同箱子组成，以充分利用空间，各“墙”依次沿车辆长度方向竖立排列，互不交叠.接下来用遗传算法来确定一个客户所形成的全部墙在车厢内的排列组合以使总深度最小，不同节点的装车计划可以在后面的路径计划中进一步合并.对大节点可能形成多个装车计划，每装车计划对应一辆车；但对填充率超过一定比例(按三维装箱结果，如60%)的近大节点，优先考虑与小节点组合形成不能再装的完整装车计划.这些装好的节点就从待求解节点集中删除.

步骤2用混合算法来解决剩下的3L-CVRP问题.路径部分采用禁忌搜索算法将多启动随机节约法产生的初始解逐步迭代到路线最少，同时树搜索算法进行路径的装车结果检查，以寻求可行路径中装车的箱子最大化.两算法还通过缓存已测过路线来提高耦合性减少计算工作量.因为要装车的箱子数量多，就以上一步GA产生的墙或块组合方案代替单个箱子来加速树搜索算法.

步骤3合并步骤1～2的解就得到最终解.

3 案例数据及结果分析

3.1 案例数据

入厂物流案例数据为某工厂市内13个待取货节点的82种不同的中小尺寸货物(平均体积0.03 m3)，篇幅原因，表略.该批中小尺寸货物具有典型的弱异性特征，总件数达23 220箱，每种货物数量平均达284件.每节点待取货物种类从1～15不等，平均为6.3种货物.

案例车型为大型车a，货厢内部装货尺寸为，L=12 024 mm，W=2 350 mm，H=2 697 mm，容积76.3 m3；中型车b，L=8 600 mm，W=2 400 mm，H=2 400 mm，容积49.536 m3.

3.2 案例及计算结果

3.2.1托盘装车方案结果

按托盘单元货物堆码净高≤1 000 mm，每种货物单独托盘化.82种货物按底面尺寸应用MPLP求解单层装码数量，再确定堆码层数，即得每种货物在托盘上可装码数量.将节点内各货物所需托盘数汇总即得各节点所需的托盘数量，见表1.表1粗体字为“大节点”，如A2，A3，A6，A9.但82种货物单独每种的总体积均没有超过任一车型的车辆容积，且总重小于车型载重量.

表1 I、T两种不同托盘化后的各节点装箱结果 托盘数

上述两种托盘化结果，按a, b两种车型的容量，对大节点直接减去满载的直取车数，便得到四个常规CVRP方案算例.因为节点距离矩阵已知，这一问题可以用Lingo求得最优解，结果见表2.

表2 4个CVRP算例的计算结果

*总托盘数与表1合计数据不同在于大节点的直取路线的托盘数量已减去.

上述总里程还要加上各条满载直取路线的双倍距离，便得各实例的总里程.

3.2.2一维堆码装车方案结果

这种方式采用的遗传算法在Matlab环境下实现，运行于i3-4130/4G配置的64位计算机上.两方案计算各运行了15次，得到了最好的计算结果见表3.

3.2.3三维优化装车方案结果

三维优化装车采用前述混合算法用C++在Intel 3.30GHz处理器的计算机上实现，不同车辆容量的二个方案结果见表3.

表3 1L-CVRP及3L-CVRP算例的计算结果

4 分析与决策

4.1 三种模型结果比较

三种模型的8个方案结果比较如表4所示，其中车辆数包括了整车直达的情况.

总体来说，托盘装车方案的结果较后两种方案差很多，主要是因为它二个层次的装箱都没有高的填充率.一维优化与三维优化的差别较小在于二者都是建墙，不过前者的等同箱子墙，后者是不同箱子的墙，因为算例数据为大量弱异性，且相对于车厢尺寸较小，故两者墙相似度较高，最终结果接近.

表4 三种模型共8种情况的结果比较

可以看到，采用大型车a的三维优化装车方案的总里程最短，车辆数最少，平均车辆满载率为77.8%.但是不管是哪种模型若采用小车型b，车辆数虽然多了，但装车尺寸契合度更好，满载率均有所提高.特别的是采用托盘化后，所需车辆数和总里程显著增加，总体满载率大幅降低.

4.2 入厂物流作业成本分析

虽然从上面结果来看，托盘装车方案最差，但是入厂物流决策不只是车辆路径和满载率，各方案的物流装卸作业的情况也需考虑，比较它们的优劣最终要从整个物流系统来衡量，物流作业成本是最终的衡量因素(各物流系统配置已定，不计系统的配置成本).

首先各节点距离决定我们是城市配送，假设按配送每车公里成本λ与总里程Z的乘积得到成本C1；每多访问一次节点(因为有需求拆分，访问次数多于节点个数)，增加固定成本C2，它只是减速停车的成本，不包括后面要考虑的可变装货成本，按各算例数的总里程和节点总访问次数g可得到车辆路线距离和访问方面的总成本.

其次就是装卸车、码箱的物流作业成本.因为装车、码箱是繁重的物流作业，这里测算出物流搬运时间，再折算成物流成本.取货时每条线路访问一个节点(停车成本已在前面C2中考虑)需要考虑装货时间T1，它包括按件(一箱或一托盘均算一件)的装车作业时间T11，和箱型不同时的挑选和排队的装车准备时间T12；其中T11为取货件数e与单件装车时间t11的累计乘积，T12为单位准备时间t12与转换次数f的乘积.最后还有到达工厂的卸车时间T2，不管是叉车作业还是人工作业都是按件来卸，单件卸车时间t2较单件装车时间t11更低，因此考虑上述因素的物流搬运总时间T为

T=T1+T2=e·t11+f·t12+e·t2

(9)

T12是指在共同的拣货作业完成之外，多箱型装车时先要准备好不同箱型分区排队顺序后才能按件依次装车.对于托盘装车，每按一种货物托盘时需要考虑一个t12，同货物托盘因为按件装箱时间已经考虑了，就不再需要；一维优化装箱时，只在每墙(同一箱型组成)不同时考虑t12.但三维优化装箱最复杂，因为要考虑每个箱子的装箱顺序和位置，每两个箱子之间都要考虑一次，但连续的同一种箱子只考虑一次t12.

设每小时平均物流搬运成本为μ，则最终有

C=C1+C2+C3=λZ+gc2+μT

(10)

根据物流实践，取t11=0.2 min，t12=1 min，t2=0.133 min，c2=50元，λ=5元(a型)，4元(b型)，μ=20 元/h，则得到的成本比较结果见表5.

表5 三种模型共8种情况的物流作业成本结果比较

由表5可知，总成本最小的是第一个决策枝，即国际托盘I装a型车；按单位车辆成本最小的是方案4，即日式托盘装b型车.虽然三维优化装车方案在里程数和车辆空间利用率方面优势明显，但平均每车千余件货物的装卸和基于三维优化装箱所必需的排序和准备成本高昂，也成为3L-CVRP在人工搬运甚至机器搬运下实现的最大障碍.综合考虑了物流装卸及排序准备成本之后，托盘单元化方案的物流作业总成本还是最低.在复杂多货物装卸搬运成本增加的情况下，托盘单元化的优势更加明显.

5 结 束 语

本文针对大量弱异性货物取货的实际情况，考虑了三种不同的车辆路径问题方案，分别进行了建模和求解.系统决策不仅是各运筹学模型总里程、车辆数和满载率结果的比较，还有更切合实际物流作业的装卸货和准备转换下的成本比较.对于总里程数和车辆空间利用率方面优势明显的三维优化装车方案，大量货物按三维优化装箱结果所必需的排序、准备和装卸的成本高昂，需要的高效低成本的自动装车技术一时还无法实现.当然，研究还未涉及循环取货式线路问题，且在成本模型中对手工搬运和叉车搬运一次作业时间等同看待存在一定误差，方案还需要更多的数据来验证.但这一基于多模型和物流作业成本的综合优化分析有助于多种不同约束条件下的车辆路径问题的应用决策.

参考文献

[1] TOTH P, VIGO D. Vehicle routing: problems, methods, and applications [M]. 2nd ed. Philadelphia: Society for Industrial and Applied Mathematics, 2014.

[2] 王征,胡培祥,王旭坪.带二维装箱约束的物流配送车辆路径问题[J].系统工程理论与实践,2011,31(12):2328-2341

[3] GENDREAU M, IORI M, LAPORTE G. A tabu search algorithm for a routing and container loading problem[J]. Transportation Science, 2006,40(3):342-350.

[4] 王长琼,戚小振.三维装载约束下的汽车零部件循环取货路径优化研究[J].武汉理工大学学报(交通科学与工程版),2015,39(6):1161-1165.

[5] IORI M, MARTELLO S. Routing problems with loading constraints [J]. Top, 2010,18(1):4-27.

[6] POLLARIS H, BRAEKERS K, CARIS A, et al. Vehicle routing problems with loading constraints: state-of-the-art and future directions [J]. OR Spectrum, 2015,37(2):297-330.

[7] DOERNER K, FUELLERER G, GRONALT M, et al. Metaheuristics for vehicle routing problems with loading constraints [J]. Networks, 2007,49:294-307.

[8] ZACHARIADIS E, TARANTILIS C, KIRANOUDIS C. The pallet-packing vehicle routing problem [J]. Transportation Sciences, 2012,46(3):341-358.

[9] ARCHETTI C, SPERANZA M G. Vehicle routing problems with split deliveries [J]. International Transactions in Operational Research, 2012,39:3-6.

[10] YI J M, SU Z X, QIU Y H. The vehicle routing problem with one-dimensional loading constraints [J]. International Journal of Industrial and Systems Engineering, 2017,27(3):412-426.

[11] 伊俊敏，苏志雄.考虑循环取货装车堆码的一种车辆路径问题研究[J].武汉理工大学学报(交通科学与工程版),2017,41(2):179-184.

[12] YI J M, BORTFELDT A. The capacitated vehicle routing problem with three-dimensional loading constraints and split delivery-a case study [J]. Operations Research Proceedings, 2016(1):47-52.