參觀博物館為國內常見的課外活動與校外學習,亦是國外旅遊團來台參訪的重要行程之一。對於有事先預約的團體,博物館通常會安排領隊帶領團體參觀展覽品並講解展覽品的由來,參觀路徑是根據參觀團體的參觀時間來安排,以避免路線雍塞或排隊而造成時間的浪費。 本研究探討博物館路徑問題,此問題需同時規劃多個團體參觀展覽室的路徑,其中各團體有必須觀看的展覽室和選擇觀看的展覽室,問題目標為最小化完成參觀時間。本研究探討博物館路徑問題為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.
為了持續優化網站功能與使用者體驗,本網站將Cookies分析技術用於網站營運、分析和個人化服務之目的。
若您繼續瀏覽本網站,即表示您同意本網站使用Cookies。