基于啟發(fā)式規(guī)則的物流配送車輛排班優(yōu)化

李栓子 施國洪

摘要：針對 A 物流公司不同車型的物流車輛配送路徑復(fù)雜，且每輛車每天可以執(zhí)行多條線路任務(wù)的特點，設(shè)計了兩種啟發(fā)式規(guī)則求解物流車輛排班任務(wù)。首先，對該物流公司存在的問題進(jìn)行了分析;其次，根據(jù)約束條件建立了目標(biāo)函數(shù)為總行駛路程的數(shù)學(xué)模型，設(shè)計了啟發(fā)式規(guī)則1用于進(jìn)行任務(wù)的安排，并使用 A 公司的物流數(shù)據(jù)Part1作為算例進(jìn)行數(shù)據(jù)仿真，通過對仿真結(jié)果的分析，在啟發(fā)式規(guī)則1的基礎(chǔ)上進(jìn)行改進(jìn)設(shè)計了啟發(fā)式規(guī)則2;最后，將兩種啟發(fā)式規(guī)則的仿真結(jié)果進(jìn)行對比，發(fā)現(xiàn)啟發(fā)式規(guī)則2的性能更佳也更穩(wěn)定，該結(jié)論進(jìn)一步驗證了啟發(fā)式規(guī)則解決物流配送車輛排班任務(wù)的有效性和可行性。

關(guān)鍵詞：啟發(fā)式規(guī)則;車輛排班;物流配送;路徑規(guī)劃

一、引言

隨著互聯(lián)網(wǎng)和大數(shù)據(jù)等信息化技術(shù)的發(fā)展，企業(yè)間的競爭日益激烈。最初，企業(yè)通過降低產(chǎn)品的成本來提高企業(yè)的經(jīng)濟(jì)效益，但原材料價格和勞動力價格的上漲使得企業(yè)難以在生產(chǎn)上節(jié)省更多成本。如今，企業(yè)紛紛將目光轉(zhuǎn)向自身物流體系的成本，而物流成本中有很大一部分責(zé)任是由運輸承擔(dān)的，因此，運輸?shù)某杀九c效率成為企業(yè)越來越關(guān)注的問題。

早在1959年，Dantzig和Ramser就提出了車輛路線問題（Vehicle Routing Problem），即如何配置車輛類型和數(shù)目，如何為各車輛安排一組最優(yōu)或者是較優(yōu)的路線，使得在滿足所有約束條件的情況下總的代價最小。帶時間窗約束的車輛路徑問題（Vehicle Routing Problem With Time Window Constraints）是車輛路徑問題（VRP）的拓展與延伸，廣泛應(yīng)用于資源配置和物流運輸?shù)确矫?。Aldair Alvarez和Pedro Munari采用了混合算法解決 VRPTW 問題，算法在分支-定價-定界算法中使用兩種元啟發(fā)式算法產(chǎn)生可行解。K.K.H.Ng等提出了一種多聚居地人工蜂群算法來解決速度時變的VRPTW 問題，并驗證了該算法優(yōu)于其它的人工蜂群算法。Duygu Tas 等運用了禁忌搜索算法和自適應(yīng)大規(guī)模鄰域搜索算法求解該問題，并驗證了算法在實際環(huán)境中的有效性。Sophie N.Parragh和Jean-Franois Cordeau分別采用了分支-定價算法和自適應(yīng)大規(guī)模鄰域搜索算法解決帶時間窗的卡車拖車路徑優(yōu)化問題。Sumaiya Iqbal等提出了一種結(jié)合了多步局部搜索和人工蜂群算法的混合算法，不過沒有驗證算法有效性。

目前求解 VRPTW 的算法可以分為精確算法和元啟發(fā)式算法兩類。精確算法（Accurately Arithmetic）在求解規(guī)模較小的路徑優(yōu)化問題時，能夠在可承受的空間與時間消耗下得到精確解。但是配送路徑優(yōu)化問題屬于NP問題，實際求解過程中問題的規(guī)模較大，使用精確算法所消耗的空間和時間成本都比較大。而啟發(fā)式算法（Heuristics）不管是求解小規(guī)模的問題還是大規(guī)模的問題，都能在一定的范圍和較短時間內(nèi)給出最優(yōu)解。因此，目前相關(guān)領(lǐng)域的專家以及研究人員，對于求解算法的主要研究方向是啟發(fā)式算法。

從文獻(xiàn)可知啟發(fā)式算法可以歸為啟發(fā)式規(guī)則和元啟發(fā)式算法兩類，現(xiàn)有的研究大多專注于元啟發(fā)式算法。陳小潘等在校車路徑規(guī)劃中首次設(shè)計了針對校車路徑問題（SDSBRP）的元啟發(fā)式求解算法，該算法首先構(gòu)造初始可行解，然后在模擬退火算法框架下，引入站點需求拆分的鄰域搜索算子進(jìn)行迭代搜索，逐步改善解的質(zhì)量。趙晶等通過應(yīng)用傳統(tǒng)啟發(fā)式規(guī)則的第一和第二規(guī)則并與隨機方法相結(jié)合的方式，解決了卡車裝配線平衡問題。唐勇等提出一種新型遺傳模擬退火算法求解VRPTW問題。張建同等考慮不同時間段車輛行駛速度不同的情況，提出一種變鄰域模擬退火算法求解速度時變的VRPTW問題。但是針對具體物流企業(yè)車輛配送路徑復(fù)雜、排班任務(wù)繁重的問題多數(shù)研究并未涉及。

鑒于此，本文從實際問題出發(fā)，考慮物流公司不同車型的物流車輛配送路徑復(fù)雜且每輛車可以執(zhí)行多條線路任務(wù)的特點，采用兩種啟發(fā)式規(guī)則來解決物流配送車輛排班問題，為企業(yè)優(yōu)化物流配送路徑，節(jié)省企業(yè)物流成本進(jìn)而提升企業(yè)的市場競爭力具有一定的理論和現(xiàn)實意義。

二、問題描述及數(shù)學(xué)模型

（一）問題描述

本文以 A 物流公司為原型，對該公司的物流配送車輛排班任務(wù)進(jìn)行研究，該公司的配送任務(wù)中，有成千上萬條不同車型運行的線路，隨著線路數(shù)量的增加，依賴人工進(jìn)行線路的規(guī)劃已經(jīng)難以滿足整體規(guī)模和復(fù)雜度。因此如何運用新的技術(shù)規(guī)劃路線，使得車輛的利用率得到提升，網(wǎng)絡(luò)運營成本降低是我們需要探索的方向。與VRPTW相比，本次研究的主要區(qū)別在于對于相同的兩個節(jié)點可能存在多次訪問任務(wù)。該物流公司物流配送方面問題可以描述為，給定一系列有效運輸任務(wù)（起止地點、起止時間）的情況下，將運輸任務(wù)組合成車輛行駛的線路，在滿足以下約束的條件下，總的行駛里程最少。其中約束為以下三條：

約束1：線路的起止點必須相同，即車輛必須回到原點;線路可以由有效運輸任務(wù)和空駛?cè)蝿?wù)構(gòu)成，線路中的每段任務(wù)必須首尾相接，即前一段任務(wù)的結(jié)束點是下一段任務(wù)的起點。

約束2：一條線路認(rèn)為分配給一輛車執(zhí)行，因此在時間上可行，即不能出現(xiàn)時間上的沖突和重疊。

約束3：考慮到司機的行駛和線路的穩(wěn)定性，線路的運行時間不能超過48個小時，線路段數(shù)不能超過4段。

1.對約束1的分析

通過對以上問題描述和約束的理解，可以將該問題歸納為目標(biāo)函數(shù)為總行駛路程最短的VRPTW問題。對于約束1，路線必須首尾相連，但可以出現(xiàn)空駛?cè)蝿?wù)，則可能出現(xiàn)情況3。

情況1：如圖1的a子圖所示，所有的任務(wù)都為有效任務(wù)，且首尾相連。

情況2：如圖1的b子圖所示，該線路沒有符合條件的后續(xù)任務(wù)，存在空駛?cè)蝿?wù)，且空駛?cè)蝿?wù)在中間，C→F為空駛?cè)蝿?wù)。

情況3：如圖1的c子圖所示，該線路沒有符合條件的后續(xù)任務(wù)，且空駛?cè)蝿?wù)在最后，三段任務(wù)完成后，第一段任務(wù)的起點不是第三段任務(wù)的終點，因此第四段任務(wù)為E→A。

2.對約束2的分析

同一條線路中，前一段任務(wù)的結(jié)束時間必須小于等于后一段任務(wù)的開始時間，若在滿足其余約束的情況下，沒有符合條件的后續(xù)任務(wù)，則該條線路結(jié)束。

3.對約束3的分析

第一段任務(wù)的起始時間與最后一段任務(wù)的結(jié)束時間之差必須小于48小時，通過對物流數(shù)據(jù)Part1的分析選取具有代表性的數(shù)據(jù)，如表1所示（本文將全天0～24小時折算為0～1439分，表1中的出發(fā)時間及到達(dá)時間均為相對于0點的分鐘數(shù)），最早的出發(fā)時間為9，而最晚的到達(dá)時間為第二天的159，間隔時間為1590min，即26.5h，因此在求解過程中可以忽略48小時的限制。

本次研究沒有一個對總行駛路程的具體約束，因此在求解過程中沒法判斷所設(shè)計算法的效果，但是通過對Part1數(shù)據(jù)進(jìn)行分析不難發(fā)現(xiàn)，總行駛里程存在一個隱含的上下界限可以驗證算法的效果。

對于上界，在任務(wù)分配時，最差的情況就是每一輛車輛行駛一個任務(wù)，而由于存在車輛必須回到原點的約束，每輛車輛在行駛完任務(wù)后需要空駛回原點，因此總行駛路程的上界為所有任務(wù)距離之和的兩倍。

對于下界，考慮一個理想狀態(tài)，所有的任務(wù)都可以以首尾相連的方式分配給車輛，即不存在空駛?cè)蝿?wù)，因此總行駛路程的下界為所有任務(wù)距離之和。

如圖2所示，假設(shè)存在10個任務(wù)，最佳方案即總行駛路程最短為不存在空駛?cè)蝿?wù)，車輛數(shù)量為3輛，最差方案即總行駛路程最長為一個任務(wù)由一輛車執(zhí)行，車輛數(shù)量為10輛。從圖2中可以看出，最差方案的總行駛路程是最佳方案的兩倍。

通過對Part1的341段任務(wù)的距離計算，可以得到理論最短總行程為22177公里，最長總行程為44354公里。

（二）數(shù)學(xué)模型

問題可描述為：已知一個車輛的集合K，節(jié)點集合N，以及任務(wù)集合G。其中車輛集合V為1，2，…，K;節(jié)點集合N為1，2，…，n;任務(wù)集合G表示為1，2，…，g;對于每一任務(wù)i，任務(wù)的時間約束為[si，ei]，lsi表示任務(wù)i的起始點，lei表示任務(wù)i的終止點，di表示任務(wù)i的行駛里程。車輛必須在早于tsi的時間內(nèi)到達(dá)任務(wù)i的起始點lsi，直至所有的任務(wù)都被訪問，求解滿足約束下的最短車輛行駛路程。

該問題的數(shù)學(xué)模型可以表示為如下：

定義決策變量如下：

Xijk1;若車輛k從任務(wù)i到任務(wù)j0;若車輛k沒有從任務(wù)i到任務(wù)j（8）

Yijk1;若車輛k從空駛?cè)蝿?wù)i到任務(wù)j0;若車輛k沒有從空駛?cè)蝿?wù)i到任務(wù)j（9）

Zijk1;若任務(wù)j為車輛k行駛?cè)蝿?wù)i的后續(xù)任務(wù)0;若任務(wù)j不為車輛k行駛?cè)蝿?wù)i的后續(xù)任務(wù)（10）

其中，式（1）為目標(biāo)函數(shù)，表示總里程，包含有效任務(wù)的總里程和空駛?cè)蝿?wù)的總里程;式（2）為每輛車的線路段數(shù)不能超過4段;式（3）為每輛車的線路運行時間不能超過48小時;式（4）為每條線路的前一段任務(wù)的結(jié)束時間小于等于后一段任務(wù)的開始時間;式（5）為每條線路的前一段任務(wù)的結(jié)束點為后一段任務(wù)的開始點;式（6）為每個有效任務(wù)都要被訪問到;式（7）為每個有效任務(wù)只能被訪問一次;式（8）為0～1變量，若車輛k從任務(wù)i到任務(wù)j，則為1，否則為0;式（9）為0～1變量，若車輛從空駛?cè)蝿?wù)i到任務(wù)j，則為1，否則為0;式（10）為0～1變量，若任務(wù)j為車輛k行駛?cè)蝿?wù)i的后續(xù)任務(wù)，則為1，否則為0。

三、啟發(fā)式規(guī)則1設(shè)計

針對所研究問題的特點，設(shè)計了一種啟發(fā)式規(guī)則進(jìn)行求解。同時采用Matlab 2014a進(jìn)行編程，并在Windows7 Intel（R） Core（TM） i5-3337U，CPU1.8GHz，內(nèi)存4GB，64位操作系統(tǒng)的計算機上運行。算法的參數(shù)設(shè)置為：種群大小50 迭代次數(shù)為200 代。

（一）啟發(fā)式規(guī)則1流程設(shè)計

啟發(fā)式規(guī)則1流程圖見圖3，具體步驟見下列。

Step1：初始化參數(shù)車輛號car=1，已訪問任務(wù)visited =0，任務(wù)總量num。

Step2：選擇第car輛的第一個任務(wù)。從剩余任務(wù)中選取出發(fā)時間最早的任務(wù)為第car輛的第一個任務(wù)，若有多個，則隨機選取，visited = visited + 1;若visited = num，則算法結(jié)束。

Step3：選擇第car輛的后續(xù)任務(wù)。篩選出符合條件的任務(wù)點（篩選規(guī)則見前文），從中任選一個，visited = visited + 1，若visited = num， 則算法結(jié)束，否則轉(zhuǎn)向Step3;若不存在符合條件的任務(wù)，則car = car + 1，并返回Step2。

（二）篩選規(guī)則

車輛在選定第一個任務(wù)后，選擇后續(xù)任務(wù)時，需要根據(jù)約束條件進(jìn)行篩選，篩選規(guī)則如下：

規(guī)則1：若該任務(wù)為第四段任務(wù)，則需要保證第三段任務(wù)的終點為該任務(wù)的起點，該任務(wù)的終點為第一段任務(wù)的起點;該任務(wù)的出發(fā)時間需大于等于第三段任務(wù)的結(jié)束時間;該任務(wù)的結(jié)束時間減去第一段任務(wù)的開始時間需要小于等于48小時。

規(guī)則2：若該任務(wù)為第二/三段任務(wù)，則需要保證前一段任務(wù)的終點為該任務(wù)的起點;該任務(wù)的出發(fā)時間需大于等于前一段任務(wù)的結(jié)束時間;該任務(wù)的結(jié)束時間減去第一段任務(wù)的開始時間需要小于等于48小時。

（三）結(jié)果分析

通過Matlab進(jìn)行代碼實現(xiàn)，算法的參數(shù)設(shè)置為：種群大小為50 迭代次數(shù)為200 代。對數(shù)據(jù)樣例_Part1運行10次，得到如表2所示的總行駛路程和所需車輛數(shù)量。

其中，總行駛路程最短為29124km，車輛的行駛路線見表3，收斂曲線如圖4所示。

四、啟發(fā)式規(guī)則2設(shè)計

通過對啟發(fā)式規(guī)則1的求解結(jié)果進(jìn)行分析，發(fā)現(xiàn)前面的車輛都可以進(jìn)行3～4段有效線路段數(shù)，但到了后期的車輛基本只有1～2段有效線路段數(shù)。那么對于后期的車輛來說，基本都需要在最后行駛一段空駛路程。從目標(biāo)函數(shù)為總行駛路程角度考慮，如果后期的車輛空駛路程都盡可能小，那么就能夠減小最后的總行駛路程。

（一）啟發(fā)式規(guī)則2流程設(shè)計

流程圖如圖5所示，與啟發(fā)式規(guī)則1相比，算法流程大致相同，只是在Step3中選擇車輛的后續(xù)任務(wù)發(fā)生改變，啟發(fā)式規(guī)則1為從符合條件的任務(wù)點中隨機選擇，啟發(fā)式規(guī)則2為通過輪盤賭的形式選擇后續(xù)任務(wù)。其中輪盤賭的概率與任務(wù)的距離成正比，任務(wù)的距離越大，被選中的概率越大。

如圖6所示，為某一車輛的后續(xù)三段任務(wù)的選取，假設(shè)A的后續(xù)任務(wù)點為C、F、E，根據(jù)相應(yīng)的距離A-C：21.978，A-F：55.99，A-E：0.306，被選中的概率分別為0.282、0.715、0.003，其輪盤賭概率區(qū)間分別為[0，0.282]、[0.282，0.997]、[0.997，1]，隨機rand值為0.56，因此，A的后續(xù)任務(wù)點為F。依次類推該車輛最終的后續(xù)路線為A→F→I→F。

（二）結(jié)果分析

通過Matlab進(jìn)行代碼實現(xiàn)，算法的參數(shù)設(shè)置為：種群大小為50 迭代次數(shù)為200 代。對數(shù)據(jù)樣例_Part1運行10次，得到如表4所示的總行駛路程和所需車輛數(shù)量。

其中，總行駛路程最短為28580km，車輛的行駛路線見表5，收斂曲線如圖7所示。

五、啟發(fā)式規(guī)則對比分析

通過對比兩種啟發(fā)式規(guī)則的10次求解結(jié)果以及兩種啟發(fā)式規(guī)則的最短路線收斂曲線，可以得到如表6的結(jié)論，與啟發(fā)式規(guī)則1相比，啟發(fā)式規(guī)則2的最短距離降低544km，平均最短距離降低468.7km，方差也更小，因此啟發(fā)式規(guī)則2的性能更佳，也更穩(wěn)定。

六、結(jié)論

本文將啟發(fā)式規(guī)則引入物流配送的車輛排班問題中，根據(jù)約束條件，建立了目標(biāo)函數(shù)為總行駛路程的數(shù)學(xué)模型，并使用A公司的真實物流數(shù)據(jù)作為算例進(jìn)行數(shù)據(jù)仿真，通過研究結(jié)果可以發(fā)現(xiàn)該研究將會降低車輛的行駛距離，這就意味著將會大大節(jié)約運輸所帶來的成本，從而使問題更具有實際意義。但是本文所提出的啟發(fā)式規(guī)則是基于A物流公司問題本身的特點設(shè)計的，首先采用啟發(fā)式規(guī)則能更好的搜索最優(yōu)解，其次，通過啟發(fā)式規(guī)則求解問題只需要很少的求解時間。但是本文的美中不足在于沒有采用固有的元啟發(fā)式算法對問題進(jìn)行求解，且所設(shè)計的兩種啟發(fā)式規(guī)則還有很大的改進(jìn)空間，例如車輛初始任務(wù)的選取可以設(shè)計一些規(guī)則，而不是選擇開始時間最早的任務(wù)，這樣將會增加求解空間的規(guī)模。進(jìn)一步的研究可以使用元啟發(fā)式算法求解該問題與其進(jìn)行對比。

參考文獻(xiàn)：

[1]Dantzig G.and Ramser J.The Truck Dispatching Problem[J].Management Science，1959，6（01）：80-91.

[2]Aldair Alvarez，Pedro Munari.An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen[J].Computers & Operations Research，2017，7（83）：1-12.

[3]Ng K K H，Lee C K M，Zhang S Z，Kan Wu，William Ho.A multiple colonies artificial bee colony algorithm for a capacitated vehicle routing problem and re-routing strategies under time-dependent traffic congestion [J].Computers & Industrial Engineering，2017，7（109）：151-168.

[4]Duygu Tas，Nico Dellaerta，Tom van Woensel，Tonde Kok.The time-dependent vehicle routing problem with soft time windows and stochastic travel times[J].Transportation Research Part C：Emerging Technologies，2014，11（48）：66-83.

[5]SophieN.Parragh，JeanFranois Cor-deau.Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows[J].Computers & Operations Research，2017，7（83）：28-44.

[6]Sumaiya Iqbal M，Kaykobad Sohel Rahman M.Solving the multi-objective vehicle routing problem with soft time windows with the help of bees[J].Swarm and Evolutionary Computation，2015，10（24）：50-64.

[7]陳印，徐紅梅.混合算法在車輛路徑優(yōu)化問題中的應(yīng)用[J].計算機仿真，2012（05）：356-359.

[8]胡純德，祝延軍，高隨祥.基于人工免疫算法和蟻群算法求解旅行商問題[J].計算機工程與應(yīng)用，2004（34）：60.

[9]陳小潘，孔云峰，鄭泰皓，等.需求可拆分校車路徑問題的元啟發(fā)式算法[J].計算機科學(xué)，2016，43（10）：234-241+261.

[10]趙晶，吳翠紅，王昭宇.應(yīng)用元啟發(fā)式算法解決特殊約束的裝配線平衡問題[J].湖北農(nóng)機化，2019（19）：128-130.

[11]唐勇，劉峰濤.新型遺傳模擬退火算法求解帶VRPTW問題[J].計算機工程與應(yīng)用，2006，42（07）：7-9.

[12]張建同，丁燁.變鄰域模擬退火算法求解速度時變的VRPTW問題[J].運籌與管理，2019，28（11）：77-84.

（作者單位：江蘇大學(xué)管理學(xué)院）

1052500511354