侯　樂，楊輝華,2+，樊永顯，李靈巧,2，蔣淑潔.桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院，廣西桂林540042.北京郵電大學(xué)自動(dòng)化學(xué)院，北京00876.桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西桂林54004

* The National Natural Science Foundation of China under Grant Nos. 21365008, 61105004 , 61462018 (國家自然科學(xué)基金); the Natural Science Foundation of Guangxi under Grant No. 2012GXNSFAA053230 (廣西自然科學(xué)基金); the Scientific Research Fund of Guangxi Education Department under Grant No. LX2014139 (廣西教育廳科研項(xiàng)目); the Innovation Project of Graduate Education of Guilin University of Electronic Technology under Grant No. GDYCSZ201478 (桂林電子科技大學(xué)研究生教育創(chuàng)新計(jì)劃資助項(xiàng)目).

Received 2015-03,Accepted 2015-06.

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-06-05, http://www.cnki.net/kcms/detail/11.5602.TP.20150605.1537.002.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0142-09

?

基于ILS-CS優(yōu)化算法的個(gè)性化旅游線路研究*

侯樂1，楊輝華1,2+，樊永顯3，李靈巧1,2，蔣淑潔1
1.桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院，廣西桂林541004
2.北京郵電大學(xué)自動(dòng)化學(xué)院，北京100876
3.桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西桂林541004

* The National Natural Science Foundation of China under Grant Nos. 21365008, 61105004 , 61462018 (國家自然科學(xué)基金); the Natural Science Foundation of Guangxi under Grant No. 2012GXNSFAA053230 (廣西自然科學(xué)基金); the Scientific Research Fund of Guangxi Education Department under Grant No. LX2014139 (廣西教育廳科研項(xiàng)目); the Innovation Project of Graduate Education of Guilin University of Electronic Technology under Grant No. GDYCSZ201478 (桂林電子科技大學(xué)研究生教育創(chuàng)新計(jì)劃資助項(xiàng)目).

Received 2015-03,Accepted 2015-06.

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-06-05, http://www.cnki.net/kcms/detail/11.5602.TP.20150605.1537.002.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0142-09

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

摘要：針對(duì)迭代局部搜索（iterated local search，ILS）算法求解旅游線路時(shí)間花費(fèi)較長(zhǎng)的問題，提出了一種ILS結(jié)合布谷鳥搜索（cuckoo search，CS）的優(yōu)化算法，來優(yōu)化旅游線路的時(shí)間花費(fèi)。該算法首先根據(jù)相關(guān)目標(biāo)和約束采用ILS算法求解旅游景點(diǎn)及初始旅游線路，然后在滿足旅游景點(diǎn)時(shí)間窗約束及景點(diǎn)總數(shù)不變的情況下采用CS算法進(jìn)一步最小化旅游線路的時(shí)間花費(fèi)。該研究獲得的線路更符合旅游習(xí)慣，并且旅游時(shí)間花費(fèi)更少。通過Daminaos數(shù)據(jù)集和桂林景點(diǎn)數(shù)據(jù)集進(jìn)行驗(yàn)證，結(jié)果表明該優(yōu)化算法相比于僅使用ILS算法所規(guī)劃出的旅游線路，平均時(shí)間花費(fèi)減少8%，更符合用戶旅游選擇習(xí)慣。

關(guān)鍵詞：旅游線路規(guī)劃；迭代局部搜索；布谷鳥搜索；帶時(shí)間窗的定向問題；帶時(shí)間窗的旅行商問題

1　引言

隨著經(jīng)濟(jì)社會(huì)的發(fā)展，旅游業(yè)競(jìng)爭(zhēng)也越來越激烈，如何減少路線安排的盲目性和隨意性，為客戶提供個(gè)性化旅游線路，從而提供更多可供用戶選擇的旅游方案已逐步成為目前相關(guān)企業(yè)以及學(xué)科的研究熱點(diǎn)。然而當(dāng)前的旅游推薦系統(tǒng)通常通過運(yùn)籌學(xué)方法來尋求最優(yōu)線路，具有如下問題：（1）未考慮組團(tuán)旅游的需求；（2）未考慮游客的個(gè)性化喜好、需求和約束[1]；（3）未考慮用戶選擇的開始與結(jié)束地點(diǎn)、預(yù)算的花費(fèi)時(shí)間以及當(dāng)前出發(fā)的時(shí)間。因此需要根據(jù)上述約束利用機(jī)器學(xué)習(xí)的方法提出更為合理、更符合用戶旅游選擇習(xí)慣的線路[2]。

最早，針對(duì)個(gè)性化旅游線路規(guī)劃問題，Hagen等人[3]通過分支界定法來實(shí)現(xiàn)旅游線路的規(guī)劃，該方法計(jì)算時(shí)間長(zhǎng)，且線路規(guī)劃不合理。Kramer等人[4]根據(jù)每個(gè)用戶對(duì)同一個(gè)景點(diǎn)評(píng)分的差異性，提出了個(gè)性化的旅游線路規(guī)劃，改善了傳統(tǒng)旅游推薦系統(tǒng)通過統(tǒng)計(jì)學(xué)方法設(shè)定單個(gè)景點(diǎn)的評(píng)分問題。當(dāng)前，Chao等人將定向問題（orienteering problem，OP）[5]作為個(gè)性化旅游線路規(guī)劃問題的求解優(yōu)化方案[6-7]。該問題為NP難問題，不能夠在多項(xiàng)式時(shí)間內(nèi)求出最優(yōu)解，且未考慮各景點(diǎn)開放和參觀時(shí)間。因此Dumas等人針對(duì)景點(diǎn)開放時(shí)間和參觀時(shí)間問題，提出了一種帶時(shí)間窗的旅行商問題（travel salesman problem with time windows，TSPTW）的旅游線路規(guī)劃。該模型要求所有的景點(diǎn)必須被訪問，因此不適用于時(shí)間有限、景點(diǎn)數(shù)量多的旅游線路規(guī)劃[8]。近期，Vansteenwegen等人[9]采用迭代局部搜索算法來對(duì)帶時(shí)間窗的定向問題進(jìn)行求解，該算法能夠在較短的時(shí)間內(nèi)計(jì)算出一條較優(yōu)的線路。Gavalas等人[10]采用聚類和迭代搜索相結(jié)合的方法解決帶時(shí)間窗的定向問題。但是上述兩種方法規(guī)劃出來的旅游線路存在行程花費(fèi)時(shí)間較長(zhǎng)的缺點(diǎn)。

根據(jù)上述研究所存在的問題，本文提出了一種基于迭代局部搜索（iterated local search，ILS）結(jié)合布谷鳥搜索（cuckoo search，CS）的優(yōu)化算法模型。該模型首先采用ILS求解出旅游景點(diǎn)及初始旅游線路，然后在滿足旅游景點(diǎn)時(shí)間窗約束及景點(diǎn)總數(shù)不變的情況下，采用CS算法最小化旅游線路的時(shí)間花費(fèi)。該優(yōu)化算法通過Daminaos數(shù)據(jù)集和桂林市的部分景點(diǎn)數(shù)據(jù)集進(jìn)行驗(yàn)證，對(duì)比于單一使用迭代局部搜索算法所規(guī)劃出的旅游線路，具有更好的優(yōu)化效果。

2　問題描述

給定一個(gè)完全有向圖G＝(V，E)，其中V＝{1，2，…，n}是節(jié)點(diǎn)集，E＝{(i，j)|i，j∈V}是邊集。每個(gè)節(jié)點(diǎn)i＝1，2，…，n對(duì)應(yīng)一個(gè)得分Si、參觀時(shí)間Ti和一個(gè)時(shí)間窗[Oi，Ci]。邊tij表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j所需的時(shí)間（包括Tj）。因此，帶時(shí)間窗的定向問題即找出一條從節(jié)點(diǎn)1出發(fā)到節(jié)點(diǎn)n終止的路徑，使得所經(jīng)過點(diǎn)的總得分最大化。每個(gè)節(jié)點(diǎn)至多能訪問一次，路徑中訪問相應(yīng)點(diǎn)所用的總時(shí)間不能超過預(yù)先規(guī)定的時(shí)間預(yù)算Tmax。若節(jié)點(diǎn)j是節(jié)點(diǎn)i的下一個(gè)訪問節(jié)點(diǎn)，則xij＝1，反之等于0，xij為決策變量。Tmax滿足Tmax＝Cn?O1，帶時(shí)間窗的定向問題的數(shù)學(xué)描述為[5]：

其中，si為訪問節(jié)點(diǎn)i的開始時(shí)間；M為一個(gè)大的常量。式（1）為目標(biāo)函數(shù)，表示路徑上所有滿足xij＝1的點(diǎn)的得分之和最大；式（2）中x1j＝1表示路徑必須從節(jié)點(diǎn)1出發(fā)，xin＝1表示路徑中n為最后節(jié)點(diǎn)；式（3）中xik和xkj表示每個(gè)節(jié)點(diǎn)至多被訪問一次，不允許節(jié)點(diǎn)被重復(fù)訪問；式（4）表示若節(jié)點(diǎn)i、j聯(lián)通，則j的開始時(shí)間等于i的開始時(shí)間加上節(jié)點(diǎn)i、j的距離和i的參觀時(shí)間，若節(jié)點(diǎn)i、j不聯(lián)通，則j的開始時(shí)間始終大于si和tij之和，確保節(jié)點(diǎn)時(shí)間的連通性；式（5）表示路徑中所有聯(lián)通節(jié)點(diǎn)花費(fèi)的時(shí)間總和（包括節(jié)點(diǎn)之間的距離、參觀時(shí)間及等待時(shí)間）小于時(shí)間預(yù)算Tmax；式（6）表示節(jié)點(diǎn)i的訪問開始時(shí)間大于i的開放時(shí)間并小于其關(guān)閉時(shí)間；式（7）表示xij為決策變量，其值為0或1。

優(yōu)化算法的核心是將ILS算法規(guī)劃出的初始旅游線路作為帶時(shí)間窗的旅行商問題[8]，使用布谷鳥搜索算法[11]對(duì)其進(jìn)行優(yōu)化。TSPTW問題可描述為：對(duì)于給定的一組節(jié)點(diǎn)集合{1，2，…，n}，節(jié)點(diǎn)1和節(jié)點(diǎn)n分別為起始和終止節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)i有一參觀時(shí)間Ti和一個(gè)時(shí)間窗[Oi，Ci]，每個(gè)節(jié)點(diǎn)只能在其時(shí)間窗內(nèi)被訪問。邊tij表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j所需的時(shí)間（包括Tj）。優(yōu)化目標(biāo)是給出一條訪問所有節(jié)點(diǎn)的路徑，使總的時(shí)間花費(fèi)最少。帶時(shí)間窗的旅行商問題的數(shù)學(xué)描述為：

式（8）為目標(biāo)函數(shù)，表示路徑中所有聯(lián)通節(jié)點(diǎn)花費(fèi)時(shí)間之和（包括節(jié)點(diǎn)之間的距離時(shí)間、參觀時(shí)間及等待時(shí)間）最??；式（9）中x1j＝1表示路徑必須從節(jié)點(diǎn)1出發(fā)，xin＝1表示路徑中n為最后節(jié)點(diǎn)；式（10）中xik和xkj表示每個(gè)節(jié)點(diǎn)必須訪問一次；式（11）表示節(jié)點(diǎn)i的訪問開始時(shí)間大于i的開放時(shí)間并小于其關(guān)閉時(shí)間；式（12）表示xij為決策變量，其值為0或1。

為求解這兩個(gè)問題，本文采用迭代局部搜索算法和布谷鳥搜索算法依次求解。首先根據(jù)相關(guān)約束采用迭代局部搜索算法，最大化總收益，求解出旅游景點(diǎn)和初始旅游線路；然后在旅游景點(diǎn)不變的情況下，采用布谷鳥搜索算法進(jìn)一步優(yōu)化時(shí)間花費(fèi)。其中，迭代局部搜索算法的基本原理和流程參見文獻(xiàn)[9]。

3　優(yōu)化模型求解

3.1編碼方案

本文根據(jù)TSPTW問題的特點(diǎn)采用基于優(yōu)先級(jí)的編碼方案，每一個(gè)編碼個(gè)體根據(jù)優(yōu)先級(jí)的大小表示一種可行解[12]。

以ILS規(guī)劃出的路徑{1，8，3，6，9，2，5，7，4，100}為例，其中1表示出發(fā)節(jié)點(diǎn)，100表示結(jié)束節(jié)點(diǎn)，則只需要對(duì)其余的8個(gè)節(jié)點(diǎn)按照優(yōu)先級(jí)編碼。具體編碼方式如下：

（1）生成8個(gè)取值范圍為[?2，2]之間的隨機(jī)數(shù)

(?1.230 5，0.345 2，1.735 6，?0.253 6，1.467 3，?0.531 6，0.432 1，0.764 6)

（2）將優(yōu)先級(jí)按照降序排列得到一條編碼方案

(1.735 6,1.467 3,0.764 6,0.432 1,0.345 2,?0.253 6，?0.531 6,?1.230 5)則根據(jù)上述編碼方案解碼得到的一條可行解為{1，8，3，6，9，2，5，7，4，100}。

以萊維飛行的方式搜索新的鳥巢并進(jìn)行位置更新[13]，如式（13）所示：

在CS算法中采用Levy搜索路徑，如式（15）所示：

本文取值β＝1.2，u和v服從式（16）的正態(tài)分布：

3.2適應(yīng)度函數(shù)

根據(jù)基于時(shí)間窗的旅行商問題的數(shù)學(xué)模型，優(yōu)化目標(biāo)是該條路徑的節(jié)點(diǎn)在滿足約束的條件下花費(fèi)時(shí)間最少，則CS算法的適應(yīng)度函數(shù)如式（17）所示：

該適應(yīng)度函數(shù)表示對(duì)可行解上所有聯(lián)通的節(jié)點(diǎn)計(jì)算其總的花費(fèi)時(shí)間，適應(yīng)度值越小，表示可行解越優(yōu)，若該可行解上聯(lián)通節(jié)點(diǎn)違反時(shí)間窗約束，則該可行解的適應(yīng)度值設(shè)為無限大。

3.3ILS-CS算法流程

ILS-CS算法求解TSPTW問題的流程[14]如下：

（1）定義適應(yīng)度函數(shù)f(x)，計(jì)算ILS初始路徑的花費(fèi)時(shí)間Tinit；

（2）初始化算法基本參數(shù)，布谷鳥選擇宿主鳥巢數(shù)目n，發(fā)現(xiàn)概率pa和最大迭代次數(shù)Niter；

（3）布谷鳥隨機(jī)選擇鳥巢位置nesti(i＝1，2，…，n)，按照3.1節(jié)的編碼方案編碼；

（4）根據(jù)Levy飛行更新鳥巢位置nesti，計(jì)算鳥巢適應(yīng)度值，保留適應(yīng)度值最小的鳥巢；

（5）更新鳥巢nesti的位置，得到新的鳥巢位置newNest；

（6）對(duì)新鳥巢中的每個(gè)個(gè)體，宿主以一定的概率pa放棄當(dāng)前的鳥巢而新建鳥巢，形成新的種群；

（7）再次計(jì)算每個(gè)鳥巢的適應(yīng)度f(x)，保留適應(yīng)度值小于Tinit的可行解；

（8）當(dāng)達(dá)到最大迭代次數(shù)則輸出最優(yōu)解，否則轉(zhuǎn)（4）進(jìn)行下一輪搜索。

4　實(shí)驗(yàn)配置及參數(shù)設(shè)定

4.1數(shù)據(jù)來源

本文主要使用兩種數(shù)據(jù)：一種數(shù)據(jù)是來源于百度旅游網(wǎng)桂林市景點(diǎn)的數(shù)據(jù)集合（http：//lvyou.baidu. co m/guilin/jingdian)，簡(jiǎn)稱Guilin數(shù)據(jù)集，其中旅游景點(diǎn)的數(shù)目為162個(gè)，每個(gè)節(jié)點(diǎn)的Ti在30～480之間。其中開放時(shí)間為0～1 440的節(jié)點(diǎn)數(shù)量86個(gè)。另一種是Daminaos[10]數(shù)據(jù)集（http：//dgavalas.ct.aegean.gr/ public/op_instainst/），其中節(jié)點(diǎn)數(shù)為n，分布在100～ 200之間，每個(gè)節(jié)點(diǎn)的參觀時(shí)間Ti在1到120之間，數(shù)據(jù)50%的節(jié)點(diǎn)開放時(shí)間為0～1 440，其余的時(shí)間窗為Oi＝510，Ci＝1 020，和各自包含有50個(gè)測(cè)試樣本，兩種數(shù)據(jù)集均為長(zhǎng)時(shí)間窗。

4.2實(shí)驗(yàn)配置

實(shí)驗(yàn)環(huán)境為一臺(tái)處理器為Intel?CoreTMi5-2400 CPU，主頻為3.1 GHz，內(nèi)存4 GB的臺(tái)式機(jī)。本文實(shí)驗(yàn)所采用的軟件為Visual Studio 2012及Sql Server 2008，迭代局部搜索算法來源于Vansteenwegen等人[9]，布谷鳥搜索算法來源于Yang等人[11]。本實(shí)驗(yàn)內(nèi)容包括兩組實(shí)驗(yàn)分析：

（1）ILS-CS算法優(yōu)化效果分析；

（2）WebGIS上線路展示效果分析。

4.3gap評(píng)價(jià)準(zhǔn)則

ILS-CS算法優(yōu)化的目標(biāo)是在滿足時(shí)間窗約束的條件下找到一條時(shí)間花費(fèi)更短的線路。本文用時(shí)間減少率gap評(píng)價(jià)優(yōu)化的效果，gap的求解方式如式（18）所示：

式（18）中，gap表示時(shí)間減少率；TILS表示ILS算法規(guī)劃出線路花費(fèi)的時(shí)間；TCS表示CS對(duì)ILS的線路優(yōu)化后花費(fèi)的時(shí)間；O1表示旅行開始時(shí)間。gap值越大表示CS算法的優(yōu)化效果越好。

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

5.1ILS-CS算法優(yōu)化效果分析

本文采用時(shí)間減少率gap以及行程的時(shí)間花費(fèi)作為評(píng)價(jià)標(biāo)準(zhǔn)來評(píng)價(jià)基于迭代局部搜索結(jié)合布谷鳥搜索的優(yōu)化算法個(gè)性化旅游路線規(guī)劃的優(yōu)化效果。

表1中前8條和后4條數(shù)據(jù)分別是使用Guilin數(shù)據(jù)集和Daminaos數(shù)據(jù)集規(guī)劃出的旅游線路。表中ItineraryILS表示ILS算法規(guī)劃出的線路；ItineraryCS表示CS算法規(guī)劃出的線路；TILS表示ILS規(guī)劃線路花費(fèi)時(shí)間；TCS表示CS優(yōu)化后花費(fèi)時(shí)間；Cn表示ILS算法規(guī)劃出的線路旅行結(jié)束時(shí)間。從表1中可以看出，針對(duì)不同的旅游結(jié)束時(shí)間規(guī)劃出的旅游線路，優(yōu)化前后的旅游線路點(diǎn)的個(gè)數(shù)不變，旅游線路上點(diǎn)的訪問順序發(fā)生變化，而優(yōu)化后的時(shí)間花費(fèi)TILS則比優(yōu)化前的時(shí)間花費(fèi)TCS有較大的減少，證明了該算法在旅游行程花費(fèi)時(shí)間上優(yōu)化的有效性。

Table 1 Comparison of trip itinerary and spend time表1　優(yōu)化線路及花費(fèi)時(shí)間對(duì)比

Table 2 Comparison of visit time表2　景點(diǎn)訪問時(shí)間對(duì)比

表2為參數(shù)Oi＝540，Ci＝1 080，旅游起點(diǎn)和終點(diǎn)分別為桂林電子科技大學(xué)（東校區(qū)）和桂林火車站所規(guī)劃出的一條旅游線路。其中f表示離開景點(diǎn)的時(shí)間，s表示開始訪問景點(diǎn)時(shí)間。表中name一欄括號(hào)內(nèi)的數(shù)字表示景點(diǎn)的編號(hào)，AILS和ACS分別表示優(yōu)化前后的線路序列。通過表中可以看出，經(jīng)過ILS-CS算法優(yōu)化后，每條旅游線路中景點(diǎn)的訪問時(shí)間以及旅游線路花費(fèi)的總時(shí)間都發(fā)生改變，由式（18）得優(yōu)化后的時(shí)間花費(fèi)比優(yōu)化前的時(shí)間花費(fèi)gap減少率達(dá)到10.3%。

表3為使用Guilin數(shù)據(jù)集和Daminaos數(shù)據(jù)集測(cè)試算法優(yōu)化效果。每個(gè)數(shù)據(jù)集分別測(cè)試100條線路樣本。其中Guilin數(shù)據(jù)集的gap值最小為1.2%，最大為12.6%，方差為0.001 48，說明ILS-CS優(yōu)化算法優(yōu)化的效果比較穩(wěn)定。對(duì)Daminaos數(shù)據(jù)集，gap值最小為0（一種情況該算法旅游時(shí)間上已經(jīng)達(dá)到最優(yōu)；另外一種情況是選擇出來的景點(diǎn)的時(shí)間窗比較短，導(dǎo)致景點(diǎn)旅游順序的改變，違反景點(diǎn)的時(shí)間窗約束，因此無法進(jìn)一步優(yōu)化）。

Table 3 Comparison of optimization gap between two data sets表3　兩種數(shù)據(jù)集的優(yōu)化結(jié)果對(duì)比

Fig.1 Convergence curves for different Cn圖1　不同Cn值的收斂曲線

以下對(duì)ILS-CS算法優(yōu)化的收斂性進(jìn)行分析，圖1為采用ILS算法O1＝540，Cn參數(shù)分別為1 320、1 200、1 080、960，隨機(jī)規(guī)劃出的8條初始線路使用CS算法優(yōu)化的收斂曲線圖，圖中每種顏色代表一條旅游線路。CS參數(shù)為n＝10，pa＝0.25，評(píng)價(jià)次數(shù)為5 000。從圖中可以得出，對(duì)不同的時(shí)間約束Cn規(guī)劃出的線路，ILS-CS優(yōu)化算法能夠快速收斂并得到最優(yōu)的結(jié)果。

Fig.2 Trip itinerary for different gap圖2　不同gap值的旅游線路

5.2WebGIS上線路展示效果分析

通過對(duì)ILS算法規(guī)劃出的旅游線路的研究發(fā)現(xiàn)，線路交叉的現(xiàn)象較多，而經(jīng)過對(duì)行程花費(fèi)時(shí)間T的優(yōu)化，則可以減少線路花費(fèi)的時(shí)間，并有效減少旅游線路交叉現(xiàn)象。圖2為ILS參數(shù)O1＝540，Cn＝1 320時(shí)隨機(jī)選取的一條旅游線路。該條線路的ILS初始花費(fèi)時(shí)間TILS＝1 286.7 min，經(jīng)過優(yōu)化后的時(shí)間為TCS＝1 252.2 min，時(shí)間減少率為3.4%，圖2（a）到圖2（d）是旅游線路gap值為0，1.2%，2.0%，3.4%時(shí)的線路在WebGIS上的展示效果。

從圖2中可以看出，隨著gap值的增大，行程花費(fèi)時(shí)間逐漸降低，WebGIS地圖上展示的旅游線路交叉現(xiàn)象也逐漸減少。分析發(fā)現(xiàn)，ILS算法在選擇旅游景點(diǎn)的時(shí)候僅考慮盡可能地選擇得分高的點(diǎn)，而沒有考慮到當(dāng)前的景點(diǎn)位置，因此在實(shí)際的旅游路線中會(huì)出現(xiàn)線路交叉現(xiàn)象，導(dǎo)致旅游行程時(shí)間的浪費(fèi)，而經(jīng)過ILS-CS優(yōu)化后的線路在滿足時(shí)間約束的同時(shí)并未出現(xiàn)線路交叉的現(xiàn)象，減少了行程花費(fèi)時(shí)間，并且更符合人們的旅游習(xí)慣。

6　結(jié)束語

本文針對(duì)個(gè)性化旅游線路規(guī)劃中存在的時(shí)間花費(fèi)問題，提出了一種基于迭代局部搜索結(jié)合布谷鳥搜索的優(yōu)化算法對(duì)旅游線路的時(shí)間花費(fèi)進(jìn)行優(yōu)化。本文算法通過相關(guān)約束，采用迭代局部搜索算法取得了更符合用戶旅游習(xí)慣的線路，再結(jié)合布谷鳥優(yōu)化算法使得旅游的時(shí)間花費(fèi)減少。本文方法使得旅游線路花費(fèi)時(shí)間較優(yōu)化前有較大的提升，并且規(guī)劃出的旅游線路更符合用戶的旅游習(xí)慣。該研究可以進(jìn)一步延伸到將當(dāng)?shù)氐奶鞖庖约皩?shí)時(shí)交通約束考慮在個(gè)性化旅游線路規(guī)劃中，使其更符合實(shí)際旅游的需要。

References：

[1] Cheverst K, Davies N, Mitchell K, et al. Developing a contextaware electronic tourist guide: some issues and experiences[C]// Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, Hague, Netherlands, 2000: 17-24.

[2] Malaka R. Artificial intelligence goes mobile[C]//Artificial Intelligence in Mobile Systems—AIMS2000, Workshop in Conjunction with ECAI 2000, 2000: 5-7.

[3] Hagen K, Kramer R, Hermkes M, et al. Semantic matching and heuristic search for a dynamic tour guide[C]//Proceedings of the 2005 International Conference on Information and Communication Technologies in Tourism, Innsbruck, Austria, 2005. Vienna: Springer, 2005: 149-159.

[4] Kramer R, Modsching M, Ten Hagen K. A city guide agent creating and adapting individual sightseeing tours based on field trial results[J]. International Journal of Computational Intelligence Research, 2006, 2(2): 191-206.

[5] Vansteenwegen P, Souffriau W, Oudheusden D V. The orienteering problem: a survey[J]. European Journal of Operational Research, 2011, 209(1): 1-10.

[6] Chao I, Golden B L, Wasil E A. The team orienteering problem[J]. European Journal of Operational Research, 1996, 88 (3): 464-474.

[7] Souffriau W, Vansteenwegen P, Vertommen J, et al.Apersonalized tourist trip design algorithm for mobile tourist guides[J]. Applied Artificial Intelligence, 2008, 22(10): 964-985.

[8] Dumas Y, Desrosiers J, Gelinas E, et al. An optimal algorithm for the traveling salesman problem with time windows[J]. Operations Research, 1995, 43(2): 367-371.

[9] Vansteenwegen P, Souffriau W, Berghe G V, et al. Iterated local search for the team orienteering problem with time windows[J]. Computers & Operations Research, 2009, 36 (12): 3281-3290.

[10] Gavalas D, Konstantopoulos C, Mastakas K, et al. Clusterbased heuristics for the team orienteering problem with time windows[M]//Experimental Algorithms. Berlin, Heidelberg: Springer, 2013: 390-401.

[11] Yang Xinshe, Deb S. Cuckoo search via Lévy flights[C]// Proceedings of the 2009 World Congress on Nature & Biologically Inspired Computing. Piscataway, USA: IEEE, 2009: 210-214.

[12] Wei Xiangyuan,Yang Huihua, Xie Pumo. Research and implementation of parallel cuckoo search based on CUDA[J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(6): 665-673.

[13] Durgun ?, Yildiz AR. Structural design optimization of vehicle components using cuckoo search algorithm[J]. Materials Testing, 2012, 54(3): 185-188.

[14] Yang Xinshe, Deb S. Engineering optimisation by cuckoo search[J]. International Journal of Mathematical Modelling and Numerical Optimisation, 2010, 1(4): 330-343.

附中文參考文獻(xiàn)：

[12]韋向遠(yuǎn),楊輝華,謝譜模.基于CUDA的并行布谷鳥搜索算法設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué)與探索, 2014, 8(6): 665-673.

HOU Le was born in 1988. He is an M.S. candidate at School of Electronic Engineering and Automation, Guilin University of Electronic Technology. His research interests include pattern recognition and machine learning, etc.

侯樂（1988—），男，河南南陽人，桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別，機(jī)器學(xué)習(xí)等。

YANG Huihua was born in 1972. He received the Ph.D. degree from East China University of Science and Technology in 2005. Now he is a professor and Ph.D. supervisor at Beijing University of Posts and Telecommunications, and an adjunct professor at Guilin University of Electronic Technology. His research interests include intelligent information processing and machine learning, etc.

楊輝華（1972—），男，湖南常德人，2005年于華東理工大學(xué)獲得博士學(xué)位，現(xiàn)為北京郵電大學(xué)自動(dòng)化學(xué)院教授、博士生導(dǎo)師，桂林電子科技大學(xué)兼職教授，主要研究領(lǐng)域?yàn)橹悄苄畔⑻幚?，機(jī)器學(xué)習(xí)等。在國內(nèi)外期刊及學(xué)術(shù)會(huì)議上發(fā)表科技論文30余篇，其中被SCI檢索13篇，EI檢索20篇，主持和參與多項(xiàng)國家自然科學(xué)基金、廣西自然科學(xué)基金、廣西高校優(yōu)秀人才資助計(jì)劃等項(xiàng)目。

FAN Yongxian was born in 1977. He received the Ph.D. degree from Shanghai Jiao Tong University in 2013. Now he is a lecturer at Guilin University of Electronic Technology. His research interests include pattern recognition and machine learning, etc.

樊永顯（1977—），男，河南平頂山人，2013年于上海交通大學(xué)獲得博士學(xué)位，現(xiàn)為桂林電子科技大學(xué)教師，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別，機(jī)器學(xué)習(xí)等。發(fā)表學(xué)術(shù)論文10余篇，主持和參與多項(xiàng)國家自然科學(xué)基金項(xiàng)目。

LI Lingqiao was born in 1986. He is a Ph.D. candidate at School of Automation, Beijing University of Posts and Telecommunications. His research interests include intelligent information processing and machine learning, etc.

李靈巧（1986—），男，四川達(dá)縣人，北京郵電大學(xué)自動(dòng)化學(xué)院博士研究生，桂林電子科技大學(xué)助理研究員，主要研究領(lǐng)域?yàn)橹悄苄畔⑻幚?，機(jī)器學(xué)習(xí)等。

JIANG Shujie was born in 1989. She is an M.S. candidate at School of Electronic Engineering and Automation, Guilin University of Electronic Technology. Her research interests include pattern recognition and image processing, etc.蔣淑潔（1989—），女，湖北武漢人，桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別，圖像處理等。在國內(nèi)外期刊及學(xué)術(shù)會(huì)議上發(fā)表科技論文5篇，其中被SCI檢索3篇，EI檢索2篇。

Research on Personalized Trip Itinerary Based on ILS-CS Optimization*

HOU Le1, YANG Huihua1,2+, FAN Yongxian3, LI Lingqiao1,2, JIANG Shujie1
1. School of Electronic Engineering and Automation, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
2. School of Automation, Beijing University of Posts and Telecommunications, Beijing 100876, China
3. SchoolofComputerScienceandEngineering,GuilinUniversityofElectronicTechnology,Guilin,Guangxi541004,China
+ Corresponding author: E-mail: yhh@bupt.edu.cn

HOU Le, YANG Huihua, FAN Yongxian, et al. Research on personalized trip itinerary based on ILS-CS optimization. Journal of Frontiers of Computer Science and Technology, 2016, 10(1)：142-150.

Abstract:For the long travel time on trip itinerary planned by iterated local search (ILS), this paper proposes an optimization algorithm based on iterated local search with cuckoo search optimization to reduce the travel time. Firstly, this algorithm adopts ILS algorithm for solving an initial trip itinerary and several tourist attractions with some relevant objectives and constraints. Then, under the circumstance of no changing the time windows and the number of tourist attractions, this paper utilizes CS algorithm to minimize the travel time. The tourist route is obtained by above methods in this paper. It is more conform to travel habits and less travel time than existed ones. The experimental results on Daminaos and Guilin city data sets show that the average travel time of the proposed method reduces bybook=143,ebook=1478%, compared with only using ILS algorithm in itinerary optimization, and planning the itinerary for personalized tourists is more in line with user's choice.

Key words:trip itinerary planning; iterated local search; cuckoo search; orienteering problem with time windows; travel salesman problem with time windows

文獻(xiàn)標(biāo)志碼：A

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

doi:10.3778/j.issn.1673-9418.1503030