基于改進遺傳算法的國內旅行交通規劃研究*

于 雁 李小光

（青島大學自動化學院 青島 266071）

1 引言

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

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

自然界中動植物的生老病死是固有的規律，當動物達到一定的年齡后，便會死亡。本文將動物會自然死亡的規律應用于遺傳算法中，對個體編碼時賦予年齡操作，將此改進遺傳算法進行國內旅行交通規劃，為人們的外出旅行提供最優化的旅行路線和旅行總費用。

2 旅行交通規劃

旅行交通規劃與旅行商問題相類似［16］，旅行商問題是以地點之間的距離總和為優化目標，使得距離總和最小。由于我國國內各個城市之間的距離相隔較遠，必須要乘坐一定的交通工具前往。旅行交通規劃是指推銷員乘坐交通工具代替步行到達多個地點，并在到達地點無重復的情況下找到最終點再回到起點的總路徑，使得所需費用最低。

旅行交通規劃問題用數學語言描述為尋找一條巡回路徑，目標函數為

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

3 遺傳算法

對于旅行交通規劃問題，通常應用遺傳算法中的選擇操作、交叉操作和變異操作。本文針對傳統遺傳算法存在的問題，對其進行改進，即在選擇操作和交叉操作后加入年齡操作，最后進行變異操作。

改進遺傳算法的流程圖見圖1。

圖1 改進遺傳算法流程圖

各個操作的具體內容如下。

選擇操作：按個體適應度大小，從舊群體中選擇部分個體到新群體。

交叉操作：根據適應度大小，利用輪盤賭注方法選擇兩個個體，交叉產生新個體。

變異操作：確定個體基因兩個位置，將其對換。

年齡操作：判斷個體年齡是否達到各種動物死亡年齡范圍，若年齡進入死亡年齡范圍，則刪除該個體，并利用交叉操作，產生新個體，同時賦予該新個體年齡為0，以保證種群數量不變。

4 仿真實驗與結果分析

以乘坐火車為旅行主要交通工具，在國內31個省會城市間，進行旅行交通路線規劃。城市與城市之間有多趟和多種列車運行，具體交通工具按照以下規則進行選擇。

1）城市之間有直達車，優先選擇高鐵；若無高鐵，選擇軟臥。

2）城市之間無直達車，進行換乘，優先選擇高鐵；若無高鐵，選擇軟臥。

3）前往臺北，選擇飛機。

將31個省會城市進行編號，見表1。

表1 編號與城市對應表

查閱中國運輸系統價格表，獲得各個城市之間的交通運輸所需費用，費用表如表2所示。

表2 城市間交通運算所需費用表

本實驗將種群大小設置為200，最大遺傳代數為1000，代溝為0.9，變異概率為0.05，對有年齡操作和無年齡操作分別進行5 次計算，變化曲線圖見圖2～7，其中圖2 為有無年齡操作后的種群最優解所需費用變化曲線圖，圖3 為有無年齡操作后的種群平均所需費用變化曲線圖，圖4 為有年齡操作種群最優解所需費用變化曲線圖，圖5 為無年齡操作種群最優解所需費用變化曲線圖，圖6 為有年齡操作種群平均所需費用變化曲線圖，圖7 為無年齡操作種群平均所需費用變化曲線圖。

圖2 種群最優解所需費用變化曲線圖

圖3 種群平均所需費用變化曲線圖

圖4 有年齡操作種群最優解所需費用變化曲線圖

圖5 無年齡操作種群最優解所需費用變化曲線圖

圖6 有年齡操作種群平均所需費用變化曲線圖

圖7 無年齡操作種群平均所需費用變化曲線圖

從圖2～7 可以看出，對傳統遺傳算法添加年齡操作具有很好的可實踐性，當參數設置相同的情況下，對有年齡操作和無年齡操作分別進行5 次計算，有年齡操作得到的最優巡回路徑比無年齡操作得到的最優巡回路徑更優，所需旅行總費用更低。當添加年齡操作，強制淘汰達到死亡年齡且適應能力高的優秀個體，可以有效避免種群的多樣性受到破壞，使遺傳算法過早地出現早熟和收斂現象。

表3為有年齡操作計算5次后的所需費用統計表，表4 為無年齡操作計算5 次后的所需費用統計表。

表3 有年齡操作計算5次費用統計表

表4 無年齡操作計算5次費用統計表

從表3和表4可以得到，進行年齡操作后，平均種群最優解所需費用比無年齡操作所得到的總費用消費更少，相應的種群平均所需費用也比無年齡操作所消費的總費用更少。由此可得，添加年齡操作，對于國內的旅行交通規劃可以實現更好的巡回路徑，能夠為人們的旅行提供更優、更合理化的建議，節約旅行資金。

對各城市旅行解碼前得到的最優路線為

解碼后的最優路線為

上述最優路徑所需總費用為10464.5 元，圖8為最優解巡回路徑圖，圖9 為文獻［15］遺傳算法所獲得的最優巡回路徑圖。

圖8 最優解巡回路徑圖

圖9 文獻［15］遺傳算法巡回路徑圖

將本文改進遺傳算法所獲得的最優巡回路線需要的總費用與文獻［15］優化路徑所需費用進行對比，結果見表5。

表5 與文獻［15］優化路徑所需費用對比表

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

5 結語

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