摘 要 長 榮 大 學 資 訊 管 理 學 系 畢 業 專 案 實 作 專 案 編 號 : 旅 遊 行 程 規 劃 - 以 台 南 市 為 例 Tour Scheduling for Tainan City CJU-IM- PRJ-096-029 執 行 期 間 : 95 年 2 月 13 日 至 96 年 1 月 20 日 陳 貽 隆 陳 繼 列 張 順 憶 練 哲 瑋 專 案 參 與 人 員 : 張 政 偉 古 敏 蓉 何 采 宸 曾 婉 柔 指 導 老 師 : 周 信 宏 助 理 教 授 在 一 般 的 旅 遊 網 站 中, 只 提 供 靜 態 的 景 點 資 訊 和 套 裝 行 程 規 劃 然 而 這 對 於 一 個 旅 行 者 要 自 行 規 劃 行 程 是 不 夠 的 旅 行 者 往 往 還 需 要 與 旅 遊 公 司 的 專 員 進 行 面 對 面 的 諮 商 和 規 劃, 才 能 得 到 一 個 符 合 金 錢 和 時 間 限 制 的 客 制 化 行 程 在 本 專 案 中, 我 們 開 發 了 一 套 以 台 南 市 為 例 的 旅 遊 行 程 規 劃 系 統 本 系 統 中 除 了 提 供 一 般 的 靜 態 資 訊 外, 另 外 還 提 供 了 一 般 旅 遊 網 站 所 沒 有 的 動 態 行 程 規 劃 功 能 使 用 者 可 以 方 便 的 在 地 圖 上 點 選 欲 拜 訪 的 景 點, 我 們 的 系 統 就 可 以 幫 使 用 者 排 出 最 佳 或 近 似 路 線 讓 使 用 者 能 事 先 評 估 規 劃 行 程 的 可 行 性 關 鍵 詞 : 行 程 規 劃 台 南 市 旅 行 推 銷 員 問 題 Abstract In the general traveling websites, only static scenic spot information and tourist packages are provides. However it is not enough for a traveler to schedule a tourist by himself. The traveler usually also needs counsel with the traveling company s specialist face-to-face to design a tourist satisfied the cost and time restrictions. In this project, we have developed a tour scheduling system for Tainan city as an example. In addition to provide the general static information, our system has also provided the dynamic scheduling functions which are not provided in the general traveling websites. User can conveniently select some scenic spots that he wants to visit from the map, and then our system can compute the optimum or approximation tourist. It would help the user to evaluate the feasibility of the tourist in advance. Keywords: tour scheduling, Tainan city, traveling salesman problem. 一 緣 由 與 目 的 由 於 網 路 的 普 及 與 發 達, 越 來 越 多 的 消 費 者 會 在 網 路 上 查 看 旅 遊 的 相 關 資 訊 因 此 旅 遊 業 者 也 開 始 迎 著 這 股 潮 流, 挖 空 心 思 架 設 擁 有 自 己 特 色 的 網 站 目 前 旅 遊 網 站 最 多 只 提 供 靜 態 的 資 料 查 詢 連 結 還 有 固 定 的 套 裝 行 程, 卻 始 終 缺 乏 動 態 的 行 程 規 劃 功 能 然 而, 這 些 套 裝 行 程 並 不 能 滿 足 大 部 分 旅 客 的 需 求, 除 非 花 一 筆 錢 找 旅 行 公 司, 幫 忙 事 先 規 劃 安 排 但 這 也 只 侷 限 在 國 外 線 和 國 內 熱 門 景 點 因 此, 引 發 我 們 想 要 開 發 旅 遊 行 程 安 排 的 代 理 人 構 想 本 專 案 計 畫 重 點 在 於 開 發 動 態 的 行 程 規 劃, 讓 使 用 者 勾 選 旅 途 中 較 喜 愛 的 景 點 小 吃 等, 在 勾 選 時 就 可 以 從 地 圖 對 照 景 點 位 置, 也 可 以 在 地 圖 上 看 到 相 關 景 1
點 小 吃 的 簡 介, 選 擇 景 點 後 本 系 統 會 將 提 供 一 個 最 佳 或 近 似 路 線 的 行 程, 給 使 用 者 參 考 目 前 大 多 數 的 旅 遊 網 站 在 資 料 方 面 都 做 的 十 分 詳 細 內 容 也 十 分 豐 富, 但 這 些 大 量 的 資 料, 卻 得 讓 使 用 者 花 上 許 多 時 間 去 消 化 內 透 過 動 態 性 行 程 規 劃 將 大 大 省 去 您 上 網 找 資 料 安 排 行 程 的 瑣 碎 時 間 由 於 系 統 為 開 發 之 初, 所 以 我 們 先 以 單 一 都 市 地 圖 作 為 行 程 規 劃 的 範 圍, 因 此, 就 地 緣 的 關 係, 以 及 挾 著 小 吃 之 都 古 蹟 府 城 的 美 名, 我 們 選 擇 以 台 南 市 為 我 們 首 要 開 發 的 對 象 二 相 關 技 術 探 討 ( 一 )ETSP 旅 行 推 銷 員 問 題 (Traveling salesman problem, TSP) 最 早 為 美 國 軍 方 建 立 全 國 通 訊 路 線 所 延 伸 出 來 的 問 題,TSP 問 題 目 前 已 被 證 實 為 NP-Complete 的 問 題 [1,11,12] TSP 問 題 定 義 : 一 旅 行 推 銷 員 到 N 個 城 市 做 生 意, 試 找 出 一 條 從 某 城 市 出 發 並 連 貫 所 有 城 市, 最 後 回 到 原 城 市, 且 城 市 至 每 城 市 間, 只 能 去 一 次 之 最 短 旅 行 拜 訪 路 徑, 稱 之 [2] 若 所 有 的 城 市 同 時 也 需 要 滿 足 三 角 不 等 式, 則 此 問 題 即 變 成 TSP 著 名 的 特 例 - Euclidean TSP 在 圖 1 中,(a) 圖 表 是 各 點 之 間 的 連 通 狀 態,(b) 及 (c) 圖 為 銷 售 員 可 能 走 的 路 徑 若 (b) 圖 中 的 路 徑 為 所 有 可 能 路 徑 中 總 長 度 最 小 的 一 條, 則 其 為 ETSP 所 得 到 的 解 能 的 路 徑 ( 二 ) 解 ETSP 問 題 的 1.5 倍 近 似 解 演 算 法 解 ETSP 問 題 的 1.5-approximation algorithm 能 在 polynomial 的 時 間 內 求 得 近 似 解, 並 保 證 該 解 會 在 最 佳 解 的 1.5 倍 之 內 目 前 所 知 解 ETSP 問 題 的 c-approximation algorithm 中, 以 此 近 似 演 算 法 所 找 得 的 解 最 接 近 最 佳 解 圖 可 1 ETSP Algorithm 1 1.5 倍 近 似 解 演 算 法 :[3,13] Input: 地 圖 上 的 一 組 點 Output: 最 佳 路 徑 Step1 : 找 一 個 MST T Step2: 對 T 上 degree 為 奇 數 的 點 找 一 個 minimum Euclidean weighted matching M G = M T Step3: 找 出 G 上 的 尤 拉 迴 路, 然 後 將 重 複 的 點 繞 過 以 找 出 它 的 Hamiltonain 迴 路 由 圖 2 至 圖 6 可 以 說 明 用 以 解 ETSP 問 題 的 1.5-approximation algorithm 的 運 作 方 式 在 圖 2 中, 共 有 五 個 點 且 分 別 標 示 從 1 到 5 的 號 碼 帶 有 箭 頭 的 線 代 表 所 走 過 的 路 徑 在 圖 6 中, 我 們 可 以 很 清 楚 看 到 銷 售 員 所 走 的 路 徑 為 1 2 3 5 4 1 在 圖 2 中 有 五 個 點, 銷 售 員 欲 使 用 1.5-approximation algorithm 找 出 一 條 近 似 路 徑 及 其 總 長 度 在 圖 3 中 表 示 使 用 Kruskal MST algorithm 所 求 得 的 minimum spanning tree 在 圖 4 中, 虛 線 所 連 結 的 點 表 示 採 用 minimum weighted matching 後 所 得 到 的 結 果 在 圖 5 中 表 示 我 們 選 擇 走 1 2 3 5 4 5 1 這 條 路 徑, 當 然 了, 你 也 可 以 選 擇 走 另 一 條 路 徑 : 2
1 5 4 5 3 2 1 在 圖 6 中, 將 重 複 經 過 的 點 5 跳 過, 便 可 得 到 一 條 Hamiltonian cycle, 此 即 為 所 得 近 似 路 徑 在 此 例 中, 我 們 將 點 5 跳 過 會 使 原 來 的 路 徑 片 段 4 5 1 變 成 4 1 圖 4 虛 線 連 結 的 點 的 結 果 weighted matching 為 minimum 圖 中 找 出 銷 一 售 條 員 近 欲 似 使 的 路 徑 及 在 總 這 長 五 度 點 2 用 倍 1.5 圖 5 走 這 1 2 3 5 4 5 1 條 路 徑 圖 得 節 點 3 使 用 Kruskal 的 所 求 MST algorithm minimum spanning tree, 其 中 的 點 為 1 根 圖 徑, 該 路 將 徑 重 的 複 總 經 長 過 度 的 即 點 為 所 繞 求 過 近 後 似 所 長 得 度 到 的 近 似 路 6 5 三 系 統 規 格 軟 體 程 式 語 言 網 頁 編 輯 C++ ActiveScript Javascript DreamWeaver8 PhotoImpact 11 Microsoft Windows 作 業 平 台 XP 開 發 工 具 Macromedia Flash 8 資 料 庫 My SQL 3
比較短 所以點多的時後 系統會把資料 傳到 1.5 倍 TSP 而暴力法因為算出路徑較 短也較費時 所以我們使用在點少時 排 程完後輸出在地圖上 顯示出完整的路 線 完成我們的行程規劃 四 實作方法 本組的網站架設以HTML語法做為基 底搭配PHP MY SQL去架設網頁用到的資 料庫(如 新聞公告等) 可讓一些網頁所 二 Flash 的作法[8,9] 需的資料 利用資料庫做呈現 新增 修 改 刪除也較不容易動到網頁的呈現 在 Flash 的功用 除了繪圖 製作動畫之 搭配FLASH和Photo Impact去做圖片美工 用者喜歡網站整體的感覺 而FLASH將地 外 也可以延伸其他的作用 讓它多了其 他不同的用途 所以本組的地圖部份 是 使用 FLASH 繪製 並利用圖層間的關係 各別擺上不同的物件 再配 ActionScript 圖的繪製 使得地圖呈現更加不同 是讓 的語法 製作出生動且人性化的地圖 和繪製地圖 Photo Impact可以使網頁更加 生動活潑 使的網頁不會那麼單調 讓使 使用者以互動的方式去呈現 較能達到人 五 成果展示 機互動的效果 整體網頁以DreamWeaver 8 做為架站的開發工具 [4,5,6,7,10] 成果展示分成網站呈現和地圖導覽兩部份 一 系統流程 網頁功能介紹 : 首先是整個網站的首頁 有新聞公告和熱 門排行 圖 7 行程規劃流程圖 由圖 7 看到使用者在地圖上加選想要 的點按下下一步時 我們的系統會依照點 的多寡來選擇使用 1.5 倍 TSP 或是暴力 法 1.5 倍 TSP 算出的路徑比較遠但是時間 4
這 頁 呈 現 台 南 美 食 的 詳 細 資 料 此 頁 介 紹 台 南 府 城 的 相 關 歷 史 第 三 步 : 滑 鼠 按 下 地 圖 上 景 點, 查 看 景 點 相 關 介 紹 地 圖 導 覽 介 紹 : 第 一 步 : 利 用 上 下 左 右 方 向 鈕 切 換 地 圖 顯 示 區 域 第 四 步 : 按 下 小 吃 景 點, 或 古 蹟 景 點, 選 擇 顯 示 或 隱 藏 相 關 景 點 圖 示 第 二 步 : 滑 鼠 觸 碰 地 圖 上 景 點, 查 看 景 點 名 稱 第 五 步 : 滑 鼠 按 下 左 方 介 紹 中 ADD 按 鈕, 景 點 加 入 清 單 5
第 六 步 : 滑 鼠 按 下 左 方 介 紹 中 DEL 按 鈕, 刪 除 清 單 中 景 點 六 結 論 與 未 來 展 望 第 七 步 : 按 下 右 邊 清 單 欄 中 清 單 確 認 按 鈕, 開 始 行 程 排 程 目 前 我 們 的 專 案 著 重 在 台 南 市 觀 光 旅 遊 的 行 程 規 劃 上, 日 後 希 望 可 以 放 大 到 全 台 灣 各 省 不 單 單 只 是 侷 限 在 單 一 地 區, 在 行 程 規 劃 上 我 們 使 用 暴 力 法 和 1.5 的 TSP 用 來 產 生 最 短 的 路 徑, 如 果 10 個 點 以 下 就 直 接 跑 暴 力 法, 但 是 超 過 10 點 以 上 就 換 成 跑 1.5 倍 TSP 的 程 式, 雖 然 比 較 複 雜 但 是 卻 比 較 能 產 生 出 符 合 實 際 的 規 劃 路 線 讓 使 用 者 更 加 便 利 隨 著 科 技 的 進 步 不 可 能 會 有 系 統 是 十 分 完 善 的, 所 以 隨 著 時 代 的 腳 步 我 們 也 要 再 讓 系 統 加 進 新 的 元 素 好 隨 時 跟 上 科 技 的 潮 流, 例 如 現 在 的 手 機 科 技 日 新 月 異 現 在 能 上 網 可 以 說 沒 什 麼 了 不 起 了 但 是 如 果 可 以 讓 我 們 的 系 統 跟 手 機 來 結 合, 能 讓 使 用 者 更 加 能 便 利 達 到 即 時 性 也 能 提 升 手 機 的 功 能 性, 另 一 方 面 也 可 以 跟 衛 星 導 航 來 結 合, 幫 你 規 劃 完 路 線 立 即 可 以 用 衛 星 定 位 馬 上 跟 你 說 你 現 在 的 位 置 你 要 往 哪 裡 走, 因 為 有 許 多 的 景 點 小 吃 如 果 不 是 當 地 人 可 能 不 會 知 道, 這 些 都 是 可 以 更 人 性 化 的 發 展, 如 果 可 以 做 到 這 些 我 想 一 定 可 以 讓 許 多 使 用 者 在 旅 遊 時 更 加 方 便 省 時 又 可 以 玩 的 愉 快 第 八 步 : 最 近 路 徑 結 果 顯 示 七 參 考 文 獻 6
[1] 楊 鄰 第 近 二 秉 搜 十 蒼 索 九 演 卷 呂 算, 淑 法 第 鈴 解 二, 期 TSP,2000, 以 問 自 題 我, 學 第 習 運 神 281~294 輸 經 計 網 畫 路 季 頁 混 刊 合, [5] [4] 德 問 瑞 工 文 作 魁 室 資 訊, 快 速 旗 解 標 決 股 份 網 有 頁 限 設 公 司 [6] 書, 旗 標 股 份 有 限 公 司 魔 法 [7] 施 威 銘 研 究 室 編 著 達 人 [8] 文 鄧 的 淵 文 階 工 淵 梯 作, 室, 編 旗 著 標 快 股 城 快 份 數 樂 有 位 樂 限 科 學 公 技 Flash 司 股 份 有 網 限 頁 公 製 司 作,, DREAMWEAVER8, DREAMWEAVER8 [10] [9] 田 典 碁 中 峰 康 資 協 訊 股 份 有 限 公 司 資 陳, 訊 思 股 聰 博 份 編 碩 有 著 文 限 化 公 股 份 有 限 公 司 11, 範 例 活 基 用 辭 峰, DREAMWEAVER 司 8, ACTIONSCRIPT, PHOTOIMPACT [13] 崗 電 腦 圖 書 資 料 股 份 有 限 公 R. [2] [3] 計 Pablo Moscato, TSPBIB Home Page, http://www. densis.fee.unicamp.br/~moscato/tspbib_home.ht ml Introduction to the design and analysis of algorithms,r.c.t.lee 300 MX 2004 FOR PHP, 知 [11] [12] Garey, M. R. and Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco 1979. Sanjeev Arora, 松 Polynomial time approximation 司 schemes for Euclidean traveling salesman and other geometric problems, Proceedings of the 37 th Annual Symposium on Foundations of Computer Science (FOCS),1996. C. T. Lee, R. C. Chang, S. S. Tseng, and Y. T. Tsai, Introduction to the Design and Analysis of Algorithms,, pp 297 308, 314 320 and 471 476, 1999... 7
長 榮 大 學 資 訊 管 理 學 系 畢 業 專 案 實 作 成 果 報 告 旅 遊 行 程 規 劃 - 以 台 南 市 為 例 專 案 編 號 : CJU-IM-PRJ-96-029 執 行 期 間 : 95 年 2 月 13 日 至 96 年 1 月 20 日 專 案 成 員 : 陳 貽 隆 陳 繼 列 張 順 憶 練 哲 瑋 張 政 偉 古 敏 蓉 何 采 宸 曾 婉 柔 指 導 老 師 : 周 信 宏 助 理 教 授 中 華 民 國 95 年 11 月 17 日 8