本研究探討開放型固定間隔參觀時間之遊客導覽排程問題(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.