許闖來，胡堅堃，黃有方

上海海事大學(xué) 物流科學(xué)與工程研究院，上海201306

1 引言

隨著我國經(jīng)濟(jì)的穩(wěn)步發(fā)展，互聯(lián)網(wǎng)消費(fèi)環(huán)境的日益成熟和企業(yè)信息化的完善，進(jìn)一步推進(jìn)了互聯(lián)網(wǎng)消費(fèi)方式的普及。來自國家郵政局公布的數(shù)據(jù)[1]顯示：2017年“雙11”當(dāng)天，主要電商企業(yè)全天共產(chǎn)生快遞物流訂單8.5億件，同比增長29.4%；全天各郵政、快遞企業(yè)共處理3.31億件，同比增長31.5%。電子商務(wù)在不同消費(fèi)群體中的普及為快遞行業(yè)帶來了巨大的發(fā)展商機(jī)，同時也要求城市配送活動在服務(wù)能力上更高效，低成本、準(zhǔn)時性地滿足多樣化的物流需求。目前我國快遞企業(yè)發(fā)展水平參差不齊，都面臨著專業(yè)化程度低，資源配置不均等問題[2]。近幾年“雙十一購物節(jié)”所引發(fā)的快遞“爆倉”事件，使得物流配送系統(tǒng)承載著巨大的壓力[3]。快遞需求的集中爆發(fā)直接表現(xiàn)為快件量的倍數(shù)增長，大量快件堆積在分撥中心[4]。為解決這個問題，快遞公司為分撥中心招聘了大量外包人員以及部分職能崗位的員工。該方法雖然可以幫助提升分撥中心的裝卸效率，但是并不能有效解決貨物積壓的問題，相反會加劇分撥中心的運(yùn)作壓力。因此合理并有效地規(guī)劃配送車輛路徑是避免“快遞變慢遞”的根本之法，也是公司控制人力投入成本，確?？蛻舭磿r收貨，提升客戶滿意度和品牌競爭力的重要保障。

車輛路徑問題來源于交通運(yùn)輸，最早是由Dantzig和Ramser[5]于1959年提出。它是指一定數(shù)量的客戶，各自有不同的貨物需求，在一定的約束下，配送中心安排車隊并設(shè)計一套運(yùn)輸路線，滿足貨物在客戶點的運(yùn)輸[6]。車輛路徑優(yōu)化是一個NP難問題，可選車輛路徑隨著客戶數(shù)量的增加而呈現(xiàn)階乘般的增長。對于一個有15個頂點的VRP問題，其可行解的數(shù)目將達(dá)到1 012個[7]?，F(xiàn)有的快遞分撥物流網(wǎng)絡(luò)設(shè)計主要針對確定性需求基礎(chǔ)上對分撥網(wǎng)路的構(gòu)建，容易受到客戶點運(yùn)輸需求劇烈變動的影響[8-9]。Baldacci等[10]回顧了有容量約束進(jìn)行VRP精確算法的發(fā)展，并對它們的計算性能進(jìn)行比較。張濤等[11]將熱軋生產(chǎn)批量計劃歸結(jié)為不確定車輛數(shù)的車輛路徑問題，并用遺傳算法和禁忌搜索算法相結(jié)合的混合算法對問題進(jìn)行求解。

在不確定車輛路徑問題上，研究人員大多采用隨機(jī)規(guī)劃或者模糊規(guī)劃的方法。戎麗霞[12]針對具有不確定需求的車輛路徑問題，建立了基于模糊可信性理論的模糊機(jī)會約束規(guī)劃模型，利用基于模糊模擬的混合遺傳算法進(jìn)行求解。邢占文[13]以啟發(fā)式算法為基礎(chǔ)，提出了勘探搜索算法和基于非精確距離矩陣的共軛優(yōu)化算法求解呼和浩特市內(nèi)帶有顧客需求不確定性和車速度不確定的車輛路徑問題。Chung[14]等運(yùn)用魯棒優(yōu)化方法解決結(jié)合交通動態(tài)性和需求不確定性的網(wǎng)絡(luò)設(shè)計問題。Yu[15]應(yīng)用魯棒優(yōu)化模型處理隨機(jī)物流問題，并設(shè)計了求解方法。該文建立魯棒線性規(guī)劃模型，并通過對比該解與對應(yīng)確定性模型的解來描述模型的魯棒性。孫華[16]用魯棒優(yōu)化的方法求解了應(yīng)急管理下需求和旅行時間不確定的車輛路徑問題。伍方凌[17]首先建立了確定性帶時間窗的班輪支線網(wǎng)絡(luò)優(yōu)化模型，并在此基礎(chǔ)上提出集裝箱班輪支線網(wǎng)絡(luò)魯棒優(yōu)化模型對不確定條件下船舶的運(yùn)輸航線進(jìn)行優(yōu)化選擇。管峰等[18]采用魯棒優(yōu)化模型解決需求不確定的、有容量限制的車輛路徑問題，證明雖然魯棒優(yōu)化模型的最優(yōu)目標(biāo)函數(shù)值較大，但能有效保證路徑在需求波動下的可行性。2017年，熊瑞琦等[19]針對危險貨物配送路徑對不確定因素敏感度較高的問題，提出了魯棒性可調(diào)的多配送中心危險貨物配送路徑魯棒優(yōu)化方法。本文通過引入基于情景集的魯棒優(yōu)化模型，先對物流分撥網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行經(jīng)濟(jì)性分析，并與運(yùn)輸時效優(yōu)先下的成本進(jìn)行比較，分析兩種選擇下的成本和總旅行時間差異；將車輛數(shù)，旅行時間和成本最低作為模型的3個因變量，通過改進(jìn)蟻群算法，并用Matlab求解模型，給出決策方案，減緩由于需求波動而帶來的不利影響，為快遞企業(yè)選擇合適的分撥路徑提供解決方案。

2 快遞配送物流網(wǎng)絡(luò)魯棒優(yōu)化模型的建立

2.1 問題描述

本文不考慮分撥中心的裝貨時間?？爝f企業(yè)的VRP模型通?？紤]一個配送中心同時服務(wù)多個需求客戶點的情況：每個客戶點的位置已知，配送中心有足夠可使用的配送車輛，且每輛車的裝載容量一定；每個客戶只能被服務(wù)一次；每條線路上的客戶需求不能超過車輛的最大裝載容量；客戶需求量超出車輛額定容量的限制，得不到運(yùn)輸?shù)牟糠纸o予懲罰。完成配送任務(wù)的車輛最終返回配送中心。本文模型求解的目標(biāo)函數(shù)是總成本最小，基于確定需求利用魯棒優(yōu)化的思想，對物流配送網(wǎng)絡(luò)進(jìn)行設(shè)計和優(yōu)化，同時利用不同的情景集來描述需求的不確定性問題。

2.2 模型建立

本文是由一個配送中心向多個客戶點進(jìn)行配送。首先建立確定需求下的以成本最低為目標(biāo)函數(shù)的確定性模型，然后在此基礎(chǔ)上建立關(guān)于需求量的魯棒性模型。

設(shè)車輛路徑網(wǎng)絡(luò)圖為G(V,A)，其中V={v0,v1,…,vn}為頂點集合；集合A={(Vi,Vj):i≠j∧i,j∈V}為弧集合；定義v0為配送中心；v1～n為需求客戶點；K為自有同質(zhì)車輛數(shù)目；D為外包同質(zhì)車輛數(shù)目；N={0,1,2,…,n}表示配送中心和客戶點集合；QV為車輛的裝載容量；gi為各客戶點的需求量，且滿足gi≤QV；dij為客戶點i和j之間的距離；tij為客戶點i和j之間的行駛時間；Cf為單位體積燃料成本；Cd為單位裝卸成本；C1為自有車輛固定費(fèi)用；C2為外包車輛固定費(fèi)用；ρ為配送車輛單位油耗；[ai,bi]為客戶點i指定的服務(wù)時間窗；Nc為完成一個配送班次所用的自有車輛的數(shù)量；Nd為完成一個配送班次所用的外包車輛的數(shù)量；Xijk為當(dāng)車輛K經(jīng)過客戶i到達(dá)客戶j時為1，否則為0；yk為當(dāng)車輛K被使用時為1，否則為0。

2.3 需求不確定下的快遞配送路徑模型

魯棒優(yōu)化模型是以確定性需求模型為基礎(chǔ)，所以首先建立確定性需求下快遞配送物流網(wǎng)絡(luò)模型。

確定性需求的車輛路徑問題模型為：

其中，式（1）為成本最小的目標(biāo)函數(shù)，包括司機(jī)工資、燃油費(fèi)用、裝卸成本和車輛固定成本；式（2）表示所有提供服務(wù)的車輛都必須從配送中心出發(fā)，并最終返回到配送中心；式（3）表示每個客戶點有且只有一輛車到達(dá)和服務(wù)；式（4）表示抵達(dá)客戶的車同時也是離開客戶的車；式（5）約束了車輛的最大載荷；式（6）中，等式左邊表示路徑中投入使用的車輛總數(shù)，是自有車輛數(shù)和外包車輛數(shù)之和；式（7）表示車輛在兩個客戶點之間的行駛要保持連續(xù)性；式（8）為參數(shù)變量的約束值。

為了更好地研究各客戶需求量不確定的情況，現(xiàn)將魯棒優(yōu)化的思想運(yùn)用到快遞配送網(wǎng)絡(luò)的設(shè)計問題中。假設(shè)存在S個需求情景，每個需求情景中含有不確定需求d，每種情景發(fā)生的概率對應(yīng)為ps，對應(yīng)情景S下客戶j的需求量為

基于情景集s下的魯棒優(yōu)化模型的目標(biāo)函數(shù)為：

其中，式（9）是基于情景集的魯棒優(yōu)化的目標(biāo)函數(shù)原型，第一部分考慮了偏離均值的情況，第二部分通過加入λ倍偏差以體現(xiàn)決策者的風(fēng)險偏好，第三部分為懲罰函數(shù)；約束式（10）～（12）保證了得出的魯棒最優(yōu)解能滿足所有情景。

現(xiàn)將確定性需求下的快遞配送路徑模型加入到基于情景集S下的魯棒優(yōu)化模型，最終目標(biāo)函數(shù)模型為：

修改和新添加的約束條件：

其中，式（13）表示任意情景S下魯棒優(yōu)化的目標(biāo)函數(shù)，即將公式（9）中的ξs替換成公式（1）中的，其余部分保持不變；式（14）松弛了確定性模型中車輛最大載荷量的約束，允許運(yùn)輸需求大于車輛最大載荷量，且兩者之間存在偏差zs，即如果客戶點i→j實際需求量小于或等于車輛的最大載荷量，則zs=0，否則zs=，表示存在運(yùn)輸量為zs的需求得不到滿足，這部分通過式（13）的最后一部分進(jìn)行懲罰；約束式（15）與基于情景集的魯棒優(yōu)化模型中約束式（11）相對應(yīng)，表示解的魯棒性，即對任意情景中的參數(shù)值，模型的解都“接近”最優(yōu)；式（16）為對新添加參數(shù)變量的約束。

3 算法設(shè)計

本文通過構(gòu)建不確定需求的魯棒模型，并與確定需求下的模型結(jié)果進(jìn)行比較。蟻群算法適用于求解規(guī)模較大的組合優(yōu)化問題。同時為了避免陷入局部最優(yōu)，采用2-opt進(jìn)行局部搜索優(yōu)化，易于尋找到全局最優(yōu)解。

采用文獻(xiàn)[20]基礎(chǔ)建立的蟻群算法，算法步驟如下。

步驟1系統(tǒng)初始化：初始化距離dij，設(shè)置迭代次數(shù)iter_max=200，Q=20為環(huán)境初始?xì)埩粜畔⑺亍?/p>

步驟2初始化m只螞蟻，將n個客戶點放入螞蟻的未訪問城市表notVisitk，客戶點需求量qk。

步驟3螞蟻k隨機(jī)選一個客戶點放入螞蟻路徑solutionk，同時從notVisitk將該客戶點刪除。

步驟4根據(jù)公式

計算螞蟻從客戶點i轉(zhuǎn)移到客戶點j的轉(zhuǎn)移概率。

步驟5如果notVisitk不為空，則用輪盤賭法隨機(jī)選擇一個客戶點放入solutionk，同時從notVisitk將該客戶點刪除，比較客戶點j的需求量和車輛剩余容量的大小，若客戶點j的需求量大于車輛剩余容量，則車輛返回配送中心開始新一輪路線尋找，否則重新選擇客戶點。

步驟6對螞蟻k構(gòu)造解路徑用2-opt進(jìn)行局部搜索優(yōu)化，避免陷入局部最優(yōu)。

步驟7根據(jù)公式τij( t+1)=(1 -ρ)τij(t)+Δτij更新信息素濃度，其中ρe∈( 0 ,1)。

步驟8若迭代次數(shù)小于iter_max，則轉(zhuǎn)步驟2；否則程序結(jié)束，輸出結(jié)果。

4 算例分析

假設(shè)坐標(biāo)點1是某快遞公司在蘇州設(shè)立的一個大型分撥中心（本文只考慮配送作業(yè)），設(shè)其坐標(biāo)為[12，6]。該快遞公司在蘇州市區(qū)內(nèi)共有55個網(wǎng)點；配送車輛每天進(jìn)行5個班次的運(yùn)輸，配送開始時間分別為06：20、08：50、13：10、15：45和18：20，每個配送班次的作業(yè)時間為2.5 h；客戶坐標(biāo)在邊長為40的矩形中隨機(jī)產(chǎn)生，需求為隨機(jī)從[100，300]取整，設(shè)為a0，如表1所示；同時表1中的需求數(shù)據(jù)也將用于計算雙十一期間情景S的服務(wù)時間，公式10+0.2×ps×(gsj-a0)，此部分?jǐn)?shù)據(jù)不再單獨(dú)列出；非雙十一期間各客戶點服務(wù)時間為10 min；公司現(xiàn)階段擁有20輛1.5 T自有車輛，裝載容量為700件。

燃油成本（元）=單位體積的燃料成本×滿載耗油量×客戶點之間的距離?？偮眯袝r間（min）=運(yùn)輸時間+服務(wù)時間。

設(shè)93#汽油價格為7.65元/L[21]；滿載耗油量為0.06 L/km；自有車輛固定成本為500元/輛；外包車輛固定成本為1 000元/輛；車輛行駛速度為50 km/h；司機(jī)工資為40元/h與1.6元/km；單位裝卸成本為2元/件；若存在兩條或兩條以上運(yùn)輸路徑總旅行時間小于時間窗2.5 h，則使用同一輛車進(jìn)行分次運(yùn)輸，并優(yōu)先使用自有車輛。

本文假設(shè)該分撥中心在雙十一期間預(yù)測了三種可能存在的需求情景，發(fā)生的概率分別是0.3、0.3和0.4，螞蟻數(shù)量為80，信息素殘留系數(shù)為0.5，信息啟發(fā)因子為0.1，期望啟發(fā)式因子為0.5。各情景下客戶點的需求量如表2所示。另設(shè)定魯棒模型參數(shù)λ為1，?為100，算法迭代200次。

運(yùn)用Matlab軟件分別對確定性模型和魯棒性模型求解。原確定需求成本為71 372元，總旅行時間為1 944 min，路徑圖見圖1。由于路徑1-19-16-1和1-30-28-25-1總旅行時間小于150 min，因此可以使用同一輛車進(jìn)行分次運(yùn)輸。同理，路徑1-9-6-27-1和1-23-22-1、1-31-35-1和1-36-37-33-1、1-49-55-1和1-5-3-1、1-21-17-1和1-50-54-1、1-24-20-42-1和1-13-7-1、1-39-40-1和1-2-4-1、1-46-44-1和1-32-26-1也分別使用一輛自有車輛進(jìn)行運(yùn)輸，其余路徑分別配置一輛自有車輛，共需要自有車輛15輛。其結(jié)果如表3所示。

魯棒優(yōu)化模型的成本為92 433元，總旅行時間為2 935 min，路徑圖見圖2。其中路徑1-16-1和1-27-7-1、1-55-47-1和1-19-23-1、1-31-1和1-43-40-1、1-50-1和1-22-20-1、1-17-29-1和1-18-1、1-39-32-1和1-13-21-1、1-35-34-1和1-26-38-1、1-46-1和1-3-5-1、1-44-1和1-24-6-1分別使用一輛自有車輛進(jìn)行運(yùn)輸，其余路徑分別配置一輛自有車輛，因此共需要自有車輛23輛，外包車輛3輛。結(jié)果如表4所示。

表1 客戶點坐標(biāo)及需求 件

表2 情景集下客戶點的運(yùn)輸需求

圖1 原確定需求車輛路徑

為了進(jìn)一步比較魯棒模型的優(yōu)勢，本文將三種情景集的運(yùn)輸需求分別代入確定性模型計算相應(yīng)的最優(yōu)值并與魯棒優(yōu)化模型進(jìn)行比較，同時比較兩者在一輪運(yùn)輸班次結(jié)束之后所花費(fèi)的總旅行時間的差異，其結(jié)果如表5所示。對比發(fā)現(xiàn)：在成本方面，成本最優(yōu)條件下魯棒模型的解與原需求的解差距最大，而與所有情景下的成本差距保持在10%左右。一方面是由于需求增加導(dǎo)致成本上漲；另一方面，由于魯棒模型是綜合考慮所有情景條件得到的，因此所有情景都可以接受，故差距穩(wěn)定，證實了魯棒模型的抗干擾性和高成本的代價；而兩種情況各自對應(yīng)的總成本之間差距較小，環(huán)比的最大值僅為1.90%。在旅行時間方面，一輪行車結(jié)束的總旅行時間存在較大差異，最多可節(jié)約47 min。由此可見，快遞企業(yè)可以在成本沒有大幅度變動的前提下優(yōu)先考慮運(yùn)輸時效，以減緩分撥中心壓力，保證快件及時送達(dá)配送站點。

表3 確定性模型最優(yōu)解 min

圖2 魯棒模型車輛路徑

表4 魯棒優(yōu)化模型最優(yōu)解min

為找出公司規(guī)模與業(yè)務(wù)量和總成本之間的相關(guān)性，將需求在[200，700]范圍內(nèi)，間隔50取整，算法運(yùn)行結(jié)果見圖3。分析發(fā)現(xiàn)：隨著公司業(yè)務(wù)量的增加，且當(dāng)超出公司自有車輛的規(guī)模時，運(yùn)營成本增長較快；運(yùn)輸費(fèi)用的上升是導(dǎo)致企業(yè)利潤增長緩慢的原因之一。

為更加直觀地對比算法收斂性能，運(yùn)用Matlab軟件，以原確定需求數(shù)據(jù)為背景，采用傳統(tǒng)蟻群算法和基于2-opt的蟻群算法對確定性模型進(jìn)行求解，設(shè)置迭代次數(shù)為500次，結(jié)果見圖4?？梢钥闯觯合噍^于基本蟻群算法，改進(jìn)后算法的探索性和收斂性強(qiáng)，求解的目標(biāo)函數(shù)值更優(yōu)。但由于本文算法添加了2-opt，故問題求解時間略有增加。

5 結(jié)論及未來工作

本文在確定性模型的基礎(chǔ)上，選用基于情景集下的魯棒優(yōu)化方法優(yōu)化分撥中心的配送網(wǎng)絡(luò)，為了避免蟻群算法在求解過程中陷入局部最優(yōu)，采用2-opt進(jìn)行局部搜索優(yōu)化。并創(chuàng)新性地通過變化的快件數(shù)量，對客戶服務(wù)時間進(jìn)行重新分配；通過對每條運(yùn)輸路徑的時間計算，若存在兩條或兩條以上路徑的旅行時間之和滿足時間窗要求，則使用同一輛車進(jìn)行配送，以實現(xiàn)對自有車輛的最大利用。提出的模型能夠在需求大幅浮動的情況下控制成本，同時保證每個運(yùn)輸班次總旅行時間的合理性，提高了企業(yè)的運(yùn)作效率。

表5 確定性模型和魯棒模型的成本及總旅行時間差異對比

圖3 公司規(guī)模與業(yè)務(wù)量和運(yùn)輸成本的相關(guān)性

圖4 原確定需求下算法性能對比

在今后的工作中，會將客戶點的需求進(jìn)行拆分，在充分利用自有車輛的前提下，提高車輛裝載率，以此實現(xiàn)設(shè)計路線的合理性，同時希望能夠發(fā)現(xiàn)更高效的算法改進(jìn)策略。