多商品分批次取送貨的模糊需求車輛路徑問題

高振迪, 計明軍, 孔靈睿, 郭興海

(大連海事大學(xué) 交通運輸工程學(xué)院,遼寧 大連 116026)

0 引言

商品銷售會因氣候、經(jīng)濟、文化等因素產(chǎn)生庫存不平衡現(xiàn)象，如區(qū)域性流感暴發(fā)可致附近藥店庫存斷貨，流感過后則可能出現(xiàn)庫存積壓，造成運營損失。連鎖體制下，連鎖店歸總公司管轄，溝通門檻低，可通過店間調(diào)貨提高閑置資源利用率，節(jié)約運營成本。目前，調(diào)貨策略已成為連鎖企業(yè)關(guān)注的熱點。

多商品多批次取送貨的模糊需求車輛路徑問題(multi-commodity vehicle routing problem with split delivery and fuzzy demand, MCVRPSPDFD)是上述調(diào)貨思想的延伸，可拆分為分批取送貨車輛路徑問題(vehicle routing problem with split pickups and deliveries, VRPSPD)和模糊需求車輛路徑問題(vehicle routing problem with fuzzy demands, VRPFD)。Dror率先提出分批送貨問題，研究指出，分批送貨拓展了解空間，可降低配送成本。隨后，研究者們逐漸將分批送貨問題轉(zhuǎn)換為供求匹配網(wǎng)絡(luò)已知的VRPSPD問題。C. Archett等[1]提煉出該問題的經(jīng)典公式，歸納了時間窗、分批次配送等變體問題。Marielle等[2]提出了單產(chǎn)品多次訪問客戶點的約束，現(xiàn)被廣泛應(yīng)用于工廠間的原料調(diào)配。多商品分批次取送貨問題(multi-commodity vehicle routing problem with split pickup and delivery, MCVRPSPD)由Al-Khayyal等[3]提出，馬艷芳等[4]在此基礎(chǔ)上研究了模糊需求下同時取送貨問題，通過將取貨目標均視為出發(fā)點，實現(xiàn)問題的求解。近年來，研究者們開始探究供求網(wǎng)絡(luò)未知的MCVRPSPD問題。供求網(wǎng)絡(luò)未知指客戶點間未形成牢固的供求關(guān)系，該問題由徐東洋[5]提出與完善，以協(xié)助煙草公司重新分配分廠的原料庫存。由于該問題的相關(guān)研究常忽略配送過程中的不確定性，反而可能導(dǎo)致成本增加。在已有研究中，對于不確定問題的研究多基于隨機理論。然而使用模糊理論描述不確定因素更貼合實際[6]。因此，張建勇等[7]定義了模糊需求車輛路徑問題，通過引入決策者主觀偏好值來限制模糊變量，節(jié)約配送成本。

1 問題描述與建模

1.1 問題描述

本文研究問題可描述為：一組對多貨物產(chǎn)生三角模糊需求的連鎖店，要求配送和/或運走不同種類的貨物，服務(wù)由一隊具有里程和容量限制的車輛提供，車輛可以多次訪問客戶點，在完成配送后需要返回倉庫，企業(yè)希望運作成本最低。

圖1 MCVRPSPDFD優(yōu)化方案

本文研究的優(yōu)化方案示意如圖1，車輛在不同需求模糊的店面(連鎖店2、3)往返平衡商店庫存，滿足對應(yīng)需求；當下一點(連鎖店5)配送失敗概率不被決策者接受時，車輛從當前位置(連鎖店6)返回倉庫取貨再進行配送。

1.2 問題假設(shè)

①模型假設(shè)了一種場景：每一個連鎖店都需要較大批量的補貨，車輛需要在補貨的同時順帶完成調(diào)貨任務(wù)，故將里程約束轉(zhuǎn)為容量約束；

②為方便商店庫存管理，設(shè)每次訪問至少滿足某一種貨物的需求。

1.3 模型參數(shù)

常量：Kmax為可用車輛數(shù)目；Q為車容量；M為趨于正無窮的數(shù)；C(R)為決策者偏好值；C0為油價；Ck為出車成本；C1為額外提取一單位貨物付出的代價。

師：看來對AP 2=BP 2=AN·BM這一關(guān)系的發(fā)現(xiàn)也是制約我們解題和出題的原因，那我們現(xiàn)在會出題了嗎？

1.4 確定需求模型

確定需求模型以出車成本與里程成本最低為目標，其目標函數(shù)為:

(1)

約束條件:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

?j∈N′,b∈U,n∈P,k∈V

(14)

siajbmk≥0,?i∈N,j∈N,a∈U,b∈U,m∈P,v∈V

(15)

(16)

(17)

(18)

(19)

qjbmk≥0,?j∈N,b∈U,m∈P,k∈V

(20)

(21)

(22)

式(2～3)：任一車輛均從起點0出發(fā)并返回終點。式(4～7)：任一車僅能訪問起點與終點各一次。式(8)：車輛訪問任一點，都有訪問次數(shù)對應(yīng)。式(9)：對路線流進行約束，確保車輛的來源和去向。式(10～11)：消除子回路。式(12～13)：車輛從倉庫空車出空車回，該式對于不同情境可做出相應(yīng)改變，如后文提到的模糊需求，可設(shè)計為返回時車輛裝載量的最大模糊數(shù)大于等于0。式(14)：裝卸平衡約束，用以確保車輛裝載貨物等于原裝載量與裝/卸貨量之差。式(15～16)：車輛在行駛時裝載貨物量不為負且不超過最大容量。式(17)：任意客戶對貨物的取/卸貨量應(yīng)與對的供/需相等。式(18)：被次訪問的客戶對貨物供貨時，車提貨量應(yīng)小于等于點供應(yīng)量和自身容量。式(19)：被次訪問的客戶對貨物需求時，車卸貨量為點需求量或0。式(20)：任意一次服務(wù)的提卸貨量均不為負。式(21)：車服務(wù)點的前提是到達點。式(22)：計算執(zhí)勤車數(shù)。

1.5 模糊需求模型

模糊需求模型借鑒了曹二保[9]提出的可信度計算公式，目標函數(shù)為:

(23)

約束如下:

(24)

?j∈N′,b∈U,k∈V,m∈P

(25)

(26)

(27)

(28)

(29)

2 遺傳禁忌算法

鑒于目前鮮有學(xué)者研究針對MCVRPSPDFD問題的算法，在分別參考多貨品、模糊需求、需求可拆分等車輛路徑問題求解算法后，本文提出了一種改進的GTHA算法，其優(yōu)勢為：遺傳算法的編碼結(jié)構(gòu)簡單，操作便捷，種群修復(fù)與全局搜索能力強；禁忌搜索算法框架簡單，局部搜索能力強，求解復(fù)雜車輛路徑問題時不僅更加準確，還具有效率優(yōu)勢。算法設(shè)計思路如下(流程見圖3):

①種群結(jié)構(gòu)。在多次訪問的條件下，未滿足的客戶會重復(fù)出現(xiàn)至被滿足(圖2)。范例中，客戶均需日常補貨，且有1種貨物要調(diào)配，flag0對應(yīng)補貨，flag1對應(yīng)貨物1，值為1時表示對應(yīng)需求被滿足。②構(gòu)建初始解?；谪澙匪惴ǎ瑢┴淈c進行單元化處理[5]，快速構(gòu)建高質(zhì)量初始解。③巡回路徑編碼。利用巡回路徑法[10]進行二次編碼，避免迭代產(chǎn)生無效解。④適應(yīng)度。參考數(shù)學(xué)模型，通過容量約束計算出每一種群所需車輛數(shù)目和車輛對應(yīng)客戶點；將各費用之和(式23)取倒數(shù)得適應(yīng)度。⑤禁忌算子。代替變異算子，鄰域產(chǎn)生方式：交換兩個基因的位置；藐視準則：當某個基因移動后得到的鄰域解優(yōu)于當前最優(yōu)解，則不論該基因移動是否處于禁忌狀態(tài)，都接受該解作為新的當前解和當前最優(yōu)解。⑥選擇算子。為提高求解效率，本文在輪盤賭選擇方法的基礎(chǔ)上引入了保留精英種群策略。⑦交叉算子。在兩條父代染色體上隨機選擇長度相同的一段基因進行交叉。

圖2 種群結(jié)構(gòu)示例

圖3 算法流程圖

3 算例求解

3.1 算例描述

本文構(gòu)建了以某醫(yī)藥連鎖公司為背景的算例如下：藥品由工廠的倉庫運往各連鎖店，公司希望名下四臺容量為150的車輛在配送的同時，將各連鎖店滯壓的2種高價值藥品進行流通。出車成本80元/次；燃油成本0.4元/單位里程；配送失敗時額外的調(diào)貨成本10元/單位，算例坐標取自Solomon R101的1～20客戶點(其中1點為倉庫)，客戶模糊需求由隨機數(shù)生成。

3.2 算例結(jié)果

算例求解結(jié)果為：總成本683.8元，其中里程成本263.8元；額外提貨懲罰成本180元；出車成本為240(3輛)元；車輛配送路徑見表1。其中，多需求的點(如點10、5、8、9、6)有被一次性滿足的傾向，因為可以縮減里程成本。

表1 車輛配送情況

3.3 參數(shù)測試

經(jīng)測試，種群規(guī)模和TS算子迭代次數(shù)對GTHA算法影響最大，故通過實驗研究參數(shù)選擇對算法性能的影響，得到結(jié)果如圖4，5。圖4中，種群規(guī)模與算法收斂速度及求解效果呈正相關(guān)，種群規(guī)模超一定規(guī)模時對結(jié)果影響會變小，考慮到算法效率，本文種群規(guī)模取20個。圖5可看出，TS算子收斂所需代數(shù)與問題規(guī)模呈正相關(guān)。故統(tǒng)計不同問題規(guī)模下，TS算子運算花費時間，得出耗時亦與問題規(guī)模呈正相關(guān)，故TS算子迭代取20次，以兼顧運算速度和運算效率。

圖4 GTHA算法收斂情況

圖5 TS算法收斂情況

4 算例分析

4.1 模型及算法驗證

本文先驗證算法求解確定模型準確性如表2。極小規(guī)模的問題中，GTHA算法求解結(jié)果與Cplex求得的最優(yōu)解基本相同。對于更大規(guī)模的算例，由于解空間變大，Cplex很難在短時間內(nèi)求出結(jié)果。

表2 Cplex對比結(jié)果

為探討GTHA的可靠性，對不同規(guī)模算例進行100次求解得到變異系數(shù)(見表3)?？梢钥闯?，運算耗時與問題規(guī)模及貨物種類呈正相關(guān)，且求解結(jié)果的變異系數(shù)低于6%，算法結(jié)果比較穩(wěn)定。

表3 變異系數(shù)

為驗證GTHA算法效率，設(shè)計GA、TS算法對不同問題規(guī)模的對照試驗，結(jié)果如圖6所示。其中，GTHA算法求解效果最好，其次是局部搜索能力強的TS算法，最后是廣域搜索能力強但局部搜索能力弱的GA算法。

圖6 三種啟發(fā)式算法對照結(jié)果

4.2 結(jié)果比較及決策者偏好值分析

為驗證分批次訪問規(guī)則的優(yōu)越性，本文對照調(diào)度規(guī)則：A. MCVRPSPDFD問題；B.模糊需求下單車單次訪問客戶點問題；C.允許配送失敗的分批取送貨問題。

表4 對照試驗結(jié)果

由表4可知，A、C方案均優(yōu)于B方案，證明了分批取送貨方案的優(yōu)勢。A方案優(yōu)于C方案，在于A方案通過提前返回倉庫補貨避免了里程浪費。在各配送點距離很近時，A、C方案結(jié)果相差較小，這是由于未對配送失敗設(shè)計額外的懲罰成本。實際中，連鎖公司會考慮包括人員工時在內(nèi)的多種懲罰成本，這會使A方案的優(yōu)勢更顯著。

圖7 總成本隨 值變化趨勢

C(R)值對車輛行駛路徑有極大影響。對不同規(guī)模的實驗結(jié)果進行分析，得某次實驗C(R)值對總成本影響如圖7。當C(R)值大于0.4時，車輛行駛總成本激增，這是因為隨著決策者對配送失敗的接受度降低，車輛配送失敗次數(shù)會增加，總成本會隨之增加至峰值。經(jīng)試驗，不同配送情況下激變點位置和激變程度不同。其中激變點變化范圍在0.3～0.5之間，激變程度與連鎖店提供貨物的數(shù)量呈負相關(guān)。

5 結(jié)論

MCVRPSPDFD問題可以幫助連鎖行業(yè)提升配送效率，降低配送成本。本文在研究該問題時，還考慮了配送時客戶點需求的模糊性，以降低物流配送運作成本、提高物流配送服務(wù)水平為目標，構(gòu)建了考慮多批次、多貨物、取送貨和模糊需求特點的車輛路徑模型?？紤]到問題復(fù)雜度，提出了改進的GTHA算法對模型進行求解，驗證了模型和算法的有效性。結(jié)果表明，MCVRPSPDFD方案可幫助企業(yè)節(jié)省調(diào)撥費用；此外，方案成本會隨決策者對配送失敗的接受度而變化，決策者可根據(jù)對配送失敗的接受程度選擇最佳的值，以獲得最優(yōu)的配送方案。