周福來

摘 要：為解決暑假旅行人員以成本最小化為目標(biāo)的最佳旅行路線選擇難題，基于路徑優(yōu)化理論（VRP）及粒子群算法，設(shè)計(jì)了以暑假旅游路線最短為優(yōu)化目標(biāo)的數(shù)學(xué)模型，采用計(jì)算機(jī)編程技術(shù)，設(shè)計(jì)了求解該優(yōu)化模型的粒子群算法，并選擇案例對(duì)模型及算法進(jìn)行了驗(yàn)證。案例應(yīng)用結(jié)果表明，該模型和算法能夠有效解決最佳旅游路線選擇難題，正確率達(dá)98%?；赩RP理論及粒子群算法的最短路選擇模型不僅能夠快速求解出最優(yōu)路徑方案，還能夠有效降低人工經(jīng)驗(yàn)選擇最短路徑中存在的誤差。

關(guān)鍵詞：智能優(yōu)化算法;旅游路徑規(guī)劃;粒子群算法;數(shù)學(xué)建模

DOI：10. 11907/rjdk. 191498

中圖分類號(hào)：TP306

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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 引言

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

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

1 問題描述

某旅游愛好者計(jì)劃在暑假旅游，但由于預(yù)算有限，希望以最小旅游成本完成整個(gè)旅游過程，因此，有必要提前對(duì)暑假的旅游路線進(jìn)行安排。在選擇交通工具時(shí)，統(tǒng)一選擇乘坐火車出行，而火車的售價(jià)基本上與火車行駛的路程呈正比例關(guān)系，因此，求解最小化路費(fèi)問題可以轉(zhuǎn)化為求解最短路程問題?，F(xiàn)假設(shè)火車每行駛1km的成本為1元，求如何合理安排出行線路可以使得總路費(fèi)最小。

該問題屬于典型的路徑優(yōu)化問題，路徑優(yōu)化問題一直被認(rèn)為是學(xué)術(shù)界的N-P難題，本文將針對(duì)該問題應(yīng)用建模理論及粒子群算法進(jìn)行求解。

2 目標(biāo)函數(shù)

3.3 交叉操作

交叉操作的目的是實(shí)現(xiàn)種群進(jìn)化，本文采用兩點(diǎn)交叉法實(shí)現(xiàn)粒子群的交叉進(jìn)化，即在根據(jù)適應(yīng)度函數(shù)選擇新種群過程中，隨機(jī)選擇兩個(gè)個(gè)體進(jìn)行交叉操作。進(jìn)行交叉操作時(shí)，先隨機(jī)選擇兩個(gè)交叉位置點(diǎn)，兩個(gè)個(gè)體的基因片段在此交叉點(diǎn)進(jìn)行交叉操作產(chǎn)生新的個(gè)體，再對(duì)個(gè)體中的標(biāo)號(hào)進(jìn)行調(diào)整，刪除重復(fù)編號(hào)，同時(shí)保證所有地點(diǎn)編號(hào)均被保留在個(gè)體的基因片段之內(nèi)。本文設(shè)計(jì)的交叉操作如圖1所示。

3.4 變異操作

與交叉操作類似，本文采用兩點(diǎn)變異法實(shí)現(xiàn)粒子群的變異進(jìn)化，與交叉操作不同的是，變異操作是在單個(gè)個(gè)體上的兩個(gè)不同點(diǎn)上進(jìn)行基因的互換操作，進(jìn)而實(shí)現(xiàn)整個(gè)種群的進(jìn)化。因此，在進(jìn)行變異操作時(shí)，不需要對(duì)變異后的種群個(gè)體進(jìn)行標(biāo)號(hào)的重復(fù)性檢查。其中，本文設(shè)計(jì)的變異操作如圖2所示。

4 案例分析

某一旅行愛好者在暑假期間計(jì)劃到國內(nèi)19個(gè)城市旅行，如何選擇最優(yōu)旅行方案困惑了該旅行者。在該問題中，算上家鄉(xiāng)所在地則一共有20個(gè)地點(diǎn)，對(duì)這20個(gè)地點(diǎn)進(jìn)行編號(hào)，對(duì)應(yīng)的坐標(biāo)值如表1所示，其中編號(hào)1表示家鄉(xiāng)所在地，其坐標(biāo)值為（15，27）。

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

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

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

5 結(jié)語

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

參考文獻(xiàn)：

[1] 陳文娟. 淺議旅游線路設(shè)計(jì)中旅游景點(diǎn)的選擇和安排[J]. 環(huán)球市場(chǎng)， 2015（3）：101.

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

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

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

[5] 鄢棟，陳家琪. ICP策略下帶軟時(shí)間窗的動(dòng)態(tài)車輛路徑優(yōu)化問題研究[J]. 軟件導(dǎo)刊，2018，17（3）：172-175.

[6] 陳婧怡，邱榮祖. 基于ArcGIS的多溫區(qū)冷藏車輛路徑優(yōu)化[J]. 上海海事大學(xué)學(xué)報(bào)，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] 常朝穩(wěn)，李黎. 基于約束規(guī)劃的旅游多車輛行程路線研究[J]. 計(jì)算機(jī)應(yīng)用，2006，26（s2）：202-204.

[11] 鄒臘英. 基于TSP問題的旅游路線安排[J]. 蘭州文理學(xué)院學(xué)報(bào)：自然科學(xué)版，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] 姚衛(wèi)粉，許峰. 求解車輛路徑問題的協(xié)同進(jìn)化遺傳算法[J]. 軟件導(dǎo)刊，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] 曹陽. 城市旅游規(guī)劃行程鏈的模型構(gòu)建及其應(yīng)用研究[D]. 南京：南京師范大學(xué)，2014.

[18] 李進(jìn)立，韋程?hào)|，劉廣會(huì)，等. 旅游路線規(guī)劃問題[J]. 廣西師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2016（1）：30-38.

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

[20] 賈振亮，司志剛. 基于混合整數(shù)規(guī)劃的旅游車輛調(diào)度設(shè)計(jì)和仿真[J]. 計(jì)算機(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.

（責(zé)任編輯：孫 娟）