有成批時限的服務系統之顧客路徑規劃問題是一新定義的路徑規劃問題，源自於主題樂園中的顧客遊園路徑導引。主題樂園中有多台批量式服務機台提供成群的顧客搭乘。當機台隊伍中等候的人數達到服務批量或成批時間達到成批時限時，啟動一批次運轉服務顧客。目的是透過重新規劃顧客途程以最小化顧客的等待和繞行時間。本研究另有一擴增問題模式，將最佳成批時限也納入考量以最小化機台運轉批次。然而計算顧客的等待時間和機台的運轉批次必須由顧客及機台的細節排程中求得，因此提出一精確的離散事件模擬演算法模擬顧客和機台在系統中的排程。此外，制定優化問題的非線性和線性數學模型並說明問題複雜度。本研究開發以遺傳演化及排程模擬為基的優化演算法，並實作一套有效求解標準和擴增問題的優化求解系統。為了驗證演算機制的效能，建構兩個實際主題樂園範例進行測試，並自創標竿範例分析不同情境下優化演算法的求解效能。數據結果顯示優化演算法能顯著地減少顧客的等待時間，且透過優化成批時限能在未大量增加運轉批次下進一步改善等待時間，提升顧客滿意度。

This work presents a customer routing problem for a batching time controlled service system, CRP4BTCSS for short. The problem originates from the customer guidance operation of a theme park, where batched ride-services are provided for a flock of customers. The batch service starts when the number of customers reaches the batch size or the batching time measuring reaches a prescribed limit. The goal is to rearrange the customers’ routing plans to minimize the total waiting and traveling times. In addition, an augmented problem mode is proposed to include batching time limits as optimization targets to additionally minimize the counts of batch runs. However, the waiting and traveling times of customers and run counts of ride machines can be evaluated only when detailed schedules of customers and machines are available. This work derives a concise simulation algorithm to generate routing schedules of customers and operation schedules of machines as well. Moreover, nonlinear and linear programming models are developed to formulate the optimization problem and illustrate the complexity of the problem. A practical solving method based on discrete event simulation and genetic algorithm optimization techniques is proposed and implemented. Two applications of real theme parks are constructed for numerical tests as well as several benchmarks for specific testing. The implemented software system has effectively carried out the simulation based optimization method and is able to efficiently solve these sample problems of the standard and augmented modes. Numerical results show that the proposed method has significantly reduced the waiting times and an optimal setting of batching time limits will yield a higher customer satisfaction without much additional resource input.

目錄
摘要 i
Abstract ii
目錄 iii
圖目錄 v
表目錄 vii
1. 緒論 1
1.1. 研究背景與動機 1
1.2. 研究目的 2
1.3. 研究方法 3
2. 文獻探討 4
2.1. 路徑規劃與主題樂園相關問題 4
2.1.1. 路徑規劃衍生問題 4
2.1.2. 主題樂園顧客路徑規劃相關問題 5
2.2. 遺傳演算法 7
3. 有成批時限的服務系統之顧客路徑規劃問題－以主題樂園為例之遺傳演算法 11
3.1. 有成批時限的服務系統之顧客路徑規劃問題定義 11
3.1.1. 問題描述與假設 11
3.1.2. 離散事件模擬演算法 15
3.1.3. 數學模式及解空間複雜度 20
3.2. 標準問題模式的遺傳演算及排程模擬為基優化演算法 29
3.2.1. 途程解的染色體編碼 30
3.2.2. 途程染色體的適應值 30
3.2.3. 遺傳演算的母體初始化 31
3.2.4. 遺傳演算的交配、突變、篩選法 31
3.2.5. 鄰近顧客同步區域搜尋法 35
3.2.6. 小結 36
3.3. 擴增問題模式的遺傳演算及排程模擬為基的優化演算法 38
3.3.1. 成批時限解的染色體編碼 38
3.3.2. 染色體的適應值 38
3.3.3. 擴增模式的母體初始化 39
3.3.4. 遺傳演算的交配、突變、篩選法 39
3.3.5. 動態鄰近顧客同步區域搜尋法 40
3.3.6. 小結 41
4. 演算法求解系統及範例驗證 42
4.1. 遺傳演算及排程模擬為基的優化演算法求解系統 42
4.2. 系統驗證分析 46
4.2.1. 實際範例測試與分析 46
4.2.2. 不同情境範例測試與分析 58
5. 結論與未來研究建議 68
5.1. 結論 68
5.2. 未來研究建議 68
參考文獻 70
附錄A 71
附錄B 74

Ahmadi, Reza H. (1997). Managing capacity and flow at theme parks. Operations research, 45(1), 1-13.
Beasley, David, Martin, RR, &; Bull, DR. (1993). An overview of genetic algorithms: Part 1. Fundamentals. University computing, 15, 58-58.
Bektas, Tolga. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3), 209-219.
Chen, Cen, Cheng, Shih-Fen, &; Lau, Hoong Chuin. (2013). Multi-Agent Orienteering Problem with Time-Dependent Capacity Constraints. Paper presented at the MIC 2013: The X Metaheuristics International Conference, Singapore.
Cheng, Shih-Fen, Lin, Junjie Larry, Du, Jiali, Lau, Hoong Chuin, &; Varakantham, Pradeep Reddy. (2013, 12-2013). An agent-based simulation approach to experience management in theme parks. Paper presented at the 2013 Winter Simulation Conference (WSC-13), Singapore.
Gen, Mitsuo, &; Cheng, Runwei. (1997). Genetic algorithms and engineering optimization (Vol. 7). New York: John Wiley &; Sons.
Goldberg, David Edward. (1989). Genetic algorithms in search, optimization, and machine learning (Vol. 412): Addison-wesley Reading Menlo Park.
Golden, Bruce L, Levy, Larry, &; Vohra, Rakesh. (1987). The orienteering problem. Naval research logistics, 34(3), 307-318.
Holland, John H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. Oxford, England: U Michigan Press.
Laporte, Gilbert. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231-247.
Laporte, Gilbert, &; Martello, Silvano. (1990). The selective travelling salesman problem. Discrete applied mathematics, 26(2), 193-207.
Syswerda, Gilbert. (1989). Uniform crossover in genetic algorithms. Paper presented at the the Third International Conference on Genetic Algorithms
Tsai, Chieh-Yuan, &; Chung, Shang-Hsuan. (2012). A personalized route recommendation service for theme parks using RFID information and tourist behavior. Decision Support Systems, 52(2), 514-527.