人工智慧演算法於博物館路徑問題的應用

Applications of Artificial Intelligence Algorithms for Museum Routing Problems

陳佳順(Jia-Shun Chen)

指導教授 ： 謝益智

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2014年)

https://doi.org/10.6827/NFU.2014.00061

摘要

參觀博物館為國內常見的課外活動與校外學習，亦是國外旅遊團來台參訪的重要行程之一。對於有事先預約的團體，博物館通常會安排領隊帶領團體參觀展覽品並講解展覽品的由來，參觀路徑是根據參觀團體的參觀時間來安排，以避免路線雍塞或排隊而造成時間的浪費。

本研究探討博物館路徑問題，此問題需同時規劃多個團體參觀展覽室的路徑，其中各團體有必須觀看的展覽室和選擇觀看的展覽室，問題目標為最小化完成參觀時間。本研究探討博物館路徑問題為NP-hard問題，我們嘗試以基因演算法(Genetic Algorithm)、免疫演算法(Immune Algorithm)、粒子群演算法(Particle Swarm Optimization，PSO)三種演算法對此博物館路徑問題進行求解。本研究針對團體數量大於展覽室數量的情況下，對於不同的參觀率組合條件，分別求解團體參觀展覽室的最小完成時間。除此之外，我們亦將三種演算法做比較，實驗數值結果顯示，基因演算法與免疫演算法的差異性不大，均優於粒子群演算法，且皆能有效地解決此問題。

關鍵字

博物館路徑問題 ； 開放式排程問題 ； 基因演算法 ； 免疫演算法 ； 粒子群演算法

並列摘要

Museum visit is a common domestic extracurricular and fieldtrip learning activity; and it is also one of the important stops for foreign tour groups to visit Taiwan. For groups that make an appointment in advance, the museum usually arranges tour guides to show visitors around exhibits or explain the origin of the exhibits. The visit route is usually arranged depending on the groups’ time of visit, so as to avoid congestion or queuing that wastes time.
This thesis explored the museum routing problem. This problem involves planning of routes for a number of groups that visit several exhibition rooms at the same time. In particular, there are must-visit exhibition rooms and select-exhibition rooms for operational viewing. The goal of this museum routing problem is to minimize the visit times (makespans) of groups. This study investigated the museum routing problem, which is an NP-hard problem. In this thesis, we attempt to solve the museum routing problem by three algorithms, namely, genetic algorithm, immune algorithm, and particle swarm optimization. Targeting the situation where the number of groups is higher than the number of exhibition rooms available, the test problems of combinations of various visit rates were solved with the objective of minimizing visit times (makespans) of groups. In addition, numerical results of three algorithms were provided and compared. The experimental results show that genetic algorithm and immune algorithm showed no significant differences and they are both better than swarm optimization method. Furthermore, as shown, the test problems were all effectively resolved.

並列關鍵字

Museum Routing Problem ； Open Shop Scheduling Problems ； Genetic Algorithm ； Immune Algorithm ； Particle Swarm Optimization

參考文獻

8.洪士程、楊逢羿(2010)，「序的最佳化於隨機工程生產排程問題之應用」，資訊科技國際期刊；4卷，2期，頁22-34。

12.黃柏輔(2010)，利用多重軌跡搜尋演算法解決開放式工廠排程問題，中興大學資訊網路多媒體研究所，碩士論文。

7.林豐澤(2005)，「演化式計算下篇：基因演算法以及三種應用實例」，東北大學資訊科學與工程學院系統工程學報，3卷，2期，頁29-56。

1.吳淑華(2012)，「博物館展示配置與參觀行為關係之研究」，科技博物，16卷，3期，頁89-108。

18.顏上晴(2002)，「博物館到館參觀導引研究－以國立科學工藝博物館為例」，科技博物，6卷，3期，頁47-61。