考慮穩(wěn)定路線約束的零散貨物拼車配送方案優(yōu)化

肖文濤，宮向陽

（1.中國石油化工股份有限公司大連石油化工研究院，遼寧 大連 116045；2.中國石油化工集團(tuán)公司信息化管理部，北京 100728）

1 引言

物流配送是物流業(yè)務(wù)的一個重要環(huán)節(jié)。為降低物流成本和提高服務(wù)質(zhì)量，需要優(yōu)化調(diào)配車輛和合理選擇路線。當(dāng)前運輸車輛逐漸大型化，配送需求逐漸個性化，為調(diào)和運輸車輛大型化和配送需求零散化之間的矛盾，需要采用相關(guān)方法，優(yōu)化拼裝-配送方案。關(guān)于車輛路徑優(yōu)化問題的研究成果較多[1-5]，但大多是在車型固定或數(shù)量確定等前提條件下得出的。隨著運輸業(yè)務(wù)外包趨勢的發(fā)展，多車型、無限量、穩(wěn)定路線、有限時間約束等復(fù)雜要求逐漸增多，現(xiàn)有研究結(jié)論不能滿足新的優(yōu)化需求?；诖?，本文提出了一種基于穩(wěn)定路線約束的零散貨物多車型拼裝配送方案優(yōu)化方法。

2 問題簡介

從遠(yuǎn)洋物流到陸地物流，從大宗商品、工業(yè)產(chǎn)品到農(nóng)副食品運輸，很多行業(yè)都存在拼裝配送業(yè)務(wù)[4-7]。本文以某公司為客戶配送產(chǎn)品為例，介紹優(yōu)化需求及求解算法。某公司生產(chǎn)有保質(zhì)期要求的食品，需要優(yōu)化車輛選型及配送路線，為客戶提供快速配送服務(wù)。物流配送業(yè)務(wù)的主要信息和相關(guān)要求如下文所述。

（1）車型信息。可供選用的車型有7種，各種車型無限量租用，其運量上限和費率見表1。各型車輛行駛速度都為50km/h，卸貨速度為3t/h。

表1 各型車輛運量上限和費率表

（2）客戶信息?？蛻艨倲?shù)共計83個，但由于A8、A31、A34、A46等4個客戶已與運輸公司約定同車統(tǒng)一配送，因而本文只考慮剩余的79個客戶，各客戶每次的貨物需求量及收貨頻次見表2。

收貨頻次可分1、2、4三種類型。其中頻次1指該客戶每天需接收一次貨物，頻次2指該客戶每兩天需接收一次貨物，同理頻次4指該客戶每四天需接收一次貨物。

要求參與運輸?shù)母鬈噺耐慌湄浿行某霭l(fā)，沿各自的規(guī)定路線為沿途客戶配送相應(yīng)的貨物。參與運輸?shù)能囕v為臨時租用，在完成最后一站客戶的配送任務(wù)后即釋放資源，停止計費。

3 模型建立

表2 客戶需求貨物量與收貨頻次信息

3.1 目標(biāo)函數(shù)

拼車配送優(yōu)化的決策變量為車輛型號和行車路線，優(yōu)化的目標(biāo)為所有參與拼裝配送車輛的總運費最小。

式中：N指參與配送的車輛總數(shù)；ri指第i號車輛的費率；Vi指第i號車輛的標(biāo)準(zhǔn)計費噸位，單位t；n指第i號車輛所服務(wù)的客戶總數(shù)；指第j-1號客戶與第j號客戶間的路程（其中0號客戶代表配貨中心），單位km；指第i號車輛的配送路線的總長度，單位km。

3.2 限制條件

拼車配送方案優(yōu)化問題的限制條件包含以下幾類：

（1）最大載重約束。所有參與拼裝配送的車輛的載貨總重量不超過最大載重限制，本文中最大允許載重為20t。

式中，vi指第i號車輛的載貨量，單位t；vmax指車輛所允許的最大載重，單位t。

（2）最長時間約束。除特殊情況外，所有車輛的路線配送時間不超出最長允許時間限制，本文中路線最長配送時間為2d。

式中，Di指第i號車輛的路線配送時長，單位s；Dmax指路線最長允許配送時間限制，單位s。

（3）穩(wěn)定路線約束。各車的行駛路線必須保持穩(wěn)定，沿途所配送客戶的頻次屬性應(yīng)保持不變或增大趨勢。

式中，F(xiàn)ij指第i輛車所服務(wù)的第j號客戶的頻次參數(shù)，單位d/次；Fij+1指第i輛車所服務(wù)的第j+1號客戶的頻次參數(shù)，單位d/次。

除上述3種主要的限制條件外，零散貨物拼車配送優(yōu)化問題還存在卸貨時間約束，也即客戶凌晨1:00-5:00期間不支持卸貨，在此期間抵達(dá)的車輛需等到5點開始卸貨；凌晨1:00前未完成卸貨的車輛需停止卸貨，等到凌晨5:00后繼續(xù)作業(yè)。卸貨時間不構(gòu)成獨立的約束條件，而主要通過最長時間約束來影響配送方案優(yōu)化問題。

4 模型求解

上述車輛路徑優(yōu)化問題屬于包含多維度變量組合優(yōu)化的大規(guī)模NP難問題。NP難問題的求解算法主要分為確定性算法和啟發(fā)式算法兩類。對于小規(guī)模問題，可以考慮采用確定性算法求解；對于大規(guī)模NP難問題，一般采用啟發(fā)式算法來求解。

4.1 算法簡介

啟發(fā)式算法具有較強(qiáng)的適用性和全局性，已被廣泛應(yīng)用于交通運輸領(lǐng)域[8-11]。本文采用改進(jìn)差分進(jìn)化（Differential Evolution,DE）算法來求解有穩(wěn)定路線約束的零散貨物拼車配送方案優(yōu)化問題。DE由R．Storn和K．Price提出[12-13]，是一種基于群體差異的自啟發(fā)式隨機(jī)搜索算法。DE算法流程如圖1所示。

圖1 差分進(jìn)化算法流程圖

在車輛型號和數(shù)量不定的情況下，應(yīng)用DE算法不能直接求解拼車配送路線優(yōu)化問題。多種維度的變量，復(fù)雜的約束條件對算法性能構(gòu)成較大挑戰(zhàn)。本文通過改進(jìn)染色體編/解碼方案，提高DE算法的尋優(yōu)效率，實現(xiàn)對復(fù)雜條件約束下的多種維度變量組合優(yōu)化的大規(guī)模NP難問題的求解。

4.2 編/解碼方案

應(yīng)用DE算法優(yōu)化拼車配送路線時，所采用的編碼方案見表3。

表3 基因編碼方案

表3中染色體編碼需經(jīng)解讀才能生成拼裝配送方案。方案解讀過程中，可充分利用路線時間限制、車輛最大載重限制等條件，直接生成滿足約束的拼裝配送方案，減少罰函數(shù)的使用。具體方案解讀方法如圖2所示。

主要步驟如下：

步驟（1）：判斷所有貨物是否已完成拼裝配送。若是，轉(zhuǎn)步驟（4）；若否，轉(zhuǎn)步驟（2）。

步驟（2）：利用編號為i的車輛Ti試裝載編號為j的貨物。若裝貨后配送時間超過2天，則認(rèn)為車輛Ti不能裝載j貨物，Ti裝貨結(jié)束，統(tǒng)計已裝載貨物量并選擇相應(yīng)車型，令i=i+1，開始下一輛車的裝貨，轉(zhuǎn)步驟（1）；若裝貨后配送時間不超過兩天，轉(zhuǎn)步驟（3）。

圖2 染色體解碼流程圖

步驟（3）：若Ti裝載j貨物后的總載貨量不超過20t，令j=j+1，轉(zhuǎn)步驟（1）；若總載貨量超過20t，則認(rèn)為車輛Ti不能裝載j貨物，Ti裝貨結(jié)束，統(tǒng)計已裝載貨物量并選擇相應(yīng)車型，令i=i+1，開始下一輛車的裝貨，轉(zhuǎn)步驟（1）。

步驟（4）：結(jié)束并輸出拼裝配送方案。

應(yīng)用上述染色體編/解碼方法，解讀表3中染色體所獲得的配送路線和車型方案，見表4。

表4 基因編碼方案

表4中，針對8個客戶共形成了3條拼車配送路線，分別為 A80→A73→A72、A68→A83和 A81→A82→A70，各條路線相應(yīng)的車型分別為T1、T1和T2。由于在編解碼過程中充分利用了約束規(guī)則，因而表4中所有行車路線都不違反車輛最大載重限制和路線最大時長限制。但應(yīng)當(dāng)注意，上述編解碼方法并未設(shè)置穩(wěn)定路線規(guī)則，運輸方案仍然需要使用罰函數(shù)，以淘汰路線不穩(wěn)定的拼車配送方案。

4.3 分組-合并優(yōu)化

在客戶總數(shù)較多時，DE算法的尋優(yōu)時效會明顯降低。因此，建議采用分組尋優(yōu)，而后合并優(yōu)化的方法，也即先尋得各組的局部優(yōu)化方案，而后將各組的局部優(yōu)化方案合并優(yōu)化。通過兩級優(yōu)化，在較短的時間內(nèi)獲得滿意解。

分組尋優(yōu)-合并優(yōu)化的方法可能丟失全局最優(yōu)解，但卻能有效提高算法尋優(yōu)時效。分組尋優(yōu)-合并優(yōu)化方法容易理解和實現(xiàn)，在配送時間約束嚴(yán)格的情況下是值得推薦的一種選擇。

分組尋優(yōu)-合并優(yōu)化主要包含分組和合并尋優(yōu)兩個環(huán)節(jié)。在分組環(huán)節(jié)，可以采用模糊C均值聚類算法等將客戶按地理位置分成容易處理的幾類，在此不再贅述。

在合并優(yōu)化環(huán)節(jié)，可以采用車間相互交互法，進(jìn)一步優(yōu)化車型和路線，方法流程如圖3所示。

圖3 車間交互法流程示意圖

在合并優(yōu)化時，各車之間應(yīng)嘗試相互交換一個或幾個貨物批次，若出現(xiàn)多個更為經(jīng)濟(jì)的配送，則應(yīng)從最優(yōu)的開始依次兩兩交換貨物。在此過程中，兩輛車間交換貨物和各車重新優(yōu)化自身的配送順序是循環(huán)進(jìn)行的，直至最終收斂。

值得注意的是，分組-合并優(yōu)化的方法可能導(dǎo)致丟失最優(yōu)解，但能夠有效提高DE算法的尋優(yōu)時效，提高使用者對時間消耗的容忍度。

4.4 案例分析

對于上文所述的優(yōu)化問題，可根據(jù)地理位置信息，采用聚類算法預(yù)先將客戶分成5組，如圖4所示。

圖4 客戶地理位置分布圖

由于客戶A29和A64的需求量都超過了20t，因此需要預(yù)先拆分配送。其中將A29客戶的需求量拆分成20t和1.07t，將A64客戶的需求量拆分成20t和2.94t。對20t的整量部分直接安排載重20t貨車進(jìn)行配送，對A29客戶剩余的1.07t和A64客戶剩余的2.94t零散部分納入拼車配送優(yōu)化中予以考慮。

采用第4節(jié)所述算法求解第2節(jié)的拼車配送問題。通過分組-合并優(yōu)化方法，得到最終方案見表5。

最終將所有客戶的零散貨物需求拼成了28輛車（算上客戶A29和A64的2輛20t整車，該方案車輛總數(shù)總計30輛）進(jìn)行配送，其中載重4t的貨車13輛，載重6t的貨車2輛，載重9t的貨車1輛，載重12t的貨車6輛，載重15t的貨車4輛，載重18t的貨車1輛，載重20t的貨車1輛。經(jīng)對比，該方案的總費用比人工方案節(jié)省約27.8%。

5 結(jié)論

隨著運輸業(yè)務(wù)外包化的發(fā)展，具有多車型、無限租量、路線穩(wěn)定等復(fù)雜要求的拼車配送優(yōu)化問題逐漸增多。本文以DE為主體，利用約束條件改進(jìn)染色體的編/解碼方案，利用車間交互法對大規(guī)模NP難問題進(jìn)行分組-合并處理，最終實現(xiàn)了對零散貨物拼車配送方案的快速優(yōu)化。改進(jìn)算法可能導(dǎo)致丟失最優(yōu)解，但有效提高了尋優(yōu)時效。應(yīng)用改進(jìn)的DE算法優(yōu)化了包含79家客戶的貨物配送方案，最終將79家客戶的零散貨物拼成30輛車進(jìn)行配送。所獲得的優(yōu)化方案路線穩(wěn)定，易于執(zhí)行，總費用比人工計劃節(jié)約了27.8%。

表5 優(yōu)化配送方案

[參考文獻(xiàn)]

[1]林宇肖.考慮油品隔離的成品油城市配送路徑優(yōu)化[D].大連:大連海事大學(xué),2015.

[2]王宇奇,李靖澤.基于改進(jìn)C-W節(jié)約算法的成品油二次配送優(yōu)化研究[J].科技與管理,2014,16(1):51-55.

[3]強(qiáng)濃,王忠偉.基于遺傳算法的物流配送路線優(yōu)化系統(tǒng)設(shè)計與實現(xiàn)[J].物流工程與管理,2013,35(10):109-112.

[4]宋強(qiáng).城市物流環(huán)境下車輛路徑問題的研究[J].物流工程與管理,2017,39(2):51-55.

[5]呂圣杰.成品油公路運輸配送系統(tǒng)優(yōu)化策略[J].物流工程與管理,2014,36(11):64-65.

[6]王勇,肖文濤,李雪,等.我國原油遠(yuǎn)洋運輸?shù)倪\作模式及面臨挑戰(zhàn)[J].油氣儲運,2016,35(7):788-792．

[7]肖文濤,徐寧,劉志玲,等.原油采購-遠(yuǎn)洋運輸方案模糊聚類圖優(yōu)化法[J].中國石油大學(xué)學(xué)報:自然科學(xué)版,2017,41(2):176-182．

[8]蔡延光,宋康,張敏捷,等.自適應(yīng)多目標(biāo)混合差分進(jìn)化算法在聯(lián)盟運輸調(diào)度中的應(yīng)用[J].計算機(jī)應(yīng)用,2010,30(11):2 887-2 890.

[9]葛顯龍,辜羽潔,王偉鑫.供應(yīng)鏈環(huán)境下的庫存與運輸整合優(yōu)化模型及算法[J].系統(tǒng)工程,2014,33(1):26-32.

[10]閆華,高黎,劉國勇,等.基于多時間窗的油料保障模型[J].計算機(jī)應(yīng)用,2015,35(7):2 096-2 100．

[11]周曉玲,王震,肖文濤.原油遠(yuǎn)洋拼船運輸方案優(yōu)化研究[J].中國石油大學(xué)學(xué)報:自然科學(xué)版,2016,40(2):174-180.

[12]Storn R,Price K.Differential Evolution-a Simple and Efficient Adaptive Scheme for Global Optimization over ContinuousSpaces[J].TechnicalReport,InternationalComputer Science Institute,1995,(8):22-25.

[13]Storn R,Price K.Differential Evolution-a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces[J].JournalofGlobalOptimization,1997,11(4):341-359.