基于遺傳算法的后勤運(yùn)輸車(chē)路徑規(guī)劃

張 亮，周繼寶

(1.沈陽(yáng)理工大學(xué) 汽車(chē)學(xué)院，沈陽(yáng) 110168;2.第二炮兵士官學(xué)校 501 教研室，山東 濰坊 262500)

軍事后勤保障主要指在戰(zhàn)時(shí)或平時(shí)軍用物資的籌措、儲(chǔ)存、運(yùn)輸和流通等過(guò)程，是軍事戰(zhàn)略戰(zhàn)術(shù)中重要的組成部分。現(xiàn)代信息化戰(zhàn)爭(zhēng)對(duì)后勤保障提出了準(zhǔn)確、快速的要求，如何建立科學(xué)有效的后勤配送運(yùn)輸體系對(duì)于提高后勤物資和作戰(zhàn)物資配送速度、節(jié)約軍費(fèi)開(kāi)支等均具有重要的意義。

后勤運(yùn)輸車(chē)的路徑優(yōu)化問(wèn)題是后勤運(yùn)輸體系中的重要組成部分，主要是指如何設(shè)計(jì)一條配送路徑，使運(yùn)輸車(chē)從出發(fā)點(diǎn)將物資成功運(yùn)送至各個(gè)需求點(diǎn)，實(shí)現(xiàn)行駛里程最短。本文針對(duì)此問(wèn)題展開(kāi)研究，將遺傳算法引入到優(yōu)化過(guò)程中，以實(shí)現(xiàn)配送車(chē)輛路徑選取的最優(yōu)決策。

1 后勤配送系統(tǒng)分析

后勤運(yùn)輸車(chē)輛配送路線的合理優(yōu)化既能夠提高后勤運(yùn)輸保障效能，又能保持運(yùn)輸保障與作戰(zhàn)部隊(duì)的保障需求協(xié)調(diào)一致，是當(dāng)代信息化戰(zhàn)爭(zhēng)不容忽視的技術(shù)性環(huán)節(jié)之一，具有重要的理論意義和使用價(jià)值，主要體現(xiàn)在以下方面:

1)優(yōu)化戰(zhàn)略物資運(yùn)輸路線，可以提高運(yùn)輸效率，實(shí)現(xiàn)整體戰(zhàn)略補(bǔ)給速度最優(yōu)化，提高后勤保障能力。

2)可以準(zhǔn)時(shí)、快速地把戰(zhàn)略物資送到相應(yīng)的部隊(duì)所在地，從而潛在地提高部隊(duì)作戰(zhàn)效能。

3)合理的優(yōu)化可以使后勤運(yùn)輸車(chē)輛的配送任務(wù)完成得更為精確。

4)可以節(jié)約運(yùn)輸成本，節(jié)省費(fèi)用開(kāi)支。

后勤運(yùn)輸車(chē)配送過(guò)程需要將軍用物資或補(bǔ)給從配送出發(fā)點(diǎn)逐次送往戰(zhàn)略基地，即接收點(diǎn)。與一般城市配送不同，戰(zhàn)略后勤運(yùn)輸車(chē)在配送任務(wù)結(jié)束后需要將配送車(chē)輛開(kāi)至指定位置而非返回原點(diǎn)，如圖1 所示。

配送路線的優(yōu)化從數(shù)學(xué)的角度屬于NP-hard 問(wèn)題，隨著節(jié)點(diǎn)數(shù)量增多的呈現(xiàn)維數(shù)災(zāi)現(xiàn)象，因此傳統(tǒng)的枚舉法往往并不適用。另外在實(shí)時(shí)戰(zhàn)略實(shí)施過(guò)程中，優(yōu)化算法必須要求時(shí)效性和通用性，能夠?qū)崿F(xiàn)路徑選取方案的動(dòng)態(tài)優(yōu)化管理［1-3］。

2 數(shù)學(xué)建模

2.1 輸入與輸出

為了便于對(duì)后勤運(yùn)輸車(chē)配送優(yōu)化問(wèn)題進(jìn)行研究，首先建立數(shù)學(xué)模型。模型的輸入為已知的各個(gè)需求點(diǎn)的地理位置，可以用各個(gè)需求點(diǎn)及運(yùn)輸起始點(diǎn)的距離矩陣描述，如式(1)所示。

其中D 為距離矩陣。

優(yōu)化模型的輸出是一系列車(chē)輛路徑的選取決策的集合，即

其中:n 為需求點(diǎn)的數(shù)目;A0為運(yùn)輸起始點(diǎn);A1為運(yùn)輸終止點(diǎn);Bki為第i 個(gè)需求點(diǎn)。

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

后勤運(yùn)輸車(chē)配送路線優(yōu)化問(wèn)題的優(yōu)化目標(biāo)是使配送任務(wù)在盡可能短的時(shí)間內(nèi)完成。假設(shè)車(chē)輛行駛速度為定值，則所耗費(fèi)的時(shí)間與行駛里程呈正比，根據(jù)輸入條件的形式，總的行駛里程在建模過(guò)程中可以分為3 部分進(jìn)行計(jì)算，即從出發(fā)點(diǎn)至第1 個(gè)需求點(diǎn)的路徑長(zhǎng)度，遍歷所有需求點(diǎn)的路徑長(zhǎng)度和最后一個(gè)需求點(diǎn)至運(yùn)輸終止點(diǎn)的路徑。優(yōu)化數(shù)學(xué)模型的目標(biāo)函數(shù)為

其中:λD為總的運(yùn)輸路線行駛里程;d(·)為距離算子;Bx為從出發(fā)點(diǎn)配送至的第1 個(gè)需求點(diǎn);By為到達(dá)終止點(diǎn)前的最后一個(gè)需求點(diǎn)。

2.3 約束條件

每輛后勤運(yùn)輸車(chē)配送至所有需求點(diǎn)的過(guò)程中所能攜帶的貨物量存在一個(gè)上限，且配送時(shí)間不能超過(guò)最大時(shí)間上限，因此約束條件可以如式(4)、(5)所示進(jìn)行描述。

其中:Qmax為每輛配送車(chē)輛的載運(yùn)上限值;q(·)為需求量計(jì)算因子。

其中:v 為平均車(chē)速;T 為配送任務(wù)所要求的最大時(shí)間限度;α 為因裝卸所產(chǎn)生的時(shí)間修正因子。

2.4 優(yōu)化模型

優(yōu)化問(wèn)題的求解是根據(jù)輸入條件與目標(biāo)函數(shù)，確定最優(yōu)的路徑解決方案，并滿足約束條件。根據(jù)上述分析過(guò)程，可以將后勤運(yùn)輸車(chē)從出發(fā)點(diǎn)向各個(gè)戰(zhàn)略需求點(diǎn)進(jìn)行配送并最終抵達(dá)終止點(diǎn)的路徑尋優(yōu)問(wèn)題的優(yōu)化模型如式(6)所示進(jìn)行描述。

3 基于遺傳算法的優(yōu)化方案

遺傳算法具有潛在的并行尋優(yōu)特性和不依賴(lài)于梯度信息的特點(diǎn)，因此廣泛應(yīng)用于諸多優(yōu)化領(lǐng)域，可以處理傳統(tǒng)搜索方法難以解決復(fù)雜非線性?xún)?yōu)化問(wèn)題［4-5］。

本文采用遺傳算法來(lái)進(jìn)行后勤運(yùn)輸車(chē)配送路線的優(yōu)化。首先將遺傳算法基本參數(shù)設(shè)定如下:

種群大小M=20

最大代數(shù)G=100

交叉概率Pc=1.0

變異概率Pm=0.1

基于遺傳算法的后勤運(yùn)輸車(chē)配送路線優(yōu)化的具體實(shí)施步驟如圖2 所示。

圖2 基于遺傳算法的車(chē)輛路徑優(yōu)化流程

在設(shè)定參數(shù)完成之后，對(duì)可行解空間進(jìn)行遺傳編碼操作，并生產(chǎn)初始種群，設(shè)定適配度函數(shù)與遺傳算法終止條件。

3.1 編碼規(guī)則

遺傳算法編碼的方案通常有二進(jìn)制編碼和浮點(diǎn)數(shù)編碼2種。針對(duì)后勤運(yùn)輸車(chē)配送路徑優(yōu)化問(wèn)題的特點(diǎn)，采用十進(jìn)制浮點(diǎn)數(shù)編碼方案，使用各個(gè)需求點(diǎn)的節(jié)點(diǎn)編號(hào)作為基因來(lái)組成染色體，例如對(duì)于染色體:

其對(duì)應(yīng)的表現(xiàn)型為:

3.2 適配度函數(shù)

適配度函數(shù)是根據(jù)優(yōu)化問(wèn)題的數(shù)學(xué)模型中的目標(biāo)函數(shù)轉(zhuǎn)化而來(lái)，如式(7)所示定義。

其中:dδs與dδe分別為路徑中第1 路段與最后路段的長(zhǎng)度，к1～кn表示由可行解的編碼所決定的配送節(jié)點(diǎn)順序。

3.3 遺傳算子設(shè)計(jì)

主要包括選擇算子、交叉算子和變異算子的設(shè)計(jì)。選擇算子的設(shè)計(jì)方案采用經(jīng)典的排序法，即根據(jù)染色體計(jì)算所得的適配度函數(shù)來(lái)進(jìn)行排序操作，根據(jù)適配度值來(lái)選擇排序靠前的10個(gè)染色體作為選擇結(jié)果。

交叉操作采用單點(diǎn)交叉，對(duì)于選定的2 個(gè)父代個(gè)體隨機(jī)地選取第t 個(gè)基因處為交叉點(diǎn)，首先將父輩X1中的前t 個(gè)基因作為子代個(gè)體的前t 個(gè)基因，然后將第2 個(gè)父輩染色體X2的后n-t 個(gè)基因依據(jù)第2 個(gè)父輩染色體中的順序構(gòu)成子代，見(jiàn)圖3。

圖3 交叉操作示意圖

變異操作采用逆位變異，即針對(duì)變異染色體的隨機(jī)選取的變異位s，使其與n -s 位進(jìn)行對(duì)換，從而生成新的染色體，如式(8)所示。

3.4 終止條件的設(shè)計(jì)

求解從后勤運(yùn)輸車(chē)配送路徑優(yōu)化問(wèn)題時(shí)，如果以下任一條件滿足時(shí)，則遺傳算法終止并輸出所記錄的最優(yōu)解。

1)優(yōu)化過(guò)程中得到的全局最優(yōu)解在連續(xù)10 次迭代中都沒(méi)有被改進(jìn);

2)達(dá)到最大迭代次數(shù)次100 次。

4 優(yōu)化結(jié)果分析

基于所設(shè)計(jì)的遺傳算法進(jìn)行后勤運(yùn)輸車(chē)配送路徑優(yōu)化問(wèn)題研究。假設(shè)從出發(fā)點(diǎn)到終止點(diǎn)之間共有7 個(gè)節(jié)點(diǎn)，初始條件為:

其中:D0為需求節(jié)點(diǎn)之間的距離矩陣;D1為從出發(fā)點(diǎn)至各節(jié)點(diǎn)的距離信息;D2為各節(jié)點(diǎn)至終止點(diǎn)的距離信息。

對(duì)于任意染色體X 適配度函數(shù)的計(jì)算實(shí)例如圖4 所示。

采用謝菲爾德Matlab 遺傳算法工具箱函數(shù)來(lái)進(jìn)行算法實(shí)現(xiàn)。選擇算子采用select( )函數(shù)，交叉算子采用xovshrs( )函數(shù)，變異算子采用mutate( )函數(shù)，經(jīng)過(guò)42 次迭代后算法收斂至最優(yōu)解

對(duì)應(yīng)的表現(xiàn)型，即最優(yōu)配送路徑見(jiàn)圖5。

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

本文采用遺傳算法對(duì)后勤運(yùn)輸車(chē)的路徑優(yōu)化問(wèn)題進(jìn)行了研究，設(shè)計(jì)了遺傳編碼、適配度函數(shù)和遺傳算子等，并基于謝菲爾德Matlab 遺傳算法工具箱進(jìn)行了算法實(shí)現(xiàn)與仿真，結(jié)果表明遺傳算法適合于后勤運(yùn)輸路徑的尋優(yōu)，針對(duì)相應(yīng)的需求點(diǎn)分布情況可以迅速做出最優(yōu)配送路徑?jīng)Q策，從而節(jié)省運(yùn)輸車(chē)行駛里程和運(yùn)輸時(shí)間。

［1］祝崇雋，劉民，吳澄.供應(yīng)鏈中車(chē)輛路徑問(wèn)題的研究進(jìn)展及前景［J］.計(jì)算機(jī)集成制造系統(tǒng)，2001，11(7):1 -6.

［2］朗茂祥，胡思繼.用混合遺傳算法求解物流配送路線優(yōu)化問(wèn)題的研究［J］.中國(guó)管理科學(xué)，2003，2(4):44 -46.

［3］孫小年，陳幼林，楊東援.裝卸一體化車(chē)輛路徑問(wèn)題的遺傳算法研究［J］.系統(tǒng)工程理論與實(shí)踐，2007(2):33 -35.

［4］郝艷偉，李祖樞.一種改進(jìn)的遺傳規(guī)劃算法［J］.重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版，2011，25(4):74 -78.

［5］晏剛.基于改進(jìn)遺傳算法的AUV 路徑規(guī)劃［J］.重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版，2010，24(5):81 -85.