謝　飛， 楊　揚， 何　杰

(1.西南交通大學 信息科學與技術學院，成都 611756;2.西南交通大學 土木工程學院，成都 611756)

?

基于改良圈算法與線性規(guī)劃的全國自駕游線路優(yōu)化研究

謝飛1， 楊揚1， 何杰2

(1.西南交通大學 信息科學與技術學院，成都 611756;2.西南交通大學 土木工程學院，成都 611756)

摘要：自駕游以自由與個性化、靈活與舒適性等特點深受廣大旅游愛好者喜愛，而其線路規(guī)劃質量直接影響自駕游者的滿意度。以全國5A級旅游景區(qū)為目的地，選取了一名西安市自駕游愛好者為研究對象，最初運用改良圈算法規(guī)劃出各省份的游覽線路，然后分別以時間最優(yōu)和費用最優(yōu)為目標函數(shù)，以年旅游時間限值、單次旅游時間限值為約束條件，建立了整數(shù)線性規(guī)劃模型；采用LINGO軟件，求解出一條全國5A級景區(qū)的自駕游最優(yōu)方案，具有一定的適用性。

關鍵詞：TSP問題;自駕游;線性規(guī)劃;改良圈算法; LINGO

近年來，隨著我國國民經(jīng)濟的不斷發(fā)展，越來越多的人選擇自駕車出游。自駕游作為一種寓健康、娛樂、休閑于一體，充滿個性化和無窮魅力的旅游活動，更能適應現(xiàn)代自助旅游的發(fā)展趨勢。但是自駕游存在一些劣勢，如道路收費太多，無法享受團隊優(yōu)惠，高昂的油費等，使得現(xiàn)階段自駕游所需費用一直居高不下[1]。制定一個合理的自駕出游路線，不僅可以節(jié)約出游時間，提高旅游質量，更能節(jié)省旅游成本。此處研究對象是一名西安市的自駕游愛好者，研究內容是以全國5A級旅游景區(qū)作為該愛好者的目的地，規(guī)劃其未來在最短時間內游覽完所有5A級景區(qū)的旅游路線。在此基礎上，進一步考慮出行次數(shù)與時間限制、旅游費用等對線路規(guī)劃的影響，最終設計出費用最優(yōu)的旅游線路。

自駕游線路優(yōu)化問題，屬于典型的旅行商問題(Traveling Salesman Problem，簡稱TSP問題)，目前國內外有不少的學者對此做了大量的研究。TSP問題是游客由某地出發(fā)，途中恰好不重復地游覽完所有景點，然后回到出發(fā)地，形成一個閉合的周游型旅游線路[2]。TSP問題的求解方法主要有線性規(guī)劃法[3]、分支定界法[4]、改良圈算法[5]、遺傳算法[6]和蟻群算法[7]等。此處采用整數(shù)線性規(guī)劃模型對TSP問題進行建模求解[13]，但直接建立整數(shù)線性規(guī)劃模型求解，由于設定變量太多而造成運算效率低下，極有可能求不出最優(yōu)解。盧欣和李衍達[14]通過將問題劃分為多層，使每個層次的問題規(guī)模限制在一定范圍內，以降低問題的復雜度。為此，將自駕游線路規(guī)劃問題拆分為兩個層次求解：各省份游覽線路最優(yōu)問題；全國游覽線路最優(yōu)問題。利用改良圈算法先解決各省份的游覽最優(yōu)線路，再建立以各省份為目的地的整數(shù)線性規(guī)劃模型，最后給出全國5A景區(qū)的具體游覽方案。

1建模方法理論研究

1.1改良圈算法

結合圖論知識，針對每個省份的5A景點，構造一個賦權完全圖G=(v,e)，頂點v表示要游覽的景點，邊e表示連通各景點的道路，邊上的權表示景點間的距離。各省份最佳游覽線路問題是要在圖G中求解出一個權值最小的Hamilton圈，這種圈被稱為最優(yōu)圈。求解最優(yōu)圈的思路是：先求出一個Hamilton圈C，然后修改C得到具有較小權的另一個Hamilton圈，最終反復修改得到最優(yōu)圈，這種修改的方法叫做改良圈算法。按照以上思路，先用最鄰近算法求解近似最優(yōu)圈[4]，具體步驟如下：

(i) 選取任意一個頂點v0作為起點，找一條與v0關聯(lián)且權最小的邊e1，e1的另一個端點記作v1，得到一條路v0v1；

(ii) 假設已選出路v0v1…vi，在現(xiàn)有路徑中找到一個與vi最鄰近的頂點vi+1得到v0v1…vivi+1；

(iii) 若i+1

于是得到了一個近似最優(yōu)圈，但最鄰近算法求得的Hamilton圈一般不是最優(yōu)解，在此基礎上，繼續(xù)通過改良圈算法，便可獲得更短的Hamilton圈。將C=v1v2…vnv1作為改良圈算法的初始圈，按照以下方法，最終可得到一個最優(yōu)圈C1。

1) 對于圈C所有滿足1

2) 返回1)，直至無法改進，最終得到最優(yōu)圈C1，停止。

1.2整數(shù)線性規(guī)劃模型

為了更好地分析出行次數(shù)與時間、旅游費用等因素對線路規(guī)劃的影響，首先建立僅考慮時間因素的自駕游線路規(guī)劃基本模型，然后逐漸考慮其他因素的影響，并建立綜合考慮年出游次數(shù)限制、單次出游時間限制以及旅游費用的線路規(guī)劃模型。

1.2.1自駕游線路規(guī)劃基本模型

僅考慮時間因素的情況下，要求游覽全國所有5A級景點，使得游覽時間最少。假設xij為旅游者從省份i到省份j旅游且每次都先抵達省會城市，tij為從省份i到省份j的自駕車時間，T0為游客游覽所有景點的逗留時間，T為游客游覽所有景點的總時間，可建立如下的基本模型：

目標函數(shù)：

(1)

約束條件：

(2)

(3)

(4)

(5)

1.2.2考慮出游限制的費用最優(yōu)線路規(guī)劃模型

在實際旅游的過程中，由于工作、家庭以及經(jīng)濟情況的原因，旅游愛好者不可能連續(xù)出游，每年出游的次數(shù)和每次出游的時間都會受到現(xiàn)實條件的約束。旅游途中，旅游費用主要由交通費用、門票費用和食宿費用3部分產(chǎn)生。假設M為旅游總費用，m0表示游覽所有景點的門票費用，c0為日均食宿費用，ci j為旅游者從省份i到省份j旅游的油費，xi j k為旅游者第k次出游時從省份i到省份j旅游，yi k為第k次出游時游覽省份i，Ti為游客游覽省份i的逗留時間，λ為年出游總次數(shù)，ω為單次出游的限制時間，于是可建立費用最優(yōu)線路規(guī)劃模型：

目標函數(shù)：

(6)

約束條件：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

上述模型中，滿足式(6)所求的xijk即為費用最優(yōu)的全國自駕游最優(yōu)線路；式(7)保證每次旅游的時間不超過出游的限制時間；式(8)(9)要求各省份都被游覽且只被游覽一次；式(10)—(12)限制游覽每個省份時，只允許從一條邊進入且從一條邊離開，最終回到出發(fā)地西安；式(13)是保證除出發(fā)地外，不允許走回頭路；式(14)限定xi j k和yi k為0-1決策變量。

2基于改良圈算法的各省份最優(yōu)線路求解結果

以四川省的5A景點作為算例，運用MATLAB軟件，得到了該省的自駕線路規(guī)劃圖，如圖1、圖2所示。

圖1　線路規(guī)劃圖(最鄰近算法)Fig.1　Route programming by nearest algorithm

圖2　線路規(guī)劃圖(改良圈算法)Fig.2　Route programming by modifeid circle algorithm

由圖1，圖2可知，改良圈算法求得的四川省最優(yōu)線路比最鄰近算法的效果明顯好，且該省的最優(yōu)路徑為成都市區(qū)→青城山→都江堰→汶川→黃龍景區(qū)→九寨溝→北川羌城→劍門關景區(qū)→閬中古城→鄧小平故里→樂山大佛→峨眉山→成都市區(qū)，距離為1 844 km。因此，可以利用改良圈算法對其他省份的自駕線路進行優(yōu)化，然后可以根據(jù)各景點間的里程信息與各景點的游覽時間，計算出全國各省份5A級景點的自駕游覽最優(yōu)時間，如表1所示。

表1　各省份5A級景點自駕游最優(yōu)時間表

由表1可知，部分省份由于5A級景點較多，游覽時間會比較長，如果每年出游次數(shù)和單次出游時間受到限制，每次游覽的景點數(shù)也將受限，線路規(guī)劃會出現(xiàn)大幅度的調整。

3基于整數(shù)線性規(guī)劃的全國最優(yōu)線路求解結果

3.1時間最優(yōu)的全國自駕游線路規(guī)劃結果

利用全國省會城市間的道路數(shù)據(jù)與各省份的自駕游覽時間信息，運用Lingo軟件，得到了時間最優(yōu)的全國自駕游線路規(guī)劃示意圖，如圖3所示。

由圖3可知，全國自駕游最優(yōu)路徑[7]為西安→武漢→合肥→南京→上?！贾荨Ｖ荨喜L沙→廣州→?？凇蠈帯ッ鳌F陽→重慶→成都→拉薩→烏魯木齊→西寧→蘭州→銀川→呼和浩特→太原→石家莊→北京→哈爾濱→長春→沈陽→天津→濟南→鄭州→西安，線路總長為19 800 km，線路總游覽時間為267 d。

圖3　全國自駕游線路規(guī)劃圖(時間最優(yōu))Fig.3　The national route programming of self-driving tour on minimum-time

3.2費用最優(yōu)的全國自駕游線路規(guī)劃結果

考慮到旅游愛好者每年出游的限制次數(shù)λ和每次出游的限制時間ω對其線路規(guī)劃造成的影響，同時要求旅游費用盡可能節(jié)省，結合各省會城市間的道路數(shù)據(jù)和各省份的游覽時間信息，利用LINGO軟件，得到了當λ=2且ω=25時，費用最優(yōu)的全國自駕游線路規(guī)劃示意圖，如圖4所示。

圖4　全國自駕游線路規(guī)劃示意圖(費用最優(yōu))Fig.4　The national route programming of self-driving tour on minimum-cost

由圖4可知，由于出游時間存在約束，旅游愛好者的每次出游范圍都只能局限于以西安為中心，向周邊輻射的某一區(qū)域，其中成都和南京為單目的地游覽線路。與時間最優(yōu)的情況相比，增加了不少往返的路程，同時也增加旅游開銷。為了節(jié)省一些路途時間，出行方式還可以考慮乘坐高鐵或飛機到達與景區(qū)相鄰的省會城市，而后采用租車的方式自駕到景區(qū)游覽。但這種出行方式也會給旅游者帶來一些不便，有時費用也會增加。根據(jù)線路規(guī)劃的結果，得到了全國自駕游的具體行程安排以及相關費用信息，如表2所示。

表2　全國自駕游行程安排表

由表2可知，該自駕線路總游覽時間為297 d，旅游總費用為110 186元。根據(jù)線路安排結果的先后順序，大致可將全國31個省份劃分為西北(新疆、西藏、青海、甘肅、寧夏、陜西)、華北(河北、天津、內蒙古、山西)、東北(黑龍江、吉林、遼寧)、華東(北京、武漢、河南、山東)、東南(福建、安徽、浙江、江蘇、上海)、華南(廣西、海南、湖南、廣東、江西)、西南(重慶、四川、云南、貴州)等7個自駕游區(qū)域進行游覽，符合實際出行的安排。

4結語

改良圈算法能夠有效地解決周游型旅游愛好者的線路規(guī)劃問題，能夠得到比較滿意的可行解，降低了線性規(guī)劃法直接求解TSP問題的難度。將改良圈算法和線性規(guī)劃法相結合，運用到全國5A級景區(qū)的自駕游線路優(yōu)化之中，簡單易懂，且線性規(guī)劃法在求解景點比較少時運行速度也非?？靃8]，得到的結果對實際自駕游線路的選擇具有一定的指導意義。

參考文獻(References)：

[1] 李勇.旅行社的自駕游業(yè)務發(fā)展策略[J].商場現(xiàn)代化,2007(6):109-110

LI Y.The Business Development Strategy of Travel Agency about Self-driving Tour[J].MARKET MODERNIZATION,2007(6):109-110

[2] 曹旭.旅游線路優(yōu)化設計[D].蘭州：西北民族大學,2012

CAO X.The Research of Tuorist Route on Optimization Design[D].Lanzhou:Northwest University for Nationalities,2012

[3] BEHDANI B,COLE S J.An Integer-programming-based Approach to the Close-Enough Traveling Salesman Problem[J].Informs Journal on Computing,2014,26(3):415-432

[4] 全惠云,江力.求解TSP的演化算法[J].湖南師范大學學報(自然科學版)：1999(2):28-34

QUAN H Y,JIANG L.An Evolutionary Algorithm for TSP[J].Hunan Normal University(Natural Science Edition),1999(2):28-34

[5] 王海莉.混合免疫算法及其應用研究[D].西安:西北大學,2005

WANG H L.Hybrid Immune Algorithm and its Application in Solving TSP[D].Xi’an:Northwest University,2005

[6] 蔣榮.遺傳算法在TSP問題上的應用[D].合肥:合肥工業(yè)大學,2009

JIANG R.Genetic Algorithm and its Application in Trav-elling Salesman Problem[D].Hefei:Hefei University of Technology,2009

[7] 李旭,汪海妹,劉家保,等.基于蟻群算法的旅游線路優(yōu)化研究：以合肥市為例[J].重慶工商大學學報(自然科學版)：2015(2):67-70

LI X,WANG H M,LIU J B,et al.Research on Tour Route Optimization Based on Ant Swarm Algorithm：Taking Hefei City as an Example[J].Journal of Chongqing Technology and Business University(Natural Science Edition),2015(2):67-70

[8] 王艷紅,黃華,張文娟.關于TSP問題的分塊解法[J].重慶文理學院學報(自然科學版)：2008(5):32-34

WANG Y H,HUANG H,ZHANG W J.A Divided Method in Solving TSP[J].Journal of Chongqing University of Arts and Sciences(Natural Science Edition),2008(5):32-34

[9] 盧欣,李衍達.TSP問題分層求解算法的復雜度研究[J].自動化學報,1999(2):279-282

LU X,LI Y D.Complexity Analysis of the Multi-Layered Clustering Algorithm In TSP[J].Acta Automatica Sinica,1999(2):279-282

責任編輯：李翠薇

Research on the Optimization of National Self-driving Tour Route Based on Modified Circle Algorithm and Linear Programming

XIE Fei1, YANG Yang1, HE Jie2

(1.School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, China;2.College of Civil Engineering, Southwest Jiaotong University, Chengdu 611756, China)

Abstract：Since the self-driving has many advantages, such as liberalization, customization, flexibility and comfort, now many travel enthusiasts have been attracted by self-driving. And the quality of the tourist routes may directly affect the satisfaction of self-driving tourists. In this paper, the national 5A tourist attractions are taken as the destination, a self-driving tourist in Xi’an City is selected as the research object. This article uses modified circle algorithm to design the tourist route of each province, sets the optimization of time and cost as objective function, takes the limit value of travel time per year and the limit value of single travel time as constraint condition, and builds the integer-linear programming model. The optimal self-driving tour decision of the national 5A tourist attractions is solved with LINGO software, which has a certain applicability.

Key words：TSP problem; self-driving tour; linear programming; modified circle algorithm; LINGO

中圖分類號：O157

文獻標志碼：A

文章編號：1672-058X(2016)03-0088-06

作者簡介：謝飛(1990-),男,四川內江人,碩士研究生,從事鐵路信號控制研究.

收稿日期：2015-11-09；修回日期：2015-12-25.

doi:10.16055/j.issn.1672-058X.2016.0003.018