包车模式中多约束条件下的路径规划

文/梁霏霏 孙佳英

关键字：包车模式、路径规划、多约束

一、业务场景概述

我们常见的路径规划，都是在满足装载率的前提下，实现路径最短，针对此种情况，行业内有多种算法支持。本文讨论的内容与此不同，运输是包车模式，即在一个固定时间内，车辆已被承包，不管车辆跑了多少距离，拉了多少货，均是按工作时间付费。这就增加了很多约束条件，如取货时间、到货时间、卸货口等限制，目标反而比较单一，即车辆数最少，接下来我们根据实际的业务场景分析此种路径规划形式。

业务场景：工厂需要根据预计的生产计划和工厂内的卸货口要求，按车辆装载率限制，提前安排好各家供应商的取货时间和到货时间，同时要求到货时间各段之间必须是均衡的，对于双班生产，必须保证白班和中班至少各有一个窗口，允许到供应商处循环取货，最终计算出所需车辆数，并将整条路线全天的取送货时间相加，保证在工作时间内，所有组合完成后，一条路线取车辆的最小组合。

在包车模式下，因增加了很多约束条件，目标反而比较单一，即车辆数最少

二、基础公式及限制条件表述

针对以上业务场景，先阐述几个公式含义：

车辆轮次=货量/装载率

（备注：车辆轮次，即为了运输一家供应商的所有零件，需要车辆来回往返运输的次数。

货量，即为供应商当日的供货量。

装载率，即为车辆内实际装载的零件包装体积之和与车辆内体积的比值）

为了计算方便，我们对货量进行处理，在此使用的车辆内可放置的包装数量是考虑了固定装载的模式，即要将包装箱摆放在货车车厢内，确认车间实际可以放置多少个箱子，这里面考虑了包装器具的外形，考虑了车内未被完全利用的空间。

货量=供应商处当日的需求供货零件包装数/车厢内可装载的包装箱数

计算过程中，部分包装器具需要使用托盘打包，先计算打包后的包装数量是多少（非托盘情况同此类似，只是托盘内包装箱装数为1，且托盘体积=包装箱体积）。

A=ROUNDDOWN(车厢内的内长/托盘的长)×(车厢的宽/托盘的宽)

B=ROUNDDOWN(车厢内的内长/托盘的宽)×(车厢的宽/托盘的长)

车厢内可装载的托盘数量C=ROUNDDOWN［MAX(A,B)×车厢内高/托盘高,0］

车厢内可装载的包装箱数D=车厢内可装载的托盘数量×单托盘的包装箱数

供应商当日的需求供货零件包装数E=ROUNDUP(零件需求数量/单包装数量,0)

货量=E/D

（备注：对于D数据，还需特别关注业务场景中的限制条件，因现场使用的车辆体积不定，有8M、9.6M、12M等多种型号，在卸货口对车辆无限制的情况下，有可能存在多种车型均可使用的情况，故D在计算时，需要计算各种车型车厢内可装载的包装箱数）

装载率要求：各个工厂有自己的装载率指标，本文中的装载率做了两个假设：同一家供应商若所有发货物料均为同一尺寸包装箱型，则装载率为100%；若不是同一尺寸箱型或虽然单一供应商为同一尺寸，但货量较小，需要和其他供应商拼车才能发货，则此时的装载率定义为85%。

货量的计算方式说明之后，接下来说明供应商的分类：

限制条件一：对卸货口的要求。不同供应商的卸货口是不同的，要求同一卸货口的供应商才可以组合使用一辆车，同一辆车不能配送超过一个卸货口的物料。匹配每家供应商的卸货口并将同一卸货口的供应商排在一起。

限制条件二：车辆限制。上文中我们提到过在卸货口对车辆无限制时，有可能存在多种车型均可在使用的情况，需要将车辆信息匹配到对应的供应商，并对每家供应商每种车型可装载的货量进行匹配。

限制条件三：供应商区域限制。在对多家供应商进行组合取货时，优先组合分布在同一区域的供应商，当同一区域的供应商无法组合时，再将沿途供应商进行组合。基于此，需要给每家供应商划定一个地域优先级，按优先级进行组合确认。

逻辑条件分析：对一家供应商来说，其单轮循环时间越少，则取货频次越多，在同等装载率下，取货量越多，所以在进行供应商组合时，从少到多组合，即最高优先级是只取一家供应商的物料，直接送到主机厂，即点对点模式；对于货量不足以满足点对点的方式，接进行两家、三家供应商等逐次累加方式组合，这种方式称作“milk-run循环取货方式”。

图1：点对点模式逻辑运算图

三、点对点模式

下面开始进行逻辑运算，图1为逻辑运算图。

确认一个货量参数V，货量小于V的供应商单独列出，不参与第一轮运算。（设置此参数的目的是提高运作效率，对于货量较小的供应商，其货量满足不了点对点的方式，没有必要再进行点对点运算）

将参与第一轮运算的供应商清单列出，开始进行运算：

轮次=r o u n d u p(货量/装载率)=roundup（货量/0.85）；

车辆单轮工作时间=2×（供应商到主机车的距离/车速）+供应行处装卸时间+主机厂装卸时间

车辆数=轮次×车辆单轮工作时间/工厂工作时间

将车辆数限定一个范围U，在此范围内的车辆数可直接向上或向下取整，作为最终结果，不在此范围内的供应商，其装载率固定的情况下，车辆使用率低，不推荐点对点模式。

关于U的范围举例如下：

U=Roundup(车辆数，0)-车辆数，若0<=U<=0.15,则最终计算车辆=roundup(车辆数，0).如计算结果为1.87辆车，实际最终给出的车辆数为2辆。

U=Rounddown(车辆数，0)-车辆数，若-0.05<=U<=0,则最终计算车辆=rounddown(车辆数，0).如计算结果为2.03辆车，实际最终给出的车辆数为2辆。

对于以上内容，也可进行反向推算：我们刚刚计算的车辆数是按85%的装载率计算的，实际也可根据估算的车辆数反向推算装载率，确认装载率可否在接受范围内。如按装载率85%计算车辆数为2.3，不适用以上U的范围，则输入车辆数2.3，按如下公式反向推算装载率：

装载率=货量/（车辆数×工厂工作时间/车辆单轮工作时间），确认这个装载率可否在接受范围内。

满足规划条件的供应商，最终确认其轮次、车辆数，生成路线报告，明确好窗口间隔。

窗口间隔=工作时间/轮次（此窗口间隔为到货时间）

对于无法满足规划条件的供应商，则进入第二轮运算清单，即两家供应商组合进行Milk-run循环取货。

图2：两家供应商循环取货模式逻辑运算图

图3：多家供应商循环取货模式逻辑运算图

四、两家供应商循环取货模式

我们在前面的假设条件中提到一个限制条件，对于两班生产的情况，要求每个班次同一家供应商的物料至少要送一轮，考虑其双班要求的特殊性，我们主要探讨双班的情况。相关的逻辑运算图如图2。图2中包含了双班和单班的情况，我们解释时以复杂的双班为例。

针对判断为双班生产的情况，两家供应商按地域优先级将货量两两组合，组合后的轮次=货量/85%要大于等于2，直到所有进入第二轮运算清单的供应商均按以上条件完成组合（特别关注：在组合时，相同车型的供应商货量才可组合）。将轮次向上取整后减掉轮次数据，查看数值是否在0到某个可接受的数之间，若在此范围之间，则留下改组合，若不在此范围之间，则释放此组合。

举例：若组合后的轮次=1.92轮，roundup(1.92,0)-1.92=0.08,确认此数值在0到0.2之间，则该组合成立，留下。

以上确认的接受范围主要是希望组合的供应商货量尽量接近85%（装载率）的倍数，越接近，越适合组合。

对组合后的供应商分别计算他们的轮次，如A供应商轮次=A货量/85%；B供应商轮次=B货量/85%。分别确认A、B供应商的轮次是否在某个可接受的范围内，如roundup(A轮次，0)-A是否在0～0.1之间，或A-rounddown(A轮次，0)是否在0～0.1之间，B操作和A操作相同。

将取整的A和B进行比对，判断A轮次是否等于B轮次且两者均不为数字1(注意我们讨论的是双班模式，双班要求每家供应商在每个班次至少出现1次)，若符合此条件，则供应商的交货方式为方式1：A,B,A,B…… 这代表第一轮取货A供应商处物料，第二轮取货B供应商处物料，第三次再次取货A供应商处物料，依次类推。

若不符合以上条件，则供应商的交货方式为方式2：AB,AB,AB……,这代表每轮取货时A和B供应商处均会去。

交货方式排列后，开始计算车辆数，车辆数=轮次×单轮循环时间/工作时间，方式1的车辆数=（A供应商的总轮次×（2×(A供应商到主机厂的距离/车速)+A供应商处的装卸时间+主机厂的装卸时间）+B供应商的总轮次×（2×(B供应商到主机厂的距离/车速)+B供应商处的装卸时间+主机厂的装卸时间））/工作时间；方式2的车辆数=总轮次×（主机厂到A供应商的距离/车速+A供应商到B供应商的距离/车速+B供应商到主机厂的距离/车速+A&B&主机厂的装卸时间）/工作时间。

将车辆数限定一个范围U，在此范围内的车辆数可直接向上或向下取整，作为最终结果，不在此范围内的供应商，其装载率固定的情况下，车辆使用率低，不推荐两家供应商组合模式。

符合以上条件的供应商各种组合车辆数取最小，生成路线报告，明确好窗口间隔。

窗口间隔=工作时间/轮次（此窗口间隔为到货时间）

不符合以上条件的供应商清单释放，进入多家供应商组合模式。

五、多家供应商循环取货模式

对于多家供应商的组合模式，我们依然以双班为例进行讨论。供应商组合数从3家开始，找不到最优解时再递增为4、5……直至所有供应商组合完毕。相关的逻辑运算图如图3，其中包含了双班和单班的情况，我们解释时以复杂的双班为例。

确认供应商组合后的交货轮次M=（组合后的货量/装载率）=roundup(组合后的货量/0.85，0)，确认此轮次必须大于等于2(我们的举例是针对双班运作，每班至少有一个轮次，所以要求大于等于2)。

将供应商按位置优先级要求的组合数进行组合，所有存在关联关系的供应商全部进行组合。因双班要求每家供应商每个班次均要有交货，所以每家供应商的交货轮次必须大于等于2,将除以2的每家供应商的货量按要求的组合供应商数进行组合，确保每个组合的货量在82%～85%之间（给一个可接接受的装载率，限定此范围，确保货量组合尽量落在此范围内，从而保证凑足一辆车），将这些组合轮次相加，总轮次=M，同时每个组合中每家供应商每（M/2）中至少出现一次，并且供应商第P轮时间-开班时间+结束时间-第Q轮时间=第P+1轮时间-第P轮时间=第P+2时间-第P+1轮时间，直到P+i=Q（Q>=2,P>=1）。

P为每条路线的第二轮，Q为每条路线的倒数第二轮。以上公式主要是保证各轮次之间的时间均衡性。

确认符合以上条件的组合是否可以完成，若可以完成，则直接进行单轮循环车间和车辆数的计算，若不能完成，则需要进行接下来的多轮循环组合。

货量最大的供应商A/R(3<=R<=总轮次)，其他供应商货量/S(2<=S<=总轮次)，自由组合货量，确保其每个组合的货量在82%～85%之间，且组合的总轮数=M，同时每个组合中供应商每（M/2轮）中至少出现一次， 且供应商第P轮时间-开班时间+结束时间-第Q轮时间=第P+1轮时间-第P轮时间=第P+2时间-第P+1轮时间，直到P+i=Q（Q>=2,P>=1）。以上内容主要是对供应商的货量进行多轮拆分，从要求此供应商至少每个工作日交2次货依次更改，直到供应商的货量拆分到所有轮次。

确认每次拆分后是否可以组合成满足条件的供应商组合，若可以完成，则直接进行单轮循环车间和车辆数的计算，若不能完成，则进入无法组合供应商清单，随后续进行当前供应商数+1的供应商数量组合再次循环运算，直至所有供应商循环组合完成。

计算组合完成的单轮循环时间：计算组合完成的单轮循环时间=DY到组合1供应商的距离/车速+各组合间的距离/车速+最后一个组合到DY的距离+DY装卸时间+各组合的装卸时间，各循环时间相加。

计算车辆数=轮次×单轮循环时间/工作时间，将车辆数限定一个范围U，在此范围内的车辆数可直接向上或向下取整，作为最终结果，不在此范围内的供应商，其装载率固定的情况下，车辆使用率低，不推荐此数目的供应商组合模式。

符合以上条件的供应商各种组合车辆数取最小，生成路线，不符合以上条件的供应商清单释放，进入此数目供应商+1组合模式。

对于最终也无法组合的供应商，生成尾线，由规划人员手工调整。

六、结论

截止以上运算结束，包车模式中的多约束条件路径规划工作已完成。此规划运算方式在一定程度上解决了包车模式复杂的规划逻辑手工运算，可使用计算机程序代替人工完成，实现了工作效率的提升。