朱 杰，張培斯，張?jiān)冇?，余微?/p>

(北京物資學(xué)院 信息學(xué)院，北京 101149)

0 引 言

多時間窗車輛路徑問題是車輛路徑問題[1]的擴(kuò)展，它源于現(xiàn)實(shí)生活中人們對服務(wù)時間的需求。例如某甲要為周邊多個用戶提供配送服務(wù)，假設(shè)用戶乙在[8:00，10:00]和[12:00，13:00]時間段有空閑時間接受服務(wù)，用戶丙在[12:00，12:30]和[16:30，17:20]時間段內(nèi)有空閑時間接受服務(wù)，用戶丁等也具有多個互不重疊的時間窗；這就需要甲安排合理的路線，在滿足用戶要求的情況下實(shí)現(xiàn)成本最低、路程最短或用車最少等目標(biāo)。

從時間窗的數(shù)量角度劃分，帶時間窗的車輛路徑問題可分為單時間窗問題和多時間窗問題；目前關(guān)于帶時間窗的車輛路徑問題研究主要集中在單時間窗[2-4]類型，而多時間窗的車輛路徑問題研究文獻(xiàn)相對較少。Belhaiza等[5]提出了變鄰域禁忌搜索算法求解最小等待和延誤時間的多時間窗車輛路徑問題；Beheshti等[6]設(shè)計(jì)了協(xié)同進(jìn)化多目標(biāo)量子遺傳算法求解帶有優(yōu)先級順序的多時間窗車輛路徑問題；Favaretto等[7]提出了允許多次訪問的多時間窗車輛路徑問題；馬華偉等[8]設(shè)計(jì)了一種求解允許分割配送的多時間窗車輛路徑問題的改進(jìn)蟻群算法；黃秋愛等[9]通過引入最優(yōu)個體保留機(jī)制改進(jìn)傳統(tǒng)的遺傳算法，并設(shè)計(jì)數(shù)學(xué)模型進(jìn)行求解，驗(yàn)證了算法及其模型的有效性；朱玲玲等[10]提出一種協(xié)同禁忌優(yōu)化算法，通過掃描算法求得初始解，再設(shè)計(jì)自適應(yīng)修改禁忌長度的算法和多個子禁忌算法進(jìn)行協(xié)同優(yōu)化進(jìn)行求解；李珍萍等[11]運(yùn)用智能水滴算法對多時間窗車輛路徑問題進(jìn)行了有效探索；閆芳等[12]應(yīng)用粒子群算法，以總成本最小和滿意度最大為目標(biāo)，求解了多模糊時間窗車輛路徑問題。

蟻群算法[13]是意大利學(xué)者Dorigo在20世紀(jì)90年代提出的一種仿生算法，具有正反饋、分布式計(jì)算以及貪婪的啟發(fā)式搜索等特點(diǎn)，同時具有較好的耦合性，易于和其他算法結(jié)合，這些特點(diǎn)為更好地解決組合優(yōu)化問題提供了可能[14]。文中以總成本最小為目標(biāo)，建立多時間窗車輛路徑問題的數(shù)學(xué)模型，改進(jìn)蟻群算法對問題進(jìn)行求解，并通過算例驗(yàn)證模型和算法有效性。

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

1.1 問題描述

1.2 模型假設(shè)

假設(shè)一：每個用戶的需求量不超過車輛最大載重量；假設(shè)二：用戶的時間窗為硬時間窗要求；假設(shè)三：用戶的各個時間窗互不重疊；假設(shè)四：單車場多需求點(diǎn)的配送模式；假設(shè)五：各個配送車裝載量相同；假設(shè)六：用戶的需求不可分割。

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

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

Rik+Tij·xijk+Si·xijk-M(1-xijk)≤Rjk

(11)

目標(biāo)函數(shù)1表示總成本最小，其中第一項(xiàng)表示動用車輛的固定成本，第二項(xiàng)表示車輛運(yùn)行成本；式2、3表示一個用戶能且僅能被訪問一次；式4表示所有車輛必須從配送中心出發(fā)，最終返回配送中心；式5表示完成所有任務(wù)共動用的車輛數(shù)；式6表示任何一輛車所服務(wù)的用戶的總需求量不超過車輛最大裝載量；式7表示如果車輛k到達(dá)j點(diǎn)，則必為j用戶提供服務(wù)；式8表示如果車輛k為i用戶提供服務(wù)，則服務(wù)完必從i點(diǎn)離開；式9表示任何車輛在其配送路線上前后兩個相繼節(jié)點(diǎn)的時刻之間的關(guān)系；式10、11為時間窗約束。

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

2.1 基本蟻群算法

螞蟻在協(xié)同覓食的過程中，會在經(jīng)過的路徑上留下信息素，每一只螞蟻經(jīng)過的路徑都可以看作是一個可行解，各個螞蟻之間通過信息素進(jìn)行聯(lián)系，螞蟻覓食時會選擇信息素較高的路徑，信息素越高，被選的概率就越大，隨著時間的推移，較優(yōu)路徑上的信息素會越來越多，而其他路徑上的信息素隨著蒸發(fā)逐漸降低，算法最終收斂到最優(yōu)解或近似最優(yōu)解[3]。但是該算法也有搜索時間長和收斂速度慢、容易陷入局部最優(yōu)解等缺點(diǎn)，對此，文中改進(jìn)轉(zhuǎn)移概率和信息素更新公式以跳出局部最優(yōu)陷阱，結(jié)合鄰域搜索策略提高算法的尋優(yōu)能力，加快算法收斂速度。

2.2 改進(jìn)算法描述

2.2.1 偽隨機(jī)轉(zhuǎn)移概率公式

(12)

其中，τij為從i到j(luò)的信息素濃度；α為信息素濃度重要因子；ηij為啟發(fā)函數(shù)，ηij=1/Dij，表示螞蟻從用戶點(diǎn)i到j(luò)的期望程度；β為啟發(fā)函數(shù)重要因子；ωij為節(jié)約值，ωij=Di0+D0j-Dij；ε為節(jié)約值重要因子；allowk表示車輛在滿足約束條件下可訪問點(diǎn)的集合。

2.2.2 鄰域搜索策略

蟻群算法具有貪婪的啟發(fā)式搜索特性，這就造成算法在構(gòu)造可行解的時候，只關(guān)心解的成分，而不關(guān)心解是怎么組成的，它只會隨機(jī)組合這些成分，而最優(yōu)解的組合方式一般是唯一的，隨機(jī)組合得到最優(yōu)解的可能性很低。因此借助鄰域搜索策略增加算法搜索廣度，提高解的質(zhì)量。鄰域搜索是指對產(chǎn)生的可行路徑進(jìn)行位置擾動并重新組合，假設(shè)當(dāng)前路徑中的節(jié)點(diǎn)個數(shù)為N，則其鄰域變換的規(guī)模大小為N(N-1)/2，通過對路徑進(jìn)行節(jié)點(diǎn)位置調(diào)換，如果調(diào)換兩點(diǎn)后的路徑滿足約束條件，并且解的質(zhì)量變優(yōu)，則接受優(yōu)化后的路徑，否則保持原路徑不變。

2.2.3 信息素更新策略

當(dāng)全部螞蟻完成對所有節(jié)點(diǎn)的訪問后，對當(dāng)前最優(yōu)路徑進(jìn)行信息素更新，更新公式為：

τij(t+1)=(1-ρ)·τij(t)+Δτij

(13)

為了防止算法容易停滯和陷入局部最優(yōu)解，結(jié)合模擬退火法[15]的特點(diǎn)，以一定概率接受惡化解，幫助算法跳出局部最優(yōu)的陷阱。fk+1為當(dāng)前螞蟻完成本次循環(huán)后得到的局部最優(yōu)解，Δf=fk+1-fk，如果Δf<0，則接受新解，否則進(jìn)行判斷，p=exp(-Δf/T)，如果p大于(0,1)間的隨機(jī)數(shù)，則接受新的惡化解作為最優(yōu)解，否則不接受，最優(yōu)解仍為fk。T是當(dāng)前溫度，完成一次循環(huán)后進(jìn)行降溫處理，降溫速率為r，T(t+1)=T(t)·r。

2.3 算法步驟

(1)輸入?yún)?shù)，初始化信息素矩陣，設(shè)置最大迭代次數(shù)N和螞蟻個數(shù)K；

(2)將螞蟻放置起點(diǎn)，設(shè)當(dāng)前出發(fā)點(diǎn)為i，建立禁忌表，即螞蟻已訪問節(jié)點(diǎn)和未訪問節(jié)點(diǎn)集合，同時建立allowk表，即可去點(diǎn)的集合；

(3)從當(dāng)前出發(fā)點(diǎn)i開始，根據(jù)約束條件從未訪問節(jié)點(diǎn)集合中搜索出下個可去點(diǎn)并將其放入allowk，直至所有節(jié)點(diǎn)搜索完畢，如果allowk為空集，則車輛返回配送中心，更新車輛信息，再令i=0，繼續(xù)執(zhí)行本步驟；

(4)根據(jù)轉(zhuǎn)移概率公式，按照輪盤賭的方法從allowk表中選擇下個訪問節(jié)點(diǎn)j，同時更新禁忌表以及車輛載重信息；如果全部節(jié)點(diǎn)訪問完畢，轉(zhuǎn)至步驟5，否則令i=j，轉(zhuǎn)步驟4；

(5)如果所有節(jié)點(diǎn)均已訪問完畢，則k=k+1，轉(zhuǎn)至步驟2；如果所有螞蟻遍歷完畢，找出當(dāng)前最優(yōu)解，按照鄰域搜索策略進(jìn)行可行解的優(yōu)化，然后根據(jù)更新公式更新信息素；n=n+1，如果n

(6)輸出結(jié)果，退出程序。

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

多時間窗車輛路徑問題尚無標(biāo)準(zhǔn)的測試數(shù)據(jù)，該算例數(shù)據(jù)取自文獻(xiàn)[11]，不在此一一列舉。改進(jìn)蟻群算法的參數(shù)設(shè)置為：種群規(guī)模100，迭代次數(shù)200，初始信息素為1，α=1，β=2，ε=1，ρ=0.1，T=1 000，r=0.9。改進(jìn)蟻群算法求得的最優(yōu)解為2 156.8，共需要4輛車完成配送任務(wù),路線如圖1、2和表1所示。

圖1 路線圖1

圖2 路線圖2

車輛路線裝載率/%10→1→4→3→6→2→5→06020→7→9→10→8→11→072.53a0→20→19→15→18→0953b0→18→15→19→20→09540→17→16→13→14→12→095

車輛一從配送中心出發(fā)，按路線4-3-6-2-5給用戶提供配送服務(wù)，完成后返回配送中心；

車輛二從配送中心出發(fā)，按路線7-9-10-8-11給用戶提供配送服務(wù)，完成后返回配送中心；

車輛三有兩種方案選擇，車輛從配送中心出發(fā)，可以按路線20-19-15-18給用戶提供配送服務(wù)，或按路線18-15-19-20給用戶提供配送服務(wù)，完成后返回配送中心；其成本和距離一樣，決策者可根據(jù)實(shí)際情況自行選擇行車路線安排配送；

車輛四從配送中心出發(fā)，按路線17-16-13-14-12給用戶提供配送服務(wù)，完成后返回配送中心。

與文獻(xiàn)[11]的結(jié)果相比較，智能水滴算法求得的結(jié)果為2 168.9，改進(jìn)后的蟻群算法求得的結(jié)果為2 156.8，最快一次僅七代就搜索到最優(yōu)解，而且結(jié)果變優(yōu)，同時線路選擇增加；相比智能水滴算法，改進(jìn)蟻群算法可以更好地求得最優(yōu)解。

同時，為進(jìn)一步驗(yàn)證改進(jìn)蟻群算法在求解多時間窗車輛路徑問題上的有效性，又分別用標(biāo)準(zhǔn)蟻群算法、模擬退火算法和禁忌搜索算法進(jìn)行20次測試對比，結(jié)果如表2所示。

表2 算法對比

從表2中可以看出，在20次實(shí)驗(yàn)中，改進(jìn)蟻群算法求得的最優(yōu)解為2 156.8，平均每次求得的最優(yōu)解為2 161，標(biāo)準(zhǔn)差為6.69，三項(xiàng)指標(biāo)均優(yōu)于其他三種算法。標(biāo)準(zhǔn)蟻群算、模擬退火算法和禁忌搜索算法均停留在某個局部最優(yōu)解上，說明改進(jìn)蟻群算法在跳出局部最優(yōu)解方面具有良好的性能，而且算法求解的標(biāo)準(zhǔn)差較小，結(jié)果相對穩(wěn)定，而未改進(jìn)的標(biāo)準(zhǔn)蟻群算法、模擬退火算法和禁忌搜索算法在求解過程中的穩(wěn)定性較差。

從圖3可以看出，模擬退火算法和禁忌搜索算法在迭代過程中變化幅度大，穩(wěn)定性差，而且求解質(zhì)量不高，而改進(jìn)蟻群算法在求解問題時速度較快，穩(wěn)定性好，求解質(zhì)量高于其他三種算法。

圖3 算法迭代對比圖

4 結(jié)束語

車輛路徑問題屬于NP難題，構(gòu)造高質(zhì)量的啟發(fā)式算法是很多學(xué)者的研究方向。針對多時間窗車輛路徑問題建立了一般數(shù)學(xué)模型，改進(jìn)蟻群算法進(jìn)行求解，和其他算法求得的結(jié)果進(jìn)行比對分析。改進(jìn)后的蟻群算法在求解多時間窗車輛路徑問題上有著較好的性能，是求解多時間窗車輛路徑問題的較好途徑。