透過您的圖書館登入
IP:18.206.13.112
  • 學位論文

演化式演算法於開放型固定間隔參觀時間之遊客導覽排程問題

Evolutionary Algorithms for the Open Shop Visitor Routing Problem with Fixed Visiting Times

指導教授 : 謝益智
若您是本文的作者,可授權文章由華藝線上圖書館中協助推廣。

摘要


本研究探討開放型固定間隔參觀時間之遊客導覽排程問題(OSVRP-FVT),為開放型工廠排程問題(OSSP)的延伸應用模式,是屬於NP-hard問題。其中遊客團與展示室可分別視為生產環境中的工件與機器,每個遊客團需花費在展覽室的參觀時間類似於工件在機器上的處理時間,而各間展示室在導覽員的解說下,使展覽室的參觀時間為固定,且遊客團於展示室與展示室之間的移動時間則視為機器與機器之間的相依整備時間。由於遊客導覽排程問題本身的複雜度,若利用最佳化的求解方法則需花費冗長時間進行求解,而啟發式演算法(Heuristic)雖然不能保證求出最佳解,但具備求解快速且能求得近似最佳解的能力。 本研究應用三種啟發式演算法,包含基因演算法(Genetic Algorithm, GA)、類免疫系統演算法(Artificial Immune System Algorithm, AISA)及粒子群最佳化演算法(Particle Swarm Optimization, PSO),來探討此遊客導覽排程問題。針對不同青年老年比例之遊客團、展示室數目及遊客團數目,我們分別以三種演算法來求解。本研究以國立台灣史前文化博物館、國立自然科學博物館、鶯歌陶瓷博物館、國立歷史博物館及國立故宮博物院等5間博物館作為5個不同的測試問題。數值結果顯示,對於不同條件之測試問題,此三種演算法均能有效地規劃各遊客團的參觀時間、移動時間及閒置時間。然而,整體而言,類免疫演算法的表現優於其他兩種演算法,而基因演算法則表現最差,但就求解速度而言,基因演算法最優,其次為粒子群最佳化演算法,最後為類免疫系統演算法。

並列摘要


This study investigates the Open Shop Visitor Routing Problem with Fixed Visiting Times (OSVRP-FVT) which is an extension of Open Shop Scheduling Problem (OSSP) and an NP-hard problem. In the OSVRP-FVT, the visitor groups and exhibit rooms can be treated as the jobs and machines in the production system of OSSP, respectively. That is, the visiting time for each visitor group in an exhibit room is similar to the processing time required for each job on a machine. The moving time required from one exhibit room to another is considered as the sequence-dependent setup time on a machine. We assume that there is a fixed visiting time for each group in each exhibition room. Due to the complexity of the OSVRP-FVT, typical mathematical programming approaches are time expensive for finding the optimal solution. Therefore, heuristic approaches are applied for solving the considered problem in this thesis. Even though they are not guaranteed to obtain the optimal solution, these approaches could obtain the near optimal solutions within a reasonable CPU time. In this thesis, we apply three heuristic algorithms, including Genetic Algorithm, Artificial Immune System Algorithm and Particle Swarm Optimization, to solve the OSVRP-FVT. We solve several test problems for various combinations of ratios of youth and elder in the groups, number of visitor groups and number of exhibition rooms. The museums in the test instances include National Museum of Prehistory, National Museum of Natural Science, Yingge Ceramics Museum, National Museum of History and National Palace Museum. Computational results indicate that the applied three heuristic algorithms are effective to schedule the route for each visitor group. Our numerical results show that Artificial Immune System Algorithm is superior to the other two algorithms in solution quality, and Particle Swarm Optimization is superior to Genetic Algorithm. However, Genetic Algorithm performs faster than Particle Swarm Optimization, and Particle Swarm Optimization performs faster than Artificial Immune System Algorithm.

參考文獻


5.林雪華(2010),應用粒子群最佳化演算法與免疫演算法為基之動態分群於顧客關係管理研究,國立台北科技大學工業工程與管理研究所,碩士論文。
21.楊昆展(2009),粒子群演算法應用於多目標車輛途程問題之研究,淡江大學運輸管理學系碩士班,碩士論文。
13.許正良(2013),應用人工智慧法於居家照顧服務排程路徑規劃問題,虎尾科技大學工業工程與管理研究所,碩士論文。
24.鄧宗倫(2010),應用人工智慧法於最佳消毒作業之時窗限制車輛途程問題,虎尾科技大學工業工程與管理研究所,碩士論文。
12.張奕謙(2008),具衰退性產品之不定點銷售問題的探討,虎尾科技大學工業工程與管理研究所,碩士論文。

被引用紀錄


蔡宗佑(2015)。應用人工智慧演算法於新的博物館路徑問題之探討〔碩士論文,國立虎尾科技大學〕。華藝線上圖書館。https://doi.org/10.6827%2fNFU.2015.00036
李浩均(2016)。應用人工智慧演算法於人數限制及固定參觀時間之博物館路徑問題〔碩士論文,國立虎尾科技大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0028-2207201615565700

延伸閱讀