應用人工智慧演算法於人數限制及固定參觀時間之博物館路徑問題

Using Artificial Intelligence Algorithms for the Museum Routing Problem with Capacity and Fixed Visting Time Constraints

李浩均(Hao-Jun Lee)

指導教授 ： 謝益智

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

摘要

本研究探討一個新的博物館路徑問題，此問題中，展覽室分為兩種：一為必看展覽室，即所有遊客團體必定會參觀的展覽室，二為選看展覽室，即遊客團體有各自想選擇參觀的展覽室，另外每間展覽室都有參觀人數限制及固定參觀時間限制(例如：簡介室)。此人數限制之博物館路徑問題的目標為最佳化多個遊客團體同時參觀展覽室的參觀總完成時間與最小化總閒置時間，因此本研究探討的問題為開放式工廠排程問題(Open Shop Scheduling Problem，OSSP)的延伸問題，所以此人數限制及固定參觀時間限制之博物館路徑問題亦為NP-hard問題。
本研究以宜蘭台灣戲劇館與臺南市南瀛科學教育館為例，嘗試以三種人工智慧演算法，包括：免疫演算法(Immune Algorithms，IA)、基因演算法(Genetic Algorithms，GA)、粒子群演算法(Particle Swarm Optimization，PSO)，來最佳化多個遊客團體同時參觀展覽室的參觀總完成時間與最小化總閒置時間，並分析在不同的實驗參數對結果所產生的影響，本研究的數值結果顯示，免疫演算法與基因演算法的求解品質優於粒子群演算法，而粒子群演算法求解速度為三者中最快。

關鍵字

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

並列摘要

This thesis explored a new Museum Routing Problem with capacity and fixed visiting time constrains. In this problem, there are two types of exhibition rooms for visitors. First type is the must-visit exhibition rooms, and it means that all visitor groups have to visit. Second type is the select-visit exhibition rooms, and it means that each visitor group may visit or not visit. Additionally, each room has fixed periods of open time and capacity restriction.
This considered Museum Routing Problem with capacity and fixed visiting time constrains amis to schedule the routes for all group such that objectives, including the makespan (maximal completion time of the groups) and the total waiting time of groups are minimized.This considered problem in this thesis is an extended problem of Open Shop Scheduling Problem (OSSP), therefore the new Museum Routing Problem with capacity and fixed visiting time constraints is also an NP-hard problem.
In this thesis, we apply three artificial intelligence algorithms, including Immune Algorithm (IA), Genetic Algorithm (GA) and Particle Swarm Optimization (PSO), to solve the New Museum Routing Problem with the objective of minimizing makespan of visitor groups and the total waiting times of visitor groups. Two examples of Taiwan Pavilion Theatre (Ilan) and Tainan Astronomical Education Area (Tainan) are solved and analyzed based upon different problem parameters.

並列關鍵字

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

參考文獻

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

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

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

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

20. 陳盈如(2013)，以改良式分枝界限演算法求解允許中斷開放型工廠排程問題，朝陽大學工業工程與管理系碩士班，碩士論文。