于 雁 李小光

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

1 引言

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

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

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

2 旅行交通規(guī)劃

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

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

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

3 遺傳算法

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

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

圖1 改進遺傳算法流程圖

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

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

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

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

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

4 仿真實驗與結果分析

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

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

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

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

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

表1 編號與城市對應表

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

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

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

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

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

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

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

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

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

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

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

表3 有年齡操作計算5次費用統(tǒng)計表

表4 無年齡操作計算5次費用統(tǒng)計表

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

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

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

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

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

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

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

表5 與文獻［15］優(yōu)化路徑所需費用對比表

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

5 結語

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