遊樂園排程最佳化問題

Abstract

在本研究中,我們探討遊樂園排程問題。每台遊樂設施皆有各自的執行時間、固定間隔時間,以及每台遊樂設施之各區段有各自起始時間、完工時間以及區段可承載量。我們並考量顧客的設施遊玩人數、設施喜好程度、遊園時間、用餐時間,以求得下列三個目標式,包含:(i)全部設施時間最小化、(ii)區段時間內設施數最大化、(iii)區段時間內加權設施數最大化。提出 整數規劃的模型最佳解,並使用基因演算法、模擬退火法求得近似解,並將其實驗結果與整數規劃求出的最佳解比較。

In this thesis, we consider the scheduling of preferred rides in amusement parks. An agent of the amusement park receives the requirements from the visitors, including preference for rides, entertainment times, and dining times. The agent has to determine the sequence of the rides to be visited and the starting times of the rides. Each ride in the amusement park has an independent fixed starting time, finishing time, setup time, processing time, visitor’s priority and capacity. The following objectives are considered, i.e., minimize the maximum completion time, maximize the total number of completed rides in a fixed time period, and maximize the total weighted completed rides in a fixed time period. We present integer programming models to formulate the problems. Genetic algorithm (GA) and simulated annealing (SA) are adopted to develop approximation algorithms. Finally, we conduct computational experiments to appraise the performances of the proposed algorithms.