基因演算法應用於具時窗限制之多天旅遊行程規劃

Using Genetic Algorithm to solve Multi-days Tour Scheduling Problem with Time Windows

王裕廷(Yu-Ting Wang)

指導教授 ： 周信宏

長榮大學/資訊暨工程學院/資訊管理研究所/碩士(2010年)

https://doi.org/10.6833/CJCU.2010.00015

摘要

近年來，有許多的個人旅遊助理(Personal Travel Assistant)系統陸續地被推出，其系統功能中包含有自動導航功能、提供景點相關資訊服務和規劃旅遊行程等功能。本論文以景點的時窗限制(Time Windows)結合最小距離成本的旅行銷售員問題(Traveling Salesman Problem, TSP)的多天旅遊行程規劃問題為研究核心。然而，旅行者在規劃旅遊行程時，隨著問題規模變大，無法以一多項式函數時間內求得最佳解。在本論文中，我們考量每一個景點的預期停留、開放和關閉時間以及每一天的旅遊時間限制，並以最小距離成本來安排旅遊行程路徑。因此，本論文應用基因演算法(Genetic Algorithm, GA)在合理的時間內求解出多天旅遊行程路徑。

關鍵字

時窗限制 ； 旅行銷售員問題 ； 多天旅遊行程問題 ； 基因演算法 ； 分支界定法

並列摘要

In this thesis, we study the tour scheduling problem, and present a new tour scheduling method to minimize the total cost of the traveling salesman problem with destination time windows. A tour scheduling problem is very complicated that needs to consider many factors such as spatial, temporal, resource, cost, preference, amenity, and the number of nearby sightseeing spots. Finding an efficient schedule for the tour across multiple days is harder than the single day tour since in the multi-days tour problem the number of possible tours to visit all destinations becomes huge, and accommodation places have to be carefully chosen by considering the schedules before and after each stay. In order to obtain the optimal or near optimal solution with minimum total cost, we have designed and implemented a genetic algorithm to solve this multi-days tour scheduling problem in a reasonably practical time.

並列關鍵字

Tour Scheduling Problem ； Traveling Salesman Problem ； Time Windows ； Multi-days Tour Scheduling Problem ； Genetic Algorithm

參考文獻

[9] 張偉振(2009)，「應用群蟻演算法於旅遊路線規劃研究」，朝陽科技大學建築及都市設計研究所碩士論文。

[4] 連英惠(2002)，「智慧型旅遊路線排成系統」，靜宜大學資訊管理學研究所碩士論文。

[6] 陳囿成(2008)，「基於旅行推銷員演算法之旅遊行程規劃系統—以台灣地圖為例」，淡江大學資訊管理學研究所碩士論文。

[2] 李世炳、鄒忠毅(2002)，「簡介導引模擬退火法及其應用」，物理雙月刊，第二十四卷，第二期，P307-319。

[13] E. Goldberg(1989), “Genetic Algorithm in search, Optimization and Machine Learning,” Addison Weslery..