一種“效率-公平-運(yùn)力”多維權(quán)衡的需求可拆分配送方法

王建偉，劉旭旭，付鑫*，楊洋，崔夢妍

(1.長安大學(xué)，運(yùn)輸工程學(xué)院，西安 710064；2.北京航空航天大學(xué)，a.交通科學(xué)與工程學(xué)院，b.車路協(xié)同與安全控制北京市重點(diǎn)實(shí)驗(yàn)室，北京 100191）

0 引言

自然災(zāi)害和重大社會公共事件等各類突發(fā)事件所引發(fā)的人員傷亡、財產(chǎn)損失及環(huán)境惡化等問題日益顯著。當(dāng)突發(fā)事件發(fā)生后，綜合考量各類救災(zāi)目標(biāo)需求，將各類應(yīng)急物資配送至受影響區(qū)域可降低由突發(fā)事件造成的損失。在研究應(yīng)急物資配送問題時，已有研究多選擇以配送總耗時最少[1]或路程最短[2]為目標(biāo)函數(shù)，將配送效率最優(yōu)作為應(yīng)急物資配送首要目標(biāo)，以降低災(zāi)害影響。而當(dāng)面臨多受災(zāi)點(diǎn)情景時，各個受災(zāi)點(diǎn)間的配送差異性也需受到關(guān)注。隨著“人道物流”的提出，有學(xué)者將配送公平性作為應(yīng)急物資配送的切入點(diǎn)。Cook 等[3]考慮供應(yīng)物資的不確定性，在兩階段人道主義供應(yīng)鏈構(gòu)建背景下，通過將最小化未滿足需求作為目標(biāo)，把配送公平性融入應(yīng)急物資配送路徑優(yōu)化問題中。曲沖沖等[4]則同時考慮配送效率與配送公平性因素，建立多目標(biāo)規(guī)劃模型以解決大規(guī)模地震后應(yīng)急物資配送問題。除需要考慮配送效率與配送公平外，突發(fā)事件還具有不確定性[5]，可能會發(fā)生路網(wǎng)損害、運(yùn)力不足等情況，因此，決策者將有限運(yùn)力、可用運(yùn)輸資源最少納入影響因素范圍具有必要性。吳珂等[6]將使用車輛數(shù)最小為優(yōu)化目標(biāo)，構(gòu)建應(yīng)急配送車輛調(diào)度模型，以保證應(yīng)急物資在時間窗范圍內(nèi)到達(dá)受災(zāi)點(diǎn)。上述研究雖然在目標(biāo)設(shè)定上存在差異，但其均假設(shè)每個受影響點(diǎn)只能被車輛訪問一次，并且各點(diǎn)物資需求量小于單車最大載重量。然而，在突發(fā)事件發(fā)生后，會產(chǎn)生多個受影響點(diǎn)短時間內(nèi)產(chǎn)生不同規(guī)模與類型物資需求，在真實(shí)救援場景中，各受影響點(diǎn)物資需求量往往超過單一車輛運(yùn)輸規(guī)模，若仍要求每個受影響點(diǎn)只能由一輛救援車輛提供運(yùn)輸服務(wù)，則會導(dǎo)致模型適用性受到影響。因此，有必要將需求可拆分這一約束條件引入應(yīng)急物資配送問題研究。

與傳統(tǒng)車輛路徑問題相比，需求可拆分車輛路徑問題一般允許需求點(diǎn)需求量大于單車容量，可將各需求點(diǎn)物資需求根據(jù)車輛剩余載重量進(jìn)行拆分，使其被多車多次訪問[7]，更加符合應(yīng)急物資配送實(shí)際情況。Zhang等[8]將需求可拆分問題引入海上應(yīng)急物流問題中，以解決運(yùn)輸網(wǎng)絡(luò)不確定情況下的應(yīng)急物流作業(yè)問題。Bortfeldt等[9]建立了一個三維裝載約束下的需求可拆分車輛路徑問題，通過3種算例證明拆分交付不僅在一維裝載下更優(yōu)，在三維裝載約束下得到的結(jié)果也更有益。需求可拆分車輛路徑問題可以提高車輛利用率，降低使用車輛數(shù)，這一特點(diǎn)對于應(yīng)對突發(fā)事件后大量物資運(yùn)輸需求或者可用運(yùn)輸資源受限問題具有更好適用性。

綜上所述，為考量多目標(biāo)場景下的應(yīng)急物資配送問題，本文在模型構(gòu)建時擬加入需求可拆分條件，并且為探究效率、公平、運(yùn)力等因素對應(yīng)急物資配送方案的影響程度，擴(kuò)大應(yīng)急物資配送模型的適用范圍，以配送時間最短、加權(quán)時間攀比值最小和使用車輛數(shù)最少為目標(biāo)函數(shù)，構(gòu)建在有限運(yùn)力條件下，權(quán)衡“效率-公平-運(yùn)力”多維需求的可拆分應(yīng)急物資配送模型，并設(shè)計改進(jìn)的蟻群算法求解模型。

1 問題描述與模型建立

1.1 問題描述

本文研究問題為：突發(fā)事件發(fā)生后，單種物資、單種車型、單供應(yīng)點(diǎn)、多需求點(diǎn)、帶時間窗、多目標(biāo)的需求可拆分應(yīng)急物資配送問題，模型假設(shè)如下：

(1)僅有一個物資供應(yīng)點(diǎn)，且該供應(yīng)點(diǎn)物資儲備量已知；

(2)各需求點(diǎn)物資需求量已知；

(3)物資供應(yīng)點(diǎn)物資儲備量等于各需求點(diǎn)總需求量；

(4)各需求點(diǎn)最多被訪問2次；

(5)不考慮道路損毀等意外影響，且路網(wǎng)節(jié)點(diǎn)、路段距離和通達(dá)性已知；

(6)配送車輛型號大小相同，車輛最大載重量均為45 t；

(7)車輛完成服務(wù)后應(yīng)返回物資供應(yīng)點(diǎn)；

(8)各受災(zāi)點(diǎn)僅有右時間窗約束(即最晚到達(dá)時間)，當(dāng)車輛到達(dá)時間超出右時間窗時不能提供服務(wù)；

(9)各需求點(diǎn)的卸貨時間默認(rèn)為30 min。

1.2 參數(shù)定義

本文模型符號說明如表1所示。

表1 模型符號說明Table 1 Notations description

1.3 模型構(gòu)建

本文總目標(biāo)主要包括配送時間、加權(quán)時間攀比值和車輛使用數(shù)這3 部分。目標(biāo)函數(shù)為總目標(biāo)最小化，即

式中：Z1為配送過程耗時最短，表示配送效率，Z2為以各需求點(diǎn)物資依賴度作為權(quán)重Γi的加權(quán)時間攀比值最小，加權(quán)時間攀比值反映了由物資匱乏時長差異引發(fā)的不公平感，表征配送公平性，；Z3為車輛使用數(shù)最少，表征運(yùn)力，w1、w2、w3為權(quán)重，三者均為正數(shù)且由決策者偏好決定，其對配送方案的具體影響見3.3節(jié)。

約束條件為

式(2)和式(3)表示各點(diǎn)最晚到達(dá)時間計算方法，其中，T0v=0，每個點(diǎn)最多被訪問2 次；式(4)表示各點(diǎn)最晚到達(dá)時間不能超過右時間窗；式(5)表示入度均衡和出度均衡，且車輛在1次行程中至多只能途經(jīng)某需求點(diǎn)1 次；式(6)表示避免子回路約束，其中，N為I的一個真子集；式(7)表示車輛容量限制；式(8)表示所有車輛為某需求點(diǎn)運(yùn)送物資之和等于該需求點(diǎn)的物資需求量，其中，di表示點(diǎn)i的物資需求量；式(9)表示車輛只有訪問某需求點(diǎn)才能對其服務(wù)，其中，dj表示點(diǎn)j的物資需求量；式(10)表示w1,w2,w3取值范圍，三者均為正數(shù)且由決策者偏好決定；式(11)表示各變量類型與范圍。

2 求解算法設(shè)計

2.1 蟻群算法的改進(jìn)

需求可拆分車輛路徑問題為一類非確定性多項式(Non-deterministic Polynomial,NP-hard)問題，本文使用蟻群算法求解模型。為加快蟻群算法搜索速度，避免求解結(jié)果陷入局部最優(yōu)，主要從選擇拆分點(diǎn)、信息素更新和引入變鄰域搜索算子這3方個面改進(jìn)蟻群算法，且當(dāng)解持續(xù)不變時，初始化信息素，以增加隨機(jī)性，具體操作步驟如下：

Step 1 初始化蟻群參數(shù)，迭代次數(shù)F=1。

Step 2 隨機(jī)生成各搜索路徑初始點(diǎn)。

Step 3 根據(jù)時間窗和車輛剩余載重量確定可訪問點(diǎn)集合，并根據(jù)狀態(tài)轉(zhuǎn)移公式選擇下一訪問節(jié)點(diǎn)。

Step 4 計算目標(biāo)函數(shù)值，并選出最優(yōu)解。

Step 5 對最優(yōu)解進(jìn)行變鄰域搜索，得到新解，并判斷新解是否優(yōu)于最優(yōu)解，若是更新最優(yōu)解。

Step 6 判斷F代最優(yōu)解是否等于F-1 代最優(yōu)解，若是，調(diào)整ρ。

Step 7 判斷是否連續(xù)20代最優(yōu)解相同，若是，初始化信息素；否則，更新信息素。

Step 8 判斷迭代次數(shù)是否達(dá)到最大迭代次數(shù)Fmax，若是，輸出當(dāng)前最優(yōu)解；否則F=F+1，并轉(zhuǎn)至Step 2。

2.2 選擇拆分點(diǎn)

本文定義拆分點(diǎn)為需求量大于車輛剩余載重量的點(diǎn)。針對拆分狀態(tài)，將每個需求點(diǎn)進(jìn)行0-1 標(biāo)記，0為未被拆分，1為已拆分。在進(jìn)行拆分點(diǎn)選擇時，若存在拆分狀態(tài)標(biāo)記為1 的需求點(diǎn)，則將其從可訪問點(diǎn)中剔除。

2.3 信息素更新

在每次迭代結(jié)束后，對所有路徑進(jìn)行信息素更新，但只允許目標(biāo)函數(shù)值最小的螞蟻釋放信息素，并為其增加一個獎勵值[10]，信息素更新方式為

式中：εij(F+1) 為F+1 代的點(diǎn)i與點(diǎn)j間信息素濃度；ρF+1為F+1 代的信息素?fù)]發(fā)因子；Δεij(F,F+1) 為兩代間信息素改變量；Q為信息素常量；Rbest為最優(yōu)路線所包含的所有??；Lbest為最優(yōu)路線的長度；Lnow為當(dāng)?shù)贔+1 代最優(yōu)路線的長度。

為加快前期信息素積累速度，自適應(yīng)改變信息素?fù)]發(fā)因子，當(dāng)兩次迭代所得最優(yōu)解相同時，減小信息素?fù)]發(fā)因子；否則，信息素?fù)]發(fā)因子為常數(shù)ρ。信息素?fù)]發(fā)因子公式為

為避免算法陷入局部最優(yōu)，增加選擇多樣性，當(dāng)連續(xù)20 次迭代所得的最優(yōu)解均相同時，對信息素矩陣進(jìn)行初始化操作。

2.4 變鄰域搜索算子

本文采用插入算子、逆轉(zhuǎn)算子和交換算子搜索鄰域解[11]。假設(shè)原始解R=(1,2,3,3,4,5,4)，i=2，j=6，插入算子是將第1 個位置i對應(yīng)的受災(zāi)點(diǎn)插入到第2 個位置j對應(yīng)的需求點(diǎn)后面，得到新解R1=(1,3,3,4,5,2,4)；逆轉(zhuǎn)算子是將i、j間的所有需求點(diǎn)進(jìn)行逆轉(zhuǎn)操作，得到新解R2=(1,5,4,3,3,2,4)；交換算子是交換i、j對應(yīng)需求點(diǎn)，得到新解R3=(1,5,3,3,4,2,4)。

3 實(shí)例分析與討論

3.1 案例描述

在建?；A(chǔ)上，本文根據(jù)2008年汶川地震開展實(shí)例驗(yàn)證。將成都市(編號為0)作為物資供應(yīng)點(diǎn)，為汶川縣、北川縣等12個區(qū)域進(jìn)行急救醫(yī)藥包運(yùn)輸。各地區(qū)傷亡人員情況如表2所示，假設(shè)人均4 個急救醫(yī)藥包[12]，每個醫(yī)藥包重量0.5 kg，生成各受災(zāi)點(diǎn)需求量，根據(jù)所羅門算例中的c101 數(shù)據(jù)生成各點(diǎn)右時間窗。提取在線開放街區(qū)地圖中四川省主干路網(wǎng)(本文指高速公路，一級公路和二級公路)作為各點(diǎn)間原始路網(wǎng)數(shù)據(jù)，使用改進(jìn)Dijkstra算法求得各點(diǎn)間最短距離，并簡化為拓?fù)浣Y(jié)構(gòu)，如圖1所示。

表2 汶川地震各地區(qū)傷亡人員情況Table 2 Casualties of Wenchuan earthquake in various regions

圖1 各點(diǎn)間最短路路網(wǎng)拓?fù)浜唸DFig.1 Topology diagram of shortest road network between points

3.2 案例求解與算法比較

使用Matlab R2018a 編寫算法代碼，相關(guān)參數(shù)設(shè)置如下：螞蟻數(shù)量m=50，最大迭代次數(shù)Fmax=100，轉(zhuǎn)移控制參數(shù)r0=0.95，初始信息素?fù)]發(fā)系數(shù)ρ=0.3，信息素重要程度因子ι=1，啟發(fā)函數(shù)重要程度因子?=5，時間窗重要程度因子ξ=3，物資依賴度重要程度因子ψ=1，更新信息素濃度的常數(shù)?=10，此時假設(shè)決策者無明顯偏好，即w1、w2、w3取值均為1 3，車輛行駛速度為v=50 km·h-1。使用改進(jìn)的蟻群算法對案例隨機(jī)求解10 次，最優(yōu)解配送路線方案如表3所示，算法收斂曲線如圖2所示。

表3 改進(jìn)蟻群算法最優(yōu)解配送路線方案Table 3 Improved ant colony algorithm optimal solution distribution route scheme

為驗(yàn)證改進(jìn)算法性能，應(yīng)用傳統(tǒng)蟻群算法在相同條件下對模型隨機(jī)求解10 次，算法最優(yōu)解收斂曲線如圖2所示。利用最優(yōu)解、平均值、標(biāo)準(zhǔn)差、平均偏差率(C1)、優(yōu)化率(C2)對比兩種算法，結(jié)果如表4所示。其中，為平均值，Zbest為最優(yōu)值，Zbest-IACO為改進(jìn)蟻群算法最優(yōu)值，Zbest-ACO為傳統(tǒng)蟻群算法最優(yōu)值。

圖2 算法所得最優(yōu)解收斂曲線對比Fig.2 Comparison of convergence curves of optimal solution obtained by traditional ant colony algorithm and improved ant colony algorithm

表4 算法求解結(jié)果對比Table 4 Comparison of solution results of traditional ant colony algorithm and improved ant colony algorithm

通過對比傳統(tǒng)算法與改進(jìn)算法的最優(yōu)解收斂情況可知，傳統(tǒng)蟻群算法迭代40 次后陷入局部最優(yōu)，改進(jìn)蟻群算法可通過鄰域搜索跳出局部最優(yōu)，得到更優(yōu)解，如圖2所示。值得一提的是，雖然在2.1 節(jié)蟻群算法改進(jìn)中存在更新信息素的操作，但更新信息素僅僅是增加獲取更多解的比例，由于在每次迭代過程中僅記錄目前為止蟻群得到的最優(yōu)目標(biāo)函數(shù)值及其配送路線(當(dāng)?shù)趎+1次迭代的最優(yōu)解劣于第n次迭代的最優(yōu)解時，算法的最優(yōu)解仍為第n次迭代的最優(yōu)解)，因此圖2中改進(jìn)蟻群算法最優(yōu)解收斂曲線在第20次到第70次之間保持平穩(wěn)。

由表4可知，改進(jìn)算法的最優(yōu)解和平均值均小于傳統(tǒng)算法，且優(yōu)化率為負(fù)數(shù)，可見改進(jìn)算法求解質(zhì)量更好，不易陷入局部最優(yōu)，并且改進(jìn)算法的標(biāo)準(zhǔn)差和平均偏差率均小于傳統(tǒng)蟻群算法，表明改進(jìn)后算法的穩(wěn)定性有所提升。

3.3 不同場景下算例結(jié)果分析

(1)三目標(biāo)場景

3.2節(jié)中，效率、公平、運(yùn)力這3個子目標(biāo)函數(shù)權(quán)重w1,w2,w3的初始取值均為1/3，為探究子目標(biāo)函數(shù)權(quán)重對模型結(jié)果的影響，對w1,w2,w3從[0,1]區(qū)間以0.1為間隔分別取值，并進(jìn)行排列組合，即針對3 個權(quán)重中每一權(quán)重的任一取值，都對另外兩個權(quán)重值以0.1 為間隔進(jìn)行窮舉，形成所有組合可能。最終得到66種權(quán)重組合，在相同實(shí)驗(yàn)環(huán)境下，根據(jù)所有權(quán)重組合使用改進(jìn)蟻群算法求解10 次，觀察各權(quán)重組合最優(yōu)值繪制目標(biāo)函數(shù)值隨子目標(biāo)函數(shù)權(quán)重變化情況，結(jié)果如圖3所示。

圖3 目標(biāo)函數(shù)值隨子目標(biāo)權(quán)重變化散點(diǎn)圖Fig.3 Scatter plot of change of objective function values with sub-target weights

通過分析各權(quán)重組合下目標(biāo)函數(shù)最優(yōu)解可知：①整體而言，子目標(biāo)函數(shù)權(quán)重變化對目標(biāo)函數(shù)值影響顯著，目標(biāo)函數(shù)值與公平權(quán)重和運(yùn)力權(quán)重呈反比關(guān)系，與效率權(quán)重呈正比關(guān)系；②同時考慮3 個目標(biāo)函數(shù)時，各子目標(biāo)函數(shù)權(quán)重滿足效率權(quán)重在0.3以內(nèi)、運(yùn)力權(quán)重在0.6以上、公平權(quán)重在0.7以上中任意一條件，均能使最終目標(biāo)函數(shù)值取得較好水平(0.15以內(nèi))。因此，在同時考慮效率、公平和運(yùn)力時，決策者應(yīng)慎重考慮各子目標(biāo)函數(shù)權(quán)重。

(2)雙目標(biāo)場景

為探究更廣泛場景下子目標(biāo)函數(shù)權(quán)重的影響，在相同實(shí)驗(yàn)條件下，對任兩個子目標(biāo)選取不同權(quán)重值，比較不同決策權(quán)重下各子目標(biāo)的變化，結(jié)果如圖4所示。

圖4 雙目標(biāo)前提下各子目標(biāo)函數(shù)值隨權(quán)重變化圖Fig.4 Variation of each sub-objective function value with weights under premise of double objective

通過分析雙目標(biāo)場景下，使用車輛數(shù)隨運(yùn)力權(quán)重變化情形可知，當(dāng)決策者僅考慮雙目標(biāo)且具有明顯運(yùn)力偏好時(運(yùn)力權(quán)重大于0.9)，配送時間與加權(quán)時間攀比值均會急劇增加，然而，使用車輛數(shù)卻不會發(fā)生減少，如圖4(b)和圖4(c)所示。因此在僅考慮雙目標(biāo)且運(yùn)力已作為目標(biāo)函數(shù)之一時，決策者一味追求運(yùn)力最小并不能達(dá)到預(yù)期目標(biāo)。

在僅考慮雙目標(biāo)且效率已作為目標(biāo)之一時，若效率權(quán)重已超過0.4，隨著效率權(quán)重增加，配送時間會收斂于約371 min 處，但車輛數(shù)或加權(quán)時間攀比值卻會急劇增加，如圖4(a)和圖4(c)所示。由此可知，在僅考慮雙目標(biāo)前提下，當(dāng)效率權(quán)重超過0.5時，配送時間將對權(quán)重變化無反應(yīng)。因此，決策者應(yīng)均衡考慮權(quán)重分配，賦予效率過高權(quán)重，不僅不能顯著降低配送時間，反而會導(dǎo)致車輛數(shù)或加權(quán)時間攀比值大幅增加。

在僅考慮雙目標(biāo)且公平已作為目標(biāo)之一時：當(dāng)公平權(quán)重小于0.4，加權(quán)時間攀比值對于權(quán)重變化非常敏感；當(dāng)公平權(quán)重處于[ ]0.4,0.9 時，加權(quán)時間攀比值會隨著權(quán)重增加減緩降速；當(dāng)公平權(quán)重超過0.9后，加權(quán)時間攀比值不再降低，如圖4(a)和圖4(b)所示。進(jìn)一步分析公平權(quán)重變化對配送時間和車輛數(shù)的影響，當(dāng)公平權(quán)重處于[0 .3,0.7]時，配送時間和車輛數(shù)不隨公平權(quán)重的變化而變化，如圖4(a)和圖4(b)所示。因此，在已考慮公平的雙目標(biāo)模型中，當(dāng)決策者傾向提高配送公平性時，將公平權(quán)重控制在[0 .3,0.7]為較優(yōu)選擇。

(3)決策者具有明顯偏好場景

特別的，當(dāng)w1,w2,w3的組合排列為時，決策者在決策時使用綜合策略，無明顯偏好；當(dāng)w1,w2,w3的組合排列為(1,0,0)時，決策者在決策時使用高效策略，傾向配送時間使用最短，此權(quán)重組合適用于突發(fā)事件爆發(fā)初期，各需求點(diǎn)均對應(yīng)急物資產(chǎn)生迫切需求，且各需求點(diǎn)受影響程度相差不大，運(yùn)力充足階段；當(dāng)w1,w2,w3的組合排列為(0,1,0)時，決策者在決策時使用公平策略，傾向配送公平最優(yōu)，此權(quán)重組合適用于突發(fā)事件爆發(fā)初期，各需求點(diǎn)均對應(yīng)急物資產(chǎn)生迫切需求，且各需求點(diǎn)受影響程度差異明顯，運(yùn)力充足階段；當(dāng)w1,w2,w3的組合排列為(0,0,1)時，決策者在決策時使用經(jīng)濟(jì)策略，傾向使用最少運(yùn)力，此權(quán)重組合適用于突發(fā)事件爆發(fā)中后期，各需求點(diǎn)的應(yīng)急物資需求得到一定滿足，且各需求點(diǎn)受影響程度差異不明顯階段，此時減少使用車輛數(shù)可降低配送成本。不同決策者偏好下各子目標(biāo)最優(yōu)解如表5所示。

表5 不同決策者偏好下各子目標(biāo)的最優(yōu)解Table 5 Optimal solutions under different decision maker preferences

對比不同決策者偏好下各子目標(biāo)函數(shù)值可知，效率、公平、運(yùn)力這3個子目標(biāo)相互悖反，理想狀態(tài)下，增加1 輛車可使效率提高6.54%，公平提高16.00%，增加運(yùn)力投入可以顯著提高配送方案的效率與公平。理想狀態(tài)下，效率提高1.00%，公平降低0.99%，當(dāng)運(yùn)力不變時，效率與公平之間近似呈現(xiàn)1∶1的反比例關(guān)系。因此，在應(yīng)急物資配送過程中，應(yīng)盡可能增加運(yùn)力投入來提高配送效率與公平。

4 結(jié)論

本文得到的主要結(jié)論如下：

(1)本文所建模型與算法可用于求解需求可拆分應(yīng)急物資配送方案生成，可根據(jù)不同需求調(diào)整模型求解。與傳統(tǒng)算法相比，改進(jìn)后算法可有效擺脫局部最優(yōu)，尋優(yōu)性和穩(wěn)定性表現(xiàn)更好。

(2)當(dāng)同時考慮“效率-公平-運(yùn)力”多維目標(biāo)時，決策者應(yīng)慎重考慮各子目標(biāo)函數(shù)權(quán)重，效率權(quán)重應(yīng)控制在0.3 以內(nèi)，否則會造成目標(biāo)效益顯著失衡。

(3)當(dāng)僅考慮雙目標(biāo)且決策者分別偏好效率、公平、運(yùn)力時，各目標(biāo)權(quán)重的合理偏好為，效率[0 .0,0.4]，公平[0 .3,0.7]，運(yùn)力[0 .0,0.9]。

(4)在需求可拆分應(yīng)急物資配送模型中，效率、公平和運(yùn)力這3個子目標(biāo)相互悖反，增加運(yùn)力投入可以顯著提高配送方案的效率與公平，當(dāng)運(yùn)力不變時，效率與公平之間近似呈現(xiàn)1∶1反比關(guān)系。