不確定需求下快遞配送網(wǎng)絡(luò)魯棒優(yōu)化

許闖來(lái)，胡堅(jiān)堃，黃有方

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

1 引言

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

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

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

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

2.1 問(wèn)題描述

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

2.2 模型建立

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

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

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

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

確定性需求的車(chē)輛路徑問(wèn)題模型為：

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

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

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

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

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

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

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

3 算法設(shè)計(jì)

本文通過(guò)構(gòu)建不確定需求的魯棒模型，并與確定需求下的模型結(jié)果進(jìn)行比較。蟻群算法適用于求解規(guī)模較大的組合優(yōu)化問(wèn)題。同時(shí)為了避免陷入局部最優(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個(gè)客戶(hù)點(diǎn)放入螞蟻的未訪(fǎng)問(wèn)城市表notVisitk，客戶(hù)點(diǎn)需求量qk。

步驟3螞蟻k隨機(jī)選一個(gè)客戶(hù)點(diǎn)放入螞蟻路徑solutionk，同時(shí)從notVisitk將該客戶(hù)點(diǎn)刪除。

步驟4根據(jù)公式

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

步驟5如果notVisitk不為空，則用輪盤(pán)賭法隨機(jī)選擇一個(gè)客戶(hù)點(diǎn)放入solutionk，同時(shí)從notVisitk將該客戶(hù)點(diǎn)刪除，比較客戶(hù)點(diǎn)j的需求量和車(chē)輛剩余容量的大小，若客戶(hù)點(diǎn)j的需求量大于車(chē)輛剩余容量，則車(chē)輛返回配送中心開(kāi)始新一輪路線(xiàn)尋找，否則重新選擇客戶(hù)點(diǎn)。

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

燃油成本（元）=單位體積的燃料成本×滿(mǎn)載耗油量×客戶(hù)點(diǎn)之間的距離。總旅行時(shí)間（min）=運(yùn)輸時(shí)間+服務(wù)時(shí)間。

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

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

運(yùn)用Matlab軟件分別對(duì)確定性模型和魯棒性模型求解。原確定需求成本為71 372元，總旅行時(shí)間為1 944 min，路徑圖見(jiàn)圖1。由于路徑1-19-16-1和1-30-28-25-1總旅行時(shí)間小于150 min，因此可以使用同一輛車(chē)進(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也分別使用一輛自有車(chē)輛進(jìn)行運(yùn)輸，其余路徑分別配置一輛自有車(chē)輛，共需要自有車(chē)輛15輛。其結(jié)果如表3所示。

魯棒優(yōu)化模型的成本為92 433元，總旅行時(shí)間為2 935 min，路徑圖見(jiàn)圖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分別使用一輛自有車(chē)輛進(jìn)行運(yùn)輸，其余路徑分別配置一輛自有車(chē)輛，因此共需要自有車(chē)輛23輛，外包車(chē)輛3輛。結(jié)果如表4所示。

表1 客戶(hù)點(diǎn)坐標(biāo)及需求 件

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

圖1 原確定需求車(chē)輛路徑

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

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

圖2 魯棒模型車(chē)輛路徑

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

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

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

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

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

表5 確定性模型和魯棒模型的成本及總旅行時(shí)間差異對(duì)比

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

圖4 原確定需求下算法性能對(duì)比

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