考虑循环取货装车堆码的一种车辆路径问题研究*

伊俊敏 苏志雄

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

考虑循环取货装车堆码的一种车辆路径问题研究*

伊俊敏 苏志雄

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

研究了某制造企业循环取货物流路径优化问题，根据弱异性小尺寸货物装车堆码特点，在装箱约束处理中通过“砌墙法”的有效简化处理，得到车辆容积和装车长度双容量约束的新型车辆路径问题模型，区别于已有带装箱约束的车辆路径问题.将不同货物作为单独的节点来处理，解决了通常需要需求可拆分路径问题才能解决的、节点需求量大于车辆容量的难题.运用遗传算法求解，松弛双容量的难约束，对该问题实际数据算例求得最终路径-装车结果.从结果解析、“砌墙”误差分析、相关问题比较和应用条件等方面验证了问题模型物流应用的可靠性和可行性.

车辆路径问题；装车堆码；需求可拆分；遗传算法；弱异性

0 引 言

循环取货(milk-run)是汽车等制造企业应用的一种先进入厂物流模式，它是对不足整车运输的多家供应商物料，按设计好的路线，采取多频次、小批量的方式取货，统一送到工厂生产现场的方式.通过对取货顺序、路线和频次的总体安排来更好地控制入厂物流.循环取货方式不仅降低了库存，还加速了物流效率和线路合理性[1].

循环取货优化的关键是路线设计和车辆装车，这离不开带容量限制的车辆路径问题(CVRP)[2].但常规的CVRP模型并未考虑装车，优化结果在实践中却装不下[3].实际上，对这类需要拼装货物的配送问题，运输和装箱是2个相互制约、不可分割的过程，不考虑装箱，车辆优化路线上的货物却无法全部装上该车；忽视路径问题，车厢装得再满成本也降不下来[4].因此，循环取货物流的研究要综合考虑路径与车辆装箱问题.

综合考虑装箱和路径问题的最常见做法是将装箱作为CVRP新的约束条件，来保证一条路线各节点的货物能够装入车厢空间，并满足不同客户货物的卸货要求.当然具有装箱约束的车辆路径复合问题总的还是路径成本最小的NP-难问题，但装箱约束本身也是NP-难问题，两者的复合更加难以求解.根据装箱约束的维数，目前的研究分为二维问题(2L-CVRP)和三维问题(3L-CVRP)[5-9]，提升了车辆路径问题和装箱问题在物流运输领域的实际应用并指明了方向.

另一方面，循环取货作业常有将外地供应商的货物先行集中到工厂附近取货节点的操作，这些节点所需取货量可能会超过车辆容量(称为“大节点”)，已不满足CVRP问题“节点惟一拜访”的基本假设，需要考虑需求可拆分的车辆路径问题(SDVRP)，允许该节点需求量被不同车辆分装送货.对于SDVRP问题，通过需求拆分可以形成更合理的路线来降低路径问题的目标总里程[10].SDVRP虽然降低了总里程成本，但是对同一客户的多次访问却提高了交易及管理成本，总的物流成本可能难以降低.从管理角度看，如果不是特别需要，并不值得推荐.

文中针对某物流循环取货问题展开研究，通过简化的装车堆码近似算法，得到专门的路径-装箱复合问题及模型.对实例数据，通过扩展节点的方法解决了“大节点”需求拆分的问题，运用遗传算法求解，并给出结果及应用分析.

1 循环取货装车堆码决策

针对汽车制造等行业生产需求的变化、众多供应商和各零部件重量与尺寸的差异，Milk-run决策先要根据既定取货周期下各零部件需要的数量，来综合解决合理数量下取货车辆的路线和装箱的复合要求.

由于汽车零部件货物体积尺寸差别大，无法全部托盘单元化，尤其是小尺寸零部件装车常是包装货物在货车车厢内堆码的传统方式.对于装车堆码，假设车型相同，即对任一车k(k=1,2,…,m)，载重量为Q，车厢内尺寸长、宽、高分别为L,W,H.每种货物包装的长宽高分别为li,wi,hi，其中装车时hi不能倒置.

就装箱优化来说，涉及到货物装车的三维容器装箱问题，这类问题2种最基本的解法是砌墙法和分层法[11].对于本问题，弱异性小尺寸货物，砌墙法更合适.

采用砌墙法可以近似算出每种货物在车厢内同方向堆码的墙厚ti(包装箱长或宽的整数倍).这种近似算法设定每堵墙在车厢内垂直于车辆L方向，且横贯整个车厢宽度(见图1)，不考虑不同墙在车厢宽度方向的拼接.这时墙厚的计算公式如下.

(1)

2 路径与装箱复合问题的建模

解决了装车堆码之后，系统优化的关键问题是确定循环取货路线安排和所需路线数量，以使总成本最小.这是CVRP类的路径问题，首先是基本的模型假设[12]：

1) 每一车辆从仓库出发并回到仓库(回路问题)，中间每节点只拜访一次.

2) 车辆到达一个节点后只取货物，并且一次取完.

3) 所用车辆均相同，一条路线一辆车，每条路线所取货物不超过车辆容量限制.

并采用以下记号：i为取货节点，i=0,1,2,…,n，其中i=0表示仓库;qi为每一取货节点的取货数量(以重量计)，i=1,2,…,n;cij为节点i和j之间的距离，i,j=0,1,2,…,n.

图1 不同货物的砌墙法装车示意图(注：t为墙厚，A为节点)

本问题的目标是所有车辆总的行程距离最小，沿用三指数车辆流动模型，设置0-1变量xijk，仅当车辆k直接从节点i到节点j，值为1，否则为0.所有的节点构成集合V，S为进入某一路线的节点的集合，显然S为V的子集，S不能为空且至少包含两点.

则问题模型如下.

(2)

(3)

(5)

(6)

(7)

(8)

(9)

其中：式(3)保证每1节点仅由1辆车拜访1次；式(4)为节点流量守恒约束，每节点流入与流出的交通量相等；式(5)和(6)保证每台车在各节点只被使用一次，m台车辆均从仓库出发并回到仓库；式(7)为子回路消除约束，采用集合的形式表示；式(8)保证所取货物不超过车辆的载重量；式(9)保证装入车辆中的每种货物的墙厚合计不超过车厢总长，这也是本问题的特殊之处，装箱约束条件简化为一维线性约束，它仍然属于带装箱约束的CVRP问题.

需要注意的是，原始节点下的需求量数据有“大节点”，不满足本问题模型的式(3)及基本假设.但将每种货物单独当成一个节点后，上述模型及假设仍然成立，详细处理见下节.

3 模型求解

本问题是NP-难问题，对于大规模问题主要采用亚启发式算法，如禁忌搜索、模拟退火和遗传算法等亚启发式算法来求解.

3.1 算法设计

考虑遗传算法(GA)求解车辆路径问题的优势在于它可以随机地从1个可行解跳到另1个可行解，从而解除其他方法容易陷入局部最优解的困扰[13].此外，GA计算速度快且易与其他算法相结合，适合较大规模的车辆路径问题.

3.1.1 编码和解码

编码问题是GA算法设计关系到算法效率和质量的首要和关键问题，这里设计了一种整数编码来表示可行的节点排序与车辆指派方案，同时避免了子回路现象.染色体由两部分组成：第一部分为基于节点的编码，用来确定节点的访问先后顺序(从左到右)；第二部分为基于车辆的编码，用来选择每个节点的访问车辆.解码是将染色体转化为CVRP解的过程.

3.1.2 适应度值计算

对原问题的式(8)～(9)进行松弛，惩罚系数分别为较大的正整数M1,M2，进而得到新的目标函数(见式(10))，并确定该染色体的适应度值(值越小越好).

(10)

3.1.3 初始种群生成

采用完全随机的方法来构造初始化种群：第一部分编码为1,2,…,n的随机排列，第二部分编码中的每一基因取值为介于1～m之间的随机整数.

3.1.4 遗传操作

1) 选择操作 选择的实质是对种群中的染色体优胜劣汰.文中采用随机遍历抽样法(SUS)，根据染色体的期望值来实际分配染色体被复制的数目.

2) 交叉操作 这里交叉操作采用单亲操作，对于基于节点编码的基因串采用翻转(Flip)算子，即将随机选择的两点之间的序列进行翻转；对于基于车辆编码的基因串也采用翻转算子.

3) 变异操作 变异操作也采用单亲操作，对于基于节点编码的基因串采用两点交换(Swap)算子；对于基于车辆编码的基因串采用整数变异，即对每一基因以一定的概率用介于1～m之间的其余整数进行替换.

3.2 案例及计算结果

3.2.1 案例数据

循环取货案例数据来源于某公司市内13个待取货节点的82种不同尺寸的小体积货物(平均体积0.03 m3).每节点待取货物种类从1～15不等(见表1)，平均为6.3种货物.

案例分别采用2种车型得到2个不同的算例，对于算例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.

表1 各节点货物类型分布

3.2.2 大节点及扩展节点分拆

由表1最后一列可知，存在“大节点”，如A6，A2，A3.但这82种小体积货物每种均没有超过2种车型的车辆容积，且小于其载重量(满足式(8))，因此采用砌墙法装车，每种货物均可单独堆码在一段车厢内.这样，待装车的82种货物扩展为82个不同的地址节点.因为13个原始节点间距离已知，且处于同1个原始节点内的扩展节点之间的两两距离为0，则82个扩展节点间的两两距离也可得，即cij数据.

3.2.3 最少路线数m的下界

按照式(8)和(9)可分别算得m的下界值，见表2最后4列，所求最优车辆数不会低于这些值.2个算例的主要数据特征见表2.

表2 1L-CVRP问题算例主要数据特征

3.2.4 计算环境及结果

文中采用的遗传算法在Matlab环境下实现，运行于i3-4130/4G配置的64位计算机上.对于式(10)，设置M1=M2=1 000，交叉概率取0.85，变异概率0.05，种群规模设为120，进化代数设为6 000代，最长运行时间控制在600 s内.两算例计算各运行了15次，最好的计算结果分别见表3～表4.

表3 1L-CVRP问题遗传算法求解最优结果(算例a：V=76.3 m3,L=12 024 mm)

注：*原始节点代号后标有星号的为采用分拆取货的节点，加下划线的为大节点，即需求量超过车辆容量，如A6.下表同.

4 分析与讨论

4.1 计算结果分析

1) 结果解析 前面是将82种货物当成节点来计算的，各条路线最终还原成原取货节点的情况见表3～4第三列所示.其中该列仅1个原始节点的实际上是直达路线，算例a有5条，均是发生在大节点(A2,A3,A6)上；算例b有12条，大节点A2,A3,A6均有直达路线，但A9无直达只是分拆取货，还有A5,A12 2个未超过车辆容量限制的节点也采用直达送货且无分拆取货，因为不同箱子尺寸降低了车辆利用率.

2个算例的主要不同在于车辆尺寸和容量，算例b的车辆更小，在要装车货物总量不变的情况下，所用车辆当然更多，路线所访问的节点数也趋小，采用直达路线的可能性也更高.

表4 1L-CVRP问题遗传算法求解最优结果(算例b：V=49.536 m3,L=8 600 mm)

2) 装箱近似算法的误差分析 在式(1)的计算中，向上取整时墙厚中的排数为整数，会有些墙的箱子没装满一排而空着(参见图1装车侧视图上部的缺口).以算例a为例，研究找到这种最大的空排部分前5个分别是货物7，33，13，60，1，它们墙厚空档部分分别占各自ti的21.1%，21.1%，4.8%，22.1%，12.7%，相应占L的2.17%，2.17%，1.88%，1.49%，1.69%，均不超过3%，而且在各自线路中这些误差均没有超过最小的ti/L百分比.再比较本文线路容积利用率77.55%的均值，可以确定装箱近似算法的误差都不足以影响装箱和线路的最终结果.

4.2 与相关CVRP问题的不同

注意到表1中有大节点，必须分拆送货.从表3～4中的分拆节点来看，算例a除3个大节点外，还有非大节点A9,A12被分拆；算例b除4个大节点外还有A11,A12被分拆.文中的大节点涉及到货物尺寸及装箱组合，并不能像对待单一体积数据那样直接减去整车的量，如何拆分这些需求量实际上是1个新的组合问题.SDVRP有专门的算法，但是还没有涉及到货物尺寸及装箱.在这里，同1节点内的不同货物被当作虚拟节点处理，扩展了节点规模n及相应距离矩阵cij，从另一个角度解决了分拆送货问题.当然节点规模的增加使得这种处理会牺牲一定的计算时间，总的还是值得的.

与现行的3L-CVRP测试算例相比，本案例为小体积弱异类货物，数量更多也更符合实际情况；当然3L-CVRP测试算例中货物常为强异类，数量常为一件，更要考虑精确装箱，不能用这里的装箱近似算法.

4.3 应用可行性分析

作为从循环取货案例中提出的特殊CVRP问题，除了砌墙法装箱的误差分析，其可行适用条件也需探讨.本例将三维装箱通过砌墙法简化为不同于3L-CVRP的单维堆码长度问题，更便于应用.这里装车堆码处理的适用条件是小型弱异类货物，即单个货物箱子尺寸相对于车厢尺寸都比较小，且同种货物数量较多，这样才能“有砖砌墙”.如果是家电配送大体积且数量少的强异性货物就难以采取这种方法，但本问题源于实际，有较好的应用意义.

5 结 束 语

针对循环取货优化决策，结合具体案例的装车堆码要求，将车辆路径问题与装箱问题综合考虑，符合当前刚兴起的3L-CVRP研究方向，克服了传统两类问题孤立研究难以实用化的不足.研究建立了包含容积和堆码长度的双约束的CVRP问题模型，并通过扩展节点解决了“大节点”处理的难题.这一问题模型及求解方案符合特定实际情况，比3L-CVRP更简洁实用.并进行了结果分析与讨论，验证了方案应用的可靠性.

[1]汪金莲,蒋祖华.汽车制造厂零部件入厂物流的循环取货路径规划[J].上海交通大学学报,2009,43(11):1703-1709.

[2]YI J M, ZHOU J, GAO X L, et al. Tactical planning and optimization of a milk run system of parts pickup for an engine manufacturer[J]. Journal of Southeast University: English Edition,2007,23(增刊1):99-104.

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

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

[5]GENDREAU M, IORI M, LAPORTE G, et al. A tabu search heuristic for the vehicle routing problem with two dimensional loading constraints[J]. Networks,2007,51(1):4-18.

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

[7]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.

[8]BORTFELDT A, HOMBERGER J. Packing first, routing second—a heuristic for the vehicle routing and loading problem[J]. Computers & Operations Research,2013,40(3):873-885.

[9]颜瑞,张群,胡睿.考虑三维装箱约束的多车场车辆路径问题[J].管理工程学报,2016,30(1):108-116.

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

[11]黄文奇,何琨.求解长方体Packing问题的纯粹拟人算法[J].中国科学 F辑:信息科学,2009,39(6):617-622.

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

[13]BAKER B M, AYECHEW M A. A genetic algorithm for the vehicle routing problem[J]. Computers & Operations Research,2003,30(5):787-800.

A Study on a Specific Vehicle Routing Problem Under the Cargo Loading and Stacking by Milk-run Operations

YI Junmin SU Zhixiong

(SchoolofEconomicsandManagement,XiamenUniversityofTechnology,Xiamen361024,China)

A special vehicle routing problem with easy-to-implement loading scheme for route optimizing of a manufacturer’s milk-run operations is proposed with focus on the loading and stacking of weak-heterogeneous small-sized cargos. A new model is formulated with dual capacity constraints on both volume and loading length by applying a wall-building method for cargo stacking inside the vehicle. It is a new variant of the Capacitated Vehicle Routing Problem with Loading Constraints. Besides, the node set is extended temporarily by treating each cargo as a different node, thus an affordable increase in solving time by the node extension is traded with way out the difficulty of node demand surplus vehicle capacity, rather by the method of Split Delivery Vehicle Routing Problem. With slack of the dual-capacity constraints, the fitness value is evaluated using the genetic algorithm, and comprehensive routing and loading results for two instances from real data are achieved. The results are examined with discussions on result analysis, error study of wall-building approximation, model comparison, application conditions, which suggest a sound reliability and feasibility of the model’s application in logistics practice.

vehicle routing problem; loading and stacking; split delivery; genetic algorithm; weak heterogeneity

2016-02-20

*国家自然科学基金项目(71371162)、福建省自然科学基金项目 (2014J01271)资助

U492.3

10.3963/j.issn.2095-3844.2017.02.001

伊俊敏(1969—)：男，博士，教授，主要研究领域为物流系统工程、物流运筹与管理