指導教授：楊烽正臺灣大學：工業工程學研究所蘇佳璇Su, Chia-HsuanChia-HsuanSu2014-11-252018-06-292014-11-252018-06-292014http://ntur.lib.ntu.edu.tw//handle/246246/261011有成批時限的服務系統之顧客路徑規劃問題是一新定義的路徑規劃問題，源自於主題樂園中的顧客遊園路徑導引。主題樂園中有多台批量式服務機台提供成群的顧客搭乘。當機台隊伍中等候的人數達到服務批量或成批時間達到成批時限時，啟動一批次運轉服務顧客。目的是透過重新規劃顧客途程以最小化顧客的等待和繞行時間。本研究另有一擴增問題模式，將最佳成批時限也納入考量以最小化機台運轉批次。然而計算顧客的等待時間和機台的運轉批次必須由顧客及機台的細節排程中求得，因此提出一精確的離散事件模擬演算法模擬顧客和機台在系統中的排程。此外，制定優化問題的非線性和線性數學模型並說明問題複雜度。本研究開發以遺傳演化及排程模擬為基的優化演算法，並實作一套有效求解標準和擴增問題的優化求解系統。為了驗證演算機制的效能，建構兩個實際主題樂園範例進行測試，並自創標竿範例分析不同情境下優化演算法的求解效能。數據結果顯示優化演算法能顯著地減少顧客的等待時間，且透過優化成批時限能在未大量增加運轉批次下進一步改善等待時間，提升顧客滿意度。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 741670969 bytesapplication/pdf論文公開時間：2016/07/08論文使用權限：同意有償授權(權利金給回饋本人)顧客路徑規劃問題遺傳演算法離散事件模擬演算thesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/261011/1/ntu-103-R01546008-1.pdf