English  |  正體中文  |  简体中文  |  全文笔数/总笔数 : 58237/91808 (63%)
造访人次 : 13783986      在线人数 : 42
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
搜寻范围 查询小技巧:
  • 您可在西文检索词汇前后加上"双引号",以获取较精准的检索结果
  • 若欲以作者姓名搜寻,建议至进阶搜寻限定作者字段,可获得较完整数据
  • 进阶搜寻


    jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/34192


    题名: 基於旅行推銷員演算法之旅遊行程規劃系統 : 以台灣地圖為例
    其它题名: A tour planning system based on solving the traveling salesman problem using the Taiwan map
    基於旅行推銷員演算法之旅遊行程規劃系統 : 以臺灣地圖為例
    作者: 陳囿成;Chen, Yu-cheng
    贡献者: 淡江大學資訊管理學系碩士班
    魏世杰;Wei, Shih-chieh
    关键词: 旅行推銷員問題;最短路徑演算法;旅遊規劃系統;Traveling Salesman Problem;Shortest Path Algorithm;Tour Planning System
    日期: 2007
    上传时间: 2010-01-11 05:01:01 (UTC+8)
    摘要: 本論文提出一套基於旅行推銷員演算法之旅遊規劃系統,此系統能針對自助旅行者給定之旅遊時間、興趣類別、以及景點範圍,推薦出符合使用者條件的旅遊行程。本研究包含三部份,第一部分是旅行推銷員問題TSP(Traveling Salesman Problem)近似法篩選,本文取基因演算法、螞蟻演算法、模擬退火,以標準案例實驗查看各演算法效果,取時間短也比較接近正確解者。第二部份是最短路徑找尋法的篩選,在Web Services環境下測試Dijkstra、直線距離A*、有向地標A*、無向地標A*共四種演算法的速度,挑選速度快而且沒有誤差的方法。第三部份是挑選景點方面,分為縣市模式及中心點模式,滿足使用者不同需求;安排住宿方面,能為每一天安排符合住宿等級而距離最近的旅館。本旅遊系統的設計與實作,最後選出有向地標A*來計算景點間的最短距離,另外使用模擬退火演算法來安排景點的探訪順序,使其總移動距離接近最短。根據實驗結果證明,此種近似解的探訪順序誤差在可容忍範圍內,方便使用者作自助旅遊之安排。
    A tour planning system based on solving the traveling salesman problem is proposed. Given the per-day traveling times, categories of interest, and the range of scenic spots, the system can recommend a suitable tour plan for the user. The research divides into 3 parts. The first part is the evaluation of three approximation algorithms for solving the traveling salesman problem which include the genetic, the ant colony optimization and the simulated annealing algorithms. Selected cases from a standard test set are tested to find an algorithm which returns a result close to the optimal answer and less time-consuming. The second part is the evaluation of four shortest path web services which include the Dijkastra, the Euclidean A*, the directional landmark-based A*, and the undirectional landmark-based A* algorithms. A randomly generated test set is tested to find a web service which returns a result fast with least error. The third part is the tour planning itself which includes selection of scenic spots and hotels. To pick scenic spots for visit, our system provides a district mode and a range mode to satisfy different user needs. To pick hotels, our system tries to arrange a hotel both close in distance to the itinerary and in rank to the given grades of hotels. As result, the directional landmark-based A* web service is selected to calculate the shortest distance between two scenic spots. Also the simulated annealing algorithm is selected to arrange the visit order such that the total moving distance in order is approximate to the shortest one. According to the experiment result, the approximation error is tolerable. Thus the proposed tour planning system is suitable for independent travelers who want to arrange self-guided tours spanning several days on their own.
    显示于类别:[資訊管理學系暨研究所] 學位論文

    文件中的档案:

    档案 大小格式浏览次数
    0KbUnknown741检视/开启

    在機構典藏中所有的数据项都受到原著作权保护.

    TAIR相关文章

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - 回馈