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

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

0 引言

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

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

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

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

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

1.1 問(wèn)題描述

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

1.2 油耗成本計(jì)算

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

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

(1)

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

(2)

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

(3)

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

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

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

(4)

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

1.3 返回策略設(shè)計(jì)

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

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

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

(5)

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

(6)

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

(7)

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

1.4 目標(biāo)函數(shù)

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

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

(8)

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

(9)

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

(10)

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

(11)

2 模型建立

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

目標(biāo)函數(shù)

minC1+C2+C3+C4。

(12)

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

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

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

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

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

3.1.1 初始種群的生成

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

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

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

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

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

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

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

3.1.2 初始解的生成

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

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

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

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

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

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

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

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

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

(27)

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

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

3.3 交叉操作

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

步驟1選擇待插入客戶。

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

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

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

(28)

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

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

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

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

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

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

(1)路徑破壞

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

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

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

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

(2)路徑修復(fù)

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

3.5 變鄰域搜索策略

為了提高HGALNS算法的深度搜索能力,本文引入變鄰域搜索算法中的擾動(dòng)策略,該策略根據(jù)各“破壞—修復(fù)”算子運(yùn)行后最優(yōu)解的變化情況調(diào)整算子的交替搜索順序和策略。在該策略下,“隨機(jī)客戶破壞—修復(fù)”算子作為第一順序鄰域搜索算子的運(yùn)行次數(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ù)值分析

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

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

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

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

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

4.2 算法驗(yàn)證

本節(jié)對(duì)HGALNS與其他啟發(fā)式算法的性能差距進(jìn)行驗(yàn)證。因?yàn)槟壳皼](méi)有MDMFVRP-MTW算例,所以對(duì)已有文獻(xiàn)中與MDMFVRP-MTW相關(guān)的基本問(wèn)題進(jìn)行3組數(shù)值實(shí)驗(yàn)。

4.2.1 實(shí)驗(yàn)1

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

表2 HGALNS與文獻(xiàn)[23]求解結(jié)果對(duì)比

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

對(duì)比已有文獻(xiàn)算法的求解結(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個(gè)算例中10個(gè)算例的最好解。在求解時(shí)間上,相同運(yùn)行環(huán)境下,本文算法的求解時(shí)間短,在中小規(guī)模算例中的求解時(shí)間略優(yōu)于HGAVNS_TS,而且隨著算例客戶規(guī)模的增加,算法求解時(shí)間明顯優(yōu)于其他兩種啟發(fā)式算法。通過(guò)對(duì)比分析說(shuō)明,HGALNS算法的性能優(yōu)于LNS和HGANLS_TS。

4.2.2 實(shí)驗(yàn)2

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

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

4.2.3 實(shí)驗(yàn)3

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

表4 HGALNS與文獻(xiàn)[27]求解結(jié)果對(duì)比

由表4可知,在求解質(zhì)量方面,CW-TS與HGALNS算法10次求解的平均值分別為8 080.70,8 012.49,本文算法求得的時(shí)間窗懲罰成本較CW-TS改進(jìn)了33.94%,總成本較CW-TS改進(jìn)了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,進(jìn)一步驗(yàn)證了本文HGALNS的有效性。

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

4.3 算例分析

4.3.1 算例設(shè)計(jì)

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

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

表5 車輛參數(shù)

續(xù)表5

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

4.3.2 算例求解

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

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

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

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

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

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

4.3.3 敏感性分析

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

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

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

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

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

表10 運(yùn)力平衡敏感性分析

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

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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