有成批時限的服務系統之顧客路徑規劃問題

Abstract

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

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.