一种大批量多品种后向反馈容重比平衡货物配装法

谢贻文, 廖秀英, 林 剑, 曾祥飞

(1.湖南科技大学资源环境与安全工程学院， 湘潭 411201； 2.湖南科技大学计算机科学与工程学院， 湘潭 411201)

车辆配装问题(vehicle fitting problem, VFP)是如何使车辆的装载效率最高，从而降低物流企业运输成本的问题。配装涉及的货物要素有几何尺寸、容重比、防压性能、成本及配送单价等，由于单一要素的配装便属于组合优化领域的非确定性多项式(non-deterministic polynomial, NP)难题(NP-hard)，因此，车辆配装研究主要是围绕某一种要素展开。在众多要素中，最为普遍存在、也是研究最为广泛的两种要素为几何尺寸[1-4]和容重比[5]。不同容重比的货物配装能充分利用车辆的容积和载重，提高车辆装载率。

货物配装问题是指一批不同类型的货物如何用最少数量的车辆使货物尽可能地装完，货物配装是车辆配装的目的，车辆配装是货物配装的基础。基于货物容重比的VFP，按研究目标的侧重面不同，可分为车辆配装和货物配装。车辆配装假设有远大于车辆装载量的不同容重比的货物，其目标是使车辆的容积和载重得到最大限度的利用，即，选择不同类型的货物装车，使所装货物的容重比趋向于车辆的容重比；货物配装假设有足够的车辆，其目标是用最少的车辆把货物尽可能地装完，要使车辆数最少，就必须考虑充分利用车辆的容积和载重，即，使每台车所装货物的容重比与车辆容重比的差值或比值均衡。

求解基于容重比的VFP的方法可分为精确算法、构造启发式算法和元启发式算法。精确算法把问题求解作为整数规划问题处理，常用的方法有分切算法[6]、分支定界算法[7]等；构造启发式算法主要有容重比平衡法、动态容重比平衡法，容重比平衡法启发式规则有货物容重比与车辆容重比(随着货物的载入车辆容重比动态调整)差值最小的规则[8]、通过聚类使待装货物单元容重比平衡的规则[9]、按货物容重比大小交叉排序的容重比平衡规则[10]、载入货物容重比均值与车辆容重比最小的容重比平衡规则[11]；元启发式算法是在构造启发式算法的基础上增加随机选择的机制，以避免局部最优，主要方法有遗传算法和蚂蚁群算法，在目标函数选择方面，有采用车辆装载率最大和车辆容积率最大的双目标函数的[12-13]，也有二者归一化的单目标函数的[14-16]；在随机选择策略方面，有利用模拟退火方法的遗传算法[17]，有构造车辆容积比和货物容积比为参数能见度函数的蚂蚁群算法[18]。上述方法适用于小批量多品种零散货物车辆配装，对大批量多品种货物配装存在以下问题：①配装单元都是以货物类型为最小配装单元，只考虑货物类型配装。大批量货物中，一种货物类型由多件包装组成，其总量有时远大于一辆车的装载量，除了考虑货物类型配装，同时还需考虑货物数量配装。在已有的构造启发式算法中，没有设计货物数量配装规则，不能实现货物数量配装；元启发式算法和精确算法虽无需设计专门的数量配装规则，但货物的数量会使算法的计算时间成指数增长。②均未事先规划所需车型及其数量组合。对于车辆配装不需考虑所有的货物是否装完，只需使已知车辆的装载率最大，所以无需进行车辆规划。对于货物配装需要尽可能地把所有货物装完，在构造启发式算法中，车辆与车辆之间容积比平衡规则的设定与所有待装货物的量及容积比有关，要建立该规则需要先进行车辆规划；在元启发式算法中，如果未事先进行车辆规划，那么在优化计算时需要同时进行车辆组合优化。如果货物类型配装和货物数量配装为2重NP-hard，那么，增加车辆组合优化则为3重NP-Hard，其优化效率进一步降低。

针对大批量多品种货物配装需要进行货物数量配装的问题，提出一种容重比平衡货物配装构造启发式算法，首先，根据所有待装货物进行所需车辆组合规划，然后，构造同时顾及货物类型配装及货物数量配装启发式规则，并用物流企业实际配送货物数据进行方法实验验证。

1 问题描述

在选择大批量多品种货物作为研究对象时，问题的研究基于以下前提条件。

(1)不考虑货物的送达时间和路径问题，以公路运输为背景，有j类车型可供选择，从配送中心将待配送货物用多辆车送往同一个地方。

(2)所有待配送货物可以相互混装，不考虑货物在车内的摆放情况，但需考虑货物在车内质量、体积以及容重比的约束。

(3)订单是指一种货物类型的需求总量，是由相同体积规格的单元组成，单元单位为件，同种货物允许载入不同的车辆，即允许拆单。

综合以上因素，针对多车型、大批量和多品种的货物配送问题可用数学方式描述为：设配送中心有n种货物向同一个门店进行配送，货物总质量为G，总体积为M，总容重比为C，同种货物对应的件数为{t1,t2,t3,…,tn}，单件货物对应的体积为{v1,v2,v3,…,vn}，单件货物对应的质量为{g1,g2,g3,…,gn}，定义Ci=gi/vi为第i种货物的容重比，所有货物类型的容重比为{C1,C2,C3,…,Cn}，用于装载货物的车型有j类，每种车型对应的数量为{s1,s2,s3,…,sj}，单个车辆对应的载重为{W1,W2,W3,…,Wj}，单个车辆对应的容积为{V1,V2,V3,…,Vj}，定义Rj=Wj/Vj为第j类车型的容重比，所有车辆类型的容重比为{R1,R2,R3,…,Rj}。要求最终实现的目标是：在给定约束条件下，合理规划所需车型及其数量的组合，同时顾及货物类型配装和货物数量配装，使货车的使用数量最少，载重利用率和容积利用率达到最高。

2 车辆规划模型

在货物配装之前，需进行车辆规划，求解出所需车型及数量的组合。车辆规划模型建立的目标函数为

(1)

(2)

(3)

约束条件为

xj≤sj

(4)

(5)

(6)

多车型车辆流程如图1所示。

图1 车辆规划流程Fig.1 Vehicle planning process

3 后向反馈容重比平衡法

后向反馈法是指根据后续待装货物容重比，确定当前载入货物的数量。后向反馈容重比平衡法的基本思想是：当货物满足容重比平衡约束时，尽可能地避免同种货物载入不同的车辆，当货物不满足容重比平衡约束时，载入不同货物使容重比平衡，所载入的货物量由后向反馈法确定。其基本原则是：在货物配装的过程中应用“先装大件再装小件”的思想，从件数最多的货物开始，并尽可能将同种货物装载在同一辆车上。

3.1 容重比平衡规则及总体流程

考虑到货物类型配装、货物数量配装及车辆组合优化为3重NP-hard，针对货物多品种、大批量的特点，构造后向反馈容重比平衡法的容重比平衡规则为

C≤Ckj≤Rj或Rj≤Ckj≤C

(7)

约束条件为

kj∈{1,2,…,m}

(8)

kj∈{1,2,…,m}

(9)

式中：tikj表示有t件i类的货物装载在车型为j的第k辆车上；Ckj为货物i加入车辆kj后所载货物的容重比。式(7)表示Ckj应在货物总容重比C和第j类车型的容重比Rj之间。

算法的求解过程是根据构造的容重比平衡规则选择解元素的过程，总体流程如图2所示。

在算法中，当货物超载时，先执行超载拆单，再判断拆分后的货物是否满足容重比平衡规则。超载拆单是当货物质量或体积超过车辆的载重或容积时，拆除超出车辆容量的货物件数后再进行配载的流程，拆除的货物件数则生成新单，归入未配载的货物中。

图2 算法总体流程Fig.2 Algorithm overall process

3.2 后向反馈法流程

货物不满足容重比平衡规则时，需采用后向反馈法确定货物的载入量，搜索满足容重比规则的未配载货物并组合一起装载，若搜索的未配载货物小于车辆剩余空间时，需对货物i配载拆单，重新搜索满足容重比规则的未配载货物，具体过程如图3所示。

图3 后向反馈法流程Fig.3 Backward feedback process

图3中：W′为车辆kj装载货物i后的剩余载重；V′为车辆kj装载货物i后的剩余容积；g′为满足式(7)所有未配载货物的质量；v′为满足式(7)所有未配载货物的体积。

在后向反馈法中，配载拆单是当搜索出所有满足容重比平衡规则的未配载货物超出车辆剩余容量时，对已加入车辆货物i进行折中拆分的流程，具体流程如图4所示。

图4 配载拆单流程Fig.4 Loading and splitting process

图4中，ti为货物i的件数。当加入车辆货物i的件数小于2件时，则停止拆单，从车辆组合中选择下一辆车，进行装载。

4 实验分析

4.1 容重比平衡法与其他算法对比分析

实验在Intel(R) Core(TM) i5-3210 CPU @ 2.5 GHz处理器，8 GB内存，Windows10 64位操作系统下，用C++语言编制后向反馈容重比平衡货物配装法的程序。为客观评价算法的有效性，使研究结果具有对比性，选取文献[19]中的数据进行实验，采用TBJ10(W=10 t，V=16.81 m3)型集装箱配装，并将解得的最优结果与文献[18]、文献[19]的实验最优结果进行对比，如表1所示。

表1 3种算法结果比较Table 1 Comparison of 3 algorithm results

由表1可知，本文算法比文献[18]、文献[19]的载重利用率分别提高了18.7%、16.09%，容积利用率分别提高了0.95%、8.57%。由此看出，考虑多品种货物的配装问题，通过本文所提出的后向反馈容重比平衡货物配装法，能充分并均衡利用装载工具的载重和容积，求解结果更好。

4.2 大批量多品种货物配装分析

为验证本文算法求解大批量多品种货物配装问题的可行性，采用商业物流管理系统提供的实际配送数据进行研究，有432种待配送货物类型，货物件数共计56 701件，货物的总质量为21.15 t，总体积为47.54 m3，配送车辆类型及规格如表2所示。

商业物流管理系统提供的432种货物的实际配送结果如表3所示。表3中展示了部分货物配装的信息。

表2 配送车辆的类型及规格Table 2 Type and specifications of the delivery vehicle

表3 货物配装信息Table 3 Cargo fitting information

表3中，A1× 400表示001号货物由第1辆车型为A的车装载400件；A1× 131，B2× 61表示002号货物由第1辆车型为A的车装载131件和第2辆车型为B的车装载61件。

表4所示为每辆车的配装结果统计。结合表3和表4可知，实验根据货物的总量，采用车辆规划模型，规划车辆的车型组合为A1B1B2C1，即一辆A型车，两辆B型车和一辆C型车。依据容重比平衡规则及后向反馈法，002号的货物拆分后由A1车和B2车进行装载，006号的货物拆分后由B2车和C1车进行装载，规划的车辆组合共计装载了56 439件货物，余下的006号的208件货物，则滞留在配送中心。一般商业物流车辆的装载率为70%～85%，实验中，车辆组合中的每辆车载重利用率和容积利用率都达到87%以上。

表4 配装结果Table 4 Result of goods arrangement

综上所述，由车辆规划和后向反馈容重比平衡法确定的配送方案，利用可拆分的配载方式，尽可能装载更多货物，使滞留的货物较少，减少车辆的使用数量，使车辆资源使用更加合理，可以有效解决大批量多品种的货物配装问题。

5 结论

针对大批量货物配装中货物类型及数量问题，提出一种大批量多品种后向反馈容重比平衡货物配装法。该算法在货物配装前进行车辆规划，有利于节约车辆资源，同时顾及货物类型配装和货物数量配装，构造了容重比平衡规则，在货物不满足容重比平衡规则时，采用后向反馈法，提高了货物配装的求解效率。通过选取类似文献中的算例进行验证，与其他2种算法相比，后向反馈容重比平衡货物配装法能同时均衡优化车辆的载重和容积。最后结合商业物流实例数据进行研究，从而验证了算法的实用性和有效性，提高了车辆在容积和载重两方面的装载量，节省运力，能够为企业决策提供科学依据，提高配载工作的自动化水平。