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

引言

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

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

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

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

一、問題描述及模型建立

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

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

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

假設(shè)2 假設(shè)客戶取送貨需求服從隨機(jī)分布，只有當(dāng)車輛到達(dá)該點時其需求才會被確認(rèn)，取送貨物可以進(jìn)行混合運(yù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均是隨機(jī)變量，服從相互獨(dú)立的離散隨機(jī)概率分布，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）為客戶點進(jìn)出平衡約束；式（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)換與求解

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

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

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

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

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

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

Step 3：根據(jù)隨機(jī)取送需求矩陣，檢驗隨機(jī)約束條件。如果隨機(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足該機(jī)會約束生成路徑方案，在實際配送過程中仍然會出現(xiàn)線路中斷，且取送一體化配送方式增大了路徑失敗的可能性，故路徑需要進(jìn)行實時調(diào)整。在調(diào)整策略上現(xiàn)有文獻(xiàn)多采用失敗點返回策略[15-16]，也有學(xué)者研究采取失敗點之前提前返回的預(yù)補(bǔ)貨策略[11]，針對客戶的隨機(jī)雙向需求，本文提出基于隨機(jī)需求分布概率的柔性點策略進(jìn)行實時調(diào)整車輛路徑。

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

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

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

（三）模型求解

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

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

Step 2：生成初始解。隨機(jī)產(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進(jìn)行鄰域結(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)的禁忌對象替換禁忌表中最早進(jìn)入的禁忌對象，同時更新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)的禁忌對象替換禁忌表中最早進(jìn)入的禁忌對象，同時更新Current_Sol=Best_Candidate_Sol。

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

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

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

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

（一）實驗算例

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

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

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

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

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

由表2可知：

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

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

隨機(jī)選取 15次仿真實驗結(jié)果中某個初始優(yōu)化方案為例進(jìn)行分析，選取優(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 ：配送失敗路徑圖

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

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

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

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

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