魏瑋　吳夢(mèng)月

摘 要：該文介紹了一種基于景區(qū)路徑的優(yōu)化方案，采用旅行商問題求解來破解旅游線路的擁堵問題，并對(duì)遺傳算法進(jìn)行了約束求解。相對(duì)于傳統(tǒng)的靜態(tài)求解方法，基于北京市旅游線路的復(fù)雜特征，通過引入堵車系數(shù)來進(jìn)行動(dòng)態(tài)求解優(yōu)化方案，對(duì)求解的實(shí)際路線進(jìn)行算法性能分析，實(shí)驗(yàn)結(jié)果證明該算法能夠快速有效地求得問題的最優(yōu)解。

關(guān)鍵詞：旅行商問題 堵車系數(shù) 優(yōu)化方案

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2017）01（b）-0014-03

隨著旅游業(yè)的高速發(fā)展，交通擁堵問題已成為制約旅游業(yè)發(fā)展的瓶頸問題。如何破解交通擁堵這一問題，近年來引起了許多學(xué)者的廣泛關(guān)注。旅行商問題（簡(jiǎn)稱TSP問題）為我們解決該問題提供了一種數(shù)學(xué)方法。從數(shù)學(xué)上講，TSP問題就是一種遍歷各個(gè)景點(diǎn)的最短路徑求解。近年來，遺傳算法在求解旅行商問題中顯示了其優(yōu)越性。它將旅行商問題的解集看作一個(gè)種群，通過群的操作最終求解。但傳統(tǒng)的算法存在速度慢的缺陷，筆者根據(jù)北京交通的復(fù)雜性，結(jié)合旅行商問題求解的算法，對(duì)已有的算法進(jìn)行了改進(jìn)，為求解最優(yōu)旅游路線方案提供了一種新的研究思路。

1 解決方案

遺傳算法是目前最常用的解決TSP問題的算法[1]，其優(yōu)勢(shì)在于算法可以進(jìn)行全局空間搜索，但也存在需要改進(jìn)的不足，如算法速度較慢。筆者針對(duì)北京城區(qū)旅游線路的不同特征，有針對(duì)性地對(duì)遺傳算法進(jìn)行改進(jìn)[2]，主要工作如下。

（1）調(diào)研了多條北京景區(qū)旅游線路，根據(jù)不同線路特征，設(shè)計(jì)了不同權(quán)重的堵車參數(shù)。

（2）對(duì)參數(shù)表達(dá)函數(shù)進(jìn)行了改進(jìn)，使之有利于問題求解。

（3）采用了改進(jìn)的貪婪交叉算子和啟發(fā)式倒位變異算子，提高了求解效率。

根據(jù)北京交通的歷史數(shù)據(jù)分析，最短旅行路線未必是時(shí)間最優(yōu)的旅行路線，而影響時(shí)間因素的最大因子是堵車，因此，筆者在方案設(shè)計(jì)中加入了堵車參數(shù)，通過對(duì)歷史數(shù)據(jù)的統(tǒng)計(jì)分析，來求解堵車系數(shù)。通過堵車系數(shù)，可以最大程度地衡量旅游路線的優(yōu)化程度。

2 算法設(shè)計(jì)與實(shí)現(xiàn)

2.1 擁堵數(shù)據(jù)分析

為了確定最優(yōu)的堵車系數(shù)，筆者結(jié)合網(wǎng)上數(shù)據(jù)抽樣調(diào)研景區(qū)路線的擁堵情況，調(diào)查范圍主要包括北京城六區(qū)，得出了北京交通通暢程度最差的7片區(qū)域[3]，如圖1所示，分別為：（1）環(huán)故宮區(qū)域，包括前門、天安門、故宮、什剎海、西單、王府井等，記為區(qū)域A；（2）雙井、勁松、南磨房、王四營(yíng)等地區(qū)，記為區(qū)域B；（3）亞運(yùn)村地區(qū)、北苑、天通苑等地區(qū)，記為區(qū)域C；（4）中關(guān)村地區(qū)，以及五環(huán)外的回龍觀地區(qū)，記為區(qū)域D；（5）香山、植物園等地區(qū)，記為區(qū)域E；（6）黃村地區(qū)，記為區(qū)域F；（7）通州區(qū)，記為區(qū)域G。

區(qū)域A的擁堵主要是由于古典名勝的存在導(dǎo)致大量外來游客的涌入，人流過多導(dǎo)致交通不暢通。區(qū)域B的擁堵是由于住宅區(qū)和商業(yè)區(qū)的集中造成。區(qū)域C和區(qū)域D主要是由于高新技術(shù)IT產(chǎn)業(yè)和房地產(chǎn)商的不斷擴(kuò)張導(dǎo)致人流過于集中。區(qū)域E交通擁堵的主要原因是城區(qū)老化所致。區(qū)域F和區(qū)域G則由于交通工具數(shù)量較少不方便，導(dǎo)致行車不暢。

2.2 堵車系數(shù)區(qū)間

根據(jù)北京交通發(fā)展研究中心發(fā)布的北京交通擁堵指數(shù)，筆者給出了堵車系數(shù)設(shè)置區(qū)間，如表1所示。

通過上述分析，該求解方案的堵車系數(shù)設(shè)置如下：

2.3 實(shí)例求解

筆者以古韻京城精品旅游線路為實(shí)例，其景點(diǎn)及編號(hào)：1——八達(dá)嶺長(zhǎng)城、2——故宮、3——天壇、4——頤和園、5——明十三陵、6——周口店北京人遺址、7——王府井、8——天安門、9——雍和宮、10——恭王府，對(duì)應(yīng)距離矩陣如表2所示。

上述景點(diǎn)對(duì)應(yīng)的堵車類別及堵車系數(shù)如表3所示。

由表2和表3中數(shù)據(jù)計(jì)算得到的堵車系數(shù)矩陣和距離權(quán)矩陣分別為：

程序運(yùn)行結(jié)果：用改進(jìn)的遺傳算法求得的最優(yōu)旅行路徑為（1，4，9，10，2，7，8，3，6，5）；總距離為287 km；以市內(nèi)平均時(shí)速50km/h為標(biāo)準(zhǔn)，同時(shí)加入堵車時(shí)間，求得路程所用最短時(shí)間為6.405 h；算法迭代時(shí)間為1.02 s。程序運(yùn)行結(jié)果界面如圖2所示。

2.4 性能分析

該文對(duì)算法的改進(jìn)，最重要的是針對(duì)北京市交通特點(diǎn)，給出了合理的堵車參數(shù)，通過節(jié)省時(shí)間來綜合求解旅游線路的最優(yōu)方案。筆者以實(shí)例古韻京城精品旅游線路為例，對(duì)比加入堵車參數(shù)和未加入堵車參數(shù)的遺傳算法求解結(jié)果，如表4所示。

從上述結(jié)果中，我們可以看出，加入堵車參數(shù)之后，求得的最優(yōu)路徑不一定是該線路的最短旅游路徑，但是所用時(shí)間卻最短，這更適合北京城區(qū)的旅游線路優(yōu)化。

3 結(jié)語

利用遺傳算法求解北京城區(qū)旅游景點(diǎn)優(yōu)化問題，為北京市內(nèi)旅游提供相應(yīng)的優(yōu)化方案和理論依據(jù)，對(duì)推動(dòng)北京市旅游業(yè)發(fā)展具有十分重要的意義。本文將路徑優(yōu)化問題映射為數(shù)學(xué)研究中的旅行商問題，通過改進(jìn)算法對(duì)其求解，可以提供一種旅游線路的最優(yōu)方案。希望該文介紹的方法為提升旅游出行提供有益參考。

參考文獻(xiàn)

[1] 王化宇.最小生成樹算法及其應(yīng)用[J].內(nèi)蒙古科技與經(jīng)濟(jì)，2011（6）：72-73.

[2] 惠燕，潘煜.騎士游歷問題算法的研究[J].電子設(shè)計(jì)工程，2011，19（11）：112-114.

[3] 高曉路，季玨，張文忠.北京市交通出行環(huán)境的空間評(píng)價(jià)[J].地理科學(xué)，2009，29（6）：817-824.