基于于M/M/s/K模型和Dijkstra算法的迪士尼樂園優化問題

時佳

摘要：本文主要研究了上海迪士尼樂園優化問題，包括為顧客提供游園引導、建立休息區等，給游客以更佳的游園體驗。利用最小二乘法預計未來一段時間的入園人數并將游樂場的游客量情況分為高峰期、中低峰期兩種狀態，分別利用TSP模型和M/M/s/K模型進行游客疏導。利用Dijkstra算法建立最短路徑分析模型，將游樂園依據地理位置和項目人數分成三個區域，將地圖離散化成以“一分鐘步行的路程”為間隔的點，點與點之間用有向線段連接，枚舉休息區。

關鍵詞：最小二乘法；蒙特卡洛樹；區域分塊；Dijkstra算法

中圖分類號：G642.0 文獻標志碼：A 文章編號：1674-9324（2019）32-0256-03

一、引言

自上海迪士尼開幕以來，游客眾多，經常會出現長時間排隊的情況，且休息區較少，游客較為密集，本文希望通過預計未來一段時間的入園人數，建立一個疏導模型，通過給予游客游覽提醒和引導，來達到入園游客整體的最優游園體驗，并在游樂設施間的道路上增設休憩區，更好地分散客流。

二、入園人數的預測

（一）模型分析

通過門票系統所收集的2016年06月16日—2018年05月07日的入園人數，發現游樂園的人數與節假日、溫度、天氣等具有一定的關聯性，同過去的節假日、溫度和天氣信息進行了對比。人數隨著周末的出現，而呈現小幅度的周期性起落。節假日如春節、國慶對入園人數的影響尤為明顯。節假日結束后會出現淡季，人數會出現一段時間內維持較低水平，例如春節結束以后從二月下旬開始，人數在低水平維持了一個月左右。

（二）建立線性模型

三、游客疏導模型的建立

（一）模型分析

在保障每位游客盡量多體驗游樂設施的前提下，建立對每個游樂項目的等候游客進行游覽提醒和疏導的模型。主要從時間方面考慮，得出相對用時最短的路徑。

假定游客到達游樂場的時間間隔服從泊松分布，分成兩種情況。

第一種情況，中、低峰期（即11個游樂項目的游客數量都沒有超過或剛好等于每場容納游客數）。游客只需要走一條最短的路徑即可得到較好的體驗。

第二種情況，高峰期（存在排隊等候），排隊等待的游客都有兩個選擇：（1）繼續排隊等候；（2）去別的游樂項目。通過建立游客疏導模型給游客提供建議，從而保證等待時間較短。

由游樂園給出的平均等候時間、單次游玩人數及時間，我們建立以下模型（其中等候時間為入園人數20，000時的期望時間，已知入園人數每增加（減少）1000人，每個設施的期望等候時間會增加（減少）2分鐘，但最少等候時間不會小于游玩時間。

（二）建立TSP模型[1]

TSP問題為簡單的基礎問題，在此不再贅述。中、低峰期游客可以按照TSP模型求得的這條路徑到達每一個游樂項目，已達到游園體驗最優（最短的時間，最少的路程）。以入口為起點，易得路程（不含排隊和游玩時間）最短時間為118min，路徑為：

出入口→B→G→F→E→D→A→K→J→I→H→C→出入口

（三）建立分區域疏導游客模型

參考快速通道模型從分散客流、縮減排隊時間、提高游客滿意度三個方面考慮，在高峰期，將游樂園的工作人員分別安排在B、C、D、K、J五個點，疏導游客，讓游客在游樂園內的分布相對均勻。將每個區域每個項目的相關數據帶入M/M/s/K模型進行計算，得到游客的在相應項目的等待時間的數據，根據得到的數據判斷游客在該項目是排隊等待，還是離開去其他項目。

1.區域分塊。游樂園是一個大的整體，為了提高疏散效率的目的，將游樂園分成聯系緊密的幾個較小的板塊。可以將游樂園分成緊密聯系的四個部分，具體的分布如圖1所示。

經過對每個區域進行合理的分析，可得到單次游玩人數、持續時間、S、λ的參數，對M/M/s/K模型進行求解。

3.結果分析。游客在每個區域可排隊游玩的評價概率都在0.93以上，平均滯留時間最長為4.14min，游客在每個區域滯留的時間相對較短，游客可以按順序游玩每個區域的項目。

在高峰期，該模型可以根據客流情況，及時分流人群，為顧客提供游園線路引導，保障游客的游園體驗。

四、休息區的增設

（一）問題分析

為了更好地提升游園體驗和分散客流，在游樂設施間的道路上增設休憩區。假設在開園后所有游客均一起入園，在不同的游樂設施排隊和各條道路上，建立模型以規劃最優的休憩區設立方案，其中，忽略路上行走的人群，只考慮等待中或者設施上的人。

（二）數據準備

某一時刻游樂場總人數n與全天游樂場游客數m的關系為n=2×■。

利用Excel依據往年數據可輕松得出近兩年來90%的情況下，游樂場的全天人數小于33814人，此時游樂場某一時刻的總人數為15432人，10%為1542人，目標為建立三個休息區，可利用票務和監控系統收集到的各項目等待及游玩時間進行評定。

（三）模型

基于Dijkstra算法建立最短路徑分析模型，將游樂園依據地理位置和項目人數分成三個區域，入口及B、F、G為一區，A、D、E、K、J為二區，C、I、H為三區。每個路段視為間距為1min路程的點，分別在每個區域選擇一個距其區域內所有游樂設施20min以內的點，并使三個點之間的距離大于等于15min。

后判斷所選定的休息區是否能夠容納其20min距離內10%的游客，得出最優解如表1所示。

五、模型檢驗

（一）模型一的檢驗

對模型一預測的結果進行差分分析，具體分析如圖2所示。

由差分分析誤差條狀圖可以知道，預測值和去年的實際值呈現一階差分趨勢，表明時間序列預測模型的預測結果是符合理想的。

（二）模型二的檢驗：蒙特卡洛樹算法驗證

子樹的數量設定為1000棵，遍歷深度設定為15。在那些找到完整路徑的子樹中，路徑（不含排隊和游玩時間）時間最短的子樹為118min（1000棵子樹中共19棵得到該答案），與TSP模型的結果相符。

六、模型評價與推廣

游園人數的預測在氣候變化比較穩定并且工作日比較規律的3月下旬至6月上旬與原數據吻合非常好，但并不能很好地表現暑期溫度過高時人數下降和春節過后人數保持較低水平的狀態，引用卷積神經網絡可以增加預測的精準度。

可以將每個人用參數描述出來，利用三個參數：心情（一開始大家的心情隨機服從正態分布，等得越久就越少，到0就離開游樂場），耐心（每個人隨機服從正態分布，如果某項目等待時間超過耐心值，就放棄），預期游玩數量（在一個范圍內隨機設定），將地圖離散化成間隔為1米的點，點與點之間用有向線段連接，枚舉休息區并用蟻群算法實驗。

參考文獻：

[1]司守奎，孫兆亮.數學建模算法與應用[M].國防工業出版社，2015.

[2]陳治佳，王曦，何苗.大型游樂場快速通道優化模型與仿真模擬[J].哈爾濱工業大學學報，2005，39（7）101-103.