考慮同時取送隨機需求的多行程車輛路徑研究

(福州大學(xué) 經(jīng)濟與管理學(xué)院，福建 福州 350108)

引言

多行程車輛路徑問題（Multi-Trip Vehicle Routing Problem，MTVRP）最早由Fleischmann提出[1]，在車輛從配送中心出發(fā)之后，允許車輛中途返回配送中心補貨后再出發(fā)繼續(xù)服務(wù)后續(xù)點，在配送中心和路徑客戶點之間進行多次往返完成配送任務(wù)，其具有能有效減少車輛使用數(shù)量、降低發(fā)車成本等優(yōu)點，近年來受到學(xué)者們關(guān)注。

在多行程物流中，目前MTVRP研究集中于確定性多行程車輛路徑問題，內(nèi)容主要針對分配路線數(shù)量和限制車輛服務(wù)時間等方面。Francois等學(xué)者采用組合裝箱構(gòu)造初始路徑集合后單獨分配給車輛，并提出了大規(guī)模鄰域搜索算法求解[2]；宋強等學(xué)者在約束條件下制定一組可行路線分配給車輛進行配送，提出改進的混合遺傳算法求解帶時間窗和發(fā)貨時間的MTVRP[3]；Hernandez等開放車輛在途服務(wù)時間限制研究帶時間窗的 MTVRP，并設(shè)計分支定價算法進行求解[4]；為研究允許車輛在工作日期間執(zhí)行多趟配送任務(wù)的MTVRP，宋強等學(xué)者提出了改進迭代局部搜索算法、變鄰域搜索算法進行求解[5-6]。

在實際物流活動中由于諸多因素存在，很多客戶信息會表現(xiàn)出不確定性、變化性，研究主要集中于考慮客戶的單向送貨需求的不確定性、帶不確定環(huán)境求解方法和動態(tài)調(diào)整策略等方面。王連鋒等學(xué)者針對客戶的模糊送貨需求，分析了實際配送途中服務(wù)失敗事件的可能性并建立模糊期望值模型，并設(shè)計了帶雙層禁忌的并行粒子群算法求解[7]；學(xué)者李陽和范厚明分別針對客戶隨機需求和模糊需求構(gòu)建不確定問題模型，提出點返回多行程策略，并采用變鄰域搜索算法進行求解[8-9]；Wassan等學(xué)者以最小化總成本為目標(biāo)研究帶回程取貨的MTVRP，提出了兩階段鄰域搜索算法[10]；張曉楠等針對帶模糊送貨需求的MTVRP，基于可信性測度理論構(gòu)建預(yù)優(yōu)化模型，提出了“基于調(diào)整成本期望值”的實時調(diào)整策略，并設(shè)計種群進化算法進行求解[11-12]。

綜上所述，目前MTVRP的研究中，主要集中于確定性問題、不確定的單向送貨需求及其求解算法的研究，考慮同時取送貨、不確定需求的運輸情況較少。而在MTVRP中，由于其可在運輸途中多次往返，如何同時兼顧客戶取送雙向動態(tài)突發(fā)性需求，避免單向物流造成的車輛能力浪費，又能滿足顧客個性化的需求，降低成本和提高配送效率，是MTVRP配送實際面臨的問題。本文針對客戶取送雙向需求隨機性的多行程車輛路徑問題，探究實際調(diào)整策略和求解算法，旨在為物流企業(yè)提供不同于傳統(tǒng)情境下實際指導(dǎo)的新思路。

一、問題描述及模型建立

（一）問題描述與假設(shè)

本文研究的是三級供應(yīng)鏈配送網(wǎng)絡(luò)中具有隨機取送貨需求的多行程車輛路徑問題，問題情境示意見圖1。配送網(wǎng)絡(luò)中有一個供應(yīng)商、一個配送中心和多個客戶點，采用取送一體化的多行程配送模式，客戶需求為同時取送貨需求且具有隨機性。多行程配送需要作出最優(yōu)路徑?jīng)Q策，確定車輛的初始配送路線方案和實際調(diào)整策略，使總物流成本最小。為突出多行程車輛配送的特性，做出如下假設(shè)：

假設(shè)1 配送網(wǎng)絡(luò)中的節(jié)點連通，配送車輛完全相同，車輛從配送中心出發(fā)，完成配送任務(wù)之后需要返回配送中心，每輛車僅有一條配送路線，且每條路線上的客戶取送貨需求總量不能超過車輛最大裝載能力；

假設(shè)2 假設(shè)客戶取送貨需求服從隨機分布，只有當(dāng)車輛到達(dá)該點時其需求才會被確認(rèn)，取送貨物可以進行混合運輸；

假設(shè)3 初始階段每個客戶點僅能接受一輛車服務(wù)，且車輛首次從配送中心出發(fā)時均處于滿載狀態(tài)。

圖1：MTVRPSPDD問題情境示意圖

（二）符號和變量說明

1.參數(shù)符號

為便于模型描述，假設(shè)配送中心為0，客戶集合C={1,2,…,n}，所有點集合V={0,1,2,…,n}，配送中心可用配送車輛集合K={1,2,…,m}，邊集合E={(i,j)|i,j∈V}，單位配送成本為cij，車輛最大載重量為Q,單位車輛派遣成本為Ck,客戶點i(i∈C)的送貨需求si和取貨需求qi均是隨機變量，服從相互獨立的離散隨機概率分布，wijk(i∈V,j∈V,k∈K)表示配送車輛k訪問客戶i之后再訪問客戶j前的裝載量。

2.決策變量

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

根據(jù)上述問題的分析、描述及假設(shè)，建立相應(yīng)初始狀態(tài)的MTVRP優(yōu)化模型Model I如下。

其中：式（1）為目標(biāo)函數(shù)，最小化車輛派遣成本和配送成本；式（2）-（3）保證任一客戶點有且僅有一條車輛配送路線，且同一個客戶點之間沒有車輛配送路線；式（4）為客戶點進出平衡約束；式（5）表示被選中的車輛最多能從配送中心出發(fā)一次；式（6）表示只有被選中的車輛才有服務(wù)路線；式（7）為支路消除約束，其中S表示車輛k服務(wù)的客戶集合；式（8）和（9）分別保證每條配送路線上正向配送需求總量、逆向攬收需求總量不超過車輛最大載重量Q；式（10）表示車輛在配送途中的負(fù)載量不超過車輛最大載重量Q；式（11）為車輛在服務(wù)客戶點j后的動態(tài)負(fù)載量的計算等式；式（12）-（13）表明決策變量為0-1變量。

二、模型轉(zhuǎn)換與求解

（一）隨機機會約束規(guī)劃模型

在模型Model I中，車輛載重約束中含有隨機送貨需求si和隨機取貨需求qi，在到達(dá)客戶點之前無法得知其取送需求的精確值，導(dǎo)致模型無法直接求解，因此需要對Model I進行轉(zhuǎn)換。針對隨機變量si和qi，引入隨機規(guī)劃理論生成隨機機會約束規(guī)劃模型Model Π[13-14]。

其中：式（14）中f為物流成本目標(biāo)函數(shù)；式（15）中g(shù)i表示Model I中含有隨機變量的約束條件即式（8）-（11），α表示預(yù)設(shè)隨機約束條件成立的置信水平，其大小取決于決策者的風(fēng)險偏好程度，該式子理論上表示事件發(fā)生的概率，實際意義是配送路徑客戶點的隨機送貨需求量之和和取貨需求量之和均不超過車輛最大載重量Q的概率要大于α；式（16）和（17）為已知分布信息的客戶隨機送取貨需求向量；式（18）表示Model I中除了隨機約束條件之外的其他約束。

根據(jù)隨機機會約束規(guī)劃理論[13-14]，當(dāng)且僅當(dāng)Model Π中所有隨機約束條件gi(X,si,qi)≤0,i=1,2,…,n均成立的概率大于等于α，則決策變量 X= xijk,yk可行，即路徑方案可行。對于隨機約束條件組，采用隨機模擬技術(shù)檢驗機會是否成立，步驟如下：

Step 1：初始化參數(shù)。包括實驗次數(shù)N，隨機約束組gi(X,si,qi)≤0,i=1,2,…,n成立的次數(shù)N′；

Step 2：基于需求分布生成隨機送貨需求矩陣、隨機取貨需求矩陣；

Step 3：根據(jù)隨機取送需求矩陣，檢驗隨機約束條件。如果隨機約束條件組gi(X,si,qi)≤0,i=1,2,…,n成立，則N′++；

Step 4：重復(fù)Step2、Step3共N次；

Step 5：如果N′/ N ≥α，則返回“成立”，否則返回“不成立”。

（二）實時柔性點策略優(yōu)化路徑

在模型Model Π中，Pr{·}≥α表示的是一種概率，即使?jié)M足該機會約束生成路徑方案，在實際配送過程中仍然會出現(xiàn)線路中斷，且取送一體化配送方式增大了路徑失敗的可能性，故路徑需要進行實時調(diào)整。在調(diào)整策略上現(xiàn)有文獻(xiàn)多采用失敗點返回策略[15-16]，也有學(xué)者研究采取失敗點之前提前返回的預(yù)補貨策略[11]，針對客戶的隨機雙向需求，本文提出基于隨機需求分布概率的柔性點策略進行實時調(diào)整車輛路徑。

假設(shè)客戶的送取需求分別服從期望為λ1、λ2的隨機分布，β表示決策者在隨機不確定環(huán)境下對某客戶點執(zhí)行配送與否意向的量化，β越大表明決策者對車輛的剩余車載量能夠滿足下一客戶的隨機送貨需求的要求越高，用Q1j和Q2j表示車輛服務(wù)當(dāng)前客戶點j之后的剩余車載量和空余可載貨量，且車輛k當(dāng)前服務(wù)客戶點j，當(dāng)Q1j＞0且Q2j≥0時，車輛有兩種選擇：直接服務(wù)下一個客戶；返回配送中心補貨之后再繼續(xù)服務(wù)下一個客戶。

P1為Q1j對應(yīng)的期望為λ1的隨機分布的分布函數(shù)值，P2為Q2j對應(yīng)的期望為λ2的隨機分布的分布函數(shù)值；若P1≥β，選擇方案直接服務(wù)初始階段計劃路徑的下一個客戶，P1越大表明車輛剩余車載量Q1j能夠滿足下一客戶點送貨需求的可能性越高。同理，P2也是如此；若P1＜β，車輛剩余載貨量Q1j能夠滿足下一客戶隨機需求的概率小于β，決策者不能接受這個風(fēng)險程度，故選擇方案返回配送中心補貨之后再出發(fā)直接前往計劃路徑中客戶點j的后序點進行繼續(xù)配送。

該多柔性點策略依據(jù)車輛實際剩余載貨量和實際空余可載貨量進行路徑選擇，由于兩者與客戶的取送貨需求量息息相關(guān)，不僅可以避免因客戶需求隨機導(dǎo)致的盲目性，同時也更能避免不恰當(dāng)?shù)倪x擇某一返回點情況的產(chǎn)生。

（三）模型求解

多行程車輛路徑問題屬于NP-hard難題，帶有同時取送隨機需求的MTVRP模型求解難度增加，禁忌搜索算法通過使用禁忌表和藐視規(guī)則可避免算法陷入局部最優(yōu)，實現(xiàn)全局最優(yōu)化[17-19]，故采用禁忌算法進行求解。針對Model Π，設(shè)計嵌套隨機模擬的變鄰域禁忌搜索算法（variable neighborhood Tabu Search，VNTS）求解得到優(yōu)化方案，具體步驟如下：

Step 1：設(shè)置算法參數(shù)：禁忌長度、禁忌表、算法最大迭代次數(shù)、控制最優(yōu)解未改進最大次數(shù)、候選解個數(shù)、置信度水平及隨機模擬次數(shù)。

Step 2：生成初始解。隨機產(chǎn)生路徑序列，采用解碼方案生成初始路徑序列Initial_TSP、初始解Initial_Sol，并設(shè)置當(dāng)前路徑序列Current_TSP=Initial_TSP、當(dāng)前解Current_Sol=Initial_Sol。

Step 3：評價初始解。計算Initial_Sol的目標(biāo)函數(shù)值f,若不滿足約束條件，則令f=f+M,其中M是一個很大的正數(shù)。

Step 4：生成候選解。對Current_TSP進行鄰域結(jié)構(gòu)變換，采用解碼方案得到候選解集Candidate_Sol。

Step 5：評價候選解。計算Candidate_Sol的目標(biāo)函數(shù)值f,若不滿足約束條件，則令f=f+M。

Step 6：更新禁忌表、選取最優(yōu)候選解Best_Candidate_Sol。

Step 6.1：若Best_Candidate_Sol滿足藐視規(guī)則，則將其對應(yīng)的禁忌對象替換禁忌表中最早進入的禁忌對象，同時更新Current_Sol=Best_Candidate_Sol，全局最優(yōu)解Best_Sol= Best_Candidate_Sol；

Step 6.2：若Best_Candidate_Sol不滿足藐視規(guī)則，則判斷其對應(yīng)的禁忌對象是否禁忌在禁忌表，若無，則從除Best_Candidate_Sol之外的候選解集中挑選出非禁忌的最優(yōu)解，用其對應(yīng)的禁忌對象替換禁忌表中最早進入的禁忌對象，同時更新Current_Sol=Best_Candidate_Sol。

Step 7：終止條件判斷。若滿足終止準(zhǔn)則，輸出Best_Sol；否則重復(fù)Step4-Step6。

其中，本文采用3種鄰域操作進行變換參與算法迭代：insert鄰域變換、reverse鄰域變換和swap鄰域變換，在算法迭代時隨機選擇其中一種鄰域變換方式作用于路徑編碼，見圖2；在考慮目標(biāo)函數(shù)值的情況下，采用基于適配值的藐視規(guī)則；算法采用兩層嵌套終止準(zhǔn)則，外層終止準(zhǔn)則為：當(dāng)?shù)螖?shù)達(dá)到預(yù)設(shè)值時，算法終止；里層嵌套終止準(zhǔn)則為：當(dāng)前最優(yōu)解未改進次數(shù)達(dá)到預(yù)設(shè)值時，跳出算法終止搜索。

圖2：鄰域結(jié)構(gòu)變換

三、算例驗證與結(jié)果分析

（一）實驗算例

本文研究的考慮隨機同時取送需求的多行程車輛路徑問題模型，尚無標(biāo)準(zhǔn)測試算例，故在 Prodhon提出的選址-路徑問題標(biāo)準(zhǔn)算例集20-5-1a之上，根據(jù)研究內(nèi)容進行擴展和選取得到本文測試算例。配送中心坐標(biāo)為(6,7)，該配送中心擁有12臺可供配送的車輛，以及20個位置坐標(biāo)已知、需求未知的客戶點。單位車輛派遣成本ck=2500，單位車輛運輸成本cv=25，車輛的最大載貨量Qv=220。已知在配送開始前存在20個送貨需求和取貨需求分別服從λ為50和35的泊松分布、位置信息如表1的客戶點。

表1：客戶節(jié)點位置坐標(biāo)

（二）實驗結(jié)果與分析

本文應(yīng)用MATLAB R2014a編程軟件進行仿真，VNTS算法參數(shù)為禁忌長度table_lengt?=20，最大迭代次數(shù)max _iter=400，控制最優(yōu)解未改進最大次數(shù)stable_iter=100，候選解個數(shù)candidate_count=60。結(jié)合算例進行15次仿真實驗,并記錄每次仿真結(jié)果，見表2。

表2：算例仿真結(jié)果

由表2可知：

1.若初始目標(biāo)函數(shù)值與實際目標(biāo)函數(shù)值相等，說明在實際配送過程中wijk未超出車輛最大載重量，車輛路徑無需進行實時策略調(diào)整；若初始目標(biāo)函數(shù)值與實際目標(biāo)函數(shù)值不相等，說明在實際配送過程中存在wijk超出車輛最大載重量，因此車輛路徑需要根據(jù)客戶實際需求情況進行策略調(diào)整。

2.在 15次的仿真實驗結(jié)果中，車輛的實際配送路線與初始優(yōu)化路徑一致的情形只存在少數(shù)，因此多數(shù)情況下車輛在實際配送階段需要進行實時策略調(diào)整。

隨機選取 15次仿真實驗結(jié)果中某個初始優(yōu)化方案為例進行分析，選取優(yōu)化路徑方案為車輛 1：0-1-4-18-20-0，車輛2：0-2-17-9-10-0，車輛3：0-11-6-8-19-0，車輛4：0-16-15-14-12-0，車輛 5：0-3-7-5-13-0，總成本為2.2388×104。實際配送過程中，在沒有采取任何實時策略的情況下，出現(xiàn)了配送失敗的客戶點，造成配送路徑的中斷，中斷情況如圖3所示。在路線2中，客戶點9開始出現(xiàn)路徑中斷，導(dǎo)致車輛2配送后序客戶點10任務(wù)失敗，在路線3中，客戶點8開始出現(xiàn)路徑中斷，造成車輛3配送客戶點19任務(wù)失敗。

圖3 ：配送失敗路徑圖

在實際配送過程中，在采取基于隨機需求分布概率的實時柔性點策略的情況下，車輛配送路徑如圖4所示。調(diào)整后路徑方案為車輛 1：0-1-4-18-20-0，車輛 2：0-2-17-9-0-10-0，車輛 3：0-11-6-8-0-19-0，車輛4：0-16-15-14-12-0，車輛5：0-3-7-5-13-0，總成本為2.4587×104。

圖4：多行程策略調(diào)整路徑圖

初始優(yōu)化路徑是在多種約束下使得總成本最小化的最優(yōu)路徑方案，實時柔性點策略調(diào)整的路徑方案在初始路徑基礎(chǔ)上沒有產(chǎn)生大幅度的變動，且較于無調(diào)整策略下實際配送產(chǎn)生的中斷情況，柔性點策略下的多行程路徑方案能避免不恰當(dāng)?shù)姆祷攸c，因此，實時柔性點的多行程路徑調(diào)整策略具有有效性。

四、結(jié)論

多行程配送由于允許車輛在運輸途中往返，因此有別于一般物流。在多行程配送中，配方考慮同時取送貨需求及其隨機性，建立多行程配送車輛路徑優(yōu)化模型；針對模型有同時取送、隨機參數(shù)和多行程動態(tài)特征，提出實時柔性點調(diào)整策略，引入隨機機會約束規(guī)則，設(shè)計了嵌套隨機模擬的變鄰域禁忌搜索算法相結(jié)合的混合算法尋求最優(yōu)配送路徑。得出以下結(jié)論：

1.低成本配送和高水平服務(wù)是物流企業(yè)的長期目標(biāo)，考慮同時取送貨的多行程物流配送可避免車輛能力浪費，提高配送質(zhì)量，因此具有較強的現(xiàn)實意義。

2.采用“實時柔性點”多行程路徑調(diào)整策略，可有效降低因同時取送隨機需求造成路徑中斷產(chǎn)生的額外成本，且避免路徑中斷，符合實際情境。

3.用隨機模擬嵌套禁忌搜索算法相結(jié)合的混合求解算法，能有效尋求最優(yōu)路徑，降低無效路徑生成的概率。

由于各種因素的存在，現(xiàn)實中的多行程車輛配送網(wǎng)絡(luò)較為復(fù)雜，本文仍存在一些不足之處，如本文并沒有考慮到客戶信息的多動態(tài)性，且配送中心單一，這將是下一步研究的重點。