排隊系統設計：抽號碼牌統一排隊、分別獨立排隊，哪種方法比較快被服務到？
想像一下，如果你是全聯的員工，結帳隊伍越來越長了，該在什麼時間點請同事支援呢？又或者，你在 7–11 結帳的時候，是否有發現，當排隊的人數超過三人時，就會請店員支援結帳呢？對於服務客人的商家而言，排隊是一定要規劃的重點。要是排隊的隊伍太長，不但趕時間的客人會放棄購買，也會降低整體的客戶滿意度，對營業額造成影響。
除了零售業以外，其他產業也有類似的問題。醫院的等待批價區只有 20 個座位，要開幾個服務櫃檯，才能讓排隊等待的總人數控制在20人以內？在規劃高速公路的建置時，要在某一路段設立幾座過磅區，才能讓等待中的大卡車總量在三台以下呢？
許多需要排隊的場景，在前期規劃的時候，可以用模擬（Simulation）方法，在一定的前提下，算出最適當的配置。本文將介紹模擬的基本概念與元素，並以 simmer 套件進行實作。
什麼是模擬？
模擬（Simulation）的概念是運用電腦去仿效真實世界的各種行為與活動，以解決複雜的決策問題。具體的做法是收集足夠的前期資訊後，建立一個數學或邏輯的模型以幫助決策。應用的範圍包含排隊、庫存管理、生產製造、物料搬運等。
本篇要談論的情境主要是離散事件模擬（Discrete-event simulation，DES），它指的是一段時間內，其變數具有隨機性的模擬過程。舉個例子：在牛奶裝瓶的生產線上，由輸送帶以固定的速度依序送進來空瓶，空瓶之間間隔時間是相等的，此時這個變數就不具有隨機性。另一方面，商店每天都會有許多客戶上門，每位客戶進到店裡之間間隔的時間皆不相同，這就是有隨機性。
佇列系統 Queuing System
離散事件模擬最常見的應用就是在佇列系統上，這類型的應用被稱為排隊理論（waiting line systems）。
我們可以在日常生活中找到許多佇列系統的身影。通常客人進入到一個商店後，視情況等待會進入到一個列隊中，待各自的任務被處理完畢後，最終離開此系統。從此流程中，可以發現一個佇列系統由三個元素所組成：進入系統的程序（the arrival process）、排隊的程序（the queues or waiting lines process）以及服務的設施（the service facility）。
進入系統的程序（the arrival process）
需求進入的速度是影響排隊隊伍長度的重要因子之一，常以相鄰兩個客人進到商店中的間隔時間，來描述需求進入的狀況。然而在真實世界中，進到店裡的客人彼此之間間隔的時間是不同的，因此常以機率分佈函數來捕捉它的隨機特性。
在真實場景中，特定時間區間內的來客數近似於 Poisson distribution。在 DES 運算上會常常使用以下轉換：若特定時間區間內的來客數為卜松分佈（Poisson distribution），則到店客戶兩兩之間相距的時間為 continuous exponential distribution。
另外，潛在的來客數也是考量的重點，如果店裡位於市中心，門庭若市、川流不息的話，可以將之視為無限大；反之，若是來客數會因已經被服務過的客人而受到影響，則要將之視為有限的。
排隊的程序（the queues or waiting lines process）
此議題包含三個面向：排隊行為、服務規則、等待區。
排隊行為描述的是客人在等待的時候，可能出現的行為。常見的有：當隊伍太長時放棄排隊（balk）、有比較短的隊伍時就換去短隊伍（jockey）、當隊伍移動速度太慢時放棄排隊（renege）。
服務規則指的是櫃台是如何選擇下一位要服務的客人。常見的有：先排隊的先服務（First in first out, FIFO）、最晚排隊的先服務（Last in first out, LIFO）、照優先順位（priority）、最快可以被完成的先服務（Shortest processing time, SPT）、循環制（Round Robin scheduling, RR）。
店內空間可以容納多少排隊人數也要納入考量，若是場地空間非常大，則會視為無限的等候區；若是等候區（便利商店、診所）的空間較小，則應該將隊伍的長度視為有限。
服務的設施（the service facility）
包含服務的機制以及服務速度。
服務的機制描述的是各種不同的情境：單一服務者（single server）、多位服務者（multiple servers）、服務者之間是完全相同（ATM）還是有所差異（服務人員）、服務者之間的相依性，是否有順序性而需要排在一起（過海關要先檢查護照，再進行安檢掃描）。
服務速度很好理解，通常也會用機率分佈函數表示。人為的服務時間通常使用常態分佈（normal distribution）表示，不過這個假設通常和實際狀況有很大的出入。
通常排隊服務成本會是等待時間和服務時間的加總，因此許多模擬問題要探究的是：需要提供怎樣的服務機制，讓總體的排隊服務成本最小化。
排隊系統設計的評價指標
最常用來評價一個排隊系統優劣的指標有三個：
- 客戶平均獲得服務的時間：一個普通的客戶，從進入系統到離開平均所花費的時間。
- 平均隊伍人數：都是普通客戶的情況下，一條隊伍裡有多少人在排隊。
- 服務者忙碌時間的佔比：過低的話表示服務資源過剩；過高的話，此服務有很高的機率是瓶頸（bottlenecks）。過低或過高都值得檢視。
抽號碼牌統一排隊、獨立排隊，哪種方法比較快被服務到？
生活中這麼多排隊的場景，大家都想知道所以哪種排隊方式可以比較快被輪到。我們可以用 R 語言的 simmer 套件進行實作。simmer 是一個處理離散事件模擬的 R 套件，它的框架設計概念參考了 SimPy ，並使用 Rcpp 加速效能運算。抽號碼牌統一排隊、獨立排隊，哪種方法比較快被服務到？
模擬情境為：二個服務櫃檯，在一個月之內，在客人進店的人數分布與服務的時間分佈已知且完全相同的情況下，在兩種不同的排隊策略下，試算其可完成服務的客人總數與平均等待時間。
情境一：多櫃檯，多隊伍
# Several Counters with individual queues
library(simmer)set.seed(1014)
run_time = 43200 # 1 month
n_arrival = 6000 # Number of customerscustomer <-
trajectory("Customer's path") %>%
log_("Here I am") %>%
set_attribute("start_time", function() {now(bank)}) %>%
select(c("counter1", "counter2"), policy = "shortest-queue") %>%
seize_selected() %>%
log_(function() {paste("Waited: ", now(bank) - get_attribute(bank, "start_time"))}) %>%
timeout(function() {rexp(1, 1/12)}) %>%
release_selected() %>%
log_(function() {paste("Finished: ", now(bank))})bank <-
simmer("bank") %>%
add_resource("counter1", 1) %>%
add_resource("counter2", 1) %>%
add_generator("Customer", customer, function() {c(0, rexp(n_arrival, 1/10), -1)})bank %>% run(until = run_time)result <- bank %>%
get_mon_arrivals() %>%
transform(waiting_time = end_time - start_time - activity_time)output <- list(n_completions = sum(result$finished),
avg_wait_time = round(mean(result$waiting_time), digits = 2))
output
# $n_completions
# [1] 4506
#
# $avg_wait_time
# [1] 8.92
情境二：多櫃檯，單一隊伍
# Several Counters but a Single Queue
library(simmer)set.seed(1014)
run_time = 43200 # 1 month
n_arrival = 6000 # Number of customerscustomer <-
trajectory("Customer's path") %>%
log_("Here I am") %>%
set_attribute("start_time", function() {now(bank)}) %>%
seize("counter") %>%
log_(function() {paste("Waited: ", now(bank) - get_attribute(bank, "start_time"))}) %>%
timeout(function() {rexp(1, 1/12)}) %>% # process time
release("counter") %>%
log_(function() {paste("Finished: ", now(bank))})bank <-
simmer("bank") %>%
add_resource("counter", 2) %>%
add_generator("Customer", customer, function() {c(0, rexp(n_arrival, 1/10), -1)})
# Arrival processbank %>% run(until = run_time)result <- bank %>%
get_mon_arrivals() %>%
transform(waiting_time = end_time - start_time - activity_time)output <- list(n_completions = sum(result$finished),
avg_wait_time = round(mean(result$waiting_time), digits = 2))
output
# $n_completions
# [1] 4506
#
# $avg_wait_time
# [1] 7.6
從模擬結果可以看出，兩種排隊策略在一個月之內完成服務的總客數是相等的（4506人），但是在「多櫃檯，多隊伍」的平均等待時間為 8.92 分鐘；而「多櫃檯，單一隊伍」的平均等待時間為 7.6 分鐘。後者的等待時間較短。
綜合評比
上述的評價方式只有看單位時間內服務的總人數與平均等待時間，而現實生活中要考量的不止這些面向。以下列出兩種方法在其他面向的考量：
情境一：多櫃檯，多隊伍
優點：
- 視覺上隊伍移動相對較快：如果等待中的客人不滿意正在排的隊伍的速度，可以自行選擇切換到較短的隊伍上。
- 較有效率的空間運用：如果沒有搭配抽號碼牌系統的話，通常會用紅龍拉出排隊的路線。紅龍在人潮較少的時候，就會顯得佔用了太大的空間，此時多隊伍的策略佔用的空間相對較小。
缺點：
- 客人會擔心排到較慢的隊伍：客人無法預測哪個隊伍可以最快得到服務。
- 鼓勵客人變換排隊隊伍：在趕時間的客人通常會不斷的切換到最短的隊伍上。
情境二：多櫃檯，單一隊伍
優點：
- 透明且公平：所有人都是抽號碼牌，或是乖乖排在人籠裡，是公平性最高的方法。
- 避免客人變換排隊隊伍：只有單一一條隊伍的話，即可避免有人持續的變換排隊隊伍。
缺點：
- 需要大量的排隊空間：在人潮較少的時候，紅龍的空間還是存在，會顯得佔用了太大的空間。
- 視覺上隊伍移動相對緩慢：雖然上述實際以程式碼模擬的結果是單一隊伍的平均等待時間較短，但是多隊伍因為有多個櫃檯的客人來來去去，在視覺上的感受服務速度是比較快的。
總結來說，如果你是客人的話，請盡量選擇單一隊伍的排隊方式，可以較快獲得服務。如果你是主管，需要設計排隊策略的話，可以依照自身的行業別，權衡利弊後再做出決策。
參考資料：
