應用人工智慧演算法於多選擇性及固定參觀時間之博物館路徑問題

Using Artificial Intelligence Algorithms for the Museum Routing Problem with Multi-Select and Fixed Visting Time Constraints

涂榮城(Rong-Cheng Tu)

指導教授 ： 謝益智

國立虎尾科技大學/管理學院/工業管理系工業工程與管理碩士班/碩士(2017年)

摘要

本研究探討一個新的多選擇性博物館遊客參觀路徑問題(Multi-Select Museum Visitor Routing Problems，MS-MVRP)，此問題中，多個遊客團體同時參觀博物館中的眾多展覽室，對於每個遊客團體，其參觀的展覽室分為兩類：(a)必看展覽室，即為其必定會參觀之展覽室，(b)選看展覽室，即其自候選的展覽室中挑選若干間參觀。本研究假設每個遊客團體依照其興趣均有二個候選的展覽室集合，且均須自其各自的候選展覽室集合挑選若干間參觀，其中每個遊客團體於二個候選的展覽室集合可挑選的展覽室總數目為已知，而於每個候選的展覽室集合挑選的展覽室數目為決策變數。
本研究以國立故宮博物院為例，嘗試以三種人工智慧演算法，基因演算法(Genetic Algorithms，GA)、免疫演算法(Immune Algorithms，IA)、粒子群演算法(Particle Swarm Optimization，PSO)，來最佳化多個遊客團體同時參觀展覽室的參觀總完成時間，並分析不同參數對結果所產生的影響。本研究的數值結果顯示，免疫演算法與基因演算法的求解品質優於粒子群演算法，而粒子群演算法求解速度為三者中最快。

關鍵字

新的博物館路徑問題 ； 粒子群演算法 ； 基因演算法 ； 免疫演算法

並列摘要

This thesis investigates a new multi-select museum routing problem (MS-MVRP) in which a number of groups visit several exhibition rooms in a museum simultaneously. The exhibition rooms are divided into two categories: (a) a set of must-see exhibition rooms, that is, all groups have to visit the must-see exhibition rooms, (b) a set of select-see exhibition rooms, that is, groups can visit or not visit the select-see exhibition room. We assume that each group has two candidate sets of select-see exhibition rooms in accordance with their interests. In addition to the given must-see exhibition rooms, each group has to be secduled to visit some exhibition rooms from these two candidate sets of select-see exhibition rooms when the total number of visited exhibition rooms is known. The objective of the MS-MVRP is to schedule the exhibition rooms for all groups such that the the makespan of all groups is minimized.
In this thesis, we apply three artificial intelligence algorithms, including Immune Algorithm (IA), Genetic Algorithm (GA) and Particle Swarm Optimization (PSO), to solve the MS-MVRP with the objective of minimizing makespan of visitor groups. The examples of Nation Palace Museum were solved and analyzed. Numerical results show that PSO is faster than IA and GA, and IA is superior to both PSO and GA.

並列關鍵字

Museum Routing Problem ； GeneticAlgorithm ； Particle Swarm Optimization ； Immune Algorithm

參考文獻

[30] 蘇桂成(2014)，應用人工智慧演算法探討需多種工序的多工件開放式排程問題，國立虎尾科技大學工業工程與管理研究所，碩士論文。

[28] 簡銓蔚(2013)，粒子群演算法應用於具容量限制的開放式車輛途程問題，元智大學工業工程與管理研究所，碩士論文。

[18] 郭弘毅(2016)，即時補貨路徑規劃系統之發展與建置，逢甲大學，工業工程與系統管理學系，碩士論文。

[14] 施懿軒(2016)，以田口方法分析高碳鋼表面粗糙度之銑削最佳製程參數研究，逢甲大學，機械與電腦輔助工程學系，碩士論文。

[10] 林益州、蘇雄義(1998)，「物流中心供應商進貨配送排程問題求解模式與方法之實證研究」，東吳經濟商學學報，第62期，頁69-96。