王夢(mèng)甜

(南京財(cái)經(jīng)大學(xué)，江蘇 南京210023)

一、引言

隨著總體國(guó)民經(jīng)濟(jì)水平和人均收入水平的不斷提高，我國(guó)社會(huì)的主要矛盾已經(jīng)轉(zhuǎn)化為人民日益增長(zhǎng)的美好生活需要和不平衡不充分的發(fā)展之間的矛盾，生活的質(zhì)量成為當(dāng)代人們普遍追求的目標(biāo)。同時(shí)人均汽車擁有量的增多使得很多家庭在短暫節(jié)假日的時(shí)候選擇去周邊城市旅游，這推動(dòng)了旅游業(yè)和經(jīng)濟(jì)的發(fā)展。有效的路徑規(guī)劃成為出門必備，如何以最短的距離、最小的成本游玩周邊城市成為問題，對(duì)于提高居民的生活質(zhì)量水平具有重要意義。旅游路線規(guī)劃問題來源于數(shù)學(xué)領(lǐng)域中經(jīng)典的旅行商問題(TSP)，同時(shí)也稱為旅行推銷員問題或者貨郎擔(dān)貨問題，不僅有理論價(jià)值，同時(shí)也非常有實(shí)際價(jià)值，目前廣泛應(yīng)用于物流行業(yè)貨物配送、智能化交通道路控制、網(wǎng)絡(luò)路由和計(jì)算機(jī)等相關(guān)領(lǐng)域。旅行商問題(TSP)是數(shù)學(xué)組合優(yōu)化問題中典型NP-Hard問題，在小規(guī)模下計(jì)算好解決但是在大規(guī)模的情況下，無法運(yùn)用傳統(tǒng)數(shù)學(xué)辦法計(jì)算。對(duì)于旅行商問題目前解決方法一般主要包括兩種:完全算法解和近似方法解。完全算法指在有限的計(jì)算步驟下可以找到問題的最優(yōu)解，例如經(jīng)典的分值定界法、Dijkstra算法、動(dòng)態(tài)規(guī)劃算法等，但是這種算法缺點(diǎn)在于時(shí)間復(fù)雜度過高，尤其目前大數(shù)據(jù)時(shí)代無法滿足大規(guī)模的數(shù)據(jù)運(yùn)算需求。近似算法解指可以在多項(xiàng)式時(shí)間內(nèi)結(jié)束，從而得到問題的一個(gè)近似解，這種算法相對(duì)于前者更優(yōu)且在實(shí)際問題中應(yīng)用更多，目前研究和應(yīng)用較多的啟發(fā)式算法主要為粒子群算法、蟻群算法和遺傳算法等?？v使有這兩種算法，但是學(xué)者們?nèi)匀粵]有尋找到一個(gè)解決TSP問題的完美方案。在這方面的研究很多，國(guó)內(nèi)學(xué)者們也取得了較多成果。高海昌等人綜述了蟻群算法、遺傳算法等一系列智能算法，讓人對(duì)這些算法有了一個(gè)較為清晰的認(rèn)識(shí)；李瑋對(duì)使用的遺傳算法中編碼部分采取矩陣編碼方式解決TSP問題；姚明海等主要采取將遺傳算法和其他智能算法相結(jié)合的方式解決問題；雷玉梅等對(duì)遺傳算法原理進(jìn)行介紹并且分解進(jìn)行；吳陽等人通過對(duì)遺傳算法的改進(jìn)研究共享汽車停車點(diǎn)布局，并用MATLAB求解得到最優(yōu)解；張璽君等人針對(duì)目前出租車運(yùn)行過程效率低下問題，基于改進(jìn)遺傳算法構(gòu)建了出租車共乘線路規(guī)劃模型，最終可以快速得到優(yōu)化路徑；徐晨暢和錢松榮基于遺傳算法建立突發(fā)公交智能調(diào)度并給出相關(guān)支援方案；張惠彬等利用構(gòu)建了事故發(fā)生時(shí)人員疏散路徑優(yōu)化并用遺傳算法進(jìn)行求解。旅行商(TSP)模型用于旅游路徑規(guī)劃也有一些成果，吳凱在理論上將定性和定量?jī)煞N方法結(jié)合進(jìn)行旅游路線設(shè)計(jì)；劉倩等利用蟻群算法對(duì)景區(qū)內(nèi)車輛調(diào)度進(jìn)行路徑規(guī)劃；王慧等為滿足旅游愛好者，設(shè)計(jì)出遍歷全國(guó)所有5A級(jí)景點(diǎn)的旅游路徑規(guī)劃并用蟻群算法求解；徐書楊等考慮景區(qū)內(nèi)部擁擠度、景點(diǎn)熱度等因素使用蟻群算法規(guī)劃景區(qū)路徑，從而提升旅客旅游體驗(yàn)。文章基于目前研究狀況，以江蘇省南京市為中心，距離最短為目標(biāo)函數(shù)，通過經(jīng)度、緯度來研究其周邊共8個(gè)省會(huì)城市或直轄市(上海、南京、合肥、杭州、武漢、南昌、鄭州、濟(jì)南)出行旅游最短路徑，并且利用遺傳算法對(duì)其進(jìn)行求解，結(jié)果證明遺傳算法在解決周邊游路徑規(guī)劃問題方面具有較高的實(shí)用性。

二、旅行商(TSP)問題描述

旅行商(TSP)問題是制定多個(gè)城市地點(diǎn)并且知道每?jī)蓚€(gè)城市之間的距離，旅行商人隨機(jī)選擇其中一個(gè)城市作為起點(diǎn)出發(fā)，對(duì)所有城市進(jìn)行訪問并且只訪問一次同時(shí)回到最初的城市，尋求最短距離的完整回路。在運(yùn)籌學(xué)中可以用圖論中的無向圖進(jìn)行解釋，如無向完全圖A＝(V，E，r)，要求遍歷A中每一個(gè)節(jié)點(diǎn)并且形成簡(jiǎn)單的回路，使各邊權(quán)重相加之和最小，其中V＝{1，2，…，n}是無向圖中的每個(gè)節(jié)點(diǎn)集，表示被訪問的城市，E是連接V中兩個(gè)不同點(diǎn)之間的邊集，r表示兩城市之間的權(quán)重即距離。其數(shù)學(xué)模型定義如下:

上述中(1)式為所求的目標(biāo)函數(shù)，即旅行商所經(jīng)過路徑最小值，其中dij表示城市i到城市j的兩地距離，也就是圖論模型中的r值，在文中距離是利用兩個(gè)城市的地理坐標(biāo)(經(jīng)度、緯度)進(jìn)行轉(zhuǎn)化計(jì)算得到；(2)式和(3)式表示旅行商有且只經(jīng)過一次其中的每一個(gè)城市；(4)式表示旅行商在整個(gè)過程不能形成循環(huán)的路徑；(5)式表示是否去過這個(gè)城市，用xij＝0表示旅行商未曾經(jīng)過該城市，xij＝1則表示旅行商已經(jīng)去過的城市。

三、遺傳算法模型構(gòu)建

遺傳算法想法來源于自然界，是繼承了生物學(xué)中的遺傳思想“優(yōu)勝劣汰” ，模仿自然界生物的進(jìn)化機(jī)制，將自然界生物的繁殖、交配以及基因突變等相關(guān)概念引入整個(gè)算法過程，實(shí)質(zhì)上是一種并行且高效的全局搜索方法。遺傳算法在尋求最優(yōu)解的過程中能夠自動(dòng)獲得關(guān)于整個(gè)搜索空間的知識(shí)，并且能夠很好地改變自己的搜索過程從而獲得整個(gè)問題的最優(yōu)解。遺傳算法主要原則還是根據(jù)生物學(xué)中的適者生存，在所有可行解中找到一個(gè)近似最優(yōu)解，而且后面的每一代遺傳過程中根據(jù)個(gè)體在該環(huán)境下的適應(yīng)度再進(jìn)行選擇從而得到一個(gè)更優(yōu)解，這個(gè)新個(gè)體相對(duì)于原來的個(gè)體能夠更好地適應(yīng)環(huán)境。遺傳算法目前是較多領(lǐng)域中獲取最優(yōu)解的一種啟發(fā)式算法。

文章在構(gòu)建旅行商問題模型和了解遺傳算法相關(guān)知識(shí)基礎(chǔ)上采取了具體的遺傳算法，主要步驟如下:

Step1:編碼。在一般問題中，多數(shù)學(xué)者在使用遺傳算法的時(shí)候會(huì)采取二進(jìn)制編碼，但是本文在TSP問題中采取順序表示的編碼方式，順序中每個(gè)數(shù)字代表一個(gè)城市，不同順序經(jīng)過城市連起來為一條新染色體即為一個(gè)解。論文以南京周邊8個(gè)省會(huì)城市或直轄市(上海、南京、合肥、杭州、武漢、南昌、鄭州、濟(jì)南)為例，城市編碼選取為1～8的數(shù)字，假如生成的染色體序列號(hào)為12345678，則代表旅行商人從城市1出發(fā)依次經(jīng)過城市2、3、4、5、6、7、8最終再回到出發(fā)點(diǎn)城市1的一條回路路徑。

Step2:初始化。隨機(jī)選擇一些數(shù)量的個(gè)體(文中初始數(shù)量為100)組成最初的種群即初始解。

Step3:評(píng)估。初始化的個(gè)體優(yōu)劣程度是不一樣的，為了使最終結(jié)果更優(yōu)，在每次選擇的過程中要選擇最優(yōu)個(gè)體，因此在評(píng)估階段使用函數(shù)來評(píng)判個(gè)體的適應(yīng)度決定其優(yōu)劣程度，從而為下一步個(gè)體選擇提供依據(jù)，通常適應(yīng)度函數(shù)是由目標(biāo)函數(shù)轉(zhuǎn)化而來，文中目標(biāo)函數(shù)是求解最小值，則使適應(yīng)度函數(shù)值最大，因此采取目標(biāo)函數(shù)的倒數(shù)值作為適應(yīng)度值即可，因此適應(yīng)度函數(shù)設(shè)置如下:

Step4:選擇。遺傳算法中選擇操作是使用輪盤賭的方式，從上一代種群中選擇出較好的個(gè)體來進(jìn)行繁衍子代，個(gè)體被選擇的概率值與其適應(yīng)度值相關(guān)，根據(jù)Step3得到適應(yīng)度的值，個(gè)體適應(yīng)度值越高其被選擇到的概率則越大，個(gè)體i被選擇的概率為P，其中m為初始化的種群數(shù)量。計(jì)算公式如下:

Step5:交叉操作?；蚪徊娈a(chǎn)生后代，將上一步選擇的兩個(gè)個(gè)體作為父代進(jìn)行交叉操作以產(chǎn)生新的子代，文中操作方法是在[1，8](共8個(gè)省會(huì)城市)之間隨機(jī)選取選取兩個(gè)整數(shù)r1和r2，將兩者之間的部分交換，文中設(shè)置的交叉概率為Pc＝0.7。

Step6:變異操作。指在新產(chǎn)生的個(gè)體上進(jìn)行突變的操作，主要維持種群子代的多樣性，具體方法是在[1，8]區(qū)間上隨機(jī)選擇兩個(gè)數(shù)r1和r2，然后將個(gè)體上這兩個(gè)數(shù)字交換，從而得到變異個(gè)體，文章實(shí)驗(yàn)中變異概率設(shè)置為Pm＝0.02。

Step7:結(jié)束。文章的終止條件為算法收斂準(zhǔn)則是否滿足，如果滿足各步驟則輸出相應(yīng)的結(jié)果，否則返回至Step2進(jìn)行循環(huán)迭代直到最終輸出結(jié)果。其主要流程圖見圖1:

圖1 遺傳算法流程圖

四、實(shí)驗(yàn)結(jié)果及分析

根據(jù)上面所構(gòu)建的模型和具體的遺傳算法步驟，文章基于Python語言對(duì)遺傳算法進(jìn)行代碼實(shí)現(xiàn)，利用遺傳算法對(duì)模型求解。首先獲取8個(gè)省會(huì)城市或直轄市(上海、南京、合肥、杭州、武漢、南昌、鄭州、濟(jì)南)的地理位置坐標(biāo)，通過對(duì)地理位置的轉(zhuǎn)化求解8個(gè)城市先后游玩的最短距離。

在設(shè)定的參數(shù)以及算法收斂原則情況下得到最優(yōu)結(jié)果為25.943488，具體路徑為南京—合肥—杭州—南昌—武漢—上?！獫?jì)南—鄭州，具體路線圖如下圖2所示。綜上所述，南京周邊8個(gè)省會(huì)城市旅游最短路徑得以解決，可見遺傳算法對(duì)于解決南京城市周邊游路徑規(guī)劃問題效果顯著，對(duì)上述八個(gè)城市居民采取周邊游都具有很好的建議；但是論文仍有不足，第一，各城市數(shù)據(jù)采取的地理經(jīng)緯度導(dǎo)致最終距離很小，這與真實(shí)地圖數(shù)據(jù)有點(diǎn)差距，但是整體結(jié)果符合真實(shí)地圖；第二，本實(shí)驗(yàn)中是將遺傳算法中各參數(shù)固定，但是對(duì)于不同的參數(shù)可能會(huì)出現(xiàn)不同情況，綜上這些不足在未來實(shí)驗(yàn)中可以繼續(xù)改進(jìn)。

圖2 最短路徑圖