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

Using Artificial Intelligence Algorithms for the New Museum Routing Problem

蔡宗佑(Tsung-Yu Tsai)

指導教授 ： 謝益智

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

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

摘要

本研究探討一個新的博物館路徑問題，此問題中，展覽室分為兩種：一為必看展覽室，即所有遊客團體必定會參觀之展覽室，二為選看展覽室，即遊客團體有各自不同選擇參觀的展覽室，遊客團體則分為小型、中型、大型與特大型4種，越大型的遊客團體通常參觀時間越久。本研究探討的問題為開放式工廠排程問題(Open Shop Scheduling Problem，OSSP)的延伸問題，亦為NP-hard問題。

本研究以台北市立美術館與台南奇美博物館為實例，嘗試以三種人工智慧演算法，基因演算法(Genetic Algorithms，GA)、粒子群演算法(Particle Swarm Optimization，PSO)、免疫演算法(Immune Algorithms，IA)，來最佳化多個遊客團體同時參觀展覽室的路線規劃與最小化總閒置時間，並分析在不同的實驗數據下，不同參數對結果所產生的影響。除此之外，本研究也提出一個新的編碼方式，將一個連續整數序列同時轉換成各遊客團體參觀不同展覽室的順序。本研究的數值結果顯示，免疫演算法與基因演算法的求解品質優於粒子群演算法，而粒子群演算法求解速度為三者中最快。

關鍵字

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

並列摘要

This thesis explored the New Museum Routing Problem. 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. In this thesis, we assume that there are four sizes of visitor groups, namely small, medium, large and very large, we also assume that larger visitor groups will have longer visiting time for exhibition rooms. This considered problem in this thesis is an extended problem of Open Shop Scheduling Problem (OSSP), and it is also an NP-hard problem.

In this thesis, we apply three artificial intelligence algorithms, including Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Immune Algorithm (IA), 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 Chimei Museum (Tainan) and Taipei Fine Arts Museum (Taipei) are solved and analyzed based upon different problem parameters. In addition, in this thesis we propose a new encoding method to convert a sequence of integers into a feasible solution of visitor group visiting sequence in different exhibition rooms. Numerical results of this thesis show that Immune Algorithm and Genetic Algorithm perform better than Particle Swarm Optimization. However, Particle Swarm Optimization is faster than both Immune Algorithm and Genetic Algorithm.

並列關鍵字

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

參考文獻

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

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

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

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

5.李奇霖(2013)，粒子群優化演算法應用於感測器最佳化配置問題，國立交通大學土木工程系，碩士論文。