范厚明, 楊 成, 張躍光, 孫秀娜, 田攀俊

(大連海事大學(xué) 交通運輸工程學(xué)院,遼寧 大連 116026)

0 引言

混合時間窗下多中心混合車隊車輛路徑問題(Multi-Depot Mixed Fleet Vehicle Routing Problem with Mixed Time Windows, MDMFVRP-MTW)是在多中心聯(lián)合配送模式下,考慮客戶對服務(wù)時間的要求及完成配送任務(wù)后各配送中心的運力平衡程度不同,對多型電動車和燃油車組成的混合車隊配送路徑進行優(yōu)化的車輛路徑拓展問題?，F(xiàn)實中,京東、菜鳥等物流企業(yè)均通過共享配送區(qū)域內(nèi)多個配送中心的資源進行聯(lián)合配送,以降低成本、提高效率,更好地滿足客戶多樣化服務(wù)的需求。同時,與傳統(tǒng)燃油車相比,電動車在環(huán)保、運營成本等方面具有顯著優(yōu)勢,許多物流企業(yè)都開啟了使用電動物流車取代燃油車的進程,出現(xiàn)了物流企業(yè)同時采用電動車和燃油車進行配送服務(wù)的情況,如亞馬遜、京東。另外,美團、京東等企業(yè)根據(jù)客戶是否購買準時送達服務(wù),將客戶區(qū)分為硬時間窗客戶和軟時間窗客戶,實際物流服務(wù)中客戶為混合時間窗的情況大量存在。MDMFVRP-MTW能更準確地描述部分配送模式,例如擁有多個配送中心且各中心配置有多種車型電動車和燃油車的物流企業(yè)對區(qū)域內(nèi)的顧客進行聯(lián)合配送,通過合理規(guī)劃配送車輛類型、服務(wù)順序等,在客戶不同類型的時間窗內(nèi)完成配送服務(wù)。因此,針對MDMFVRP-MTW的研究具有重要意義。

帶混合時間窗的車輛路徑問題(Vehicle Routing Problem with Mixed Time Windows, VRPMTW)是從帶時間窗車輛路徑問題(Vehicle Routing Problem with Time windows, VRPTW)衍生出的更為復(fù)雜的問題。已有學(xué)者對VRPTW的各類衍生問題進行了研究。ONGCUNARUK等[1]考慮城市配送中的城區(qū)限制,即要求在統(tǒng)一硬時間窗內(nèi)完成部分區(qū)域內(nèi)客戶的需求,以車輛固定成本、可變成本之和最小為目標建立優(yōu)化模型,并設(shè)計改進的遺傳算法進行求解;TAS等[2]針對一種特殊的時間窗形式,即允許車輛在其時間窗外一定范圍內(nèi)到達,但需要支付一定的懲罰成本,以車輛可變成本、固定成本和時間窗懲罰成本之和最小為目標建立VRPTW優(yōu)化模型,并設(shè)計改進的禁忌搜索算法進行求解;范厚明等[3]針對客戶的模糊需求和模糊時間窗,以總行駛距離最小化、平均客戶滿意度最大和車輛使用數(shù)量最小為目標建立VRP優(yōu)化模型,并設(shè)計混合遺傳算法進行求解。本文VRPMTW同時存在軟時間窗約束客戶和硬時間窗約束客戶,目前相關(guān)研究較少。周蓉等[4]針對因客戶訂單時間緊迫程度不同而使軟硬時間窗共存的情況,如緊急訂單與常規(guī)訂單可分別視為硬時間窗約束和軟時間窗約束,以總成本最小為目標建立同時集送貨VRP優(yōu)化模型,并設(shè)計改進離散粒子群算法進行求解;FALLAHTAFTI等[5]針對第三方物流配送中同時存在帶硬時間窗的供應(yīng)商與帶半軟時間窗的工廠和倉庫的現(xiàn)實特征,以總成本最小為目標建立VRPMTW優(yōu)化模型,并設(shè)計分支定界算法進行求解;王勇等[6]提出將客戶重要度與時間窗相結(jié)合的差異化管理策略,該策略首先對客戶重要度進行評價,其次對重要客戶進行硬時間窗管理,對普通客戶進行軟時間窗管理,以成本最小和配送車輛數(shù)最小為目標建立雙目標優(yōu)化模型,并設(shè)計遺傳—禁忌搜索混合算法進行求解;鄒宗峰等[7]考慮危險品運輸網(wǎng)絡(luò)中同時具有軟硬時間窗限制,以運輸風(fēng)險、時間窗懲罰成本、交通狀況、道路能力、運輸時間最優(yōu)為目標,建立帶混合時間窗的多目標路徑優(yōu)化模型,并設(shè)計改進的多目標遺傳算法進行求解。

本文涉及的MDMFVRP既是多中心異型車輛路徑問題(Multi-Depot Heterogeneous fleet Vehicle Routing Problem, MDHVRP),也是燃油車與電動車構(gòu)成的混合車隊路徑優(yōu)化問題。針對MDHVRP,馬建華等[8]針對車輛在應(yīng)急狀態(tài)下進行配送,配送結(jié)束返回原配送中心,以總配送時長最小為目標建立MDHVRP優(yōu)化模型,并設(shè)計變異蟻群算法進行求解;張群等[9]針對多貨種配送,車輛配送結(jié)束返回原車場,以總行駛距離最小為目標建立多貨種MDHVRP優(yōu)化模型,并設(shè)計改進模糊遺傳算法進行求解;羅鴻斌[10]同樣考慮車輛配送完成返回原配送中心,以車輛運輸成本最小為目標建立MDHVRP優(yōu)化模型,并設(shè)計改進的粒子群優(yōu)化算法進行求解。在電動車車輛路徑問題(Electric Vehicle Routing Problem, EVRP)研究中,SCHNEIDER等[11]針對帶時間窗和充電站的EVRP問題,以行駛距離最小為目標建立電動車路徑優(yōu)化模型,并設(shè)計一種結(jié)合可變鄰域搜索算法和禁忌搜索算法的混合算法進行求解;HIERMANN等[12]考慮異型電動車的運輸能力、電池尺寸和購置成本差異,以派遣成本和路徑可變成本之和最小為目標建立帶時間窗的路徑優(yōu)化模型,并設(shè)計自適應(yīng)大鄰域搜索(Large Neighborhood Search,LNS)算法進行求解;BASSO等[13]考慮地形、速度等因素對電動車能耗的影響,以能耗最小為目標建立EVRP優(yōu)化模型,并使用Bellman-Ford算法進行求解;RAEESI等[14]使用移動換電車為電量不足的電動車提供換電服務(wù),以總成本最小為目標建立了帶時間窗的EVRP數(shù)學(xué)模型,并提出一種基于動態(tài)規(guī)劃和整數(shù)規(guī)劃的兩階段混合算法進行求解;KESKIN等[15]考慮充電站內(nèi)充電樁的數(shù)量限制,以總成本最小為目標建立電動車排隊等待服從M/G/1分布且考慮充電效率非線性的路徑優(yōu)化模型,并設(shè)計改進的自適應(yīng)LNS算法進行求解。隨著研究的深入,考慮同時使用電動車、燃油車進行配送的VRP研究逐漸豐富,李英等[16]針對MFVRP,以總成本最小為目標建立混合車隊路徑優(yōu)化模型,并設(shè)計分散搜索和改進蟻群算法相結(jié)合的混合啟發(fā)式算法進行求解;MACRINA等[17]考慮各充電站充電速度存在差異,以總成本最小為目標建立電動車不完全充電下的混合車隊路徑優(yōu)化模型,并設(shè)計混合鄰域搜索算法進行求解;SASSI等[18]在充電成本受時間變化的影響下,以總成本最小為目標建立具有時間依賴性的混合車隊車輛路徑優(yōu)化模型,并設(shè)計包含多種插入策略的局部搜索算法進行求解;GOEKE等[19]考慮速度、坡度和載重量對能耗的影響,分別以行駛距離最小、充電成本與人工成本之和最小、電池更換成本最小為目標,建立非線性能耗的混合車隊路徑模型,并設(shè)計自適應(yīng)LNS算法進行求解;LEBEAU等[20]考慮客戶時間窗約束,以總成本最小為目標建立混合車隊車輛路徑優(yōu)化模型,并設(shè)計節(jié)約試探法進行求解;MACRINA等[21]考慮電動車電池不完全充電策略和客戶的硬時間窗約束,以總成本最小為目標建立MFVRP優(yōu)化模型,并設(shè)計改進局部搜索算法進行求解。

通過梳理以上文獻可知,現(xiàn)有研究已經(jīng)取得一定成果,對本文研究具有重要指導(dǎo)意義,但還存在以下不足:①現(xiàn)有VRPTW的研究多考慮單一硬時間窗或軟時間窗,缺乏對不同類型時間窗并存的車輛路徑問題的研究;②現(xiàn)有MDHVRP研究中,各配送中心采取聯(lián)合配送模式,但車輛返回策略均為返回原中心,該策略返回方案固定,其返回成本較高;③現(xiàn)有MFVRP研究的燃油車和電動車多為單一車型,缺乏對多車型燃油車或電動車并存的車輛路徑問題進行研究。針對以上不足,本文MDMFVRP-MTW綜合考慮影響油耗的多種因素和客戶混合時間窗等約束,基于配送中心運力平衡的車輛返回策略,以車輛派遣成本、油耗成本、電動車能耗成本和時間窗懲罰成本之和最小為目標建立數(shù)學(xué)模型,并設(shè)計遺傳—大鄰域混合算法(Hybrid Genetic Algorithm with Large Neighborhood Search, HGALNS)進行求解。

1 問題分析與返回策略設(shè)計

1.1 問題描述

以圖1為例,配送區(qū)域內(nèi)有2個配送中心、12個軟時間窗客戶和12個硬時間窗客戶,3種不同車型的車輛分別由配送中心1,2出發(fā),并在時間窗約束下為客戶提供配送服務(wù),電動車2,3,5,6分別在服務(wù)客戶5,10,19,22后由于電池最低荷電狀態(tài)約束無法繼續(xù)服務(wù)其他客戶,就近選擇存有該車型備用電池的配送中心更換電池,然后繼續(xù)服務(wù)后續(xù)客戶,車輛完成配送后遵循運力平衡原則選擇配送中心返回。

1.2 油耗成本計算

車輛行駛過程中的油耗與載重量等因素有關(guān),本文采用文獻[22]的綜合模式排放模型(Comprehensive Modal Emission Model, CMEM)計算車輛油耗,該模型在已知車輛參數(shù)和行駛狀態(tài)下,能夠較準確地估計配送過程中車輛的燃油消耗量。根據(jù)CMEM模型可知,車輛由節(jié)點i到j(luò)的油耗率fij(單位:g/s)為

fij=φ(λNVs+Pij/η)/μ。

(1)

式中:φ為油氣質(zhì)量比;λ為發(fā)動機摩擦系數(shù);N為發(fā)動機轉(zhuǎn)速(單位:r/s);Vs為發(fā)動機排量(單位:L);η為柴油發(fā)動機的效率參數(shù);μ為柴油的熱量值(單位:kJ/g);Pij為車輛由節(jié)點i行駛至節(jié)點j所需的牽引功率(單位:kW),

(2)

本文假設(shè)車輛為勻速行駛,道路坡度為0,則

(3)

式中:m為車輛自重(單位:t);g為重力加速度(單位:g/m2);Cd為空氣阻力系數(shù);A為車輛迎風(fēng)面積(單位:m2);ρ1為空氣密度(單位:kg/m3);Cr為滾動阻力系數(shù)。

綜合上述分析可得車輛k1從i到j(luò)的油耗Fijk1(單位:L)為

Fijk1=3.6fijlij/(ρ2·v)。

(4)

式中:ρ2為柴油密度(單位:g/mL);3.6為單位轉(zhuǎn)換系數(shù)。

1.3 返回策略設(shè)計

目前MDHVRP研究中,車輛的返回策略為返回原配送中心。為保證各配送中心運力守衡,配送中心也可按照發(fā)出和接收的各車型車輛數(shù)守恒原則優(yōu)化決策配送方案,這兩種返回策略示意圖如圖2a和圖2b所示。

圖2a為返回原配送中心策略,即各車輛完成配送任務(wù)后分別返回出發(fā)時的配送中心,該策略雖然能夠保證各中心運力絕對平衡,但是車輛返回方案固定,車輛調(diào)度不靈活,運營成本較高。該返回策略的約束為

?i∈V0,?r∈R,?kr∈Kr。

(5)

圖2b為各車型車輛數(shù)平衡策略,即各車輛配送完成后可選擇任一配送中心返回,但需要保證各中心各車型車輛數(shù)與初始狀態(tài)相同。該策略通過多中心聯(lián)合調(diào)度保證各中心運力絕對平衡,相比返回原中心策略,可選擇的返回方案較多,但可能存在部分車輛返回較遠的配送中心而造成較高運營成本的情況。該返回策略的約束為

(6)

由上述分析可知,返回原配送中心策略與各車型車輛數(shù)平衡策略均存在可選擇的返回方案較少、運營成本較高的缺點,而且在聯(lián)合配送模式下,各配送中心客戶與載具資源共享,配送中心無需維持車輛配置相同。因此,本文結(jié)合現(xiàn)實中配送中心每日配送任務(wù)量保持相對穩(wěn)定但呈現(xiàn)小幅度上下波動的現(xiàn)狀,提出運力平衡的車輛返回策略,該策略既能通過維持配送中心運力相對平衡保證配送中心的穩(wěn)定運力供給,又能增加可選擇的返回方案數(shù)量、降低運營成本。運力平衡的車輛返回策略要求車輛完成配送后根據(jù)各中心運力情況選擇配送中心返回,允許各配送中心所有車輛的最大載重量之和在一定范圍內(nèi)浮動,但不得高于運力上限或低于運力下限。如圖1中,各配送中心在配送前的總運力均為10,假設(shè)配送周期(1天)內(nèi)運力允許的波動幅度為10%,車輛3若返回原配送中心1,則配送結(jié)束后配送中心1,2的總運力分別為13,7,均超出運力可接受的波動幅度,因此車輛3遵循運力平衡返回原則返回運力不足的配送中心2,此時配送中心1,2的總運力分別為11,9,均達到可接受的運力要求,而且避免了較長的車輛行駛里程。圖2c為運力平衡的返回策略示意圖,相比返回原配送中心策略和各車型車輛數(shù)平衡策略,該策略下車輛可選擇的返回方案更多、車輛調(diào)度更靈活,既可降低運營成本,又能保證配送中心的基本調(diào)度需求。該返回策略的約束為

(7)

式中y1,y2分別為各配送中心的運力下限和運力上限系數(shù)。

1.4 目標函數(shù)

梳理近年來的文獻可知,現(xiàn)有車輛路徑問題大多以成本最小為優(yōu)化目標。本文將以車輛派遣成本、油耗成本、電動車能耗成本和時間窗懲罰成本之和最小為目標建立數(shù)學(xué)模型。

派遣成本C1與車輛使用數(shù)量呈線性關(guān)系,不同車型派遣成本不同:

(8)

油耗成本C2的計算采用CMEM模型,由1.2節(jié)可知

(9)

由于缺乏準確的電動車能耗計算模型,電動車能耗成本C3和大部分EVRP文獻相同,假設(shè)與車輛行駛距離呈線性關(guān)系,則有

(10)

時間窗懲罰成本C4包括硬時間窗早到等待成本、軟時間窗早到懲罰成本和軟時間窗晚到懲罰成本3項,其中不同車型因早到等待產(chǎn)生的硬時間窗機會損失成本不同,有

(11)

2 模型建立

基于以上分析,建立如下MDMFVRP-MTW數(shù)學(xué)模型:

目標函數(shù)

minC1+C2+C3+C4。

(12)

約束條件中,本文提出的運力平衡返回約束式(7)是其中的一個約束條件,除此之外,其他約束如下:

?r∈R,?kr∈Kr;

(13)

(14)

(15)

(16)

(17)

?i∈V1,?r∈R,?kr∈Kr;

(18)

Ts≤Tikr≤Tf,

?i∈V0,?r∈R,?kr∈Kr;

(19)

(20)

(21)

(22)

(23)

(24)

Qik1-di-M(1-xijkr)≤Qjk1,

(25)

(26)

其中:式(12)為目標函數(shù),即以車輛派遣成本、油耗成本、電動車能耗成本和時間窗懲罰成本之和最小為目標;式(13)表示車輛服務(wù)客戶的需求量之和不超過其最大載重量;式(14)表示每個客戶點只被服務(wù)一次;式(15)表示車輛由配送中心出發(fā),最終返回任一配送中心;式(16)表示客戶與換電節(jié)點車輛進出平衡;式(17)表示r型電動車到配送中心j的換電次數(shù)不超過該配送中心配備的r型電動車電池的數(shù)量;式(18)表示車輛在硬時間窗客戶點可接受的時間窗內(nèi)為其提供服務(wù);式(19)表示車輛必須在配送中心工作時間窗內(nèi)執(zhí)行配送任務(wù);式(20)表示車輛由節(jié)點i出發(fā)到達節(jié)點j的時刻,同時消除子回路;式(21)約束配送中心i派出的r型車車輛數(shù)不超過其擁有的最大車輛數(shù);式(22)表示車輛離開配送中心和客戶點時的電量;式(23)表示配送過程中從i點出發(fā)的電動車到達j點時的電量;式(24)為電動車最低荷電狀態(tài)約束;式(25)為從i點出發(fā)的車輛到達j點時的載重量;式(26)為決策變量屬性。

3 算法設(shè)計

本文MDMFVRP-MTW是車輛路徑拓展問題,包括多中心、多車型、混合車隊、混合時間窗、電動車荷電狀態(tài)約束、電池分布及數(shù)量約束、運力平衡返回規(guī)則等多個特征,屬于NP-Hard問題,在該類問題求解中,精確算法求解較為困難。遺傳算法(Genetic Algorithm, GA)是基于生物進化論中“適者生存”思想設(shè)計的經(jīng)典啟發(fā)式算法,具有較好的魯棒性,適合求解復(fù)雜的優(yōu)化問題,但在迭代后期易陷入局部最優(yōu),全局搜索能力較差;LNS通過對當前解決方案的重復(fù)“破壞”和“修復(fù)”尋找新的可行解,算法尋優(yōu)能力強。因此,本文在GA基礎(chǔ)上,將其與LNS算法結(jié)合。為了進一步提高算法的全局尋優(yōu)能力,引入變鄰域搜索策略,通過交替搜索不同鄰域結(jié)構(gòu)來提高算法搜索深度。本文設(shè)計采用變鄰域搜索策略的HGALNS算法對MDMFVRP-MTW進行求解,該算法采用聚類法生成初始種群來提高初始解的質(zhì)量,并采用多個不同的“破壞—修復(fù)”算子交替搜索來提高算法的局部搜索能力,算法流程如圖3所示。

3.1 初始解的構(gòu)造

3.1.1 初始種群的生成

為了提高初始解的質(zhì)量,本文采用聚類法生成初始種群,具體步驟如下:

步驟1隨機選擇若干客戶作為聚類簇中心,聚類簇數(shù)量與車輛總數(shù)成比例,比例系數(shù)=需求總量/運力總量。

步驟2計算其余客戶到各聚類簇的平均距離,確定距各客戶最近的聚類簇及其平均距離d1和次近的聚類簇及其平均距離d2。

步驟3在滿足(d2-d1)>0.3d1的客戶中,選擇距離差最大的客戶加入與其距離最近的聚類簇,轉(zhuǎn)步驟5;如果不存在滿足條件的客戶,則執(zhí)行步驟4。

步驟4計算客戶與各聚類簇的平均距離方差,選擇方差最小的客戶點加入對應(yīng)的聚類簇中。

步驟5重復(fù)上述步驟,直到所有客戶分配完畢。

步驟6按照客戶時間窗的最早時間與最晚時間的平均值由小到大對各聚類簇中的客戶進行排序,得到初始種群。

3.1.2 初始解的生成

針對3.1.1節(jié)構(gòu)造的初始種群,本文按照“先電動車,后燃油車;先大車型,后小車型”的原則解碼構(gòu)造初始解,在該過程中,燃油車看作為電量無窮大的“電動車”。對初始種群中每條染色體的操作步驟如下:

步驟1在擁有所選車型的配送中心,選擇滿足首個客戶時間窗約束和返回電量約束(服務(wù)完客戶后,在不違反電池最低荷電狀態(tài)約束的情況下,至少可返回一個配送中心)的出發(fā)配送中心,如果配送中心均不滿足條件,則選擇下一車型并重復(fù)上述操作。

步驟2判斷下一客戶點是否滿足客戶服務(wù)時間窗、車輛載重和返回電量約束,滿足則將該客戶添加入路徑,重復(fù)步驟2,不滿足則返回電量約束執(zhí)行步驟3,否則轉(zhuǎn)步驟4。

步驟3在服務(wù)當前客戶點后尋找配送中心換電,如果換電后電量可前往下一客戶點,則重復(fù)步驟2,否則執(zhí)行步驟4。

步驟4結(jié)束當前路徑客戶分配,按照“運力平衡”原則選擇可到達的配送中心返回,如果車輛不可到達,則在其他配送中心換電后前往該配送中心。

步驟5派遣新車輛,重復(fù)步驟1～步驟4,直至所有客戶劃分完畢。

如圖4所示,圖中1～10表示客戶點,11～12表示配送中心。以車輛1路徑(211-1-5-12-2-212)為例,車型2車輛從配送中心11出發(fā),依次服務(wù)客戶1,5后,由于電量不足,前往配送中心12更換電池,然后服務(wù)客戶2,完成配送服務(wù)后返回配送中心12。

3.2 適應(yīng)度計算與選擇

種群中各染色體的適應(yīng)度可由模型目標函數(shù)式(8)構(gòu)建,適應(yīng)度

(27)

式中Z為染色體的目標函數(shù)值。

選擇操作采用精英選擇和輪盤賭相結(jié)合的策略,選擇部分精英個體直接保留進入下一代,剩余數(shù)量的個體則由輪盤賭產(chǎn)生,適應(yīng)度越高,個體越容易被選擇。

3.3 交叉操作

本文采用改進子路徑交叉操作,交叉過程如圖5所示。針對父代染色體S1,S2,在考慮運力平衡約束和配送中心各車型車輛數(shù)量約束的基礎(chǔ)上,隨機選擇子路徑進行交換,交換后刪除所有重復(fù)客戶,并對路徑中因交換缺失的客戶進行重插入,具體步驟如下:

步驟1選擇待插入客戶。

步驟2判斷車輛剩余可載重量是否滿足客戶需求,對于無法滿足載重約束的子路徑,令插入成本Cm為無窮大。

步驟3計算可插入路徑中的所有位置插入成本Cm,客戶m在i點和j點之間的插入成本

Cm=Z1·(lim+lmj-lij)+Z2·CTW。

(28)

式中:Z1,Z2為距離權(quán)重系數(shù)和時間窗懲罰成本權(quán)重系數(shù);CTW為m點的時間窗懲罰成本。

步驟4若所有位置插入成本均為無窮大,則執(zhí)行步驟5,否則選擇插入成本最小的位置試插入當前待分配客戶,判斷后續(xù)客戶是否滿足時間窗約束,并重新分配該子路徑上的換電配送中心和返回配送中心位置。如果后續(xù)客戶未違反時間窗約束,并能返回符合運力平衡的配送中心,則插入當前位置,重復(fù)步驟1;否則,令插入成本為無窮大,重復(fù)步驟4。

步驟5為當前待插入客戶新增一條子路徑,選擇車型、出發(fā)配送中心和滿足運力平衡的返回配送中心,步驟如3.1.2節(jié)的步驟1和步驟4。

步驟6重復(fù)上述操作,直到將所有被移除客戶重新插入至路徑中。

3.4 破壞—修復(fù)操作

本文設(shè)計的HGALNS算法的鄰域搜索思想是對可行路徑進行重復(fù)破壞和修復(fù),從而構(gòu)造新的可行路徑,該算法包括3個鄰域搜索算子,每個算子包括路徑破壞和路徑修復(fù)兩部分。

(1)路徑破壞

1)移除隨機客戶 隨機移除10%客戶,如圖6a所示。

2)移除距離節(jié)約客戶 移除與前后客戶或配送中心的距離之和最大的10%客戶,如圖6b所示。

3)移除最短路徑 移除各個體中客戶數(shù)量最少的子路徑,如圖6c所示。

移除客戶的目的是破壞路徑,移除最短路徑的主要目的是減少所使用車輛,降低派遣成本。

(2)路徑修復(fù)

路徑修復(fù)的目的是將被移除的客戶重新插入路徑,具體步驟如3.3節(jié)的客戶重插入操作

3.5 變鄰域搜索策略

為了提高HGALNS算法的深度搜索能力,本文引入變鄰域搜索算法中的擾動策略,該策略根據(jù)各“破壞—修復(fù)”算子運行后最優(yōu)解的變化情況調(diào)整算子的交替搜索順序和策略。在該策略下,“隨機客戶破壞—修復(fù)”算子作為第一順序鄰域搜索算子的運行次數(shù)較高,能夠有效提高算法的全局搜索能力。變鄰域搜索策略偽代碼如下:

Variable neighborhood search strategy

Input:Ik={I1,I2,…,Im}: destroy and repair operators, Imis the mth destroy and repair operator。

1 s←Current Solution;

2 s′←s;

3 m=1;

4 while m

5 Destroy and repair operators:st←Im(s′);

6 if f(st)

7 s′←st;

8 m=1;

9 else

10 m++;

11 end

12 end

13 returns′

4 數(shù)值分析

為了驗證本文模型的有效性及本文所設(shè)計算法的性能,首先將HGALNS求解結(jié)果與Gurobi精確算法求解結(jié)果進行對比;然后采用HGALNS算法分別求解本文問題涉及的帶軟時間窗的多中心車輛路徑問題(Multiple Depot Vehicle Routing Problem with Soft Time Windows, MDVRPSTW)、帶硬時間窗的車輛路徑問題(Multiple Depot Vehicle Routing Problem with Hard Time Windows,MDVRPHTW)、帶時間窗的電動車車輛路徑問題(Electric Vehicle Routing Problem with Time Windows, EVRPTW),并與其他啟發(fā)式算法的求解結(jié)果進行對比驗證;最后設(shè)計本文問題算例,并對影響方案制定的主要因素進行敏感性分析。本文算法編程采用MATLAB R2018b,操作系統(tǒng)為Windows10,電腦內(nèi)存為8 G,CPU為Intel i7-7700 M,主頻為3.6 GHz。經(jīng)過反復(fù)測試,本文算法涉及的參數(shù)設(shè)置為:交叉概率Pc=0.95,代溝GGAP=0.95。

4.1 與Gurobi求解結(jié)果的對比分析

Gurobi采用Python3.9進行編程,運行環(huán)境與HGALNS相同,使用的算例為Solomon系列VRPTW標準算例。因為Gurobi在超過15個節(jié)點數(shù)量的算例中求解時間較長,所以設(shè)置Gurobi的最大運行時間為18 000 s,當達到最大運行時間時,輸出Gurobi當前求得的最好解。求解結(jié)果如表1所示,其中n,d分別為客戶和配送中心的數(shù)量,Obj為Gurobi和HGALNS的求解結(jié)果,Gap為HGALNS和Gurobi求解結(jié)果偏差的平均值。

表1 HGALNS與Gurobi求解結(jié)果的對比

由表1可知,HGALNS較Gurobi在求解效率上有明顯優(yōu)勢,其可在30 s內(nèi)求得接近或優(yōu)于Gurobi的解決方案,而Gurobi在客戶規(guī)模超過15的算例中的求解速度很慢,且在規(guī)定時間內(nèi)的求解質(zhì)量較差。HGALNS與Gurobi的求解平均偏差為0.41%,證明了本文模型的有效性以及HGALNS算法較高的求解效率。

4.2 算法驗證

本節(jié)對HGALNS與其他啟發(fā)式算法的性能差距進行驗證。因為目前沒有MDMFVRP-MTW算例,所以對已有文獻中與MDMFVRP-MTW相關(guān)的基本問題進行3組數(shù)值實驗。

4.2.1 實驗1

為了驗證HGALNS與LNS算法的性能差距以及HGALNS求解MDVRPSTW的有效性,采用本文算法對文獻[23]中的MDVRPSTW算例進行求解,并與LNS算法、考慮時空距離的混合遺傳變鄰域算法(Hybrid Genetic Algorithm with Variable Neighborhood Search considering the Temporal-Spatial distance,HGAVNS_TS)[23]進行對比,該算法運行環(huán)境與本文相同。表2所示為LNS,HGAVNS_TS,HGALNS的求解結(jié)果,其中Pre-Best為前兩種算法的最好解,Gap為本文算法求解的最優(yōu)值相對Pre-Best的改進幅度,Avg.Gap為各算法的最優(yōu)值(best)、平均值(Avg)和Pre-Best偏差的平均值。

表2 HGALNS與文獻[23]求解結(jié)果對比

由表2可知,在與LNS的求解結(jié)果對比中,本文HGALNS求解最優(yōu)值、平均值較LNS的改善幅度分別達到7.78%,7.04%,求解時間也明顯優(yōu)于LNS,證明了本文設(shè)計的HGALNS及變鄰域搜索策略的有效性。

對比已有文獻算法的求解結(jié)果,在求解質(zhì)量上,HGAVNS_TS,HGALNS的求解最優(yōu)值與Pre-Best的平均偏差分別為0.58%,-3.7%,最優(yōu)值的改善幅度為4.28%,求解平均值與Pre-Best的平均偏差分別為2.53%,-0.28%,求解平均值的改善幅度為2.81%,而且HGALNS算法求得全部12個算例中10個算例的最好解。在求解時間上,相同運行環(huán)境下,本文算法的求解時間短,在中小規(guī)模算例中的求解時間略優(yōu)于HGAVNS_TS,而且隨著算例客戶規(guī)模的增加,算法求解時間明顯優(yōu)于其他兩種啟發(fā)式算法。通過對比分析說明,HGALNS算法的性能優(yōu)于LNS和HGANLS_TS。

4.2.2 實驗2

選擇文獻[24-25]的算法進行對比分析。表3所示為MPMSFLA[24],DFCAN[25]與本文HGALNS對CORDEAU等[26]提出的MDVRPTW標準算例的求解結(jié)果,其中DFCAN[25]未提供運行時間數(shù)據(jù),因此未列出。

由表3可知,在求解質(zhì)量方面,本文HGALNS的求解結(jié)果與Pre-Best的平均偏差為1.92%;在求解時間方面,HGALNS求解大規(guī)模算例的最長運行時間為23.18 min,對于物流企業(yè)制定一個整體配送方案來說,這個時間范圍完全可以接受。通過以上對比分析,驗證了HGALNS求解MDVRPHTW問題的有效性。

4.2.3 實驗3

選擇文獻[27]驗證HGALNS求解EVRPTW問題的有效性,以及與文獻中使用的節(jié)約—禁忌搜索混合算法(節(jié)約—禁忌搜索(Clarke-Wright saving and Tabu Search, CW-TS)混合算法)的性能差距,該算例包括1個配送中心、2個換電站和25個客戶。表4所示為CW-TS算法[27]和HGALNS運行10次的結(jié)果,其中L為車輛行駛總距離,P為時間窗懲罰成本,C為總成本,Avg為各算例數(shù)值的平均值,Range為10次運行結(jié)果的方差,Gap為改進比例。

表4 HGALNS與文獻[27]求解結(jié)果對比

由表4可知,在求解質(zhì)量方面,CW-TS與HGALNS算法10次求解的平均值分別為8 080.70,8 012.49,本文算法求得的時間窗懲罰成本較CW-TS改進了33.94%,總成本較CW-TS改進了0.84%;在求解穩(wěn)定性方面,CW-TS和HGALNS 10次求解結(jié)果的方差分別為76 909.41,9 821.85,HGALNS求解穩(wěn)定性較好。綜上所述,本文算法在求解質(zhì)量和穩(wěn)定性上均優(yōu)于CW-TS,進一步驗證了本文HGALNS的有效性。

通過3組數(shù)值實驗說明,本文算法能夠在相對較短的時間內(nèi)求得問題的較優(yōu)解,求解結(jié)果具有較好的穩(wěn)定性,HGALNS的求解效率接近或優(yōu)于以上算法。

4.3 算例分析

4.3.1 算例設(shè)計

由于目前沒有MDMFVRP-MTW算例,本文在MDVRPTW標準算例的基礎(chǔ)上進行改編,改編規(guī)則為:①時間窗參數(shù)/60(單位:h);②服務(wù)時間參數(shù)/60(單位:h);③客戶需求量(3/k),其中k為算例中各車型中的最大車輛載重量參數(shù)(單位:t);④坐標參數(shù)/2(單位:km)。

客戶中前62.5%為軟時間窗客戶,后37.5%為硬時間窗客戶。車輛參數(shù)如表5所示,每個配送中心3種車型的車輛數(shù)分別為算例中車輛數(shù)量的1/2,1/4,1/3(向上取整),兩種電動車的可替換電池數(shù)分別為2和3。計算燃油車油耗成本使用的CMEM模型相關(guān)參數(shù)參考文獻[28],算例中涉及的其他參數(shù)如表6所示。

表5 車輛參數(shù)

續(xù)表5

表6 算例其他相關(guān)參數(shù)

4.3.2 算例求解

(1)算例參數(shù)設(shè)置分析

為確定Z1和Z2的參數(shù)設(shè)置,本文對Z1和Z2的不同參數(shù)組合進行對比實驗分析。表7所示為使用本文HGALNS對5組Z1,Z2參數(shù)進行不同規(guī)模算例的求解結(jié)果,其中Best為5種參數(shù)組合的最好解?？梢?5組參數(shù)的Gap平均值分別為55.86%,8.61%,2.83%,0.87%,17.16%,而且[0.75,0.25]取得了其中7個算例的最好解,因此選擇表現(xiàn)更好的[0.75,0.25]作為后續(xù)實驗的參數(shù)值。

表7 參數(shù)設(shè)置求解結(jié)果對比

(2)不同規(guī)模的算例求解

表8所示為HGALNS對不同規(guī)模算例的求解結(jié)果,其中N表示電動車換電次數(shù),Ratio表示優(yōu)化結(jié)果中使用的3種車型車輛數(shù)量,Ctotal表示總成本,Avg表示各項成本與總成本比值的平均值?？梢?當算例為n≤72的中小規(guī)模算例時,優(yōu)化方案中使用的車輛均為電動車,隨著客戶規(guī)模的增加,燃油車的使用數(shù)量顯著增加,證明了電動車在中小規(guī)模配送中的經(jīng)濟性;在成本結(jié)構(gòu)方面,車輛派遣成本、油耗成本、電動車能耗成本、時間窗懲罰成本與總成本比值的平均值分別為75.08%,7.85%,6.96%,10.45%。

表8 HGALNS求解不同算例的結(jié)果

4.3.3 敏感性分析

(1)不同返回策略的影響

為驗證本文所提運力平衡的車輛返回策略的合理性,對不同返回規(guī)則下的多組算例進行求解分析。表9所示為3種返回策略在不同算例下的求解結(jié)果,其中Best為3種策略下總成本的最優(yōu)值,Gap為C與Best的偏差,Max_L和Min_L表示配送結(jié)束時各配送中心擁有的運力與其起始運力比值的最大值和最小值?？梢?在10組不同規(guī)模算例中,3種返回策略與Best值偏差的平均值分別為2.46%,3.52%,0.00%,其中運力平衡的返回策略在每組算例中均能求得最好解;在運力的穩(wěn)定性方面,運力平衡返回策略的最小和最大運力比的平均值分別為78.77%,119.24%,各配送中心運力具有較好的穩(wěn)定性。雖然返回原中心和各車型車輛數(shù)平衡返回策略均能保持運力絕對平衡,但是可選擇的返回方案較少,經(jīng)濟性較差,而本文所提運力平衡的返回策略能夠保證運力相對平衡,可有效降低總成本。

表9 不同返回策略的敏感性分析

(2)運力平衡系數(shù)的影響

為分析不同運力平衡系數(shù)對制定配送方案的影響,設(shè)置4組不同的運力平衡系數(shù)分別進行求解,求解結(jié)果如表10所示,其中Best為4組運力平衡系數(shù)下平均總成本的最優(yōu)值,Gap為C與Best的偏差?？梢?4組不同的運力平衡系數(shù)在不同算例下求得的配送成本與最優(yōu)值的平均偏差分別為5.23%,0.83%,0.15%,0%,即隨著運力平衡系數(shù)的松弛,滿足運力平衡的車輛返回方案增加,總配送成本會有所降低。當運力平衡系數(shù)為[0,-]時,運力平衡約束完全松弛,取到每組算例的最優(yōu)值。因此,運力平衡系數(shù)的變化會影響配送方案的制定。

表10 運力平衡敏感性分析

(3)混合時間窗比例的影響

為分析不同混合時間窗客戶比例對配送方案的影響,對不同混合時間窗客戶比例的多組算例進行求解分析。表11所示為10組算例的求解結(jié)果,其中S∶H為軟時間窗客戶數(shù)和硬時間窗客戶數(shù)之比。可見,4組不同混合時間窗客戶比例下求得的配送成本的平均值與最優(yōu)值的偏差分別為18.62%,9.08%,3.44%,0.00%,即隨著軟時間窗客戶數(shù)量比例的增加,求得的總配送成本的平均值有所降低,而且當軟時間窗客戶比例為100%時求得最優(yōu)值。當S∶H=0%∶100%時本文問題為VRPHTW,此時客戶時間窗類型均為硬時間窗;當S∶H=100%∶0%時本文問題為VRPSTW,此時客戶時間窗類型均為軟時間窗,VRPHTW下求解得到的總配送成本平均值較VRPSTW增加了18.62%。因此,混合時間窗客戶比例變化對配送方案的制定具有重要影響。

5 結(jié)束語

本文針對MDMFVRP-MTW進行研究,得到以下結(jié)論:

(1)所建立的MDMFVRP-MTW優(yōu)化模型,不僅考慮了多中心聯(lián)合配送、混合車隊、客戶混合時間窗等特征,還考慮了配送中心運力平衡返回規(guī)則,雖然增加了模型復(fù)雜度和問題求解難度,但是更符合現(xiàn)實配送生產(chǎn)活動。

(2)所設(shè)計的HGALNS采用聚類法生成初始解,基于運力平衡的返回策略設(shè)計交叉、變異算子,并引入變鄰域搜索結(jié)構(gòu)和LNS算法的移除和插入算子進行搜索優(yōu)化,有效提升了算法的局部搜索能力。

(3)通過分析不同返回策略的敏感性表明,返回原配送中心和各車型車輛數(shù)平衡返回策略由于可選擇返回方案有限,運營成本較高,而運力平衡的返回策略允許配送中心適當調(diào)整運力,能夠有效降低運營成本;通過分析不同運力平衡系數(shù)的敏感性表明,隨著運力平衡系數(shù)的松弛,滿足運力平衡的車輛返回方案增加,總配送成本有所降低;通過分析不同混合時間窗客戶比例的敏感性表明,隨著軟時間窗客戶在客戶總體中所占比例的增加,總配送成本有所降低。

基于本文研究得出以下管理啟示:

(1)對于僅使用燃油車作為載運工具的物流企業(yè),適當引入電動車能夠有效降低企業(yè)運營總成本;對于使用電動車和燃油車混合車隊的物流企業(yè),應(yīng)考慮合理配置電動車與燃油車的車型和數(shù)量,以使企業(yè)總成本最低。

(2)由于電動車存在里程約束,企業(yè)應(yīng)結(jié)合訂單數(shù)量、位置分布和客戶時間窗等信息,合理制定當期混合車隊結(jié)構(gòu),盲目使用電動車取代燃油車配送可能會造成效益背反。

(3)對運力平衡策略的分析表明,擁有多個配送中心的企業(yè)在多中心聯(lián)合配送的基礎(chǔ)上,采用運力平衡返回策略適當調(diào)整運力分布能夠有效降低企業(yè)配送成本。

未來將針對配送車輛速度連續(xù)變化情況下的多中心混合車隊車輛路徑優(yōu)化問題進行研究。