遺傳算法求解帶時間窗的車輛路徑問題

文/周景欣

引言

隨著互聯(lián)網(wǎng)的進(jìn)步，電子商務(wù)業(yè)的飛速發(fā)展，人們的生活愈發(fā)信息化，車輛路徑問題的客戶已經(jīng)從以前的大型超市、生產(chǎn)基地等更多的落地到如家庭、個人等小而精的客戶身上。帶時間窗的車輛路徑問題（VRPTW）更加貼切現(xiàn)在和未來對于車輛路徑問題的描述。VRPTW 是VRP問題的一種常見的變體，配送車輛容量有限，每一個客戶都擁有一個特定的交付時間窗口所限定，車隊運(yùn)輸需要在客戶的時間窗內(nèi)抵達(dá)客戶所在位置為客戶服務(wù)，否則將受到一定的懲罰。VRPTW 也被認(rèn)為是NP-hard[1]，精確算法求解車輛路徑問題僅僅適用于規(guī)模較小的問題，而面對現(xiàn)實世界中大型的VRPTW 時，啟發(fā)式和元啟發(fā)式通常更加適合[2]。模擬退火（SA）、禁忌搜索（TS）[6]、蟻群優(yōu)化(ACO)[4]、遺傳算法(GA)[3]、粒子群優(yōu)化（PSO）[5]等算法已被證明可有效解決復(fù)雜的多目標(biāo)問題，在求解車輛路徑問題上取得了顯著的成果。本文以最小化物流配送成本為目標(biāo)，研究帶時間窗的車輛路徑問題，建立數(shù)學(xué)模型;為克服遺傳算法收斂速度慢的缺陷，設(shè)計并采用了自適應(yīng)大鄰域算法中的破壞算子，通過局部搜索策略，保留較優(yōu)解。通過實際算例測試表明，改進(jìn)的遺傳算法較簡單遺傳算法有較好的局部尋優(yōu)能力，驗證了本文算法的有效性。

1.問題描述

VRPTW 可描述為：對一系列的裝貨點和（或）卸貨點，組織合理的行車線路，使車有序地通過它們，在滿足貨物的需求量、車輛的容量限制、車輛的行駛時間、顧客要求的服務(wù)時間窗口等約束條件下，以最低的總成本滿足所有客戶的需求[9]。時間窗可分為硬時間窗和軟時間窗，本文的研究都是以軟時間窗為基礎(chǔ)。

圖1-1中線路上的數(shù)值表示的是車輛的行駛時間，且以配送中心時間窗開始時間為車輛的出發(fā)時間。圖1-1(a)表示配送網(wǎng)絡(luò)優(yōu)化前，配送中心服務(wù)客戶的配送線路存在著大量交錯運(yùn)輸和長距離運(yùn)輸?shù)那闆r，并且存在違反時間窗的客戶點較多，而配送網(wǎng)絡(luò)優(yōu)化后（見圖1-1(b)），客戶被分配到臨近的配送中心接受物流服務(wù)，不僅沒有出現(xiàn)違反時間窗的客戶點，而且消除了長距離的交錯運(yùn)輸。

圖1 -1配送網(wǎng)絡(luò)優(yōu)化前后對比

表1 -1 配送網(wǎng)絡(luò)優(yōu)化前后成本對比

2.模型建立

2.1 符號定義

配送網(wǎng)絡(luò)優(yōu)化問題的變量定義如表2-1所示。

表2 -1變量定義

2.2 模型構(gòu)建，為構(gòu)建模型做如下假設(shè)：（1）客戶的貨物需求量均小于車輛的載容量，一輛車可以滿足多個客戶需求；（2）所有的客戶均由一個配送中心供貨；（3）只有一種型號的車輛參與配送；（4）車輛的行駛速度是保持恒定的，即勻速行駛、以配送物流運(yùn)營成本Z最小化為目標(biāo)，建立帶時間窗的車輛路徑優(yōu)化模型:

Z3：表示配送車輛違反客戶時間窗的懲罰成本。

式（5）表示一個客戶僅由一輛車服務(wù)；式（6）表示每個客戶僅接受一條配送線路服務(wù)；式（7）表示車輛服務(wù)客戶后必須離開；式（8）表示消除線路上的子回路；式（9）表示車輛離開配送中心的時間必須在其開放時間之內(nèi)；式（10）表示車輛到達(dá)配送中心的時間必須在其開放時間之內(nèi)；式（11）-（14）表示時間連續(xù)性約束；式（15）表示車輛的裝載量不超過車輛容量；式（16）-（17）表示決策變量。

3.改進(jìn)的遺傳算法

應(yīng)用改進(jìn)的遺傳算法進(jìn)行優(yōu)化計算和模型求解，相關(guān)變量定義為：popsize表示種群規(guī)模，genmax表示最大迭代次數(shù)，ps，pc和pm分別表示選擇，交叉和變異概率，Pt與Qt分別表示初始種群和子代種群，gen表示當(dāng)前算法迭代次數(shù)?；旌纤惴ǖ木唧w流程下：Step 2：應(yīng)用改進(jìn)的方式生成初始種群Pt，設(shè)置gen=1。Step 3：對初始種群Pt中的染色體進(jìn)行選擇，交叉和變異操作生成子代種群Qt。具體的選擇，交叉和變異過程如下述Step3.1-Step3.3所示[8][9][10]。Step 3.1：設(shè)計適應(yīng)度函數(shù)并計算適應(yīng)度函數(shù)值，根據(jù)染色體的適應(yīng)度大小應(yīng)用輪盤賭方法經(jīng)過多輪選擇確定子代種群。Step 3.2：交叉操作，根據(jù)交叉概率隨機(jī)選擇染色體進(jìn)行交叉運(yùn)算，并采用單點交叉法，兩點交叉法和部分映射交叉法生成子代染色體，并與父代染色體進(jìn)行比較選擇子代染色體。Step 3.3：變異操作，根據(jù)變異概率隨機(jī)選擇染色體進(jìn)行變異運(yùn)算，并采用部分映射變異和互換操作算子生成子代染色體，并與父代染色體比較選擇子代染色體。Step 4：將Pt與Qt合并形成新的種群Rt，評價種群個體的目標(biāo)函數(shù)值。Step 5：令gen=gen+1，重復(fù)混合算法Step3進(jìn)行循環(huán)操作，直到達(dá)到最大迭代次數(shù)genmax。Step 7：通過計算染色體對應(yīng)個體目標(biāo)函數(shù)值的大小，選取并輸出最優(yōu)解，結(jié)束算法。

4.算例及結(jié)果分析

4.1 算例相關(guān)數(shù)據(jù)。本文以重慶市某物流企業(yè)的配送網(wǎng)絡(luò)為例進(jìn)行研究，選擇了一個配送中心和50個客戶，最多可使用車輛15輛。其中配送中心的坐標(biāo)為（40，50），客戶點特征如表4-1所示。根據(jù)已有相關(guān)文獻(xiàn)和實例數(shù)據(jù)規(guī)模，設(shè)置相應(yīng)參數(shù)為：種群大小=100，迭代次數(shù)=100，交叉概率=0.9，變異概率=0.05。

表4 -2 優(yōu)化結(jié)果

表4 -1客戶特征

4.2 VRPTW 配送優(yōu)化方案

在配送中心的服務(wù)周期內(nèi)，應(yīng)用上述改進(jìn)的遺傳算法求解帶VRPTW 的物流成本和車輛使用數(shù)，得到8條車輛優(yōu)化路徑，如下所示：配送路線1：0→2→5→6→4→3→1→0；配送路線2：0→7→9→10→11→8→0；配送路線3：0→37→35→34→30→29→32→36→0；配送路線4：0→12→14→16→15→13→0；配送路線5：0→28→26→25→33→31→27→0；配送路線6：0→19→18→17→20→22→23→24→21→0；配送路線7：0→43→39→38→40→41→42→44→0；配送路線8：0→49→47→46→45→48→50→0；該結(jié)果中車輛行駛總距離為626.2806，總成本為3314.03元。

4.3 優(yōu)化結(jié)果分析。由圖4-2可知，車輛固定成本，懲罰成本和配送成本都有所下降，且物流運(yùn)營總成本由7835.43元下降到了4114.03，直接下降了47.5%。此外，利用改進(jìn)的遺傳算法求解的優(yōu)化結(jié)果有效地消除了違反客戶時間窗的現(xiàn)象，并且大幅度地減少了行駛路程，從而得到了較優(yōu)的結(jié)果。

結(jié)束語

本文結(jié)合配送中心對配送路徑的要求，以VRPTW 為研究對象，站在物流企業(yè)的角度，建立了成本最小化的數(shù)學(xué)模型。針對遺傳算法局部搜索能力差的缺點，結(jié)合混合遺傳算法的特點，在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上，改進(jìn)了初始種群的生成方式，并且引進(jìn)自適應(yīng)大領(lǐng)域算法中破壞算子的移除和插入操作對個體進(jìn)行局部搜索。研究結(jié)果表明，該算法對求解帶時間窗約束車輛路徑問題是有效的，并且能有效降低物流成本和提高配送車輛使用效率。

引用出處

[1]胡大偉,陳希瓊,高揚(yáng).定位-路徑問題綜述[J].交通運(yùn)輸工程學(xué)報,2018,18(01):111-129.

[2]賀協(xié)騰.選址路徑問題及其優(yōu)化算法綜述[J].中國新技術(shù)新產(chǎn)品,2009(18):13.

[3]慕晶晶.基于遺傳算法的服裝退貨回收車輛路徑優(yōu)化問題研究[J].物流工程與管理,2021,43(03):123-125.

[4]熊沂鋮,王棟.基于蟻群算法的車輛路徑問題研究[J].信息技術(shù),2019,43(07):15-17+23.

[5]胡小宇,劉慶,賀文寧,馬炫.基于粒子群算法的單倉儲多車物流配送優(yōu)化[J].計算機(jī)應(yīng)用,2018,38(S2):21-26.

[6]李陽,范厚明,張曉楠,楊翔.求解模糊需求車輛路徑問題的兩階段變鄰域禁忌搜索算法[J].系統(tǒng)工程理論與實踐,2018,38(02):522-531.