高振迪, 計(jì)明軍, 孔靈睿, 郭興海

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

0 引言

商品銷售會(huì)因氣候、經(jīng)濟(jì)、文化等因素產(chǎn)生庫存不平衡現(xiàn)象，如區(qū)域性流感暴發(fā)可致附近藥店庫存斷貨，流感過后則可能出現(xiàn)庫存積壓，造成運(yùn)營損失。連鎖體制下，連鎖店歸總公司管轄，溝通門檻低，可通過店間調(diào)貨提高閑置資源利用率，節(jié)約運(yùn)營成本。目前，調(diào)貨策略已成為連鎖企業(yè)關(guān)注的熱點(diǎ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)典公式，歸納了時(shí)間窗、分批次配送等變體問題。Marielle等[2]提出了單產(chǎn)品多次訪問客戶點(diǎn)的約束，現(xiàn)被廣泛應(yīng)用于工廠間的原料調(diào)配。多商品分批次取送貨問題(multi-commodity vehicle routing problem with split pickup and delivery, MCVRPSPD)由Al-Khayyal等[3]提出，馬艷芳等[4]在此基礎(chǔ)上研究了模糊需求下同時(shí)取送貨問題，通過將取貨目標(biāo)均視為出發(fā)點(diǎn)，實(shí)現(xiàn)問題的求解。近年來，研究者們開始探究供求網(wǎng)絡(luò)未知的MCVRPSPD問題。供求網(wǎng)絡(luò)未知指客戶點(diǎn)間未形成牢固的供求關(guān)系，該問題由徐東洋[5]提出與完善，以協(xié)助煙草公司重新分配分廠的原料庫存。由于該問題的相關(guān)研究常忽略配送過程中的不確定性，反而可能導(dǎo)致成本增加。在已有研究中，對(duì)于不確定問題的研究多基于隨機(jī)理論。然而使用模糊理論描述不確定因素更貼合實(shí)際[6]。因此，張建勇等[7]定義了模糊需求車輛路徑問題，通過引入決策者主觀偏好值來限制模糊變量，節(jié)約配送成本。

1 問題描述與建模

1.1 問題描述

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

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

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

1.2 問題假設(shè)

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

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

1.3 模型參數(shù)

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

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

1.4 確定需求模型

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

1.5 模糊需求模型

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

(23)

約束如下:

(24)

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

(25)

(26)

(27)

(28)

(29)

2 遺傳禁忌算法

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

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

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

圖3 算法流程圖

3 算例求解

3.1 算例描述

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

3.2 算例結(jié)果

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

表1 車輛配送情況

3.3 參數(shù)測試

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

圖4 GTHA算法收斂情況

圖5 TS算法收斂情況

4 算例分析

4.1 模型及算法驗(yàn)證

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

表2 Cplex對(duì)比結(jié)果

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

表3 變異系數(shù)

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

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

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

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

表4 對(duì)照試驗(yàn)結(jié)果

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

圖7 總成本隨 值變化趨勢

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

5 結(jié)論

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