基于改進(jìn)遺傳算法的國(guó)內(nèi)旅行交通規(guī)劃研究*

于 雁 李小光

（青島大學(xué)自動(dòng)化學(xué)院 青島 266071）

1 引言

隨著中國(guó)全面進(jìn)入小康社會(huì)，人們不再局限于物質(zhì)消費(fèi)，越來(lái)越重視精神文化滿足。隨著旅游業(yè)的快速發(fā)展，人們對(duì)已有的地域空間和距離的認(rèn)識(shí)不斷健全，時(shí)間距離和成本距離逐漸替代傳統(tǒng)的空間距離被廣泛應(yīng)用于研究中［1］，在“四縱四橫”客運(yùn)專(zhuān)線建設(shè)全面展開(kāi)形勢(shì)下［2］，中國(guó)游客對(duì)于交通路線和外出成本的需求在逐漸提高。從黑龍江到海南島，上海到烏魯木齊這種長(zhǎng)時(shí)間和多地點(diǎn)的外出旅行，進(jìn)行合理的旅行交通規(guī)劃，使得所需總費(fèi)用最少，具有重要的現(xiàn)實(shí)和研究意義。

旅行交通規(guī)劃與旅行商問(wèn)題具有一定的內(nèi)在聯(lián)系，旅行商問(wèn)題是一個(gè)典型的數(shù)學(xué)組合優(yōu)化問(wèn)題，已經(jīng)被廣泛應(yīng)用到許多實(shí)際問(wèn)題中［3～7］，如物流配送、飛機(jī)航線安排和產(chǎn)品的生產(chǎn)安排問(wèn)題等。這些問(wèn)題都可以通過(guò)數(shù)學(xué)變換轉(zhuǎn)化為旅行商問(wèn)題進(jìn)行求解［8］。求解旅行商問(wèn)題的方法有簡(jiǎn)單插值算法、模擬退火算法、蟻群算法和遺傳算法等，其中，最受歡迎的是遺傳算法［9］。傳統(tǒng)的遺傳算法存在易早熟收斂、后期收斂速度慢的缺陷，許多學(xué)者針對(duì)此問(wèn)題對(duì)傳統(tǒng)遺傳算法進(jìn)行改進(jìn)并與其他算法相結(jié)合，滿足了自身對(duì)不同問(wèn)題的具體解決方法需求。羅金亮等［10］利用擇向交叉遺傳算法對(duì)遠(yuǎn)距支援干擾部署問(wèn)題進(jìn)行了研究；Sonmez A等［11］利用遺傳算法對(duì)無(wú)人機(jī)的路徑規(guī)劃做了優(yōu)化；王勇臻等［12］利用改進(jìn)分組遺傳算法求解了多旅行商問(wèn)題；許宏志等［13］提出了一種仿細(xì)粒度的粗粒度并行模型，實(shí)現(xiàn)了雙層并行的遺傳算法在旅行商問(wèn)題中的應(yīng)用；易云飛等［14］通過(guò)將牛頓力學(xué)中的加速度因子映射到粒子群算法的慣性權(quán)重，改進(jìn)粒子群算法對(duì)旅行商問(wèn)題進(jìn)行了研究；李敏等［15］利用遺傳算法、蟻群算法和模擬退火算法對(duì)中國(guó)旅行商問(wèn)題進(jìn)行了仿真。

自然界中動(dòng)植物的生老病死是固有的規(guī)律，當(dāng)動(dòng)物達(dá)到一定的年齡后，便會(huì)死亡。本文將動(dòng)物會(huì)自然死亡的規(guī)律應(yīng)用于遺傳算法中，對(duì)個(gè)體編碼時(shí)賦予年齡操作，將此改進(jìn)遺傳算法進(jìn)行國(guó)內(nèi)旅行交通規(guī)劃，為人們的外出旅行提供最優(yōu)化的旅行路線和旅行總費(fèi)用。

2 旅行交通規(guī)劃

旅行交通規(guī)劃與旅行商問(wèn)題相類(lèi)似［16］，旅行商問(wèn)題是以地點(diǎn)之間的距離總和為優(yōu)化目標(biāo)，使得距離總和最小。由于我國(guó)國(guó)內(nèi)各個(gè)城市之間的距離相隔較遠(yuǎn)，必須要乘坐一定的交通工具前往。旅行交通規(guī)劃是指推銷(xiāo)員乘坐交通工具代替步行到達(dá)多個(gè)地點(diǎn)，并在到達(dá)地點(diǎn)無(wú)重復(fù)的情況下找到最終點(diǎn)再回到起點(diǎn)的總路徑，使得所需費(fèi)用最低。

旅行交通規(guī)劃問(wèn)題用數(shù)學(xué)語(yǔ)言描述為尋找一條巡回路徑，目標(biāo)函數(shù)為

其中vi為城市號(hào)，i∈N，1 ≤vi≤n，p(vi,vj)表示城市i與城市j 之間乘坐交通工具所需費(fèi)用，對(duì)于對(duì)稱旅行交通規(guī)劃問(wèn)題有p(vi,vj)=p(vj,vi)。

3 遺傳算法

對(duì)于旅行交通規(guī)劃問(wèn)題，通常應(yīng)用遺傳算法中的選擇操作、交叉操作和變異操作。本文針對(duì)傳統(tǒng)遺傳算法存在的問(wèn)題，對(duì)其進(jìn)行改進(jìn)，即在選擇操作和交叉操作后加入年齡操作，最后進(jìn)行變異操作。

改進(jìn)遺傳算法的流程圖見(jiàn)圖1。

圖1 改進(jìn)遺傳算法流程圖

各個(gè)操作的具體內(nèi)容如下。

選擇操作：按個(gè)體適應(yīng)度大小，從舊群體中選擇部分個(gè)體到新群體。

交叉操作：根據(jù)適應(yīng)度大小，利用輪盤(pán)賭注方法選擇兩個(gè)個(gè)體，交叉產(chǎn)生新個(gè)體。

變異操作：確定個(gè)體基因兩個(gè)位置，將其對(duì)換。

年齡操作：判斷個(gè)體年齡是否達(dá)到各種動(dòng)物死亡年齡范圍，若年齡進(jìn)入死亡年齡范圍，則刪除該個(gè)體，并利用交叉操作，產(chǎn)生新個(gè)體，同時(shí)賦予該新個(gè)體年齡為0，以保證種群數(shù)量不變。

4 仿真實(shí)驗(yàn)與結(jié)果分析

以乘坐火車(chē)為旅行主要交通工具，在國(guó)內(nèi)31個(gè)省會(huì)城市間，進(jìn)行旅行交通路線規(guī)劃。城市與城市之間有多趟和多種列車(chē)運(yùn)行，具體交通工具按照以下規(guī)則進(jìn)行選擇。

1）城市之間有直達(dá)車(chē)，優(yōu)先選擇高鐵；若無(wú)高鐵，選擇軟臥。

2）城市之間無(wú)直達(dá)車(chē)，進(jìn)行換乘，優(yōu)先選擇高鐵；若無(wú)高鐵，選擇軟臥。

3）前往臺(tái)北，選擇飛機(jī)。

將31個(gè)省會(huì)城市進(jìn)行編號(hào)，見(jiàn)表1。

表1 編號(hào)與城市對(duì)應(yīng)表

查閱中國(guó)運(yùn)輸系統(tǒng)價(jià)格表，獲得各個(gè)城市之間的交通運(yùn)輸所需費(fèi)用，費(fèi)用表如表2所示。

表2 城市間交通運(yùn)算所需費(fèi)用表

本實(shí)驗(yàn)將種群大小設(shè)置為200，最大遺傳代數(shù)為1000，代溝為0.9，變異概率為0.05，對(duì)有年齡操作和無(wú)年齡操作分別進(jìn)行5 次計(jì)算，變化曲線圖見(jiàn)圖2～7，其中圖2 為有無(wú)年齡操作后的種群最優(yōu)解所需費(fèi)用變化曲線圖，圖3 為有無(wú)年齡操作后的種群平均所需費(fèi)用變化曲線圖，圖4 為有年齡操作種群最優(yōu)解所需費(fèi)用變化曲線圖，圖5 為無(wú)年齡操作種群最優(yōu)解所需費(fèi)用變化曲線圖，圖6 為有年齡操作種群平均所需費(fèi)用變化曲線圖，圖7 為無(wú)年齡操作種群平均所需費(fèi)用變化曲線圖。

圖2 種群最優(yōu)解所需費(fèi)用變化曲線圖

圖3 種群平均所需費(fèi)用變化曲線圖

圖4 有年齡操作種群最優(yōu)解所需費(fèi)用變化曲線圖

圖5 無(wú)年齡操作種群最優(yōu)解所需費(fèi)用變化曲線圖

圖6 有年齡操作種群平均所需費(fèi)用變化曲線圖

圖7 無(wú)年齡操作種群平均所需費(fèi)用變化曲線圖

從圖2～7 可以看出，對(duì)傳統(tǒng)遺傳算法添加年齡操作具有很好的可實(shí)踐性，當(dāng)參數(shù)設(shè)置相同的情況下，對(duì)有年齡操作和無(wú)年齡操作分別進(jìn)行5 次計(jì)算，有年齡操作得到的最優(yōu)巡回路徑比無(wú)年齡操作得到的最優(yōu)巡回路徑更優(yōu)，所需旅行總費(fèi)用更低。當(dāng)添加年齡操作，強(qiáng)制淘汰達(dá)到死亡年齡且適應(yīng)能力高的優(yōu)秀個(gè)體，可以有效避免種群的多樣性受到破壞，使遺傳算法過(guò)早地出現(xiàn)早熟和收斂現(xiàn)象。

表3為有年齡操作計(jì)算5次后的所需費(fèi)用統(tǒng)計(jì)表，表4 為無(wú)年齡操作計(jì)算5 次后的所需費(fèi)用統(tǒng)計(jì)表。

表3 有年齡操作計(jì)算5次費(fèi)用統(tǒng)計(jì)表

表4 無(wú)年齡操作計(jì)算5次費(fèi)用統(tǒng)計(jì)表

從表3和表4可以得到，進(jìn)行年齡操作后，平均種群最優(yōu)解所需費(fèi)用比無(wú)年齡操作所得到的總費(fèi)用消費(fèi)更少，相應(yīng)的種群平均所需費(fèi)用也比無(wú)年齡操作所消費(fèi)的總費(fèi)用更少。由此可得，添加年齡操作，對(duì)于國(guó)內(nèi)的旅行交通規(guī)劃可以實(shí)現(xiàn)更好的巡回路徑，能夠?yàn)槿藗兊穆眯刑峁└鼉?yōu)、更合理化的建議，節(jié)約旅行資金。

對(duì)各城市旅行解碼前得到的最優(yōu)路線為

解碼后的最優(yōu)路線為

上述最優(yōu)路徑所需總費(fèi)用為10464.5 元，圖8為最優(yōu)解巡回路徑圖，圖9 為文獻(xiàn)［15］遺傳算法所獲得的最優(yōu)巡回路徑圖。

圖8 最優(yōu)解巡回路徑圖

圖9 文獻(xiàn)［15］遺傳算法巡回路徑圖

將本文改進(jìn)遺傳算法所獲得的最優(yōu)巡回路線需要的總費(fèi)用與文獻(xiàn)［15］優(yōu)化路徑所需費(fèi)用進(jìn)行對(duì)比，結(jié)果見(jiàn)表5。

表5 與文獻(xiàn)［15］優(yōu)化路徑所需費(fèi)用對(duì)比表

如表5 所示，文獻(xiàn)［15］利用遺傳算法、蟻群算法和模擬退火算法所獲得的優(yōu)化路徑全都比有年齡操作遺傳算法優(yōu)化的路徑總距離少，但所需費(fèi)用都更高，改進(jìn)遺傳算法獲得最優(yōu)路徑的所需總費(fèi)用比文獻(xiàn)［15］三種算法所需費(fèi)用分別省527 元、564元和502.5 元，為人們的外出旅行節(jié)約了一定的資金。

5 結(jié)語(yǔ)

對(duì)國(guó)內(nèi)旅行外出進(jìn)行旅行交通規(guī)劃，可以為人們出行路線安排提供合理化的建議，使人們對(duì)出行安排進(jìn)行理性分析，節(jié)約外出消費(fèi)資金，做出更正確的路線規(guī)劃和決策，滿足了人們的精神文化追求和享受。在國(guó)內(nèi)旅行交通規(guī)劃研究中，對(duì)傳統(tǒng)遺傳算法中添加年齡操作相比無(wú)年齡操作遺傳算法，能夠更好地求得巡回路線最佳解，得到更優(yōu)的旅行路線以及更少的所需費(fèi)用，提供合理化的旅行線路圖。改進(jìn)遺傳算法以所需費(fèi)用為優(yōu)化目標(biāo)，可能會(huì)增加部分總距離，但是在限定的資金范圍內(nèi)，能夠緩解經(jīng)濟(jì)壓力，減輕成本負(fù)擔(dān)，讓出行更加的輕松享受。