基于遺傳算法的旅游最優(yōu)路徑探究

李振業(yè) 陳婷 陳靜

摘要：旅游越來越成為人們喜愛的一種娛樂方式，但隨著大量游客的涌入，各個(gè)旅游園區(qū)迫切需要設(shè)計(jì)合理高效的旅游路線提高游客的旅游質(zhì)量。以徐州潘安湖風(fēng)景區(qū)為例，采用遺傳算法生成最優(yōu)旅游路徑，高效簡(jiǎn)單，能快速為消費(fèi)者找到限制條件下的最優(yōu)路徑方案。

關(guān)鍵詞：最優(yōu)路徑;遺傳算法;旅游路線;數(shù)學(xué)建模

中圖分類號(hào)：TP302? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? 文章編號(hào)：1009-3044（2018）34-0181-03

1 問題描述

1.1 問題背景

隨著徐州當(dāng)?shù)亟?jīng)濟(jì)的發(fā)展，徐州潘安湖濕地公園游客不斷增加，設(shè)計(jì)合理高效的旅游線路直接影響到園區(qū)的游客承受能力、廣大游客的游覽體驗(yàn)以及園區(qū)的經(jīng)濟(jì)效益等。

1.2 問題描述及假設(shè)

選取潘安湖景區(qū)的部分景點(diǎn)（如圖1所示，每?jī)删包c(diǎn)之間往返距離已知）給出如下假設(shè)：

（1）各景點(diǎn)設(shè)置編號(hào)表示：S0：景石，S1：游客服務(wù)中心，S2：陽(yáng)光草坪，S3：森林小劇場(chǎng)，S4：兒童科普體驗(yàn)區(qū)，S5：兒童戲水場(chǎng)，S6：濕地博物館，S7：濕地商業(yè)街。

（2）任兩個(gè)景點(diǎn)間存在最短步行距離分別為d（n1，n2）表示景點(diǎn)n1到景點(diǎn)n2的最短路徑。

（3）假設(shè)游客的步行速度平均在2km/h左右。

（4）游客在景區(qū)停留的時(shí)間由“景點(diǎn)之間的步行時(shí)間”“景點(diǎn)游覽時(shí)間（即在景點(diǎn)內(nèi)游玩的時(shí)間）” 和“在景區(qū)外的等待時(shí)間”三部分組成，其他時(shí)間忽略不計(jì)。

有3個(gè)旅游團(tuán)，12：00同時(shí)從景石出發(fā)，要求三個(gè)旅游團(tuán)17：00前到達(dá)濕地商業(yè)街，17：30離開濕地商業(yè)街（注：?各景點(diǎn)限時(shí)開放?森林小劇場(chǎng)只在半點(diǎn)或整點(diǎn)開放;?濕地商業(yè)街游覽時(shí)間至少為30分鐘），并且每個(gè)景點(diǎn)（濕地商業(yè)街除外）同時(shí)只能容納1個(gè)旅游團(tuán)游覽，按照時(shí)間順序后到達(dá)的旅游團(tuán)，需要等待先到達(dá)的旅游團(tuán)游覽結(jié)束之后才能開始游覽。建立數(shù)學(xué)模型，為三個(gè)旅游團(tuán)分別設(shè)計(jì)一條能游覽完全部7個(gè)景點(diǎn)且游覽總時(shí)間最長(zhǎng)的游覽路線。

3 結(jié)論

3.1 模型的優(yōu)點(diǎn)

（1）計(jì)算簡(jiǎn)單，結(jié)果準(zhǔn)確，符合實(shí)際，具有可行性;

（2）遺傳算法具有系統(tǒng)優(yōu)化、適應(yīng)和學(xué)習(xí)的高性能計(jì)算，不需要求導(dǎo)或其他輔助知識(shí)，只需要適應(yīng)度函數(shù)值。基于自適應(yīng)搜索技術(shù)增加搜索過程的靈活性，具有較好的全局優(yōu)化求解能力。直接以目標(biāo)函數(shù)值為搜索信息，對(duì)函數(shù)的形態(tài)無要求，具有較好的普適性和易擴(kuò)充性，更適合大規(guī)模復(fù)雜問題的優(yōu)化。

3.2 模型的缺點(diǎn)

（1）約束條件少，具有理想化;

（2）節(jié)點(diǎn)變多會(huì)使計(jì)算量劇增;

（3）輪盤賭法策略可能會(huì)產(chǎn)生較大的抽樣誤差，如果產(chǎn)生異常個(gè)體引起早熟收斂，影響求得全局最優(yōu)解，

（4）進(jìn)化過程中產(chǎn)生大量數(shù)據(jù)，計(jì)算大、占用時(shí)間長(zhǎng)。

3.3 模型的改進(jìn)

（1）改變遺傳算法的控制參數(shù)，控制參數(shù)一般有群體大小、交叉概率、變異概率等，它們對(duì)算法性能有很大影響。

（2）輪盤賭法可能產(chǎn)生較大的抽樣誤差，可選用改進(jìn)方法，如非線性排名選擇，基于局部競(jìng)爭(zhēng)機(jī)制的選擇等。

參考文獻(xiàn)：

[1] 王法有，劉玉娟.通過數(shù)學(xué)建模設(shè)計(jì)四川11名景最佳旅游路線[J].數(shù)學(xué)學(xué)習(xí)與研究，2010（17）.

[2] 于瑩瑩，陳燕，李桃迎.改進(jìn)的遺傳算法求解旅行商問題[J].控制與決策，2014，29（8）.

[3] 李波，秦華旺.路徑優(yōu)化案例遺傳算法的實(shí)現(xiàn)[J].電子設(shè)計(jì)工程，2017，25（20）.

[4] 鄧雪，李家銘.層次分析法在權(quán)重計(jì)算方法分析極其應(yīng)用研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012，42（7）.

[5] 常洪江.遺傳算法綜述[J].電腦學(xué)習(xí)，2016（3）.

【通聯(lián)編輯：代影】