應用蟻群演算法於旅程規劃之研究

A Study of Trip Planning Using an Ant Algorithm

林信宏(Shin-Hong Lin)

指導教授 ： 江季翰

國立虎尾科技大學/電機資訊學院/資訊工程研究所/碩士(2013年)

摘要

尋找旅遊資訊以及旅程規劃是一件繁瑣的事情，雖然許多旅遊網站及各地的政府機構都提供相當充足的景點資訊，提供旅遊行程的商家也不在少數，但大部分的旅程都是固定的，並不能符合每位遊客需求，即使使用導航系統規劃旅程，也只能隨著遊客先後輸入的景點順序，去做最短路徑的導航，並沒有考慮其他因素，如：景點的開放時間、旅遊時間以及景點喜愛分數等等。因此有學者對此進行研究，考慮景點特性及遊客需求，並在短時間內計算出最符合需求的遊玩路線，儘管如此還是有不足的地方，如沒有考慮實際的車程時間，或者挑選景點過多時該如何進行篩選，以及如何運用每次計算的結果，讓旅遊行程規劃更佳多元化。

本論文實作出一套結合電子地圖的旅遊網站系統，使用蟻群演算法(Ant algorithm)規劃旅程問題，並考慮實際車程、旅遊時間、景點喜愛分數、景點營業時間等因素，客製化每位遊客的行程，當選擇景點過多，超出旅遊時間時，則以挑選旅程分數最高的組合當作這次的結果;除此之外，我們將每位旅行者比喻成一隻螞蟻，每次的旅程就好比螞蟻走過所遺留下的費洛蒙(Pheromone)，藉由收集這些費洛蒙，我們可以得知景點的流動性，分析出螞蟻最有可能前往的下個景點、以及最熱門的景點等等，這些資訊除了用於推薦給遊客觀看外，還可以提供螞蟻演算法運算所使用，使結果更接近遊客所需，徹底達到螞蟻費洛蒙的特性。經驗證測試，此方法可以在短時間內根據遊客需求客製化旅程，在實驗的最後還經過多次的情境模擬測試，證實本研究可應用於實際的旅程規劃上。

關鍵字

蟻群演算法 ； 偏好評估 ； 旅程規劃 ； 推薦系統

並列摘要

People have taken traveling as an important situation in the life recently. Collecting tourist information is an extremely complicated thing. Nowadays, there is a lot of abundant information about traveling on the tourist websites which are not only provided by the travel agencies, but also the governments. Even though, those useful websites can truly help us gain a lot of traveling information, they are too unchangeable to be suitable to meet everyone’s need. If you use the Navigation System while you traveling in some places, the Navigation System can’t meet you what you need. Because the Navigation System just can search the shortest way for traveling in some areas without considering any factors, such as the opening hours of the scenic spots, the recommendation from other tourists or the time limited touring in some landscapes, etc.

In this paper, we implement a travel system combined with electronic map, use Ant algorithm to develop tourist-oriented itineraries that considered the traveling time, score of scenic spots and opening hours. And then we select a schedule of travel that conforms combination of the score of total scenic spots is highest. In addition, we can obtain some information about route of scenic spots, the popular scenic spots by collecting tourist itineraries, that not only can offers to tourists, but also apply to Ant Colony algorithm calculate and make results closer to the personal travel needs. In this case, people can find the way they really want to travel.

並列關鍵字

Ant Algorithm ； Preference Estimation ； Trip Planning ； Recommender System

參考文獻

[5] Yin-Fu Huang and Chao-Nan Chen, “Implementation for the arrangement and mining analysis of traveling schedules,” Journal of Information Science and Engineering, Vol. 22, No. 1, pp. 123-146, 2006.

[2] L.M. Gambardella and M. Dorigo, “Solving symmetric and asymmetric TSPs by ant colonies,” in Proc. 1996 IEEE International Conference on Evolutionary Computation (ICEC’96), pp. 622–627, May. 1996.

[3] M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-56, Apr. 1997.

[4] M. Dorigo and L. M. Gambardella, “Ant colonies for the traveling salesman problem,” BioSystems, Vol. 43, No. 2, pp. 73–81, July 1997.

[8] Chen-Shu Wang, Chia-Chuan Yeh and Chun-Yi Li, “Intelligence traveling schedule recommender based on commonsense reasoning algorithm,” 2010 International Conference on Computer and Communication Engineering (ICCCE), pp. 1-6, May. 2010.