趙 雄,李 琳

(沈陽(yáng)航空航天大學(xué) 理學(xué)院,遼寧 沈陽(yáng) 110136)

0 引 言

車輛路徑規(guī)劃問(wèn)題(vehicle routing problem,VRP)是規(guī)定一組車輛在一組客戶集合間運(yùn)輸貨物,并使車輛路徑滿足相應(yīng)目標(biāo)函數(shù)要求的研究,是物流運(yùn)輸行業(yè)中十分重要的一個(gè)研究命題,是優(yōu)化物資分配,調(diào)度運(yùn)輸?shù)姆椒ㄖ?。VRP自1959年被提出后便得到了學(xué)者們的關(guān)注,形成以VRP為基礎(chǔ)的各項(xiàng)分支研究。HVRP便是其中之一,主要研究不同車輛在運(yùn)輸調(diào)度中的物資分配問(wèn)題,其中車輛以車輛歸屬、車輛屬性等進(jìn)行區(qū)分。在HVRP下存在不同的研究方向,比如帶時(shí)間窗的HVRP問(wèn)題[1-3](heterogeneous fixed fleet vehicle routing problem with time windows,HVRPTW)、帶取送貨的HVRP問(wèn)題[4-5](heterogeneous fixed fleet vehicle routing problem simultaneous pickup and delivery,HVRPSPD)等。

VRP已知是NP難問(wèn)題,可知HVRP也是NP難問(wèn)題。精確方法求解問(wèn)題具有一定難度,為能快速求解問(wèn)題,部分學(xué)者通過(guò)模擬自然演變,采用元啟發(fā)式方法進(jìn)行求解,并取得了不錯(cuò)的成果。Wu[6]在求解車輛數(shù)量限制下的VRP時(shí),使用自適應(yīng)大鄰域搜索算法,并將算法的消除與添加兩個(gè)變換步驟加以改進(jìn),將客戶運(yùn)用聚類方法分類,并在消除變換過(guò)程按照聚類結(jié)果消除,避免單客戶消除方法中客戶返回原位置這種算力上的浪費(fèi)。Molina[7]在求解HVRPTW時(shí)設(shè)計(jì)了一種具有局部搜索的混合蟻群算法(ant colony system,ACS),稱為memetic-ACS算法,并在其實(shí)驗(yàn)中得到了新的最優(yōu)解。

魯建廈[8]研究了不同初始解對(duì)算法的影響,并證明使用聚類算法生成的初始解能使算法收斂速度有較大改進(jìn)。Meliani[9]和Wei[10]在其研究中就用C-W節(jié)約算法來(lái)求解模型的初始解。Jin[11]使用多啟動(dòng)策略來(lái)增加每次迭代的初始解的多樣性,以此加大產(chǎn)生當(dāng)前最優(yōu)解的可能性。閆軍[12]通過(guò)將客戶集合分成不同的子群,簡(jiǎn)化數(shù)據(jù)復(fù)雜度然后再進(jìn)行求解。

為提高初始解效率,該文通過(guò)均值漂移聚類算法將客戶分成多個(gè)子類,在初始化時(shí)優(yōu)化每條路徑對(duì)客戶個(gè)體的選擇,從而優(yōu)化算法初始解。而后通過(guò)單鏈設(shè)計(jì)優(yōu)化鄰域變換方法,加快LNS算法的收斂速度,并通過(guò)三組實(shí)驗(yàn)驗(yàn)證了MS-LNS算法的合理性及有效性。

1 問(wèn)題描述與數(shù)學(xué)模型

HVRP包括車輛數(shù)量限制下(heterogeneous fleet vehicle routing problem)的HFVRP和無(wú)車輛數(shù)量限制(fleet size and mix vehicle routing problem)的FSMVRP兩類[13]。HFVRP主要求解在現(xiàn)有資源下如何優(yōu)化分配,而FSMVRP則更側(cè)重于市場(chǎng)需求的最優(yōu)調(diào)度方案。該文研究了FSMVRP。

1.1 問(wèn)題描述

該模型以最小化總成本為目標(biāo)函數(shù)值。共有N個(gè)客戶需要服務(wù),每個(gè)客戶的需求量為qi。車場(chǎng)標(biāo)記為0點(diǎn)。運(yùn)輸車輛數(shù)量為K,共有M種車輛。異構(gòu)車輛按照最大載荷量區(qū)分,第k種車輛的載荷為Qk,啟動(dòng)成本為Ck,單位行駛成本為Cu。車輛從車場(chǎng)出發(fā)服務(wù)客戶,服務(wù)完后回到車場(chǎng)。dij表示客戶i到j(luò)的距離。

1.2 數(shù)學(xué)模型

(1)

s.t.

(2)

(3)

(4)

其中,式(1)F為目標(biāo)函數(shù),最小化車輛總成本;式(2)保證每輛車必經(jīng)過(guò)0點(diǎn),即車輛必從0點(diǎn)出發(fā)且回到0點(diǎn);式(3)保證每個(gè)客戶只有一輛車服務(wù),且只服務(wù)一次(此條件可以消除子路徑的可能性);式(4)保證車輛不會(huì)超載。xijk為0-1變量,當(dāng)車輛k經(jīng)過(guò)弧ij時(shí)為1,否則為0。

2 基于均值漂移聚類的LNS算法

在求解HVRP問(wèn)題時(shí)常使用隨機(jī)算法或貪心算法生成初始解。相較于隨機(jī)算法,貪心算法獲取的初始解距最優(yōu)解更近,能加快算法前期收斂進(jìn)度,但由于貪婪算法的最近鄰選擇機(jī)制減弱了初始解群的多樣性,使算法容易出現(xiàn)早熟現(xiàn)象。為找到更合適的初始解,加快算法收斂,該文提出使用均值漂移聚類算法區(qū)分客戶子集,依照客戶子集初始化客戶列表。

2.1 編 碼

總路徑Ω采用單鏈編碼方式?？蛻魪?開(kāi)始編號(hào)V={1,2,…,N}。車輛依照類型從客戶集后一位開(kāi)始編號(hào)M={N+1,N+2,…,N+L},其中任意一個(gè)元素表示一類車輛。每輛車的子路徑Ωk表示為(N+1,3,5,9,12,4,7),其中起始點(diǎn)為車輛類別,其后所有點(diǎn)為子路徑中的客戶點(diǎn)。總路徑表示為Ω={Ω1,Ω2,…,ΩK}。

2.2 均值漂移聚類算法初始化

均值漂移聚類的主要方法是在客戶區(qū)域內(nèi)設(shè)置M個(gè)移動(dòng)點(diǎn)粒子X(jué)m,在每次迭代過(guò)程中移動(dòng)點(diǎn)粒子搜索掃描半徑內(nèi)的所有客戶點(diǎn),依照公式(5)(其中Sm為fm限制條件)生成移動(dòng)向量來(lái)更新移動(dòng)點(diǎn)坐標(biāo)(6),當(dāng)某些移動(dòng)點(diǎn)十分接近的時(shí)候?qū)⑦@些移動(dòng)點(diǎn)合并,直到所有移動(dòng)點(diǎn)不再變化時(shí)停止迭代。此時(shí)剩余移動(dòng)點(diǎn)的個(gè)數(shù)就代表客戶點(diǎn)聚類的個(gè)數(shù),而每個(gè)移動(dòng)點(diǎn)掃描過(guò)的客戶就屬于此類別的客戶子集。

(5)

(6)

初始化步驟為:

Step1:隨機(jī)選擇車輛k,生成子路徑Ωk;

Step2:隨機(jī)選擇客戶子集Vl,l∈M,隨機(jī)選擇其中一客戶作為當(dāng)前點(diǎn)i,添加到Ωk末尾;

Step3:選Vl中距當(dāng)前點(diǎn)i最近的客戶點(diǎn)j=argmin{dij},?j∈Vl添加到Ωk末尾,令i=j;

Step4:判斷下列三種情況:若車輛k達(dá)到載荷上限或最長(zhǎng)工作時(shí)間,Vl中還存在未服務(wù)客戶則隨機(jī)選擇車輛k=k',重新生成子路徑Ωk并返回步驟3;若車輛k未達(dá)到載荷上限和最長(zhǎng)工作時(shí)間,Vl中客戶已完全服務(wù),則返回步驟2;若車輛k達(dá)到載荷上限或最長(zhǎng)工作時(shí)間,且Vl中客戶已完全服務(wù),則進(jìn)行步驟5;

Step5:判斷客戶是否全部分配完成:是,則初始化完成;否,則回到步驟1。

2.3 鄰域變換

該文使用四種鄰域變換方法:insert、swap、two-swap、載重少車輛重新分配(redistribution)。insert為將總路徑Ω中隨機(jī)位置的客戶插入到此路徑的其他位置當(dāng)中;swap是隨機(jī)選取Ω中兩個(gè)不同的客戶互相交換其位置;two-swap是同時(shí)選4個(gè)不同客戶兩兩交換位置(two-swap相當(dāng)于執(zhí)行兩次swap)。在每次迭代時(shí)多次搜索當(dāng)前解鄰域,盡可能找到使目標(biāo)函數(shù)值更好的解。

由于編碼的特殊性質(zhì),使得前三種變換方法不用處理子路徑內(nèi)及子路徑間的區(qū)別,且車輛編號(hào)與客戶編號(hào)在同一編碼當(dāng)中,使得前三種變換方法產(chǎn)生了兩種不同的變換形式,見(jiàn)圖1和圖2。

圖1 insert變換

圖2 swap變換

Step1:檢測(cè)總路徑中每條子路徑載貨率是否達(dá)到標(biāo)準(zhǔn)h;

Step2:將所有未達(dá)到標(biāo)準(zhǔn)的子路徑從總路徑中刪除,生成客戶子集Vl;

Step3:計(jì)算Vl中總客戶需求量Qd,判斷其與不同車輛載荷間的關(guān)系:若Qd>max{Qk},?k∈K則轉(zhuǎn)到步驟4;若Qk>Qd>hQk,?k∈K則轉(zhuǎn)到步驟5;若Qd

Step5:選擇對(duì)應(yīng)車輛k,按照總路徑初始化方式生成子路徑;

2.4 變換后解的接受準(zhǔn)則

該文采用模擬退火算法的接受準(zhǔn)則判斷每次變換后的路徑能否替換當(dāng)前解。當(dāng)前解的目標(biāo)函數(shù)值高于當(dāng)前個(gè)體最優(yōu)解時(shí),通過(guò)計(jì)算公式(7)得到接受概率,再通過(guò)輪盤(pán)賭形式?jīng)Q定是否接受當(dāng)前解。其優(yōu)點(diǎn)在于前期溫度值T較高時(shí)使粒子具有較大的容錯(cuò)能力,可以讓粒子在鄰域內(nèi)快速移動(dòng);而后期T值減小使粒子容錯(cuò)能力減弱,增強(qiáng)了粒子鄰域搜索能力,加快收斂進(jìn)程。每當(dāng)接受準(zhǔn)則成功執(zhí)行時(shí)需要更新溫度值T=ρT。其中ρ為溫度變化率。

P=e(F(Papb)-F(Ω))/T

(7)

算法流程見(jiàn)圖3。

圖3 MS-LNS算法流程

先使用聚類算法將客戶分為多個(gè)子群,而后對(duì)每個(gè)子群使用貪婪算法,這樣既能兼顧貪婪算法對(duì)初始解群的優(yōu)化,也能保證初始種群的多樣性。該文通過(guò)單鏈編碼方式改進(jìn)變換方法使得每次變換的空間更大,搜索速度更快。對(duì)于使用率較差的車輛使用redistribution變換重排。以此三種方式對(duì)LNS算法進(jìn)行改進(jìn),加快LNS求解速度。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)

使用Golden[14]及Penna[15]提供的13-17、20號(hào)算例和對(duì)應(yīng)車輛數(shù)據(jù)(表1中共有六種不同的運(yùn)輸車輛Ver.A-Ver.F),以及Solomon[16]中c201、r201、rc201算例進(jìn)行實(shí)驗(yàn)。Solomon算例使用20號(hào)算例中車輛數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。表1中Q為車輛載荷,C為車輛固定成本。

表1 車輛數(shù)據(jù)

3.2 參數(shù)設(shè)計(jì)

為保證算法的收斂速度與跳出局部最優(yōu)的能力,需要優(yōu)化現(xiàn)有的算法參數(shù)。文中算法涉及兩個(gè)參數(shù),即聚類算法掃描半徑r和模擬退火溫度變化量ρ。分別通過(guò)以下兩種方式計(jì)算適合文中算法的參數(shù)值:

3.2.1 聚類算法掃描半徑r

為保證使用均值漂移聚類時(shí)不會(huì)出現(xiàn)過(guò)多孤立點(diǎn),保證客戶集合分類符合實(shí)際,采用箱型圖檢測(cè)客戶點(diǎn)距離并嘗試1/4位數(shù),中位數(shù),3/4位數(shù)做掃描半徑的效果。15、16號(hào)算例為50個(gè)客戶點(diǎn)(圖4(a)),17號(hào)算例為75個(gè)客戶點(diǎn)(圖4(b)),20號(hào)算例為100個(gè)客戶點(diǎn)(圖4(c))。

圖4 四組數(shù)據(jù)在1/4位數(shù)時(shí)的客戶分類

四組客戶數(shù)據(jù)在取中位數(shù)作為掃描半徑時(shí)都無(wú)法對(duì)客戶集合進(jìn)行分類,取1/4位數(shù)時(shí)每組的分類情況如圖4所示。在1/4位數(shù)周圍取值進(jìn)行驗(yàn)證時(shí)發(fā)現(xiàn),相較于rc201,15號(hào)及17號(hào)客戶數(shù)據(jù)的分類對(duì)掃描半徑的取值十分敏感,令15號(hào)數(shù)據(jù)的掃描半徑r=20.7時(shí),分類個(gè)數(shù)縮減到3個(gè)。令r=19時(shí)分類的數(shù)據(jù)較r=20.2時(shí)有比較明顯的變化,而r=17時(shí)15號(hào)客戶數(shù)據(jù)則被分為六類。為保證分類質(zhì)量,在3.2節(jié)計(jì)算當(dāng)中使用1/4位數(shù)進(jìn)行計(jì)算求解。

3.2.2 模擬退火溫度變化率ρ

采用多組不同的變化率對(duì)算例進(jìn)行檢測(cè),以檢查不同變化率之間的差別,找到盡可能好的參數(shù)值。如圖5所示,共設(shè)置4組參數(shù)值0.95、0.9、0.8、0.7。依照算法生成50個(gè)粒子迭代變換1 000次,總計(jì)10次實(shí)驗(yàn)的平均結(jié)果。

圖5 模擬退火溫度變化率ρ變化曲線

模擬退火的接受條件(7)中粒子每接受一次變換,溫度變量T便會(huì)依照變化率ρ進(jìn)行變化,當(dāng)ρ過(guò)大時(shí)會(huì)導(dǎo)致溫度T變化緩慢,粒子變換的容錯(cuò)能力過(guò)強(qiáng),不利于粒子的局部搜索;而當(dāng)ρ過(guò)小時(shí)T變化過(guò)快,會(huì)導(dǎo)致算法過(guò)快收斂,無(wú)法跳出局部最優(yōu)解?？梢钥闯霾徽撛趫D5(a)還是在圖5(b),當(dāng)變化率ρ=0.9時(shí),算法收斂能力最好。當(dāng)ρ=0.8或0.7時(shí),算法收斂能力相差不大,但都弱于ρ=0.9的時(shí)候,說(shuō)明ρ=0.9時(shí)可以保持良好的收斂性能,具有較快的下降速度。

3.3 實(shí)驗(yàn)結(jié)果

進(jìn)行了三組仿真實(shí)驗(yàn)。實(shí)驗(yàn)一通過(guò)比較同種車輛下與異種車輛下的總成本、總路徑長(zhǎng)度及實(shí)際平均載貨率,驗(yàn)證異構(gòu)車輛在VRP中是否存在優(yōu)勢(shì)。實(shí)驗(yàn)二通過(guò)比較20號(hào)數(shù)據(jù)、c201、r201、rc201在MS-LNS算法及LNS算法下的實(shí)驗(yàn)結(jié)果,檢驗(yàn)均值漂移算法是否對(duì)算法收斂有增益效果。實(shí)驗(yàn)三使用文中算法計(jì)算13-16號(hào)算例并與Penna[15]中結(jié)果進(jìn)行比較。該文使用java編程,在Intel(R) Core(TM) i5-4200H CPU @ 2.80 GHz計(jì)算機(jī)上運(yùn)行。

實(shí)驗(yàn)一:對(duì)17號(hào)算例進(jìn)行10次計(jì)算,每次計(jì)算共得出四組數(shù)據(jù):總成本、固定成本、移動(dòng)成本及載重比,再將所得數(shù)據(jù)按照總成本大小順序排列。為減少數(shù)據(jù)區(qū)間不同所造成的影響,使用相對(duì)數(shù)進(jìn)行比較,其計(jì)算公式為:qR=qA/q,其中qR代表相對(duì)結(jié)果,qA代表數(shù)據(jù)絕對(duì)值,q代表各組數(shù)據(jù)的平均值。計(jì)算結(jié)果如圖6所示。

圖6 17號(hào)算例實(shí)驗(yàn)結(jié)果

其中,車輛類型B的使用量與總成本成反比,而載重比在總成本不斷升高情況下有著逐漸下行的表現(xiàn),說(shuō)明在車輛低載重比的情況下難以達(dá)到最優(yōu)解。分別比較異構(gòu)車輛與其中四種單一車輛的計(jì)算結(jié)果,觀察總成本、總路徑長(zhǎng)度及實(shí)際平均載貨率之間的差別。

由表2可知,B類車輛的計(jì)算結(jié)果與異構(gòu)車輛的計(jì)算結(jié)果十分相近,且比A、C、D類結(jié)果要好,該結(jié)果正好和圖6中顯示的各類車輛數(shù)量與總成本之間的關(guān)系相對(duì)應(yīng),且異構(gòu)車輛問(wèn)題中車輛的平均載重比在五類數(shù)據(jù)中最大,表示異構(gòu)車輛問(wèn)題中所有種類車輛都得到了充分的利用。由此可以證明,異構(gòu)車輛的VRP模型相較于單一車輛的VRP模型具有一定優(yōu)勢(shì)。

實(shí)驗(yàn)二:運(yùn)用MS-LNS算法和LNS算法分別計(jì)算20號(hào)算例、c201、r201及rc201算例10次,其中實(shí)驗(yàn)結(jié)果的平均值如圖7所示。

圖7 MS-LNS算法與LNS算法比較

可以看出,圖7(a)和7(c)中兩種初始化方案尚未產(chǎn)生較大差異,比較(a)(c)兩圖的迭代曲線可知:兩種算法的收斂速度相當(dāng)。在圖7(b)和圖7(d)中均值漂移算法使得初始值相較于使用貪心算法有較大改進(jìn),圖7(b)中雖然MS-LNS在起始點(diǎn)位置的目標(biāo)函數(shù)值與LNS相比稍差,但后續(xù)迭代過(guò)程中MS-LNS的收斂速度卻比LNS的收斂速度要快,使得1 000次迭代后MS-LNS算法的結(jié)果要比LNS算法的更好。

實(shí)驗(yàn)三:將文中算法與四種算法進(jìn)行比較,數(shù)據(jù)如表3～表5所示。其中FSMFD模型的目標(biāo)函數(shù)為固定成本與移動(dòng)成本總和最小,FSMF模型為固定成本最小,FSMD模型指移動(dòng)成本最小。BKs指目前對(duì)應(yīng)算例中的最優(yōu)解值,CG算法及計(jì)算結(jié)果由文獻(xiàn)[17]給出,SMA-U1由文獻(xiàn)[18]給出,VNS1由文獻(xiàn)[19]給出。時(shí)間(t)單位為秒。%為MS-LNS算法與ILS-RVND算法的增量百分比。從表3可以看出,文中算法在最優(yōu)值(m)上與Penna[15]的改進(jìn)算法還有一定差距。文中算法最優(yōu)解與ILS-RVND算法的平均差距為2.67%。在求得文中算法最優(yōu)解情況下所耗時(shí)間(t)要少,算例13所耗時(shí)間比ILS- RVND少20.39 s,算例14的時(shí)間少6.25 s,算例15少6.15 s,算例16少10.97 s。

表3 FSMFD模型結(jié)果

表4 FSMF模型結(jié)果

表5 FSMD模型結(jié)果

在FSMFD模型中MS-LNS算法的平均耗時(shí)較ILS-RVND算法減少了59.33%;在FSMF模型中平均耗時(shí)減少了66.58%;在FSMD模型中減少了66.15%。由此驗(yàn)證了文中算法的高效性和可行性。

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

在基本HVRP模型的基礎(chǔ)上,根據(jù)客戶點(diǎn)分布的空間特性,提出了結(jié)合均值漂移聚類的大鄰域搜索算法,設(shè)計(jì)了三組仿真實(shí)驗(yàn)。三組仿真實(shí)驗(yàn)結(jié)果分別驗(yàn)證了異構(gòu)車輛配送方案在求解VRP問(wèn)題中的效果更好,表明均值漂移聚類算法在隨機(jī)分布和聚類分布這兩類客戶數(shù)據(jù)下對(duì)LNS算法的收斂速度提高更有效果。未來(lái)的研究方向可以對(duì)車輛的不同屬性,如車輛載荷、車輛移動(dòng)成本等因素進(jìn)行敏感性分析,研究不同屬性變化情況對(duì)目標(biāo)函數(shù)的影響。