(同濟大學經(jīng)濟與管理學院　上?！?01804)

一、引言

隨著人們生活水平的提高，旅游已經(jīng)成為人們?nèi)粘Ｉ钪斜夭豢缮俚囊徊糠??？茖W的旅游路線設計，不僅可以有效地節(jié)約游客的時間、金錢和精力，使之充分享受到旅途的樂趣，還有助于旅游景區(qū)之間的相互對比，統(tǒng)籌配置。

上海便是中國舉世聞名的旅游城市之一。上海位于中國東南部沿海，在長江入?？谖恢?，是中國最發(fā)達的城市之一，也是中國的經(jīng)濟中心。上海密布的交通網(wǎng)絡、繁華的街道、競相增長的摩天大樓，都映射著這座摩天都市的不斷雄起。

上海是一座極具現(xiàn)代化而又不失中國傳統(tǒng)特色的都市。有超過2000萬人居住和生活在這里。作為中國歷史上最早的通商口岸，上海也是最早接觸“外界”的地方。隨著時代的變遷，上海也逐漸成為了東亞地區(qū)重要的金融貿(mào)易城市。上海是多元的，老城廂里原汁原味的老弄堂，外灘沿岸百年歷史的歐式建筑，陸家嘴地區(qū)各式各樣的摩天大樓，城隍廟間承載記憶的中華園林。多元的城市元素匯聚在這里，讓上海獨具魅力。

同濟大學坐落于有著“東方巴黎”之稱的上海，是教育部直屬全國重點大學，國家“211工程”和“985工程”重點建設高校，在國際上享有較高的聲譽。每年，都有大批的學子包括國外留學生慕名來到同濟學習。上海作為一座極具現(xiàn)代化而又不失中國傳統(tǒng)特色的國際大都市，擁有諸多的旅游景點，游客可以在外灘夜觀美景，去城隍廟品嘗美食。

對來滬求學的學生而言，在外求學獲取知識的同時，領略上海當?shù)氐娘L土人情、游覽特色景點，也是學生期間一個難忘的經(jīng)歷。但全日制學生因課業(yè)壓力較大，時間上往往會受限制；同時經(jīng)濟上的預算往往也并不充足，出行選擇公共交通較多。基于上述時間和經(jīng)濟上的限制，我們決定以遺傳算法為求解算法，建立模型解決這一路線規(guī)劃問題。

旅行商問題(Traveling Salesman Problem,TSP)是威廉·哈密爾頓爵士和英國數(shù)學家克克曼于19世紀初提出的一個數(shù)學問題。它是一個是典型的NP問題，其簡單描述是，一名商人欲到n個城市推銷商品，目標是找到一條經(jīng)過所有城市且每個城市只經(jīng)過一次的最短路徑[1]。本文所研究的旅游路線規(guī)劃問題類似于TSP問題，但不同之處在于游客要用m天游覽完n個旅游景點，其中m要盡可能小，且每天必須從同一地點出發(fā)再回到該出發(fā)點，出發(fā)時間固定，返回時間不能晚于某個時刻，要求所有旅游所花費的總時間最短，也即得到了最短的天數(shù)m。

遺傳算法(Genetic Algorithm,GA)是由美國Michigan大學的Holland教授于1969年提出，后經(jīng)De Jong、Goldberg等人歸納總結(jié)所形成的一類模擬進化算法。它來源于達爾文的進化論、魏茨曼的物種選擇學說和孟德爾的群體遺傳學說。遺傳算法是模擬自然界生物進化過程與機制求解極值問題的一類自組織、自適應人工智能技術,其基本思想是模擬自然界遺傳機制和生物進化論而形成的一種過程搜索最優(yōu)解的算法,具有堅實的生物學基礎；它提供從智能生成過程觀點對生物智能的模擬,具有鮮明的認知學意義；它適合于無表達或有表達的任何類函數(shù)，具有可實現(xiàn)的并行計算行為；它能解決任何種類實際問題，具有廣泛的應用價值。因此，遺傳算法廣泛應用于自動控制、計算科學、模式識別、工程設計、智能故障診斷、管理科學和社會科學等領域，適用于解決復雜的非線性和多維空間尋優(yōu)問題[2]。遺傳算法是求解復雜的組合優(yōu)化問題的有效方法。它將問題的可行解編碼為由基因組成的染色體，通過模擬染色體群的選擇、交叉和變異等操作，不斷迭代，最終收斂到高適應度值的染色體，從而求得問題的最優(yōu)解或滿意解，非常適用于解決旅行商問題[3]。

二、問題提出

本文選取了上海市15個著名的旅游景點，旨在幫助同濟大學嘉定校區(qū)的學生規(guī)劃出合適的旅游路線。上海市交通便利，基本各景點都有地鐵或公交可以到達，且班次較為固定，所以從學校到各景點以及各景點間往返所耗費的時間和路費基本固定，可以通過在上海公共交通平臺查詢，估計出各兩點間行程的最短耗時。景點的最佳游覽時長可根據(jù)以往經(jīng)驗估計出，為已知常量。如果游客到達景點時刻時的剩余時間不足以完整地游覽景點，則選擇當天不去此景點，而去另一景點或者返回出發(fā)點。

出于人身安全及擁有良好的游玩狀態(tài)考慮，設定每天從學校出發(fā)時間為8點，晚上23點前必須返回學校。我們借助網(wǎng)絡資源査閱了相關資料，確定了上海市15個著名的旅游景點，用自然數(shù)1，2，3……15為各個景點和地點編碼；同時收集到了各景點的最佳游玩時間：

景點1:外灘，最佳游玩時間：4小時；景點2:豫園，最佳游玩時間：2小時；景點3:田子坊，最佳游玩時間：2.5小時；景點4:世博公園，最佳游玩時間：4小時；景點5:新天地，最佳游玩時間：1.5小時；景點6:復旦大學，最佳游玩時間：3小時；景點7:老城隍廟，最佳游玩時間：2.5小時；景點8:外白渡橋，最佳游玩時間：4小時；景點9:上海博物館，最佳游玩時間：6小時；景點10:金茂大廈，最佳游玩時間：2小時；景點11:思南路，最佳游玩時間：2.5小時；景點12:靜安寺，最佳游玩時間：1小時；景點13:1933老廠坊，最佳游玩時間：2小時；景點14:古漪園，最佳游玩時間：2小時，景點15:杜莎夫人蠟像館，最佳游玩時間：3小時。

表1表示了各景點間的交通時間：

表1　各點間的交通時間(單位：小時)

三、模型假設與符號說明

(一)基本假設

(1)所有的公共交通都是準點出發(fā)，不存在故障或停運等突發(fā)性情況；

(2)旅游者每天都是八點準時從學校出發(fā)，在各景點逗留時間固定；

(3)對于道路的擁堵程度不予考慮，認為都是暢通的；

(4)天氣等一切突發(fā)情況不考慮在內(nèi)；

(5)每個旅游景點只游覽一次。

(二)符號說明

四、模型建立及求解

(一)目標函數(shù)的確立

由于游覽完全部景點所花費的門票、購物等費用基本相同，唯一的區(qū)別在于交通費用，而往往走過的路程最短，相應的交通費往往也會更短，同時路程與時間一般也成正比，所以本模型的目標可以抽象為花費最少的時間游覽完這15個景點，游覽的總時間T包括了往來于各景點、學校間的時間，即總交通時間T1，以及在景點逗留游玩的總時間T2

為簡化運算，本文決定根據(jù)游客每天回到學校即出發(fā)點的時刻減去出發(fā)時刻，來得到該日的總游完時間。已知游客于每天早上8點從同濟大學嘉定校區(qū)出發(fā)，假設第k天游玩返回學校的時刻是hk，則這天旅游所耗費的時間tk則為(hk-8)個小時，m天一共花費的旅游時間則為每天旅游時間之和，目標函數(shù)為：

(二)約束條件

(三)基于遺傳算法的模型求解

遺傳算法在求解NP問題中得到了普遍運用，其包括初始化種群、評價種群中個體的適應度、選擇運算、交叉運算、變異運算和終止判斷等基本步驟，下面將對其原理進行闡述。

(1)編碼

利用遺傳算法求解問題不是直接作用于問題的解空間上，而是利用解的某種編碼表示，而編碼是指在遺傳算法中如何描述問題的可行解，即把問題的可行解從解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法。常用的遺傳算法編碼方法有：二進制編碼、符號編碼、樹編碼、自適應編碼、亂序編碼等[4]。本文將采用符號編碼方法，其主要特點是意義明確，遺傳操作不需要頻繁地編碼解碼，計算復雜性降低，算法效率較高。

本文研究15個旅游景點的路徑規(guī)劃問題，每個景點用一個自然數(shù)表示，隨機生成1～15的15個自然數(shù)的隨機排列，便組成了一條染色體，如2 8 3 1 15 6 9 12 14 10 4 7 5 13 11。

(2)適應度函數(shù)設計

本文以時間最小化作為目標函數(shù)，且總?cè)》秦摂?shù)，故可直接利用目標函數(shù)構(gòu)造適應度函數(shù)，可表示為：F=tk

(3)算法參數(shù)設置

下面對GA的參數(shù)作出說明：

種群個數(shù)：70；迭代次數(shù)：150；交叉率：0.9；變異率：0.1；

(4)遺傳操作

①種群初始化

隨機產(chǎn)生含有70個個體的初始種群。

②個體評價

此步驟是對繁衍出來的后代進行評估打分。在本文研究的問題中，時間越少，分數(shù)越高。

③選擇運算

選擇的目的是為了從交換后的群體中選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。選擇以達爾文的適者生存為原則，適應性越強的個體為下一代貢獻的概率也就越大。本文將適應度按照從小到大的順序排列，選取前70個個體作為下一代進行繁殖。

④交叉運算

交叉運算是遺傳法中產(chǎn)生新個體的主要操作過程，它以某一概率相互換某兩個個體之間的部分染色體。本文采用單點交叉的方法，對于隨機生成的70*16初始種群矩陣，先對種群隨機配對，再隨機設置交叉點位置，從而把母體對中兩個個體從交叉點分為前后兩段，確定交叉概率0.9，當產(chǎn)生的隨機數(shù)小于交叉概率時，將兩個個體的后半部分交換。如生成[1,15]內(nèi)的隨機整數(shù)r=9，對9之后的位置部分進行交叉。

283115691214104751311

491411361181572510312

交叉為：

28311569121572510312

4914113611814104751311

⑤變異運算

變異運算是對個體的某一個或某一些基因座上的基因值按較小的變異概率進行改變，它也是產(chǎn)生新個體的一種操作方法。如生成[1,15]內(nèi)的隨機整數(shù)r1=5和r2=8，將其代表的位置對換。

28311569121572510312

變異后：

28311269151572510312

(5)終止

本文以進化代數(shù)作為遺傳算法的終止條件?？蓪⒔?jīng)過150代遺傳篩選出的最優(yōu)基因，近似認為得到了最優(yōu)解。當然，可以通過無限增加初始種群以及繁衍代數(shù)，得到理論上的最優(yōu)解。本文求解迭代過程如下圖2所示，最后函數(shù)值穩(wěn)定在61.3左右。

圖1　迭代逼近真值圖

(四)結(jié)果分析

本文運用遺傳算法求解了該旅游路線規(guī)劃模型，通過MATLAB 2015b編程，得到了在有往返時間限制和起點終點固定的前提下，游覽完這15個景點所用的最短時間為61.3h，共需要5天完成，同時得出了相應的5條旅游路線，各路線路徑及到達各點的時刻等詳情如下所示：

路徑交通時間/h到達時刻游覽時間/h出發(fā)時刻總游玩時間/h①從0出發(fā)———8:00—0→51.689:411.511:11—5→110.3311:312.514:01—11→150.3314:21317:21—15→30.3317:402.520:10—3→01.7321:54———總計4.4—9.5—13.9②從0出發(fā)———8:00—0→121.589:35110:35—12→100.511:05213:05—10→10.513:35417:35—1→80.2217:48118:48—8→01.8820:41———總計4.68—8—12.68③從0出發(fā)———8:00—0→61.959:57312:57—6→130.513:27215:27—13→01.6717:07———續(xù)表總計4.12—5—9.12④從0出發(fā)———8:00—0→4210:00414:00—4→20.6714:40216:40—2→70.116:462.519:16—7→01.9321:12———總計4.7—8.5—13.2⑤從0出發(fā)———8:00—0→141.49:24211:24—14→91.1712:34618:34—9→01.8320:24———總計4.4—8—12.4

五、模型的評價、改進及推廣

本模型為身處同濟大學嘉定校區(qū)的同學外出旅游提供了一定的參考，具有明確的現(xiàn)實意義。旅游者可根據(jù)自身實際情況，只需對旅游景點、游玩時間、出行時間等參數(shù)做出些許調(diào)整，即可帶入模型，得出適宜的旅游路徑，不僅有助于其有目的地選擇并安排自己的旅游活動，避免漫無目的地游玩，而且還可以使其合理利用時間，爭取游覽更多的風景，并且合理的路徑規(guī)劃也增加了旅游者游玩的舒適度和愉悅感。

綜上分析，本模型適用于有時間約束的定點往返的路線規(guī)劃問題，具有廣泛的使用意義。但是，本模型由于未將一些現(xiàn)實因素納入考慮范圍，還存在以下幾點不足：

(1)實際情況中，多數(shù)景點都有規(guī)定的開放時間，本文只選取了開放時間較為寬松的旅游景點為例，在日后的研究中，可將景點的開放時間考慮其中，以期規(guī)劃出更加貼合實際的旅游路線。

(2)景點游玩時間的長短往往因人而異，本文僅根據(jù)以往經(jīng)驗估計出了一個大概值，靈活性較差，可在日后對模型進行改進，增加游玩時間的彈性，將其設定在一個合理的區(qū)間內(nèi)。

(3)現(xiàn)實生活中，人們在出行時往往會選擇多種交通工具，并且選擇的交通工具不同，所花費的交通時間自然也有所不同。另外，不同的時間路況信息有所差別，出行高峰期所花費的時間一般比低谷期長。本文僅選擇了頻次、時間相對固定的公共交通作為交通工具進行研究，未考慮不同交通工具、不同出發(fā)時間的影響。