基于遺傳算法的旅游路徑規(guī)劃問題研究

(同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院　上海　201804)

一、引言

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

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

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

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

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

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

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

二、問題提出

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

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

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

表1表示了各景點(diǎn)間的交通時(shí)間：

表1　各點(diǎn)間的交通時(shí)間(單位：小時(shí))

三、模型假設(shè)與符號(hào)說明

(一)基本假設(shè)

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

(2)旅游者每天都是八點(diǎn)準(zhǔn)時(shí)從學(xué)校出發(fā)，在各景點(diǎn)逗留時(shí)間固定；

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

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

(5)每個(gè)旅游景點(diǎn)只游覽一次。

(二)符號(hào)說明

四、模型建立及求解

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

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

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

(二)約束條件

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

遺傳算法在求解NP問題中得到了普遍運(yùn)用，其包括初始化種群、評(píng)價(jià)種群中個(gè)體的適應(yīng)度、選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算和終止判斷等基本步驟，下面將對(duì)其原理進(jìn)行闡述。

(1)編碼

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

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

(2)適應(yīng)度函數(shù)設(shè)計(jì)

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

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

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

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

(4)遺傳操作

①種群初始化

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

②個(gè)體評(píng)價(jià)

此步驟是對(duì)繁衍出來的后代進(jìn)行評(píng)估打分。在本文研究的問題中，時(shí)間越少，分?jǐn)?shù)越高。

③選擇運(yùn)算

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

④交叉運(yùn)算

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

283115691214104751311

491411361181572510312

交叉為：

28311569121572510312

4914113611814104751311

⑤變異運(yùn)算

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

28311569121572510312

變異后：

28311269151572510312

(5)終止

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

圖1　迭代逼近真值圖

(四)結(jié)果分析

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

路徑交通時(shí)間/h到達(dá)時(shí)刻游覽時(shí)間/h出發(fā)時(shí)刻總游玩時(shí)間/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———總計(jì)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———總計(jì)4.68—8—12.68③從0出發(fā)———8:00—0→61.959:57312:57—6→130.513:27215:27—13→01.6717:07———續(xù)表總計(jì)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———總計(jì)4.7—8.5—13.2⑤從0出發(fā)———8:00—0→141.49:24211:24—14→91.1712:34618:34—9→01.8320:24———總計(jì)4.4—8—12.4

五、模型的評(píng)價(jià)、改進(jìn)及推廣

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

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

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

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

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