包車模式中多約束條件下的路徑規劃

文/梁霏霏 孫佳英

關鍵字：包車模式、路徑規劃、多約束

一、業務場景概述

我們常見的路徑規劃，都是在滿足裝載率的前提下，實現路徑最短，針對此種情況，行業內有多種算法支持。本文討論的內容與此不同，運輸是包車模式，即在一個固定時間內，車輛已被承包，不管車輛跑了多少距離，拉了多少貨，均是按工作時間付費。這就增加了很多約束條件，如取貨時間、到貨時間、卸貨口等限制，目標反而比較單一，即車輛數最少，接下來我們根據實際的業務場景分析此種路徑規劃形式。

業務場景：工廠需要根據預計的生產計劃和工廠內的卸貨口要求，按車輛裝載率限制，提前安排好各家供應商的取貨時間和到貨時間，同時要求到貨時間各段之間必須是均衡的，對于雙班生產，必須保證白班和中班至少各有一個窗口，允許到供應商處循環取貨，最終計算出所需車輛數，并將整條路線全天的取送貨時間相加，保證在工作時間內，所有組合完成后，一條路線取車輛的最小組合。

在包車模式下，因增加了很多約束條件，目標反而比較單一，即車輛數最少

二、基礎公式及限制條件表述

針對以上業務場景，先闡述幾個公式含義：

車輛輪次=貨量/裝載率

（備注：車輛輪次，即為了運輸一家供應商的所有零件，需要車輛來回往返運輸的次數。

貨量，即為供應商當日的供貨量。

裝載率，即為車輛內實際裝載的零件包裝體積之和與車輛內體積的比值）

為了計算方便，我們對貨量進行處理，在此使用的車輛內可放置的包裝數量是考慮了固定裝載的模式，即要將包裝箱擺放在貨車車廂內，確認車間實際可以放置多少個箱子，這里面考慮了包裝器具的外形，考慮了車內未被完全利用的空間。

貨量=供應商處當日的需求供貨零件包裝數/車廂內可裝載的包裝箱數

計算過程中，部分包裝器具需要使用托盤打包，先計算打包后的包裝數量是多少（非托盤情況同此類似，只是托盤內包裝箱裝數為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組合模式。

對于最終也無法組合的供應商，生成尾線，由規劃人員手工調整。

六、結論

截止以上運算結束，包車模式中的多約束條件路徑規劃工作已完成。此規劃運算方式在一定程度上解決了包車模式復雜的規劃邏輯手工運算，可使用計算機程序代替人工完成，實現了工作效率的提升。