三阶段越库车辆排序及算法研究

李 欣，孙 军，陈 欣 （大连工业大学，辽宁 大连 116034）

0 引言

根据我国国家标准《物流术语》中给出的定义，可以知道越库模式是指物流环节中的产品和商品，不经过中间站点和仓库，直接从一个交通运输工具换载到另一个交通运输工具的物流承接方式。随着越库管理模式在实践中的广泛运用，越库中的各类问题也引起了学者的研究兴趣。例如毛道晓、徐克林等[1]以总成本最小为目标，从长期战略角度利用混合整数规划模型研究了越库模式的中心选址问题.。强瑞、缪朝炜、吴为民[2]则从中期策略角度出发探讨带有时间窗口的仓门分配问题，将贪婪算法、遗传算法以及禁忌算法的思想整合、衍生出了混合启发式算法来解决问题，并将其结果与这3种算法各自的结果进行对比，验证了该混合启发式算法在问题解决中的优势。同样研究仓门分配问题的还有李敬峰[3]。除了仓门、选址等问题之外，在总施工时间最短的目标下，对配送中心车辆入库卸货顺序的优化问题也是学者关注的一个部分。高晶、高举红[4]把越库作业流程分成两个阶段，利用约翰逊算法解决了配送中心内部越库车辆排序问题，为服务连锁零售企业的发展提供指导。马东彦、陈峰[5]考虑现实情况，对越库作业的流程、类型和实施所需的条件进行分析研究，在此基础上研究了对配送中心内部的作业顺序优化。在多位学者的研究基础上，本文研究了越库车辆排序问题发展现状并解析原因，再运用约翰逊算法解决问题，并提出相关建议。

1 越库车辆排序问题现状分析

从越库的定义看出，整个越库流程起点是各大供货商，车辆从供应商处取得商品到达越库中心，经过越库中心，再由出库车辆运送至各大门店。看似很简单的流程，但在实际工作过程中却存在着大量的问题，总要有以下几点。（1）排序不当导致配送中心仓储压力增大。随着电子商务的高速发展，例如双十一、双十二等购物节日的出现，使得物流行业会出现阶段性订单量暴增。尽管物流公司提前备车，但是激增的订单量还是难以消化，除了运输路途问题，当车辆来到各个配送中心，按照什么样的顺序出入库可以实现效率最高也是一个艰巨的问题。不当的排序，可能导致各个环节之间配合不当，商品滞留，最后堆积的商品必然会为配送中心带来巨大的仓储压力，更有可能导致运送时间和运输成本的增加。（2）相关物流企业关注度不够。对于越库模式的研究国外在80年代就已经有所提及，并且国外很多企业例如沃尔玛、UPS、丰田等都已将越库模式融入自己的企业生产中，但是这并没有引起国内企业的重视，更不要说越库车辆排序的问题了。主要原因在于中国大多数物流企业尚处于发展阶段，企业没有多余的精力投放到物流作业的优化中，再加上越库模式对企业自身的要求也较高，自然导致对车辆排程问题的关注度不够，想要解决这一类问题，还有很长一段路需要探索。（3）缺乏切实可行地解决配送中心越库车辆排序问题的方法。对车辆排序问题的研究，在研究算法上，学者主要集中于常规的算法如遗传算法、禁忌搜索算法等，并针对这些算法的缺陷进行改进以更适应实际问题。例如蒋鹏、佘艳[6]以遗传算法为基础考虑了越库车辆排程问题，并利用完善之后的配送模型对接驳车辆配送排程方案进行了优化设计。黄尚[7]研究的则是在如今电子商务的整体大环境下，物流发展情况的新特点，分析研究了遗传算法在物流配送中，尤其是在如何确定越库配送车辆出入库顺序中的使用。经过这些学者的研究，确实证明了这些高级算法在问题解决中的可行性，但同时这些算法自身对问题的约束条件较多，加上算法自身存在的缺陷都为其日常企业实践带来了一定的障碍。为了解决上述问题，本文提出运用简单易行的约翰逊算法帮助企业确定车辆进出的最佳顺序。

2 越库车辆排序算法探究

2.1 算法简介。约翰逊算法是一种基础的作业排序方法，虽然在越库车辆排序问题中的应用较少，但在求解以加工时间最短为目标的工件顺序问题上被广泛运用，已经发展成为一种相当成熟的算法，并且应用简单，容易得到最优解，对于解决车辆排序问题更具有实践意义。它强调只有当n个工件要经过二、三个机器（必须是有限个机器）进行加工，并且所有工件在有限个机器上加工的顺序都是相同时才可以被使用到越库车辆排序问题中。当工件要经过两个机器即经过两道工序时，使用约翰逊算法解决问题的一般顺序为：一是找出工时表中最小的数字。如果该数字在第一道工序，则将对应的工件放在最开始加工；如果该数字在第二道工序，则将对应的工件放在最末尾加工。二是将第一步已经确定了顺序的工件划去。三是重复上述两道工序，直至确定工时表中所有工件的顺序。

可以看出约翰逊算法的应用十分简单，但是随着设备数量的增加，优化难度也随之增加。为了求解三阶段问题，必须对算法进行改进。当有n项工件且要经过三道工序时，可以使用下述方法求得最优解：一是将工时表中第一道工序的施工时间和第二道工序的施工时间相加；二是将工时表中第三道工序的施工时间和第二道工序的施工时间相加；三是将上两步得到的时间当成两个独立的工序的施工时间，然后重复机器数目为2时的处理方法，得出正确的工件加工顺序。根据赵辉、张红云[8]的论证，要想使用上述方法，必须要满足下面两种情况中的其中一个：即第一道或是第三道工序中的最小施工期≥第二道工序中的最大施工期。

为了更好地将约翰逊算法运用到越库模式的车辆排序问题中，需要将整个越库作业分成三个阶段，对应约翰逊算法的三道工序。商品从入库车辆卸载至暂存区，等候进入分拣带的过程看成第一阶段，记做M1；第二阶段则是商品从暂存区出来经过分拣带，按照订单分拣到各个门店对应的暂存区等待重新装箱，记做M2；商品从暂存区再打包到达站台上车的过程看做是第三阶段，记做M3。如图1所示。

图1

2.2 相关假设。为了方便理解约翰逊算法的实际运用，首先制定相关假设条件，一是假设配送中心只有一个门口，车辆入库、出库都要从这里经过，并且每一次只能经过1辆车俩。二是假设有3家供应商向4家门店供货，每辆车辆对应1个供应商，并且每家供应商供应的商品是独一无二的，即每辆车辆只负责1种商品。三是假设配送中心一共有2个站台，每个站台都对应着特定的车辆，每辆车辆都对应着特定的一条路线，且每条线可以配送不止1家门店。四是配送中心内部只有一条分拣带，分拣带的传输速度是一定的，物品在分拣带上的时间只与物品的体积和分拣口的距离有关并且暂存区的数量是不限的，每个暂存区必须等所需商品分拣结束之后才重新包装、装车。五是当各个阶段开始正式工作之后就不允许中断。

2.3 相关数据的确立。假设有3家供应商向4家门店供货的客户订单表如表1所示，每一格的数据代表了对应门店所需商品数量。假设Si表示各个供应商，本假设中有3个供应商可分别表示为S1、S2、S3，同时由于各个供应商只供应唯一一种商品，所以Si还可用于表示各个供应商供应的商品S1、S2、S3，其中S1的体积最小，S3的体积最大；Zi：Zi表示各个站台，如2个站台分别表示为Z1、Z2；Di：Di代表各个门店即需求方，如 4个门店可分别表示为 D1、D2、D3、D4。

由于资金有限，越库中心只有有限个站台，并且每个站台对应着特定的线路，每个线路可以配送多于1家门店，因此站台与门店之间的对应关系，如表2所示。Z1站台对应着D1、D2两个门店，即将D1、D2的货物集中在Z1站台，当货物搜集完毕之后，由1辆车进行配送。而Z2站台对应的是D3、D4，就是将D3、D4的货物集中在Z2，装车后由1辆车完成运送。这样可以最大限度地提高车辆的利用率，减少循环取货带来的时间和成本上的浪费。

表1 客户信息表 单位：个

表2 站台与门店之间的对应关系

2.4 计算步骤及结果。商品在各阶段所需时间受不同因素影响，如：第一阶段：M1阶段要完成商品拆包卸货到暂存区的工作，因此所需要的时间主要是受商品自身的体积和门口与卸货区之间距离的影响，而不会受到车辆入库顺序的影响。第二阶段：M2则是商品从暂存区出来经过分拣带，按照订单进行分拣到达每个门店所对应的各个暂存区，由于配送中心内部只有一条分拣带，分拣带的传输速度是一定的，因此这一阶段所需的时间会受到物品的体积、分拣口的距离、暂存区与分拣带之间距离的影响。第三阶段：M3是商品依据订单重新包装好再装车的过程，由于只有当所有的货物都收集完毕之后才能打包，并且打包之后立即就能进入站台上车，因此这个阶段所需要的时间主要受到各个门店所需商品的体积和商品入库顺序以及各个暂存区与站台之间距离的影响，并且商品的体积与各阶段停留时间成正比。因此根据表1客户信息表和表2站台与门店之间的对应关系的数据，再结合工人日常分拣经验以及机器的运作效率，可以大致估算出各个货物在每个程序中所需的时间，如表3.所示。

商品在各阶段所花费的时间满足了上述两个要求，所以可以使用约翰逊算法。一是将工时表中第一道工序的施工时间和第二道工序的施工时间相加，得到M1+M2的数据；二是将工时表中第三道工序的施工时间和第二道工序的施工时间相加，得到M3+M2的数据；三是将上两步得到的时间当成两个独立的工序的施工时间，然后找出后两行中最小的数字是6，并且在第一道工序中，因此将S1放在最前面，并将S1从表中暂时剔除，发现剩下的数中最小的是10，在第二道工序中，因此将对应的S2放在最后面，最终可以得到最佳的入库顺序是S1-S3-S2。

3 解决越库车辆排序问题的相应对策

根据约翰逊法则，确定了在上述条件下最佳的入库顺序是S1-S3-S2。这样的安排不仅能大大提高各个工序之间的契合度，提高了整体效率，同时节约了成本，为企业竞争创造了条件。为了解决文中提出的相关问题，针对性的提出了下面几种对策。（1）对越库车辆合理排序可以降低仓储压力。如果利用GPS技术实时监控车辆的位置，预估出各个车辆大概的到达时间、有哪些车辆会到达，再依据约翰逊算法合理确定进入顺序，这样可以大大减少配送中心可能产生的临时库存，降低仓储压力、提高车辆利用率，对降低企业配送成本有益。（2）物流企业应提高对越库车辆排序问题的关注度。传统的配送模式被代替是不可避免的，越库模式作为如今配送模式发展的大方向，已经被越来越多的企业证明了它的有效性，但是由于越库模式在国内的发展较晚，加上越库模式对企业自身的要求过高，所以一直发展不快。物流企业应该提高对越库模式的关注，约翰逊算法作为一个成熟简单的算法，能够有效地解决越库车辆排序的问题，并且符合现阶段大多数企业发展状况，应该大力倡导企业实践，从实践中寻找问题，再做出相应的改善。只有大量企业进行实践，才能发现并解决问题，才能促进物流行业的快速发展。（3）物流企业应对越库车辆排序方法进行创新。越库模式的目标是实现“零库存”，这种模式的实行将为企业节约大量成本，提高作业效率，作为越库模式的第一道关口，车辆排序问题急需解决。但是现阶段集中研究的高级算法的约束条件太多，在实际应用中会受限，再者由于算法本身的局限性，经常只能得到局部最优解，这些都为解决问题带来了阻碍。对于解决车辆排序问题，运用约翰逊算法的使用要求较低，使用方法也较简单，对于一些一线工作的员工很容易上手，再者其在流水作业领域的广泛运用已经使其发展得很成熟，不存在早熟或是局部最优的问题，对于现阶段中国企业是适合的。同时，学者们还应当时刻关注企业实践中存在的问题、物流配送未来的发展方向，针对这些问题，积极探索更多操作性强的方法，促进排序方法的创新。

4 结论

本文探讨了越库模式和越库车辆排序问题的发展现状，发现并分析了其中存在的一些问题及其产生的原因，对于每个问题都针对性的给出了建议。为了实现总的作业时间最短，提出了使用约翰逊算法解决越库车辆排序的问题，同时还能得到对应的入库顺序。相较于高级算法，约翰逊算法更具有实践性，操作性更强，更符合大多数中国企业的现状，对企业实践操作具有一定的指导意义。

[1] 毛道晓，徐克林，张志英,等.越库中心选址模型与启发式算法[J].中南大学学报，2013(44):564-570.

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

[3] 李敬峰.面向货物装卸需求的越库仓门分配和车辆调度问题研究[D].广州：广东工业大学（硕士学位论文），2016.

[4] 高晶，高举红.服务连锁零售企业的配送中心内越库车辆调度研究[J].技术与方法，2012(2):113-115.

[5] 马东彦，陈峰.以总加权完工时间为目标的两台机越库排序的动态规划算法[J].上海交通大学学报，2007(5):852-856.

[6] 蒋鹏，佘艳.基于遗传算法的接驳转运车辆排程的分析研究[J].信息与电脑，2011(6):168-170.

[7] 黄尚.遗传算法在物流配送中的研究与应用[D].广州：广东工业大学（硕士学位论文），2013.

[8] 赵辉，张红云.约翰逊—贝尔曼法则在流水作业中的应用[J].河南城建高等专科学校学报，2001(10):62-63.

[9] 陈杰，陈峰.非对称不确定性越库调度算法[J].上海交通大学学报，2010,44(9):1302-1306.

[10] 王刚.基于排队和排序理论的两阶段越库作业调度算法研究[D].北京：北京交通大学（硕士学位论文），2008.

[11] 宋凯雷.越库物流的两阶段混合调度模型及优化算法[D].上海：上海交通大学（硕士学位论文），2008.