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

文/梁霏霏 孫佳英

關(guān)鍵字：包車模式、路徑規(guī)劃、多約束

一、業(yè)務(wù)場(chǎng)景概述

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

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

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

二、基礎(chǔ)公式及限制條件表述

針對(duì)以上業(yè)務(wù)場(chǎng)景，先闡述幾個(gè)公式含義：

車輛輪次=貨量/裝載率

（備注：車輛輪次，即為了運(yùn)輸一家供應(yīng)商的所有零件，需要車輛來回往返運(yùn)輸?shù)拇螖?shù)。

貨量，即為供應(yīng)商當(dāng)日的供貨量。

裝載率，即為車輛內(nèi)實(shí)際裝載的零件包裝體積之和與車輛內(nèi)體積的比值）

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

貨量=供應(yīng)商處當(dāng)日的需求供貨零件包裝數(shù)/車廂內(nèi)可裝載的包裝箱數(shù)

計(jì)算過程中，部分包裝器具需要使用托盤打包，先計(jì)算打包后的包裝數(shù)量是多少（非托盤情況同此類似，只是托盤內(nèi)包裝箱裝數(shù)為1，且托盤體積=包裝箱體積）。

A=ROUNDDOWN(車廂內(nèi)的內(nèi)長(zhǎng)/托盤的長(zhǎng))×(車廂的寬/托盤的寬)

B=ROUNDDOWN(車廂內(nèi)的內(nèi)長(zhǎng)/托盤的寬)×(車廂的寬/托盤的長(zhǎng))

車廂內(nèi)可裝載的托盤數(shù)量C=ROUNDDOWN［MAX(A,B)×車廂內(nèi)高/托盤高,0］

車廂內(nèi)可裝載的包裝箱數(shù)D=車廂內(nèi)可裝載的托盤數(shù)量×單托盤的包裝箱數(shù)

供應(yīng)商當(dāng)日的需求供貨零件包裝數(shù)E=ROUNDUP(零件需求數(shù)量/單包裝數(shù)量,0)

貨量=E/D

（備注：對(duì)于D數(shù)據(jù)，還需特別關(guān)注業(yè)務(wù)場(chǎng)景中的限制條件，因現(xiàn)場(chǎng)使用的車輛體積不定，有8M、9.6M、12M等多種型號(hào)，在卸貨口對(duì)車輛無限制的情況下，有可能存在多種車型均可使用的情況，故D在計(jì)算時(shí)，需要計(jì)算各種車型車廂內(nèi)可裝載的包裝箱數(shù)）

裝載率要求：各個(gè)工廠有自己的裝載率指標(biāo)，本文中的裝載率做了兩個(gè)假設(shè)：同一家供應(yīng)商若所有發(fā)貨物料均為同一尺寸包裝箱型，則裝載率為100%；若不是同一尺寸箱型或雖然單一供應(yīng)商為同一尺寸，但貨量較小，需要和其他供應(yīng)商拼車才能發(fā)貨，則此時(shí)的裝載率定義為85%。

貨量的計(jì)算方式說明之后，接下來說明供應(yīng)商的分類：

限制條件一：對(duì)卸貨口的要求。不同供應(yīng)商的卸貨口是不同的，要求同一卸貨口的供應(yīng)商才可以組合使用一輛車，同一輛車不能配送超過一個(gè)卸貨口的物料。匹配每家供應(yīng)商的卸貨口并將同一卸貨口的供應(yīng)商排在一起。

限制條件二：車輛限制。上文中我們提到過在卸貨口對(duì)車輛無限制時(shí)，有可能存在多種車型均可在使用的情況，需要將車輛信息匹配到對(duì)應(yīng)的供應(yīng)商，并對(duì)每家供應(yīng)商每種車型可裝載的貨量進(jìn)行匹配。

限制條件三：供應(yīng)商區(qū)域限制。在對(duì)多家供應(yīng)商進(jìn)行組合取貨時(shí)，優(yōu)先組合分布在同一區(qū)域的供應(yīng)商，當(dāng)同一區(qū)域的供應(yīng)商無法組合時(shí)，再將沿途供應(yīng)商進(jìn)行組合?；诖?，需要給每家供應(yīng)商劃定一個(gè)地域優(yōu)先級(jí)，按優(yōu)先級(jí)進(jìn)行組合確認(rèn)。

邏輯條件分析：對(duì)一家供應(yīng)商來說，其單輪循環(huán)時(shí)間越少，則取貨頻次越多，在同等裝載率下，取貨量越多，所以在進(jìn)行供應(yīng)商組合時(shí)，從少到多組合，即最高優(yōu)先級(jí)是只取一家供應(yīng)商的物料，直接送到主機(jī)廠，即點(diǎn)對(duì)點(diǎn)模式；對(duì)于貨量不足以滿足點(diǎn)對(duì)點(diǎn)的方式，接進(jìn)行兩家、三家供應(yīng)商等逐次累加方式組合，這種方式稱作“milk-run循環(huán)取貨方式”。

圖1：點(diǎn)對(duì)點(diǎn)模式邏輯運(yùn)算圖

三、點(diǎn)對(duì)點(diǎn)模式

下面開始進(jìn)行邏輯運(yùn)算，圖1為邏輯運(yùn)算圖。

確認(rèn)一個(gè)貨量參數(shù)V，貨量小于V的供應(yīng)商單獨(dú)列出，不參與第一輪運(yùn)算。（設(shè)置此參數(shù)的目的是提高運(yùn)作效率，對(duì)于貨量較小的供應(yīng)商，其貨量滿足不了點(diǎn)對(duì)點(diǎn)的方式，沒有必要再進(jìn)行點(diǎn)對(duì)點(diǎn)運(yùn)算）

將參與第一輪運(yùn)算的供應(yīng)商清單列出，開始進(jìn)行運(yùn)算：

輪次=r o u n d u p(貨量/裝載率)=roundup（貨量/0.85）；

車輛單輪工作時(shí)間=2×（供應(yīng)商到主機(jī)車的距離/車速）+供應(yīng)行處裝卸時(shí)間+主機(jī)廠裝卸時(shí)間

車輛數(shù)=輪次×車輛單輪工作時(shí)間/工廠工作時(shí)間

將車輛數(shù)限定一個(gè)范圍U，在此范圍內(nèi)的車輛數(shù)可直接向上或向下取整，作為最終結(jié)果，不在此范圍內(nèi)的供應(yīng)商，其裝載率固定的情況下，車輛使用率低，不推薦點(diǎn)對(duì)點(diǎn)模式。

關(guān)于U的范圍舉例如下：

U=Roundup(車輛數(shù)，0)-車輛數(shù)，若0<=U<=0.15,則最終計(jì)算車輛=roundup(車輛數(shù)，0).如計(jì)算結(jié)果為1.87輛車，實(shí)際最終給出的車輛數(shù)為2輛。

U=Rounddown(車輛數(shù)，0)-車輛數(shù)，若-0.05<=U<=0,則最終計(jì)算車輛=rounddown(車輛數(shù)，0).如計(jì)算結(jié)果為2.03輛車，實(shí)際最終給出的車輛數(shù)為2輛。

對(duì)于以上內(nèi)容，也可進(jìn)行反向推算：我們剛剛計(jì)算的車輛數(shù)是按85%的裝載率計(jì)算的，實(shí)際也可根據(jù)估算的車輛數(shù)反向推算裝載率，確認(rèn)裝載率可否在接受范圍內(nèi)。如按裝載率85%計(jì)算車輛數(shù)為2.3，不適用以上U的范圍，則輸入車輛數(shù)2.3，按如下公式反向推算裝載率：

裝載率=貨量/（車輛數(shù)×工廠工作時(shí)間/車輛單輪工作時(shí)間），確認(rèn)這個(gè)裝載率可否在接受范圍內(nèi)。

滿足規(guī)劃條件的供應(yīng)商，最終確認(rèn)其輪次、車輛數(shù)，生成路線報(bào)告，明確好窗口間隔。

窗口間隔=工作時(shí)間/輪次（此窗口間隔為到貨時(shí)間）

對(duì)于無法滿足規(guī)劃條件的供應(yīng)商，則進(jìn)入第二輪運(yùn)算清單，即兩家供應(yīng)商組合進(jìn)行Milk-run循環(huán)取貨。

圖2：兩家供應(yīng)商循環(huán)取貨模式邏輯運(yùn)算圖

圖3：多家供應(yīng)商循環(huán)取貨模式邏輯運(yùn)算圖

四、兩家供應(yīng)商循環(huán)取貨模式

我們?cè)谇懊娴募僭O(shè)條件中提到一個(gè)限制條件，對(duì)于兩班生產(chǎn)的情況，要求每個(gè)班次同一家供應(yīng)商的物料至少要送一輪，考慮其雙班要求的特殊性，我們主要探討雙班的情況。相關(guān)的邏輯運(yùn)算圖如圖2。圖2中包含了雙班和單班的情況，我們解釋時(shí)以復(fù)雜的雙班為例。

針對(duì)判斷為雙班生產(chǎn)的情況，兩家供應(yīng)商按地域優(yōu)先級(jí)將貨量?jī)蓛山M合，組合后的輪次=貨量/85%要大于等于2，直到所有進(jìn)入第二輪運(yùn)算清單的供應(yīng)商均按以上條件完成組合（特別關(guān)注：在組合時(shí)，相同車型的供應(yīng)商貨量才可組合）。將輪次向上取整后減掉輪次數(shù)據(jù)，查看數(shù)值是否在0到某個(gè)可接受的數(shù)之間，若在此范圍之間，則留下改組合，若不在此范圍之間，則釋放此組合。

舉例：若組合后的輪次=1.92輪，roundup(1.92,0)-1.92=0.08,確認(rèn)此數(shù)值在0到0.2之間，則該組合成立，留下。

以上確認(rèn)的接受范圍主要是希望組合的供應(yīng)商貨量盡量接近85%（裝載率）的倍數(shù)，越接近，越適合組合。

對(duì)組合后的供應(yīng)商分別計(jì)算他們的輪次，如A供應(yīng)商輪次=A貨量/85%；B供應(yīng)商輪次=B貨量/85%。分別確認(rèn)A、B供應(yīng)商的輪次是否在某個(gè)可接受的范圍內(nèi)，如roundup(A輪次，0)-A是否在0～0.1之間，或A-rounddown(A輪次，0)是否在0～0.1之間，B操作和A操作相同。

將取整的A和B進(jìn)行比對(duì)，判斷A輪次是否等于B輪次且兩者均不為數(shù)字1(注意我們討論的是雙班模式，雙班要求每家供應(yīng)商在每個(gè)班次至少出現(xiàn)1次)，若符合此條件，則供應(yīng)商的交貨方式為方式1：A,B,A,B…… 這代表第一輪取貨A供應(yīng)商處物料，第二輪取貨B供應(yīng)商處物料，第三次再次取貨A供應(yīng)商處物料，依次類推。

若不符合以上條件，則供應(yīng)商的交貨方式為方式2：AB,AB,AB……,這代表每輪取貨時(shí)A和B供應(yīng)商處均會(huì)去。

交貨方式排列后，開始計(jì)算車輛數(shù)，車輛數(shù)=輪次×單輪循環(huán)時(shí)間/工作時(shí)間，方式1的車輛數(shù)=（A供應(yīng)商的總輪次×（2×(A供應(yīng)商到主機(jī)廠的距離/車速)+A供應(yīng)商處的裝卸時(shí)間+主機(jī)廠的裝卸時(shí)間）+B供應(yīng)商的總輪次×（2×(B供應(yīng)商到主機(jī)廠的距離/車速)+B供應(yīng)商處的裝卸時(shí)間+主機(jī)廠的裝卸時(shí)間））/工作時(shí)間；方式2的車輛數(shù)=總輪次×（主機(jī)廠到A供應(yīng)商的距離/車速+A供應(yīng)商到B供應(yīng)商的距離/車速+B供應(yīng)商到主機(jī)廠的距離/車速+A&B&主機(jī)廠的裝卸時(shí)間）/工作時(shí)間。

將車輛數(shù)限定一個(gè)范圍U，在此范圍內(nèi)的車輛數(shù)可直接向上或向下取整，作為最終結(jié)果，不在此范圍內(nèi)的供應(yīng)商，其裝載率固定的情況下，車輛使用率低，不推薦兩家供應(yīng)商組合模式。

符合以上條件的供應(yīng)商各種組合車輛數(shù)取最小，生成路線報(bào)告，明確好窗口間隔。

窗口間隔=工作時(shí)間/輪次（此窗口間隔為到貨時(shí)間）

不符合以上條件的供應(yīng)商清單釋放，進(jìn)入多家供應(yīng)商組合模式。

五、多家供應(yīng)商循環(huán)取貨模式

對(duì)于多家供應(yīng)商的組合模式，我們依然以雙班為例進(jìn)行討論。供應(yīng)商組合數(shù)從3家開始，找不到最優(yōu)解時(shí)再遞增為4、5……直至所有供應(yīng)商組合完畢。相關(guān)的邏輯運(yùn)算圖如圖3，其中包含了雙班和單班的情況，我們解釋時(shí)以復(fù)雜的雙班為例。

確認(rèn)供應(yīng)商組合后的交貨輪次M=（組合后的貨量/裝載率）=roundup(組合后的貨量/0.85，0)，確認(rèn)此輪次必須大于等于2(我們的舉例是針對(duì)雙班運(yùn)作，每班至少有一個(gè)輪次，所以要求大于等于2)。

將供應(yīng)商按位置優(yōu)先級(jí)要求的組合數(shù)進(jìn)行組合，所有存在關(guān)聯(lián)關(guān)系的供應(yīng)商全部進(jìn)行組合。因雙班要求每家供應(yīng)商每個(gè)班次均要有交貨，所以每家供應(yīng)商的交貨輪次必須大于等于2,將除以2的每家供應(yīng)商的貨量按要求的組合供應(yīng)商數(shù)進(jìn)行組合，確保每個(gè)組合的貨量在82%～85%之間（給一個(gè)可接接受的裝載率，限定此范圍，確保貨量組合盡量落在此范圍內(nèi)，從而保證湊足一輛車），將這些組合輪次相加，總輪次=M，同時(shí)每個(gè)組合中每家供應(yīng)商每（M/2）中至少出現(xiàn)一次，并且供應(yīng)商第P輪時(shí)間-開班時(shí)間+結(jié)束時(shí)間-第Q輪時(shí)間=第P+1輪時(shí)間-第P輪時(shí)間=第P+2時(shí)間-第P+1輪時(shí)間，直到P+i=Q（Q>=2,P>=1）。

P為每條路線的第二輪，Q為每條路線的倒數(shù)第二輪。以上公式主要是保證各輪次之間的時(shí)間均衡性。

確認(rèn)符合以上條件的組合是否可以完成，若可以完成，則直接進(jìn)行單輪循環(huán)車間和車輛數(shù)的計(jì)算，若不能完成，則需要進(jìn)行接下來的多輪循環(huán)組合。

貨量最大的供應(yīng)商A/R(3<=R<=總輪次)，其他供應(yīng)商貨量/S(2<=S<=總輪次)，自由組合貨量，確保其每個(gè)組合的貨量在82%～85%之間，且組合的總輪數(shù)=M，同時(shí)每個(gè)組合中供應(yīng)商每（M/2輪）中至少出現(xiàn)一次， 且供應(yīng)商第P輪時(shí)間-開班時(shí)間+結(jié)束時(shí)間-第Q輪時(shí)間=第P+1輪時(shí)間-第P輪時(shí)間=第P+2時(shí)間-第P+1輪時(shí)間，直到P+i=Q（Q>=2,P>=1）。以上內(nèi)容主要是對(duì)供應(yīng)商的貨量進(jìn)行多輪拆分，從要求此供應(yīng)商至少每個(gè)工作日交2次貨依次更改，直到供應(yīng)商的貨量拆分到所有輪次。

確認(rèn)每次拆分后是否可以組合成滿足條件的供應(yīng)商組合，若可以完成，則直接進(jìn)行單輪循環(huán)車間和車輛數(shù)的計(jì)算，若不能完成，則進(jìn)入無法組合供應(yīng)商清單，隨后續(xù)進(jìn)行當(dāng)前供應(yīng)商數(shù)+1的供應(yīng)商數(shù)量組合再次循環(huán)運(yùn)算，直至所有供應(yīng)商循環(huán)組合完成。

計(jì)算組合完成的單輪循環(huán)時(shí)間：計(jì)算組合完成的單輪循環(huán)時(shí)間=DY到組合1供應(yīng)商的距離/車速+各組合間的距離/車速+最后一個(gè)組合到DY的距離+DY裝卸時(shí)間+各組合的裝卸時(shí)間，各循環(huán)時(shí)間相加。

計(jì)算車輛數(shù)=輪次×單輪循環(huán)時(shí)間/工作時(shí)間，將車輛數(shù)限定一個(gè)范圍U，在此范圍內(nèi)的車輛數(shù)可直接向上或向下取整，作為最終結(jié)果，不在此范圍內(nèi)的供應(yīng)商，其裝載率固定的情況下，車輛使用率低，不推薦此數(shù)目的供應(yīng)商組合模式。

符合以上條件的供應(yīng)商各種組合車輛數(shù)取最小，生成路線，不符合以上條件的供應(yīng)商清單釋放，進(jìn)入此數(shù)目供應(yīng)商+1組合模式。

對(duì)于最終也無法組合的供應(yīng)商，生成尾線，由規(guī)劃人員手工調(diào)整。

六、結(jié)論

截止以上運(yùn)算結(jié)束，包車模式中的多約束條件路徑規(guī)劃工作已完成。此規(guī)劃運(yùn)算方式在一定程度上解決了包車模式復(fù)雜的規(guī)劃邏輯手工運(yùn)算，可使用計(jì)算機(jī)程序代替人工完成，實(shí)現(xiàn)了工作效率的提升。