智能優化算法在暑假旅游路線安排中的應用

周福來

摘 要：為解決暑假旅行人員以成本最小化為目標的最佳旅行路線選擇難題，基于路徑優化理論（VRP）及粒子群算法，設計了以暑假旅游路線最短為優化目標的數學模型，采用計算機編程技術，設計了求解該優化模型的粒子群算法，并選擇案例對模型及算法進行了驗證。案例應用結果表明，該模型和算法能夠有效解決最佳旅游路線選擇難題，正確率達98%。基于VRP理論及粒子群算法的最短路選擇模型不僅能夠快速求解出最優路徑方案，還能夠有效降低人工經驗選擇最短路徑中存在的誤差。

關鍵詞：智能優化算法;旅游路徑規劃;粒子群算法;數學建模

DOI：10. 11907/rjdk. 191498

中圖分類號：TP306

文獻標識碼：A文章編號：1672-7800（2019）006-0021-04

Abstract： In order to solve the problem of choosing the best travel route for the travelers during the summer vacation with the goal of minimizing the cost， based on the theory of path optimization （VRP） and particle swarm optimization （PSO）， this paper studies the application of intelligent optimization algorithm in summer vacation tourism route arrangement. Firstly， a mathematical model is designed to optimize the shortest route of summer vacation tourism. Secondly， a PSO algorithm is designed to solve the optimization model by using computer programming technology. Finally， a case is selected to illustrate the model designed in this paper. The algorithm is validated. The application results show that the model and the algorithm can effectively solve the problem of travelers choosing the best tour route in summer vacation， and the correct rate is 98%. The shortest path selection model based on VRP theory and particle swarm optimization can not only solve the optimal path scheme quickly， but also effectively reduce the error in manual selection of shortest path.

Key Words： intelligent optimization algorithm; tourism path planning; particle swarm optimization; mathematical modeling

0 引言

隨著人們生活水平的提高和交通設施的完善，越來越多的人開始利用節假日去往不同的地方旅游。“食、住、行、游、購、娛”是旅游過程中的六要素[1]，合理安排旅游過程中的“行”，采用合適的智能優化算法解決旅行路線有效安排問題尤為重要。陳榮虎等[2]為了提高粗粒度并行遺傳算法性能，縮短對立體倉庫路徑優化問題的求解時間，將一種單程序多數據流（簡稱SPMD）并行結構運用到粗粒度并行遺傳算法中，并對算法進行改進;楊樂等[3]采用改進的蟻群算法解決了迷宮路徑選擇問題;黎澤等[4]考慮“旅行船接觸最小”因素，利用0-1規劃方法建立多線通航、船只最多模型并進行了求解，給出了最佳船只行程安排;鄢棟等[5]針對動態車輛路徑中出現新的客戶請求時的車輛路徑優化問題，提出了緊急動態客戶和數據包的概念，解決了車輛路徑優化問題;陳婧怡等[6]采用多溫區冷藏車，構建考慮運輸成本、貨損成本、制冷成本的路徑優化模型，利用遺傳算法對算例進行求解。Manuela Graf等[7]剖析了一個包括災難模擬中獨立飛行無人機或駕駛車輛的救援路徑規劃特殊的動態車輛路徑問題，設計算法并進行了求解;Changxi Ma等[8]以最小傳輸時間為目標，基于Bertsimas的魯棒離散優化理論，建立了具有可調魯棒性的電動汽車配電線路魯棒優化模型;Lai Mingyong等[9]提出了考慮不確定性的車輛初始路徑優化模型，考慮了車輛通行能力、客戶時間窗、最大行駛距離以及道路通行能力。常朝穩等[10]對帶時間約束的旅行社劃分旅游景點并制定線路，同時對該路線配送車輛建模問題進行了研究;鄒臘英等[11]研究了基于TPS的旅行者旅游路線安排問題;Hungerl Nder等[12]提出了一種自適應鄰域搜索啟發式算法，用于根據給定的交付時間表實時確定插入新客戶訂單的可行時段，解決了路徑優化問題;Lu Han等[13]根據電子商務的特點，設計了一個求解路徑優化的模型和算法;姚衛粉等[14]針對遺傳算法優化車輛路徑問題易陷入局部最優解以及收斂速度慢等問題，引入基于動態小生境的協同進化模型;Jing Wen等[15]建立了一個考慮二氧化碳排放、客戶時間窗和擁擠的自提儲物柜車輛路徑優化模型;Guezouli等[16]研究了具有時間窗的多車輛段機群規模混合車輛路徑問題;曹陽等[17]分析了國內外相關領域的研究現狀，梳理了傳統旅游線路的概念定義與旅游線路設計的方法;李進立等[18]針對旅行者的出行問題，通過分析時間、路線及旅行費用等數據，建立模型，解決旅行者出行前如何安排行程的問題;鐘儀華等[19]用賦權圖和近鄰聚類的思想構建分塊網絡加權圖，建立考慮旅游時間、行車時間和游覽時間的改進旅行商優化模型;賈振亮等[20]采用混合整數規劃方法對帶時間約束的旅行社配送車輛調度問題進行了建模研究;Rogerson[21]研究了陸游路線與當地經濟發展的關系。

綜上可知，當前國內外學者針對旅游中的線路選擇問題進行了多方位的探討，在一定程度上可以解決不同的商旅問題，但未能解決暑假期間以最低出行成本為首選因素的旅游路線安排問題。鑒于此，本文利用路徑優化理論（VRP）及粒子群算法進行旅行路徑優化求解，以節約旅行成本，提升旅游體驗。

1 問題描述

某旅游愛好者計劃在暑假旅游，但由于預算有限，希望以最小旅游成本完成整個旅游過程，因此，有必要提前對暑假的旅游路線進行安排。在選擇交通工具時，統一選擇乘坐火車出行，而火車的售價基本上與火車行駛的路程呈正比例關系，因此，求解最小化路費問題可以轉化為求解最短路程問題。現假設火車每行駛1km的成本為1元，求如何合理安排出行線路可以使得總路費最小。

該問題屬于典型的路徑優化問題，路徑優化問題一直被認為是學術界的N-P難題，本文將針對該問題應用建模理論及粒子群算法進行求解。

2 目標函數

3.3 交叉操作

交叉操作的目的是實現種群進化，本文采用兩點交叉法實現粒子群的交叉進化，即在根據適應度函數選擇新種群過程中，隨機選擇兩個個體進行交叉操作。進行交叉操作時，先隨機選擇兩個交叉位置點，兩個個體的基因片段在此交叉點進行交叉操作產生新的個體，再對個體中的標號進行調整，刪除重復編號，同時保證所有地點編號均被保留在個體的基因片段之內。本文設計的交叉操作如圖1所示。

3.4 變異操作

與交叉操作類似，本文采用兩點變異法實現粒子群的變異進化，與交叉操作不同的是，變異操作是在單個個體上的兩個不同點上進行基因的互換操作，進而實現整個種群的進化。因此，在進行變異操作時，不需要對變異后的種群個體進行標號的重復性檢查。其中，本文設計的變異操作如圖2所示。

4 案例分析

某一旅行愛好者在暑假期間計劃到國內19個城市旅行，如何選擇最優旅行方案困惑了該旅行者。在該問題中，算上家鄉所在地則一共有20個地點，對這20個地點進行編號，對應的坐標值如表1所示，其中編號1表示家鄉所在地，其坐標值為（15，27）。

設定最大迭代次數為200，種群規模設置為1 000，借助Matlab軟件，采用本文設計的方法求解出的最短旅行路徑為：4 19 11 2 1 8 17 14 20 12 5 18 10 3 6 9 15 16 7 13，則暑假期間的旅行安排順序應為：1 8 17 14 20 12 5 18 10 3 6 9 15 16 7 13 4 19 11 2 1，按照此路徑安排旅行行程花費的路費最少，此時最短旅行距離為831km（即831元）。本文優化的最佳旅行路徑如圖4所示。

采用Matlab軟件求解上述問題時，得到的算法進化迭代收斂情況如圖5所示。

由圖5可知，本文設計的算法在求解該問題時約在第56步時收斂到最優目標函數值，即為831，這表明本文設計的算法能夠有效地解決暑假旅行安排問題。此外，圖5也說明本文設計的算法能夠快速尋找到最佳旅行方案，在求解該問題時具有一定的優越性。

5 結語

本文利用粒子群算法解決了旅游過程中成本最小化的最佳路線選擇問題。首先，對旅游路線問題進行描述，將最小化的成本問題轉換成最短的行駛路程問題;其次，建立求解該問題的數學模型，設計并求解該優化模型的粒子群算法，并從個體編碼、適應度函數值設計、交叉操作、變異操作4個方面進行詳細介紹;最后，選擇案例，對本文設計的模型及算法進行驗證。研究結果表明，本文設計的模型及算法能夠有效解決旅行人員以最低成本為目標的旅游路線選擇難題。

參考文獻：

[1] 陳文娟. 淺議旅游線路設計中旅游景點的選擇和安排[J]. 環球市場， 2015（3）：101.

[2] 陳榮虎，何運杰. 基于SPMD的粗粒度并行遺傳算法在立體倉庫路徑優化中的應用[J]. 軟件導刊，2018，17（12）：108-112.

[3] 楊樂，向鳳紅，毛劍琳. 基于改進蟻群算法快速求解迷宮路徑問題研究[J]. 軟件導刊，2018，17（7）：108-110，115.

[4] 黎澤，黃俊毅，劉冠弟，等. 基于數學建模方法的旅游船只行程安排探究[J]. ?科技與生活， 2012（8）：198-199.

[5] 鄢棟，陳家琪. ICP策略下帶軟時間窗的動態車輛路徑優化問題研究[J]. 軟件導刊，2018，17（3）：172-175.

[6] 陳婧怡，邱榮祖. 基于ArcGIS的多溫區冷藏車輛路徑優化[J]. 上海海事大學學報，2019，40（1）：8-13.

[7] GRAF M，POY M，BISCHOF S， et al. Rescue path optimization using ant colony systems[C]. 2017 IEEE Symposium Series on Computational Intelligence， 2017.

[8] MA C，HAO W，HE R，et al. Distribution path robust optimization of electric vehicle with multiple distribution centers[J]. PLoS ONE， 2018， 13（3）：e0193789.

[9] LAI M，YANG H，YANG S，et al. Cyber-physical logistics system-based vehicle routing optimization[J]. Journal of Industrial and Management Optimization，2013，10（3）：701-715.

[10] 常朝穩，李黎. 基于約束規劃的旅游多車輛行程路線研究[J]. 計算機應用，2006，26（s2）：202-204.

[11] 鄒臘英. 基于TSP問題的旅游路線安排[J]. 蘭州文理學院學報：自然科學版，2015，29（5）.

[12] HUNGERL NDER P，RENDL A，TRUDEN C. On the slot optimization problem in on-line vehicle routing[J]. Transportation Research Procedia， 2017， 27：492-499.

[13] HAN L，HOU H，YANG J，et al. E-commerce distribution vehicle routing optimization research based on genetic algorithm[C]. 2016 International Conference on Logistics， Informatics and Service Sciences （LISS）， 2016.

[14] 姚衛粉，許峰. 求解車輛路徑問題的協同進化遺傳算法[J]. 軟件導刊，2015，14（1）：57-59.

[15] WEN J，LI Y. Vehicle routing optimization of urban distribution with self-pick-up lockers[C]. International Conference on Logistics， 2017.

[16] GUEZOULI L，ABDELHAMID S. A multi-objective optimization of multi-depot fleet size and mix vehicle routing problem with time window[C]. International Conference on Systems & Control， 2017.

[17] 曹陽. 城市旅游規劃行程鏈的模型構建及其應用研究[D]. 南京：南京師范大學，2014.

[18] 李進立，韋程東，劉廣會，等. 旅游路線規劃問題[J]. 廣西師范學院學報：自然科學版，2016（1）：30-38.

[19] 鐘儀華，羅仕明. 分塊分層優化的旅游路線規劃問題研究[J]. 運籌與管理，2017（9）：66-71.

[20] 賈振亮，司志剛. 基于混合整數規劃的旅游車輛調度設計和仿真[J]. 計算機仿真，2007，24（8）：233-235.

[21] ROGERSON C M. Tourism routes as vehicles for local economic development in South Africa： the example of the magaliesberg meander[J]. ?Urban Forum，2007，18（2）：49-68.

（責任編輯：孫 娟）