網路預約停車排隊理論
網路預約停車排隊理論
摘要
電子商務正在改變人類的生活，新興的行業如雨後春筍般不停的浮現。創
意帶來商機，二十出頭歲的年輕小伙子就擁有億萬財富。本篇論文以一個網路預
約停車的構想，引出預約背後所需解決的數學問題，用以求得最大獲利。
此篇論文假設停車位一位難求。駕駛員寧願花較高費用，經由網站來預約車
位，以確保有車位可停。停車場則將預約的流量以及臨時停車的車流量用Poisson
的出現機率來表示。以取得最大獲利為目標來控管停車流量。
第 6 頁，共 6 頁
第 7 頁，共 7 頁
目錄
第一章 緒論_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _ _ _ 8
第一節 前言_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 8
第二節 環境定義_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 9
第三節 論文章節編排_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 0
第二章 預約的特性及演算法_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 1
第一節 預約的特性_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 1
§ 2. 1. 1 : 預約量( Z) _____________________________________________ 11
§ 2. 1. 1 : 提前時間( T) ___________________________________________ 12
§ 2. 1. 2 : 保留量( X) _____________________________________________ 14
§ 2. 1. 3 : 多個預約點____________________________________________ 16
§ 2. 1. 4 : 預約過量______________________________________________ 18
§ 2. 1. 5 : 影響預約量的因素______________________________________ 20
§ 2. 1. 6 : 每個預約點接受幾個預約呢?_____________________________ 22
第二節 演算法( Parki ng A l gori thm) _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 2 5
§ 2. 2. 1 : Parki ng Al gor i t hm_____________________________________ 25
§ 2. 2. 2 : 範例討論______________________________________________ 29
第三章 演算法的加速及數學式_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 3 1
第一節 演算法的加速_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 3 1
第二節 數學式_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 3 2
第三節 結果比較_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 4 0
第四章 未來工作及結論_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __ _ _ 4 2
第一節 未來工作_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 4 2
第二節 結論_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 4 3
參考文獻: _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _ _ _ _ 4 5
第 8 頁，共 8 頁
第一章 緒論
第一節 前言
在許多擁擠的都市，停車已經變成了一種夢魘。 有時候，為了參加一個短
短的會議，可能要花上比會議還長的時間停車。又要擔心被拖吊或因此錯過
會議時間，造成諸多不可預期的結果。因此，若駕駛員能在出門前就確定有
車位可停，這樣將可有效的解決停車問題。
預約停車的服務，除可免除找不到停車位的困窘，亦可藉由預約的通訊設備
(例: 網路)，告知駕駛員停車場的現況。可避免駕駛員擠在同時段停車或停
在同一個停車場，能有效的將停車流量攤平。不過，問題也來了，停車場要
如何處理預約停車，如何保留車位以及何時該關閉現場臨時停車，才得到最
多的獲利呢？
在此，我們將利用 Queueing 數學理論來看預約系統，求得預約的最佳化。
首先，將定義預約的環境及變數，分析預約的特性，再依這些特性提出一套
演算法(Parking Algorithm)，來找尋擁有最多獲利的預約狀況。接著是此演
算法的加速方法及相關的數學式。最後，將舉例討論停車場能由預約服務而
多得的獲利。
結論中，我們將指出可改進的地方，並將此觀念推廣到頻寬，飯店.. 等的預
約，可見此預約系統的應用面極廣。
第 9 頁，共 9 頁
第二節 環境定義
假想，我們身處在一個交通擁擠的都市，連出門都怕找不到停車位。幸運
的是，駕駛員可在出門前就先行預約，以確保有車位可停。但在享受此服務
的同時，駕駛員則則必需付出額外的費用；相對的，停車場為滿足預約停車，
也必需付出保留車位的代價。因此，就有了以下的預約規則:
1. 停車場開放24 小時預約，每隔半小時一個預約點。
(例: 8:00、8:30、9:00 …。)
2. 預約加價: 因為駕駛員要享有保留車位的服務，所以停車費用
加價。(例: 兩倍價 )
3. 預約賠償: 若駕駛員已先行預約，但到停車場時，卻無車位可
停，此時停車場需付給駕駛員的賠償。 ( EX: 800 元)
此篇論文的目地，就是要在上述的預約規則下，利用 Queueing 數學理論來
看預約系統，求得預約的最佳化，找出每個預約點所能接受的預約量，該保
留多少車位數，以及何時該關閉現場臨時停車。在進入主題前，我們需作些
假設及定義計算中會用到的變數。
假設:
1. 任何時候均有車輛等待進入停車場。
l 因若無車輛等待要進入停車場，那駕駛員亦無需預約。
l 其他沒有車輛等待進入停車場的情況，停車場因預約停車
而多得的獲利將增加。
2. 有預約的車輛一定會到。
l 停車場可用一些限制來逼近假設。
例: 只要一預約，停車場將先行收取半小時的預約停車費。
若半小時內沒出現，停車場就將此預約視為自動放棄。
3. 停車場的車輛以 Poisson [1]
的機率離開。
f(x)= 1/β * e-x/β , x 停車時間; β 平均停車時間。
變數:
n 停車場總車位數 α 個(例: 200 個)
n 平均停車時間 β 分鐘(例: 100 分鐘)
第 10 頁，共 10 頁
第三節 論文章節編排
在此論文中，第一章簡介為何要預約以及預約的環境，第二章介紹預約的特
性，再依這些特性提出一套演算法(Parking Algorithm)求得預約的最佳化，
第三章介紹加快演算法的方法以及相關的數學式，第四章 舉例討論停車場
能因預約服務而多得的獲利，最後，將列出可改進的地方和相關的應用。
第 11 頁，共 11 頁
第二章 預約的特性及演算法
第一節 預約的特性
§ 2.1.1 :預約量(Z)
在論文一開始所制定的預約規則下，停車場開放 24 小時的預約，每隔 30
分鐘一個預約點，也就是說預約者可在 8:00，8:30，9:00 …等，來預約停車，
停車場將會為預約者保留車位，這樣預約者就可以免去找尋車位的問題。不
過，因為預約者享受了保留車位的服務，所以停車的費用加價以避免預約者
隨意的亂預約，停車場也可藉由預約加價增加獲利。可以說是一個雙贏的方
法。 所謂的預約量(Z) ，就是，每個預約點停車場被預約的車望數量。
第 12 頁，共 12 頁
§ 2.1.1 :提前時間(T)
停車場在接受預約之後，一定要設法空出足夠的空車位來滿足預約。因為若
無法滿足預約的車位，將會損失大量的預約賠償，這樣將導致停車場的獲利
下降，反而造成虧損，完全享受不到預約加價所帶來的獲利增加。那停車場
到底要如何空出車位呢? 最簡單直覺的方法就是提前關閉現場臨時停車，讓
停車場內的車輛慢慢離開，也就是說停車場的車輛有出無進，自然而然空車
位的數目就會持續的增加，這樣就有足夠的空車位來滿足預約的車位。所
以，可選定一個預約點為基準，例如: 9:00 的預約點，然後提前T 分鐘關
閉現場臨時停車，來空出停車位。我定義T 為 “提前時間”。
停車場要如何決定 T 的大小呢? 當然，停車場將以獲利為考量，以取得最
多獲利為宗旨。所以首先我們將先探討影響獲利的因素，影響獲利的因素有
三，一、停車場可藉由收取預約加價的費用來增加獲利。二、停車場要避免
空車位不足的發生，因為空車位不足將無法滿足所有的預約而需負擔預約賠
償。三、若停車場保留的車位數太多，或保留的時間太長，這樣都會造成浪
費。因為多出來的空車位可讓現場臨時停車來補滿。基於以上的考量，若T
值太大，也就是說，停車場太早關閉現場臨時停車，這種情況將會發生保留
過多車位的問題，而且保留的時間也會拉長，都將造成浪費。相對的，若 T
太小，停車場的車輛來不及離開，也就是說空車位太少了，這樣將無法滿足
所有的預約，導致需負擔預約賠償的虧損。所以，停車場需找到一個最佳的
T 值，讓停車場在 T 分鐘內剛好離開預約的數量，而這些空車位又能百分
之百由預約車輛填滿，不會有空車位太多，或不足的現象。如此，停車場將
能得到最大的獲利。決定 T 值得大小，將是本篇論文的重點之一。論文中
將利用找尋獲利的最大值來決定 T 值得大小。
以下將以一個簡單的例子，來說明如何決定 T 值得大小。如圖一，首先定
義預約的環境，停車場共有 200 個車位，平均停車時間是 100 分鐘，預約
加價是兩倍，預約賠償 800 元，每分鐘停車費用 1 元。停車場接受了 90 個
9:00 的預約，由 表一 可得知，若 T 等於 46 分鐘， 也就是說停車場提
前在 8:14 分的時候就關閉現場臨時停車，慢慢地讓車輛離開停車場，以滿
足 9:00 的 90 個預約，剛剛好能滿足預約，所以 46 分鐘是一個最佳
值。若 T 小於 46 分鐘將造成空車位足而損失預約賠償，若 T 大於 46 分
鐘，將造成空車位太多的浪費。
第 13 頁，共 13 頁
圖一; 提前時間; 9:00 預約了90 個車位，停車場
於 8: 14開始關閉現場臨時停車以空出足夠的空
車位。提前時間: 46 分鐘。
表一; 提前時間和多賺的
對照表; 若提前 46 分鐘
關閉現場臨時停車，停車
場將會有最有最多獲利。
提前的時間(T) 多賺
44 分 4528.61 元
45 分 4566.62 元
46 分 4581.70 元
47 分 4580.25 元
48 分 4567.49 元
90
全滿
8:00 8:30 9:00
46 分
預約量
變數
停車場車位數: 200 個
平均停車時間: 100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
第 14 頁，共 14 頁
§ 2.1.2 :保留量(X)
因為停車場要設法保留車位來滿足預約，所以最簡單的方法就是提前關閉現場臨
時停車，讓停車場的車輛自由的離開。但問題也來了，因為是讓車輛自由的離開，
所有，有時候可能一瞬間離開好多輛，也有可能久久都沒有任何一輛車離開，這
要怎麼辦呢? 最簡單的方法，當然就是在每個預約點來調整保留車位的數量，以
減少自由離開所產生的不確定因素。首先，我們將先看兩種保留車位的情況，一、
我們先給定某預約點P，例如 圖二 8:30 的預約點，來調整保留車位的數量。若
我們發現 P 點保留的車位嚴重不足，停車場車輛離開的速度太慢，根本無法滿
足所有的預約，眼看就要負擔大量的預約賠償。這時候要如何呢? 當發生這種情
況，那就真的沒救了，因為我們不可能將停車場的車輛趕走，又沒有多餘的車位
來救急。所以這種情況將無法調整。二、若我們發現 P 的的空車位太多，也就
是說停車場的車輛以快於平常的速度離開，這時候，我們將適度的由現場臨時停
車來補滿空車位。那P 點到底要保留多少個車位呢? 我們定義，P 點保留車位
的數目為保留量(X)。
同樣的，若 X 太小，這樣將導致空車位不足，而無法滿所有的預約，需要負擔
大量的預約賠償，停車場的獲利會因此而下降。若 X 太大，將會造成空車位太
多或保留的時間太長，而造成了浪費。所以，和提前預約時間(T)一樣，我們需
求得一個最佳值。如何求得最佳值，將是本論文的重點之一，我們將利用找尋停
車場最大的獲利，來決定 X 值。
此外，由預約點來調整是唯一的方法嗎? 答案是否定的。若我們將調整的間格縮
小將會提高保留車數目的準確度，也就是說保留車位的數目在嚴密的監控下，最
有可能百分支百等於預約的數量。這邊，我們是以最方便的方法來監控。
圖二 所舉的例子和 § 2. 1. 1 完全相同。在 9:00 的預約點，被預約了 90 個車
位，停車場提前 46 分鐘，於 8:14 分關閉現場臨時停車，所以我們可在 8:30 的
時候來調整空車位數，若 8:30 可保留 30 個車位，這樣將可有最多獲利。若 8:30
實際停車場的保留車位大於 30 個，多出來的車位將由現場臨時停車補滿。若小
於 30 個，則無法調整。
第 15 頁，共 15 頁
提前的時間(T) 多賺 8:30 車位保留數
46 分 4581.705 元 30 個
全滿
8:00 8:30 9:00
90
46 分 ( T )
圖 二; 保留量; 若停車場在 8:30 保留 30 個
車位，將可得最多獲利。
30; 保留量( X)
保留量
預約量
變數
停車場車位數: 200 個
平均停車時間; 100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
第 16 頁，共 16 頁
§ 2.1.3 :多個預約點
之前的討論，都是只有一個預約點有預約量。現在將考慮同時有多個預約點
均有預約量的情況。當考慮多個有預約量的預約點時，每一個預約點同樣都
要提前關閉現場臨時停車(T) ，但，值得注意的是，同時考慮多個預約點時，
T 最大只能 30 分鐘，其餘的不足的空車位，將算在前一個預約點的保留量
身上，也就是說，每一個預約點所需的空車位，將由前一個預約點保留量，
以及 T 分鐘內停車場內車輛離開的數量所提供。所以，每一個預約點的空
車位數量，要能同時每滿足預約停車的數量又要能滿足保留量。 可見，他
的情況有稍稍的複雜一點。首先，我們給定多預約點內的某個預約點 P，因
為 P 點的空車位要同時滿足預約量及保留量，那到底要做怎樣的分配呢?
我們需考慮到，空車位有可能太多，大於預約量加上保留量 。反之，也有
可能太少，連預約量都無發滿足。由預約的規則我們可知，最大的損失莫過
於要負擔預約賠償，所以說，每一個預約點的空車位第一要緊就是趕快讓預
約停車進入停車場。再來才是保留給保留量，因為，若 P 點無法滿足保留
量，將會提高後續預約點無法滿足預約量的機會，所以說，無法滿足保留量
將是一種潛藏的損失。若空車位太多呢? 如果空車位的數目大於預約量加上
保留量，多餘的空車位將由現場臨時停車補滿，這就是保留量原先調整保留
車位的功能。
在圖三，我們將時討論 4 個預約點，時間是 7:30 ~ 9:00 。我們將先利用
Parking Algorithm(將在 2.1.1 節介紹)求得此四個預約點在獲利最多時，每
一個預約點所能接受的預約量、保留量及提前關閉現場臨時停車的時間。我
們將可看到，在獲利最多時，對 7:30 的預約點而言，停車場必須提前 18 分
鐘，在 7:12 分時關閉現場臨時停車，開始讓停車場的車輛離開，以滿足20
個預約車位， 15 個保留車位， 若 7:30 的空車位數大於 35 (20 + 15)個，
也就是說停車場車輛離開的速度太快，這時候多出的車位將由現場臨時停車
補滿。對 8:00 的預約點而言，提前 30 分鐘(沒有標明時間代表提前 30 分
鐘)關閉現場停車，需滿足 50 個車位，保留 13 個車位，若空車位大於
63(50+13) 個，將由現場臨時停車補滿。8:30 和 9:00 的情況亦同。
所以說，我們秉持一個最基本的原則，要讓停車場的獲利達到最大值。對每
一個預約點而言，只需要知道，該預約點可接受多少個預約量，多少個保留
量，要提前多久關閉現場臨時停車，這樣可將預約的處理變得很簡單。
第 17 頁，共 17 頁
圖三; 多預約點的預約量及保留量;
在考慮多個預約點時，每一預約點均需
滿足預約量及保留量。
預約點 7:30 8:00 8:30 9:00
保留數 15 個 13 個 5 個 0 個
預約數 20 個 50 個 53 個 46 個
7:00 7:30 8:00 8:30 9:00
18
變數
停車場車位數: 200 個
平均停車時間; 100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
53 46
5
50
13
20
15
全滿
保留量
預約量
第 18 頁，共 18 頁
§ 2.1.4 :預約過量
現在我們又暫時跳回只考慮一個預約點有預約量的討論，假若只有 9:00 的
預約點有預約量，那我們可以沒有限制地讓預約者持續的預約該預約點嗎?
可否讓停車場的所有的車位被預約一空呢?這些答案都是否定的。為什麼呢?
我們將先觀察停車場車輛離開的行為: 當我們關閉現場臨時停車後，停車場
的車輛一輛輛的離開，也就是說停車場內的車輛漸漸的減少，當停車場內的
車輛減少，整個停車場空出車位的機率總和也降低了，也就是說，停車場空
出車位的速度將漸漸的變慢。這個時候，我們又必須考慮到，停車場內已經
有很多的保留車位，所以保留車位所照成的浪費將隨之增加。因此，我們可
以得知保留車位的浪費將會隨著所需要的空車位數量增加而增加。若所需的
空車位大於某一個數量，也就是說當我們的預約量大於某一個數量，停車場
因預約而得的獲利，將小於保留車位所造成的損失。如此，若持續的接受預
約，將導致獲利下滑。
由 圖四 的表格中，我們可以很清楚的看到，若預約量小於 93 個，增加預
約量將會使得獲利上升。所以，接受 92 個預約，所帶來的獲利將大於 91
個，接受93 個的獲利又大於 92 個，這時增加預約量將會使得獲利上升，
但當接受的預約量為 94 個的時候，獲利反而下降了，也就是說，這個時候
的預約量已經太多了，增加的預約量所到來的獲利，將小於保留車位少造成
的損失。我們稱這種情況為預約過量，該預約點為預約過量點。
那我們要如何找尋預約過量的預約點呢? 此篇論文先假設所有預約點的預
約量都是已知，然後減少該點的預約量看看是否會使獲利增加，若能使獲利
增加的話，那就表示該點的預約過量了。
第 19 頁，共 19 頁
預約量 多賺
90 個 5191.63 元
91 個 5196.41 元
92 個 5196.99 元
93 個 5198.42 元
94 個(預約過量) 5197.94 元
預約量
多賺
全滿
8:30 9:00
變數
停車場車位數: 200 個
平均停車時間:100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
8:00
圖 四；預約過量；當預約量超過 93 個時，獲利將下
滑；也就是說此時已經預約過量，減少該點的預約量
將可使獲利增加。
93
第 20 頁，共 20 頁
§ 2.1.5 :影響預約量的因素
當考慮多個預約點都有預約量時，到底是那幾個預約點的預約量太多了?到
底要接受幾個預約才能擁有最多的獲利呢?首先我們將討論每個預約點接受
的預約量會受到那些因數的影響。在下一小節§ 2.1.6 才會提出方法來找尋
預約過量的預約點，且決定要減少多少個預約量才能讓停車場的獲利達到最
大值。
預約量和保留量的平衡
當考慮多個預約點均有預約量時，那每一個預約點的空車位不但要滿足預約
量，以避免發生已預約的車輛無法停車而浪費預約賠償，也需要滿足保留量
以確保後續的預約均有車位可停。但每個預約點的空車位有限，在多個預約
點都有預約量時，每一個預約點都希望前面的預約點能夠為他保留車位以減
少本身發生空車位無法滿足預約的現象，且每一個預約點也都想多接受一些
預約，以增加預約所帶來的獲利，但增加預約又導致需要前面的預約點為他
保留更多的車位。所以說，這是一個雙向馬車，想要增加預約量，但空車位
又有限，增加預約量又需往前增加保留量。所以我們必須取得一個平衡點。
攤平預約量
再來我們要討論的是，保留車位的浪費和預約車位的獲利之間的微妙關係。
因為我們希望多接受一些預約來增加預約所帶來的獲利。但隨之而生的是，
空車位的需求也要增加，但停車場空出車位的速度隨著停車場的車輛減少而
漸漸變慢，所以需要拉長保留車位的時間才能讓停車場從容的空出足夠的車
位，造成浪費變大。也就是說，當接受的預約車位增加後，預約所帶來的獲
利扣除保留車位的浪費，所得的淨利將慢慢的變少，最後將由正值轉成負值
而發生預約過量的情況。所以我們就能得到以下的結論: 如過能夠將預約量
平均的攤在每一個預約點，不要發生某一預約點接受了太多預約量的情況，
將可有最多獲利。因為這個時候，預約所帶來的獲利扣除空車位的浪費，所
得的淨利將比後續所接受的預約所帶來的獲利大。
最小預約量
因為我們將預約的時間以 30 分鐘為預約間隔，將一天分為 24 個預約點。
這時，我們給定某一預約點 P，若停車場在 P 的前一個預約點時，停車位
全滿，也就是前一個預約點完全沒有為 P 點保留任何車位，這個時候， P 點
第 21 頁，共 21 頁
所能接受的預約數量最小。只能靠預約間隔的時間停供給停車場，讓停車場
的車輛慢慢離開，以便空出車位來滿足預約。所以每個預約點所能接受的預
約量有一個下限，我們稱這個下限為最小預約量。例如，在圖四 的預約變
數下，其下限為 46 個。
寧願接受前面預約點的預約
若有兩個相鄰預約點 a、b ， a 在b 的前面，且a 需要為 b 保留車位 。
現在有一預約者想要預約，請問他預約那一個預約點能夠為停車場帶來較大
的獲利? a 或 b? 答案是 a。為什麼呢? 因為若預約者預約 b 點 ，則 a 點
的保留量將增加，以確保 b 點能夠滿足預約，而且不管預約任何一點，停
車場所接受的預約量都一樣，但若預約 b 點，將會拉長保留的時間，導致
保留車位的浪費加大。這裡所舉的例子只為方便說明。”寧願接受前面預約
點的預約” 適用在任何需為後續預約保留車位的任何兩個預約點。
第 22 頁，共 22 頁
§ 2.1.6 :每個預約點接受幾個預約呢?
停車場如何決定每個預約點該接受幾個預約? 當然，不二法則的考慮因素
“擁有最多獲利”。首先，我們假設每個預約點將來會被預約的數量都是已
知。然後由會被預約的數量去反推每個預約點應接受多少個預約，才能讓停
車場擁有最多獲利。為了簡化討論，我們將定義 Group
Group
連續的m 個預約點
前面的預約點需為後續的預約點保留車位
其實，Group 就是相互影響的一群預約點。前面的預約點需要為後續的預約
點保留車位，彼此相互影響。Group 的目的就是要將影響的範圍限制在m
個預約點。我們可藉由對 Group 的討論，延伸到所有的預約點，以求得每
個預約點應接受多少個預約，才能讓停車場擁有最多獲利。一開始，我們已
經知道 Group 內每個預約點將來會有幾個預約，那每個預約點個別要接受
幾個預約才能讓 Group 的獲利最多呢? 要如何反推可接受的預約量呢?我
們可藉由減少預約量，看看是否會增加 Group 的獲利，以決定是否預約過
量。那我們要如何減少呢? 要減少那一個? 首先我們回想在§ 2.1.5 影響預
約量的因素，”寧願接受前面預約點的預約” 我們希望預約者預約前面的預
約點，這樣保留車位的時間才不至拉長。由此可知，若一個 Group 的預約
量太多了，則我們將減少後面的預約，因此，我們得到一個結論:
由後往前減少預約量
所以，將由 Group 的最後一個預約點開始減少預約量。再來所要頭痛的是，
那要減少幾個呢? 其他預約點是否也有預約過量呢? 如何找到下一個預約
過量點呢? 首先，我們第一個問題，”要減少幾個預約?” 這時又得搬出大原
則，”讓停車場獲利最多” ，然後我們將丟給 Greedy Algorithm 持續減少
最後一點的預約量，讓 Greedy Algorithm 自己去跑出最大獲利時的預約，
詳細步驟如下:
利用Greedy Algorithm 求 Group 的最多獲利
步驟一: 給定Group 內的所有變數:
預約點: m 個
預約量: Z1~Zm
保留量: X1-Xm
第 23 頁，共 23 頁
提前時間:T
值得注意的是，為什麼只有一個提前時間(T) 。因為 Group 的每一個預約
點均需為後續的預約保留車位，也就是現場臨時停車在最後一個預約點結束
後才會再開啟。再來，Group 中間任何一個預約點的空車位若大於預約量加
上保留量，多出來的車位將由現場臨時停車補滿。另外，我們將每一預約點
將來會被預約的數量當作預約量，所以，每一個預約點的預約量是可以減少
的。例如 圖五 Group 內總共有 4 個預約點 7:30 ~ 9:30 ，預約量分別
為: Z1、Z2、Z3、Z4，保留量為: X1、X2、X3、X4 ，提前時間是 T。
步驟二: 減少最後一點的預約量，來找尋最大獲利
之後，我們開始減少最後一點的預約量，再丟給 Greedy Algorithm 讓
Greedy Algorithm 改變 T、X1~Xm 的變數，求得 Group 的最大獲利。所以，
我們就可以知道最後一個預約點該減少多少的預約量，才能讓停車場擁有最
大的獲利。
步驟三: 找尋下一個預約過量點
在決定最後一個預約點該減少多少的預約量後，我們必須再找尋下一個預約
過量點，然後減少該點的預約量以增加停車場的獲利。那，到底那一個預約
點的預約數目過量了。我們如何找到它? 其實很簡單，我們只需由後往前，
減少每一預約點的預約量，若發現減少該點的預約量能使 Group 的獲利增
加，該點就是下一個預約過量點。
7:00 7:30 8:30 9:00 9:30
保留量
預約量
圖 五; Gr o u p 的預約過量; 7: 30 ~9: 30 為一 Group，預約
量: Z1~Zm ，X1-Xm
T
X1
Z1
Z2 Z3
Z4
X4
X2
X3
第 24 頁，共 24 頁
步驟四: 忽略新預約過量點以後的預約
當我們由後往前減少每一個預約的預約量，然後檢查 Group 的獲利是否增
加。若發現減少某預約點 P 的預約量後，能使 Group 的獲利上升，那 P
點就是下一個預約過量點。很重要的一件事情是，我們將不再考慮 P 的後
面的預約量了，為什麼呢? 因為P 點後面的預約量將無需再改變，Group 即
可得到最多獲利? 那為何會如此呢? 因為:
1. 不可能增加: P 點是一個預約過量點，所以我們將會減少該點的預約
量以增 Group 的獲利，所以將會減少P 點的預約量。我們回想在§
2.1.5 影響預約量的因素，”寧願接受前面預約點的預約” ，將可得
知，我們不可能減少 P 點的預約，只是為了滿足後面的預約，也就
是說，P 點後面的預約量，不會因 P 點的減少而增加，所以不可能
增加。
2. 不可能減少: 因為Ｐ點的預約量減少了，所以可以接受更多的保留
車位，後續的預約點將可接受更多的預約量。也就是說，後續的預
約點不可能因 P 點預約量的減少反而只能接受更少的預約量。所以
不可能減少。
因此，我們根本無須變更後續預約點的預約量。
所以 P 點以後的預約點將由 Group 中剔除。然後我們重新執行 步驟二.
減少最後一個預約點的預約量，之後再找下一個預約過量點。直到 Group 內
沒有預約過量點。此外，我們必須注意到， 步驟四: 忽略P 點以後的預約
量，這樣會導致 P 點的保留量不正確，但此時 P 點所需的保留量極小，因
為 P 點預約過量點，表示所有的空車位幾乎全部都給了預約量，因此根本
沒有多餘的空車位可以給保留量。故誤差極小。
第 25 頁，共 25 頁
第二節 演算法(Parking Algorithm)
本篇論文的目的，就是要讓停車場知道: 若要擁有最多獲利，每一個預約點要接
受幾個預約，保留幾個車位，提前多久關閉現場臨時停車。經過了這麼多的準備
後，我們終於可以真正踏入主題了。在此，將提出一套演算法 Parking Algorithm
來求得停車場擁有最多獲利時，每個預約點的預約量、保留量及提前時間。
§ 2.2.1 :Parking Algorithm
Parking Algorithm 分為兩部分: 第一部份，先預估每一個預約點將來會被預約的
數量。第二部分，利用 Greedy Algorithm 來求得獲利最多時，每個預約點應接
受幾個預約，保留幾個車位，提前多久關閉現場臨時停車。整個演算法都是架構
在 Group 上，以 Group 為一個討論的範圍。
2.1.1.a 估算每個預約點的預約量
首先，將先估算每一個預約點將來會被預約幾個車位也就是每一個預約點的起始
預約量。 預約量來自於已經預約車位的數量加上將來可能會再預約的數量。
預約量 = 已預約量 + 未來預約量
已預約量是指程式執行時已最被預約的車位數目; 未來預約量是指該預約點將
來有可能會再被預約的數量。我們需小心的是，已經預約的數量是不可以減少
的，所以當利用 Greedy Algorithm 減少Group 最後一個預約點的預約量，以找
尋最多獲利時，這些已預約的車位是不可以減少的。那未來預約量要如何求得呢?
首先，我們對每一個預約點作如下表的時間及預約速度的對照表;
距離第 i 個預約點的時間 第 i 個預約點 的預約速度(個/分)
0:00 - 1:00 R1
1:00 – 2:00 R2
2:00 – 3:00 R3
3:00 – 4:00 R4
針對每一個預約點，例如第i 點，找出距離此預約點的時間及預約速度的對照表。
在上表中，距離第 i 點的時間是指，程式執行時間到第 i 個預約點的時間。假
設程式執行時，距離第 i 個預約點的時間為 3 時40 分。那，第i 點的未來預約
量為何?
未來預約量 =
Rj * 60 R4 * 40
j 1, 2 ,3
å +
=
第 26 頁，共 26 頁
如此，我們就可很容易的預估出所有預約點的未來預約量。
第 27 頁，共 27 頁
2.1.1.b 程式的流程
再來將解釋整個程式的流程:
程式的目的:
求得停車場獲利最多時，每個預約點應該接受預約的數量、要保留的車位數目、
及何時關閉現場臨時停車。
先給定兩的變數: S、E
S: Group 的第一個預約點
E: Group 的最後一個預約點
步驟一: 估算所有預約點的預約量
必須取得每一預約點已經被預約的車位數目，然後各自算出每一預約點將來還會
在被預約的車位數目，然後將兩者相加，即為該點的預約量。
步驟二:
將所有預約點的最後一點加入 Group
2 . S = E = L a s t Poi nt of a l l
步驟三:
然後減少 Group 最後一點的預約量，找尋 Group 獲利的最大值。並求得每一預
約點在最多獲利時的預約量、保留量、提前時間。
3 . Gr e e dy a l g or i t h求m出 Gr o u p 的 Z , X , T
步驟四:
由後往前找尋 Group 中，下一個預約過量的預約點，然後設定新預約過量點為
Group 的最後一點。也就是說，我們忽略的新預約過量點以後的預約點。
4 . f or ( i = E t o S )
i f ( Poi nt i Ov e r k ooi ng ) E = i ;
步驟五:
若發現，經由 Greedy Algorithm 所求得的提前時間 T 大於預約間隔，也就是
說，前一個預約點需要為後續的預約保留車位，程式將往前將此點加到 Group，
然後跳到步驟二: 否則，程式將找尋下一個 Group 。 找尋的方法很簡單，只要
把 S 的前一個預約點設定為Group 即可 。
5 . i f T >預= 約間格 t he n S- -; ( Add ne w poi nt t o Gr o u p)
e l s e S =- -S; E = S ; ( New Gr ou p)
步驟六:
然後，將所有的預約點處理完畢。這樣就能夠得到再最佳獲利時，每一個預約點
第 28 頁，共 28 頁
要保留幾個車位。當處理完畢之後，這時已經有新的預約被接受，所以我們必須
再從新估算預約量，再重新處理所有的預約點。 所以，整個預約的全程，程式
需不停的求出每個時間點的最大獲利，因為預約量一值在變，不同的預約量就會
導致不同的獲利。
最後還需修改的地方是，因為程式的預約量包含了已經預約的車位數量及未來可
能會預約的數量。未來還會在預約的數量，我們可以不接受，但已經接受的預約
是不可以反悔的。所以，當 Greedy Algorithm 減少Group 最後一個預約點的預
約量時，若該點只剩下已預約車位數，那 Greedy Algorithm 就把它視為已經找
到最多獲利了。
程式虛擬碼:
1.估算預約量
2. S = E = Last Point of all
3. Greedy algorithm 求出 Group 的 Z,X,T
4. for (i =E to S)
if (Point i Overkooing) E = i;
5. if T >= 預約間格 then S --; (Add new point to Group)
else S = S--; E = S;(New Group)
6. If E>0 Jump 3. else Jump 1.
第 29 頁，共 29 頁
§ 2.2.2 :範例討論
以下將以一個簡單的例子，討論程式的執行結果;
時間: 6:00 ~ 9:00
程式一開始，將先求得每個預約點的預約量，所以，我們去必須取得已經預約的
車位數目及未來可能預約的車位數目:
預約量 = 已預約量 + 未來預約量
執行完一次 Parking Algorithm 之後，我們得到每一個預約點在最多獲利時的預
約量，保留量及提前時間。
預約點 6:00 6:30 7:00 7:30 8:00 8:30 9:00
已預約量 0 1 10 30 53 40 10
未來預約量 3 4 10 20 47 80 20
變數
停車場車位數: 200 個
平均停車時間; 100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
保留量
預約量
5
6:00 6:30 7:00 7:30 8:00 8:30 9:00
46
50 53
20
5 30
6 18 22
15
13
3
5
3 個小時
6:00 6:30 7:00 7:30 8:00 8:30 9:00
100 120
50
3 5 20 30
預約量
第 30 頁，共 30 頁
最重要的是，停車場要如何依據所得到的資料來處理現場臨時停車以及預約停車
呢? 在此，將以預約點為主角: 預約點6:00 的提前時間是 5 ，所以停車場於5:55
關閉現場臨時停車，6: 30 之後在開啟; 預約量是5 ，但已經被預約了一個車位
所以還可再接受 4 個預約; 不需要保留車位。再來是討論，預約點 7:00，提前
時間是18 ，所以於 6:42 關閉現場停車，7:00 再開啟;預約量是 20，但已經有
10 個車位被預約了，所以還能再接受 10 個預約; 保留量是 15 ，所以需要保
留 15 個車位。再來是預約點 7:30，提前時間是 30 ，於 7:00 關閉現場停車;
7:30 在開啟; 預約量是50 ，已經接受了 30 個預約，所以還可再接受 20 個預
約; 保留量是 13 ，所以需要保留 13 個車位。其他每一個預約點均是如此處
理。那停車場任何時候都可由上述資料得知該做那些相對的動作。
第 31 頁，共 31 頁
第三章 演算法的加速及數學式
第一節 演算法的加速
在演算法的流程中，我們會利用 Greedy Algorithm 來找尋獲利最多時，Group
預約量、保留量及提前時間。若T 大於約間格，我們將會往前加入一個的預約
點到Group 中，然後重新跑 Greedy Algorithm 再次找尋新Group獲利最多時，
Group 預約量、保留量及提前時間。所以，此演算法將會持續的使用 Greedy
Algorithm。也就是說，此演算法的速度取決於 Greedy Algorithm 的快慢。若我
們想加快演算法的速度，就必須有效的加快 Greedy Algorithm 的速度。
方法: 有效的預估每一預約點該保留多少車位(Xi)
當我們往前加入一個預約點到Group 後，會再次利用 Greedy Algorithm 減少新
預約群最後一個預約點的預約量，以找尋獲利最多的預約。所以原有的預約量只
會減少，也就是說，保留車位的數目也只會減小。因此，當我們再次利用 Greedy
Algorithm 找尋獲利最多的預約情況時， 每一個預約點的保留量可以用原有保留
量為初始值，然後以遞減的方法找尋新的保留量，如此將可快速的找到新Group
獲利最多的預約狀態。
圖六; 原有的保留量只可能減少; 當加入新預約量到 Group 時，原有的
預約量只可能減少，所以保留量也只可能減少
時間軸
T
X1
X2 X3
保留量
預約量
第 32 頁，共 32 頁
第二節 數學式
在演算法的流程中， 我們會利用 Greedy Algorithm 來找尋獲利最多的預約。所
以，演算法必需求得每種預約情況Group 的獲利。因此，我們將討論的數學式，
其目的就是要求出 Group 獲利的期望值。
目的: 求出Group 獲利的期望值
整個運算的過程分為四個步驟:
1. 求得單一個預約點的獲利
2. 求得整個 Group 的獲利
3. 考慮保留車位的浪費
4. 算出Group 獲利的期望值
首先，先給定預約的相關變數:
如圖:
步驟一、求得單一個預約點的獲利
假設在第i-1 個預約點，停車場保留μ i-1 個車位，此時停車場有α -μ i-1 輛車，之
變數
停車場總車位數:α 個
平均停車時間; β 分鐘
預約加價: γ 倍
預約賠償: δ 元
每分鐘停車費: 1 元
預約間格 t 分
G r o u p
共 m 個預約點
預約量: Z1 ~ Zm
保留量: X1 ~ Xm
提前關閉現場停車的時間: T
時間軸
…
Z1
Z2
Z3
Zm
X1
X2
X3
Xm
T
保留量
預約量
第 33 頁，共 33 頁
後關閉現場臨時停車，到第i個預約點時，停車場共空出 Li 個停車位。如圖:
在此，計算所求得的獲利，將先不考慮空車位的浪費。第 i 個預約點將會因預約
功能而多出 Ei 的獲利:
Ei :第i 個預約點相較於無預約功能而多出來的收入。
Pi: 出現的機率
μ i : 第 i 點停車場實際保留的車位數
當 Li 小於 Zi 時，停車場車輛離開的速度太慢，所以空車位嚴重不足，無法
滿足預約停車，因此要負擔 Li- Zi 個預約賠償。所以此種情況可因滿足 Li 個預
約，而多賺 Li*β *(γ -1) ，但有 (Zi- Li) 個預約無法滿足，所以虧了(Zi- Li)*
δ ，而且，根本沒有多出來的空車位可以滿足保留量，此種情窗出現的機率為
Pi。 同樣的道理，若 Zi<Li<=Xi+Zi 則可以滿足Zi 個預約，多賺Zi*β *(γ
-1) ，且多出Li – Zi 個車位可留給保留量，出現機率是Pi。第三種情況是
Li>Xi+Z 也就是說停車場車輛的離開速度太快空車位太多，可以滿足Zi 個預
約，多賺 Zi*β *(γ -1) 還有足夠的空車位可留給保留量 Xi，最後多出來的
空車位將由現場臨時停車補滿。
可分為三種情況 ，如表所列:
步驟二、求得Group 的獲利
在此所求得的獲利將先不考慮空車位的浪費，因為 Group 內共有 m 個預約
獲利 (Ei) 保留量(μ i) 出現的機率 Pi
Li<Zi Li*β *(γ -1) – (Zi- Li)* δ 0
Zi<Li<=Xi+Zi Zi*β *(γ -1) Li - Zi
Li>Xi+Zi Zi*β *(γ -1) Xi
t Li t Li
Li
C i e i e
i
- - - - -
- - -
-
a m b m b a
m (1 ) ( ) 1 / /
1
Zi
Xi
Li
μ i-1
t 分鐘
保留量
預約量
圖七 單一個預約點的停車情況: 停車場餘第 i - 1 個
預約點保留μ i-1 個車位，經過 t 分鐘後 於第 i 個預
約點共空出Li 個空車位
第 34 頁，共 34 頁
點，所以Group 的獲利，就等於這 m 個獲利的總和，出現的機率就是這 m 個
預約點各自出現機率的積。因此，只要我們將所有可能出現的獲利及向對應的機
率求出，然後累加獲利乘以機率就可得到 Group 獲利的期望值。
考慮整個Group ( 共 m 個預約點):
總獲利: å
<=i<=m
Ei
1
出現的機率: Õ
<=i<=m
Pi
1
獲利期望值 為:
å å Õ
<= <= <= <= 所有可能的停車狀況
( * )
1 i m 1 i m
Ei Pi
我們必須注意到的是，在計算第一個預約獲利時，此時 t = T( 提前時間) 。
第 35 頁，共 35 頁
步驟三、保留車位的浪費
停車場為了滿足預約停車，必需要保留車位，也因此也造成了保留車位的浪費。
在 步驟一、二中， 我們並未考慮到空車位的浪費，所以本小節將會加入保留車
位的浪費。
如圖，我們假設停車場在t 分鐘內將有 a 輛車子離開。但只需要再離開b 輛，
停車場所保留的車位就足以滿足預約量及保留量。因此，當離開的車輛大於 b
時，馬上就由現場臨時停車補滿。也就是說，停車場最多只會空出預約量+保留
量個停車位。我們可以很簡單的求出保留車位的浪費:
保留車位的浪費: μ i-1* t + Mi
Mi: 前 b 輛離開停車場車輛所造成的保留車位浪費。
所以，只要我只要能夠求得曲線面積 Mi，就可求得保留車位的浪費
a
t 分鐘
b
μ i-1
由現場臨時停車補滿
Mi
圖八 多出的空車位將現場臨時停車補滿 ; 因每個預約
點的空車位只需滿竹預約量及保留量，多出來的空車位將
由場臨時停車補滿
第 36 頁，共 36 頁
如何求Mi:
我們知道，t 秒內共有 a 輛車離開停車場，t’
內共有 b 量離開。有 a –b 個車位
由現場臨時停車補滿。
如圖
若有一車輛於 x 分鐘時離開停車場，則:
1. 浪費: t-x
2. 出現的機率:
dx
b a e
e
t
x
/ * ( 1 )
*
1
/
/
b
b
b
-
-
-
在求出現機率時，我們利用到條件機率: P( x| 在 t 秒內離開，且為離開者的前 b/a)
= P(x)/P(在 t 秒內離開， 且為離開者的前 b/a ) ，先求出 P(在 t 秒內離開)再
求出 x 點出現的機率。
3. 共 b 輛
b
b a e
t x e dx
Mi
t
t
t
*
/ * ( 1 )
*
1
( )
/
0
/
'
b
b
b
-
-
-
-
=
ò
a
t 分鐘
b
t’
x
μ i-1
Mi
*[( 1) *(1 ) * ] /(1 ) / ' / / t ' b t ' b t b = a t - - e- + t e- - e-
第 37 頁，共 37 頁
我們假設，由現場臨時停車補滿的 a-b 輛，在第 i 個預約點前將不會離開。因
為，我們求 t 分鐘內離開幾個的機率時，是不考慮這 a-b 個離開的情況。所以
說，我們只要在求得 t’ ，就可以求出保留車位的浪費。
第 38 頁，共 38 頁
如何求 t’
我們知道，t 秒內共有 a 輛車離開停車場，t’
內共有 b 輛離開。所以t’ 分內離
開的機率比上 t 分鐘內離開的機率，等於 b : a
如圖:
所以 t’ 秒內離開的機率/ t 秒內離開的機率 = b/a
b a
e dx
e dx
t x
t x
/
1 / *
1 / *
0
0
'
=
ò
ò
-
-
b
b
b
b
b b (1 * (1 )) * ' t / e
a
b
t = - Ln - - -
t
t’
時間軸
離開的機率
第 39 頁，共 39 頁
步驟四、算出Group 獲利的期望值
所以考慮保留車位的浪費時，我們只需再將每個預約點的獲利扣除保留車位浪
費，然後總和所有情況的獲利乘以出現機率:
此Group 的獲利的期望值:
å å Õ
<= <= <= <=
- -
所有可能的停車狀況
( ( * )* )
1 1 i m
i
i m
Ei Mi m t Pi
必須注意到的是，當 i=1， 即 Group 第一個預約點，此時 t=T。
第 40 頁，共 40 頁
第三節 結果比較
在此，我們將觀察，停車場能夠經由預約服務而多得的獲利。還有比較 Parking
Algorithm 和另一種預約方法，放任法，在獲利上的比較。我們將觀察，當預約
量太少及太多，此兩種方法在獲利上的表現。
首先，介紹預約的環境:
時間: 6:00 ~ 9:00
預約量太少的情況:
先給定預約量: 預約量= 已預約量 + 未來預約量
6:00 ~ 9:00 每個預約點的預約量都只有 20 個
執行完一次 Parking Algorithm 之後:
放任法: 不限制預約，不保留車位， 只調整 T
我們可以看到， Parking Algorithm 和 放任法 都有多出近 3 成的獲利。這時候
因為預約量很少，所以根本不需要減少預約，也不需要保留車位，所以看不出
Parking Algorithm 的功力。
預約點 6:00 6:30 7:00 7:30 8:00 8:30 9:00
已預約量 ０ ０ ０ ０ ０ ０ ０
未來預約量 ２０ ２０ ２０ ２０ ２０ ２０ ２０
總獲利 多賺 多賺/B
無預約 36000 (B) 0 0
放任法 46511.78 10551.78 0.29
Parking Algorithm 46511.78 10551.78 0.29
變數
停車場車位數: 200 個
平均停車時間; 100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
第 41 頁，共 41 頁
預約量太多的情況:
先給定預約量: 預約量= 已預約量 + 未來預約量
6:00 ~ 9:00 每個預約點的預約量都有 200 個，也就是說，所有的車位都已經被
預約光。
總獲利 多賺 多賺/B
無預約 36000 (B) 0 0
放任法 -293389.14 -329389.14 -9.15
Parking
Algorithm
57083.42 21083.42 0.586
放任法: 不限制預約，不保留車位， 只調整 T
Parking Algorithm 多出了近六成的獲利，但 放任法 卻虧了近 9 倍。因為 放
任法 接受了所有的預約，導致空車位無法負荷，造成大量的預約賠償。
預約點 6:00 6:30 7:00 7:30 8:00 8:30 9:00
已預約量 ０ ０ ０ ０ ０ ０ ０
未來預約量 ２０0 ２０0 ２０0 ２０0 ２０0 ２０0 ２０0
第 42 頁，共 42 頁
第四章 未來工作及結論
第一節 未來工作
在論文的一開始 ，我們就對預約環境作了一些假設，若將這些假設也考
慮進去，則會有更大的獲利空間。
假設:
任何時後均有車輛等待要進入停車場。
有預約的車輛一定會到。
n 當停車場要關閉現場臨時停車時，此時，停車場並非全滿。
我們假設任何時候均有車輛等待進入停車，所以這時候停車場應該
是全滿，但實際上已經有空車位。所以，我們必須把這些空車位用
掉，因此可適度的延後關閉現場臨時停車讓現場停車輛來補滿這些
空車位。
n 預約的車輛，不可能在所預約的時刻一次全部到齊。
例如，若7:00 有 30 輛預約停車，不可能 30 輛都在 7:00 的時後
到達停車場。所以停車場可適度的偷偷讓現場停車來遞補空缺。
n 預約未到:
不可能百分之百的預約都會到，所以，我們也可適度的讓現場停車
來遞補預約未到的車位。
第 43 頁，共 43 頁
第二節 結論
本篇論文一開始制定了預約規則，並探討預約的特性；詳細的討論，預約量
(Z)，保留量(X)及提前時間(T)，並分析三者之間的關係。所有的考量均以取
得最大獲利為宗旨。假定每個預約點會被預約的數量已知，反推該接受幾個
預約，保留幾個車位以及何時該關閉現場臨時停車。程式不斷的執行，算出
每個時間點的最大獲利，並求出每個預約點的預約量，保留量及提前時間。
停車場只需依據此三個變數即可控管車流量。
為了簡化討論，我們定義了 Group，將討論的範圍限定在 Group 內。並架
構在 Group 上，推演出 Parking Algorithm。論文中並提出了 Parking
Algorithm 的加速方法，並解析了相關的數學式，最後比較此演算法在獲利
上的表現。
預約規則:
預約時間: 開放 24 小時預約，每 30 分鐘一個預約點。
預約加價: 提高預約停車的費用。
預約賠償: 發生無法滿足預約車位時，停車場要付的賠償費。
變數定義:
預約量: 每個預約點可接受的預約數量。
保留量: 每個預約點該保留的車位數目。
提前時間: 每個預約點提前關閉現場臨時停車的時間。
Group
連續的 M 個預約點
前面的預約點需要為後續預約保留的車位
Parking Algorithm 是利用 Greedy Algorithm 由後往前減少 Group 最後一點
的預約量，找尋最大獲利。並利用機率的觀念求出 Group 獲利的期望值。
Parking Algorithm 可很有效率並以極為簡單的方式，決定停車場對於預約流
量及現場車流量的處理。值得一提的是，因預約而得到的獲利非常可觀，在
預約加價為兩倍的情況下，停車場可以多到近六成的獲利。這對停車場的業
者而言，可說是一大福音。
其他應用
此預約系統的應用面極廣，可套用到其它非常多類似的系統。例:
頻寬的預約
當在網路上傳大量的即時資料時，例如視訊會議，此時應用軟體為保證有良
好的 QOS，將會向路由器(Router)要求保留頻寬。但在一些黃金時段，跟本
保留不到。 所以, 若路由器(Router)也開放頻寬的預約，則預約情況將和停
車場極為相似。
諸如此類的預約不勝枚舉，就等待您的發覺囉!
摘要
電子商務正在改變人類的生活，新興的行業如雨後春筍般不停的浮現。創
意帶來商機，二十出頭歲的年輕小伙子就擁有億萬財富。本篇論文以一個網路預
約停車的構想，引出預約背後所需解決的數學問題，用以求得最大獲利。
此篇論文假設停車位一位難求。駕駛員寧願花較高費用，經由網站來預約車
位，以確保有車位可停。停車場則將預約的流量以及臨時停車的車流量用Poisson
的出現機率來表示。以取得最大獲利為目標來控管停車流量。
第 6 頁，共 6 頁
第 7 頁，共 7 頁
目錄
第一章 緒論_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _ _ _ 8
第一節 前言_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 8
第二節 環境定義_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 9
第三節 論文章節編排_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 0
第二章 預約的特性及演算法_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 1
第一節 預約的特性_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 1
§ 2. 1. 1 : 預約量( Z) _____________________________________________ 11
§ 2. 1. 1 : 提前時間( T) ___________________________________________ 12
§ 2. 1. 2 : 保留量( X) _____________________________________________ 14
§ 2. 1. 3 : 多個預約點____________________________________________ 16
§ 2. 1. 4 : 預約過量______________________________________________ 18
§ 2. 1. 5 : 影響預約量的因素______________________________________ 20
§ 2. 1. 6 : 每個預約點接受幾個預約呢?_____________________________ 22
第二節 演算法( Parki ng A l gori thm) _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 2 5
§ 2. 2. 1 : Parki ng Al gor i t hm_____________________________________ 25
§ 2. 2. 2 : 範例討論______________________________________________ 29
第三章 演算法的加速及數學式_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 3 1
第一節 演算法的加速_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 3 1
第二節 數學式_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 3 2
第三節 結果比較_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 4 0
第四章 未來工作及結論_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __ _ _ 4 2
第一節 未來工作_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 4 2
第二節 結論_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 4 3
參考文獻: _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _ _ _ _ 4 5
第 8 頁，共 8 頁
第一章 緒論
第一節 前言
在許多擁擠的都市，停車已經變成了一種夢魘。 有時候，為了參加一個短
短的會議，可能要花上比會議還長的時間停車。又要擔心被拖吊或因此錯過
會議時間，造成諸多不可預期的結果。因此，若駕駛員能在出門前就確定有
車位可停，這樣將可有效的解決停車問題。
預約停車的服務，除可免除找不到停車位的困窘，亦可藉由預約的通訊設備
(例: 網路)，告知駕駛員停車場的現況。可避免駕駛員擠在同時段停車或停
在同一個停車場，能有效的將停車流量攤平。不過，問題也來了，停車場要
如何處理預約停車，如何保留車位以及何時該關閉現場臨時停車，才得到最
多的獲利呢？
在此，我們將利用 Queueing 數學理論來看預約系統，求得預約的最佳化。
首先，將定義預約的環境及變數，分析預約的特性，再依這些特性提出一套
演算法(Parking Algorithm)，來找尋擁有最多獲利的預約狀況。接著是此演
算法的加速方法及相關的數學式。最後，將舉例討論停車場能由預約服務而
多得的獲利。
結論中，我們將指出可改進的地方，並將此觀念推廣到頻寬，飯店.. 等的預
約，可見此預約系統的應用面極廣。
第 9 頁，共 9 頁
第二節 環境定義
假想，我們身處在一個交通擁擠的都市，連出門都怕找不到停車位。幸運
的是，駕駛員可在出門前就先行預約，以確保有車位可停。但在享受此服務
的同時，駕駛員則則必需付出額外的費用；相對的，停車場為滿足預約停車，
也必需付出保留車位的代價。因此，就有了以下的預約規則:
1. 停車場開放24 小時預約，每隔半小時一個預約點。
(例: 8:00、8:30、9:00 …。)
2. 預約加價: 因為駕駛員要享有保留車位的服務，所以停車費用
加價。(例: 兩倍價 )
3. 預約賠償: 若駕駛員已先行預約，但到停車場時，卻無車位可
停，此時停車場需付給駕駛員的賠償。 ( EX: 800 元)
此篇論文的目地，就是要在上述的預約規則下，利用 Queueing 數學理論來
看預約系統，求得預約的最佳化，找出每個預約點所能接受的預約量，該保
留多少車位數，以及何時該關閉現場臨時停車。在進入主題前，我們需作些
假設及定義計算中會用到的變數。
假設:
1. 任何時候均有車輛等待進入停車場。
l 因若無車輛等待要進入停車場，那駕駛員亦無需預約。
l 其他沒有車輛等待進入停車場的情況，停車場因預約停車
而多得的獲利將增加。
2. 有預約的車輛一定會到。
l 停車場可用一些限制來逼近假設。
例: 只要一預約，停車場將先行收取半小時的預約停車費。
若半小時內沒出現，停車場就將此預約視為自動放棄。
3. 停車場的車輛以 Poisson [1]
的機率離開。
f(x)= 1/β * e-x/β , x 停車時間; β 平均停車時間。
變數:
n 停車場總車位數 α 個(例: 200 個)
n 平均停車時間 β 分鐘(例: 100 分鐘)
第 10 頁，共 10 頁
第三節 論文章節編排
在此論文中，第一章簡介為何要預約以及預約的環境，第二章介紹預約的特
性，再依這些特性提出一套演算法(Parking Algorithm)求得預約的最佳化，
第三章介紹加快演算法的方法以及相關的數學式，第四章 舉例討論停車場
能因預約服務而多得的獲利，最後，將列出可改進的地方和相關的應用。
第 11 頁，共 11 頁
第二章 預約的特性及演算法
第一節 預約的特性
§ 2.1.1 :預約量(Z)
在論文一開始所制定的預約規則下，停車場開放 24 小時的預約，每隔 30
分鐘一個預約點，也就是說預約者可在 8:00，8:30，9:00 …等，來預約停車，
停車場將會為預約者保留車位，這樣預約者就可以免去找尋車位的問題。不
過，因為預約者享受了保留車位的服務，所以停車的費用加價以避免預約者
隨意的亂預約，停車場也可藉由預約加價增加獲利。可以說是一個雙贏的方
法。 所謂的預約量(Z) ，就是，每個預約點停車場被預約的車望數量。
第 12 頁，共 12 頁
§ 2.1.1 :提前時間(T)
停車場在接受預約之後，一定要設法空出足夠的空車位來滿足預約。因為若
無法滿足預約的車位，將會損失大量的預約賠償，這樣將導致停車場的獲利
下降，反而造成虧損，完全享受不到預約加價所帶來的獲利增加。那停車場
到底要如何空出車位呢? 最簡單直覺的方法就是提前關閉現場臨時停車，讓
停車場內的車輛慢慢離開，也就是說停車場的車輛有出無進，自然而然空車
位的數目就會持續的增加，這樣就有足夠的空車位來滿足預約的車位。所
以，可選定一個預約點為基準，例如: 9:00 的預約點，然後提前T 分鐘關
閉現場臨時停車，來空出停車位。我定義T 為 “提前時間”。
停車場要如何決定 T 的大小呢? 當然，停車場將以獲利為考量，以取得最
多獲利為宗旨。所以首先我們將先探討影響獲利的因素，影響獲利的因素有
三，一、停車場可藉由收取預約加價的費用來增加獲利。二、停車場要避免
空車位不足的發生，因為空車位不足將無法滿足所有的預約而需負擔預約賠
償。三、若停車場保留的車位數太多，或保留的時間太長，這樣都會造成浪
費。因為多出來的空車位可讓現場臨時停車來補滿。基於以上的考量，若T
值太大，也就是說，停車場太早關閉現場臨時停車，這種情況將會發生保留
過多車位的問題，而且保留的時間也會拉長，都將造成浪費。相對的，若 T
太小，停車場的車輛來不及離開，也就是說空車位太少了，這樣將無法滿足
所有的預約，導致需負擔預約賠償的虧損。所以，停車場需找到一個最佳的
T 值，讓停車場在 T 分鐘內剛好離開預約的數量，而這些空車位又能百分
之百由預約車輛填滿，不會有空車位太多，或不足的現象。如此，停車場將
能得到最大的獲利。決定 T 值得大小，將是本篇論文的重點之一。論文中
將利用找尋獲利的最大值來決定 T 值得大小。
以下將以一個簡單的例子，來說明如何決定 T 值得大小。如圖一，首先定
義預約的環境，停車場共有 200 個車位，平均停車時間是 100 分鐘，預約
加價是兩倍，預約賠償 800 元，每分鐘停車費用 1 元。停車場接受了 90 個
9:00 的預約，由 表一 可得知，若 T 等於 46 分鐘， 也就是說停車場提
前在 8:14 分的時候就關閉現場臨時停車，慢慢地讓車輛離開停車場，以滿
足 9:00 的 90 個預約，剛剛好能滿足預約，所以 46 分鐘是一個最佳
值。若 T 小於 46 分鐘將造成空車位足而損失預約賠償，若 T 大於 46 分
鐘，將造成空車位太多的浪費。
第 13 頁，共 13 頁
圖一; 提前時間; 9:00 預約了90 個車位，停車場
於 8: 14開始關閉現場臨時停車以空出足夠的空
車位。提前時間: 46 分鐘。
表一; 提前時間和多賺的
對照表; 若提前 46 分鐘
關閉現場臨時停車，停車
場將會有最有最多獲利。
提前的時間(T) 多賺
44 分 4528.61 元
45 分 4566.62 元
46 分 4581.70 元
47 分 4580.25 元
48 分 4567.49 元
90
全滿
8:00 8:30 9:00
46 分
預約量
變數
停車場車位數: 200 個
平均停車時間: 100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
第 14 頁，共 14 頁
§ 2.1.2 :保留量(X)
因為停車場要設法保留車位來滿足預約，所以最簡單的方法就是提前關閉現場臨
時停車，讓停車場的車輛自由的離開。但問題也來了，因為是讓車輛自由的離開，
所有，有時候可能一瞬間離開好多輛，也有可能久久都沒有任何一輛車離開，這
要怎麼辦呢? 最簡單的方法，當然就是在每個預約點來調整保留車位的數量，以
減少自由離開所產生的不確定因素。首先，我們將先看兩種保留車位的情況，一、
我們先給定某預約點P，例如 圖二 8:30 的預約點，來調整保留車位的數量。若
我們發現 P 點保留的車位嚴重不足，停車場車輛離開的速度太慢，根本無法滿
足所有的預約，眼看就要負擔大量的預約賠償。這時候要如何呢? 當發生這種情
況，那就真的沒救了，因為我們不可能將停車場的車輛趕走，又沒有多餘的車位
來救急。所以這種情況將無法調整。二、若我們發現 P 的的空車位太多，也就
是說停車場的車輛以快於平常的速度離開，這時候，我們將適度的由現場臨時停
車來補滿空車位。那P 點到底要保留多少個車位呢? 我們定義，P 點保留車位
的數目為保留量(X)。
同樣的，若 X 太小，這樣將導致空車位不足，而無法滿所有的預約，需要負擔
大量的預約賠償，停車場的獲利會因此而下降。若 X 太大，將會造成空車位太
多或保留的時間太長，而造成了浪費。所以，和提前預約時間(T)一樣，我們需
求得一個最佳值。如何求得最佳值，將是本論文的重點之一，我們將利用找尋停
車場最大的獲利，來決定 X 值。
此外，由預約點來調整是唯一的方法嗎? 答案是否定的。若我們將調整的間格縮
小將會提高保留車數目的準確度，也就是說保留車位的數目在嚴密的監控下，最
有可能百分支百等於預約的數量。這邊，我們是以最方便的方法來監控。
圖二 所舉的例子和 § 2. 1. 1 完全相同。在 9:00 的預約點，被預約了 90 個車
位，停車場提前 46 分鐘，於 8:14 分關閉現場臨時停車，所以我們可在 8:30 的
時候來調整空車位數，若 8:30 可保留 30 個車位，這樣將可有最多獲利。若 8:30
實際停車場的保留車位大於 30 個，多出來的車位將由現場臨時停車補滿。若小
於 30 個，則無法調整。
第 15 頁，共 15 頁
提前的時間(T) 多賺 8:30 車位保留數
46 分 4581.705 元 30 個
全滿
8:00 8:30 9:00
90
46 分 ( T )
圖 二; 保留量; 若停車場在 8:30 保留 30 個
車位，將可得最多獲利。
30; 保留量( X)
保留量
預約量
變數
停車場車位數: 200 個
平均停車時間; 100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
第 16 頁，共 16 頁
§ 2.1.3 :多個預約點
之前的討論，都是只有一個預約點有預約量。現在將考慮同時有多個預約點
均有預約量的情況。當考慮多個有預約量的預約點時，每一個預約點同樣都
要提前關閉現場臨時停車(T) ，但，值得注意的是，同時考慮多個預約點時，
T 最大只能 30 分鐘，其餘的不足的空車位，將算在前一個預約點的保留量
身上，也就是說，每一個預約點所需的空車位，將由前一個預約點保留量，
以及 T 分鐘內停車場內車輛離開的數量所提供。所以，每一個預約點的空
車位數量，要能同時每滿足預約停車的數量又要能滿足保留量。 可見，他
的情況有稍稍的複雜一點。首先，我們給定多預約點內的某個預約點 P，因
為 P 點的空車位要同時滿足預約量及保留量，那到底要做怎樣的分配呢?
我們需考慮到，空車位有可能太多，大於預約量加上保留量 。反之，也有
可能太少，連預約量都無發滿足。由預約的規則我們可知，最大的損失莫過
於要負擔預約賠償，所以說，每一個預約點的空車位第一要緊就是趕快讓預
約停車進入停車場。再來才是保留給保留量，因為，若 P 點無法滿足保留
量，將會提高後續預約點無法滿足預約量的機會，所以說，無法滿足保留量
將是一種潛藏的損失。若空車位太多呢? 如果空車位的數目大於預約量加上
保留量，多餘的空車位將由現場臨時停車補滿，這就是保留量原先調整保留
車位的功能。
在圖三，我們將時討論 4 個預約點，時間是 7:30 ~ 9:00 。我們將先利用
Parking Algorithm(將在 2.1.1 節介紹)求得此四個預約點在獲利最多時，每
一個預約點所能接受的預約量、保留量及提前關閉現場臨時停車的時間。我
們將可看到，在獲利最多時，對 7:30 的預約點而言，停車場必須提前 18 分
鐘，在 7:12 分時關閉現場臨時停車，開始讓停車場的車輛離開，以滿足20
個預約車位， 15 個保留車位， 若 7:30 的空車位數大於 35 (20 + 15)個，
也就是說停車場車輛離開的速度太快，這時候多出的車位將由現場臨時停車
補滿。對 8:00 的預約點而言，提前 30 分鐘(沒有標明時間代表提前 30 分
鐘)關閉現場停車，需滿足 50 個車位，保留 13 個車位，若空車位大於
63(50+13) 個，將由現場臨時停車補滿。8:30 和 9:00 的情況亦同。
所以說，我們秉持一個最基本的原則，要讓停車場的獲利達到最大值。對每
一個預約點而言，只需要知道，該預約點可接受多少個預約量，多少個保留
量，要提前多久關閉現場臨時停車，這樣可將預約的處理變得很簡單。
第 17 頁，共 17 頁
圖三; 多預約點的預約量及保留量;
在考慮多個預約點時，每一預約點均需
滿足預約量及保留量。
預約點 7:30 8:00 8:30 9:00
保留數 15 個 13 個 5 個 0 個
預約數 20 個 50 個 53 個 46 個
7:00 7:30 8:00 8:30 9:00
18
變數
停車場車位數: 200 個
平均停車時間; 100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
53 46
5
50
13
20
15
全滿
保留量
預約量
第 18 頁，共 18 頁
§ 2.1.4 :預約過量
現在我們又暫時跳回只考慮一個預約點有預約量的討論，假若只有 9:00 的
預約點有預約量，那我們可以沒有限制地讓預約者持續的預約該預約點嗎?
可否讓停車場的所有的車位被預約一空呢?這些答案都是否定的。為什麼呢?
我們將先觀察停車場車輛離開的行為: 當我們關閉現場臨時停車後，停車場
的車輛一輛輛的離開，也就是說停車場內的車輛漸漸的減少，當停車場內的
車輛減少，整個停車場空出車位的機率總和也降低了，也就是說，停車場空
出車位的速度將漸漸的變慢。這個時候，我們又必須考慮到，停車場內已經
有很多的保留車位，所以保留車位所照成的浪費將隨之增加。因此，我們可
以得知保留車位的浪費將會隨著所需要的空車位數量增加而增加。若所需的
空車位大於某一個數量，也就是說當我們的預約量大於某一個數量，停車場
因預約而得的獲利，將小於保留車位所造成的損失。如此，若持續的接受預
約，將導致獲利下滑。
由 圖四 的表格中，我們可以很清楚的看到，若預約量小於 93 個，增加預
約量將會使得獲利上升。所以，接受 92 個預約，所帶來的獲利將大於 91
個，接受93 個的獲利又大於 92 個，這時增加預約量將會使得獲利上升，
但當接受的預約量為 94 個的時候，獲利反而下降了，也就是說，這個時候
的預約量已經太多了，增加的預約量所到來的獲利，將小於保留車位少造成
的損失。我們稱這種情況為預約過量，該預約點為預約過量點。
那我們要如何找尋預約過量的預約點呢? 此篇論文先假設所有預約點的預
約量都是已知，然後減少該點的預約量看看是否會使獲利增加，若能使獲利
增加的話，那就表示該點的預約過量了。
第 19 頁，共 19 頁
預約量 多賺
90 個 5191.63 元
91 個 5196.41 元
92 個 5196.99 元
93 個 5198.42 元
94 個(預約過量) 5197.94 元
預約量
多賺
全滿
8:30 9:00
變數
停車場車位數: 200 個
平均停車時間:100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
8:00
圖 四；預約過量；當預約量超過 93 個時，獲利將下
滑；也就是說此時已經預約過量，減少該點的預約量
將可使獲利增加。
93
第 20 頁，共 20 頁
§ 2.1.5 :影響預約量的因素
當考慮多個預約點都有預約量時，到底是那幾個預約點的預約量太多了?到
底要接受幾個預約才能擁有最多的獲利呢?首先我們將討論每個預約點接受
的預約量會受到那些因數的影響。在下一小節§ 2.1.6 才會提出方法來找尋
預約過量的預約點，且決定要減少多少個預約量才能讓停車場的獲利達到最
大值。
預約量和保留量的平衡
當考慮多個預約點均有預約量時，那每一個預約點的空車位不但要滿足預約
量，以避免發生已預約的車輛無法停車而浪費預約賠償，也需要滿足保留量
以確保後續的預約均有車位可停。但每個預約點的空車位有限，在多個預約
點都有預約量時，每一個預約點都希望前面的預約點能夠為他保留車位以減
少本身發生空車位無法滿足預約的現象，且每一個預約點也都想多接受一些
預約，以增加預約所帶來的獲利，但增加預約又導致需要前面的預約點為他
保留更多的車位。所以說，這是一個雙向馬車，想要增加預約量，但空車位
又有限，增加預約量又需往前增加保留量。所以我們必須取得一個平衡點。
攤平預約量
再來我們要討論的是，保留車位的浪費和預約車位的獲利之間的微妙關係。
因為我們希望多接受一些預約來增加預約所帶來的獲利。但隨之而生的是，
空車位的需求也要增加，但停車場空出車位的速度隨著停車場的車輛減少而
漸漸變慢，所以需要拉長保留車位的時間才能讓停車場從容的空出足夠的車
位，造成浪費變大。也就是說，當接受的預約車位增加後，預約所帶來的獲
利扣除保留車位的浪費，所得的淨利將慢慢的變少，最後將由正值轉成負值
而發生預約過量的情況。所以我們就能得到以下的結論: 如過能夠將預約量
平均的攤在每一個預約點，不要發生某一預約點接受了太多預約量的情況，
將可有最多獲利。因為這個時候，預約所帶來的獲利扣除空車位的浪費，所
得的淨利將比後續所接受的預約所帶來的獲利大。
最小預約量
因為我們將預約的時間以 30 分鐘為預約間隔，將一天分為 24 個預約點。
這時，我們給定某一預約點 P，若停車場在 P 的前一個預約點時，停車位
全滿，也就是前一個預約點完全沒有為 P 點保留任何車位，這個時候， P 點
第 21 頁，共 21 頁
所能接受的預約數量最小。只能靠預約間隔的時間停供給停車場，讓停車場
的車輛慢慢離開，以便空出車位來滿足預約。所以每個預約點所能接受的預
約量有一個下限，我們稱這個下限為最小預約量。例如，在圖四 的預約變
數下，其下限為 46 個。
寧願接受前面預約點的預約
若有兩個相鄰預約點 a、b ， a 在b 的前面，且a 需要為 b 保留車位 。
現在有一預約者想要預約，請問他預約那一個預約點能夠為停車場帶來較大
的獲利? a 或 b? 答案是 a。為什麼呢? 因為若預約者預約 b 點 ，則 a 點
的保留量將增加，以確保 b 點能夠滿足預約，而且不管預約任何一點，停
車場所接受的預約量都一樣，但若預約 b 點，將會拉長保留的時間，導致
保留車位的浪費加大。這裡所舉的例子只為方便說明。”寧願接受前面預約
點的預約” 適用在任何需為後續預約保留車位的任何兩個預約點。
第 22 頁，共 22 頁
§ 2.1.6 :每個預約點接受幾個預約呢?
停車場如何決定每個預約點該接受幾個預約? 當然，不二法則的考慮因素
“擁有最多獲利”。首先，我們假設每個預約點將來會被預約的數量都是已
知。然後由會被預約的數量去反推每個預約點應接受多少個預約，才能讓停
車場擁有最多獲利。為了簡化討論，我們將定義 Group
Group
連續的m 個預約點
前面的預約點需為後續的預約點保留車位
其實，Group 就是相互影響的一群預約點。前面的預約點需要為後續的預約
點保留車位，彼此相互影響。Group 的目的就是要將影響的範圍限制在m
個預約點。我們可藉由對 Group 的討論，延伸到所有的預約點，以求得每
個預約點應接受多少個預約，才能讓停車場擁有最多獲利。一開始，我們已
經知道 Group 內每個預約點將來會有幾個預約，那每個預約點個別要接受
幾個預約才能讓 Group 的獲利最多呢? 要如何反推可接受的預約量呢?我
們可藉由減少預約量，看看是否會增加 Group 的獲利，以決定是否預約過
量。那我們要如何減少呢? 要減少那一個? 首先我們回想在§ 2.1.5 影響預
約量的因素，”寧願接受前面預約點的預約” 我們希望預約者預約前面的預
約點，這樣保留車位的時間才不至拉長。由此可知，若一個 Group 的預約
量太多了，則我們將減少後面的預約，因此，我們得到一個結論:
由後往前減少預約量
所以，將由 Group 的最後一個預約點開始減少預約量。再來所要頭痛的是，
那要減少幾個呢? 其他預約點是否也有預約過量呢? 如何找到下一個預約
過量點呢? 首先，我們第一個問題，”要減少幾個預約?” 這時又得搬出大原
則，”讓停車場獲利最多” ，然後我們將丟給 Greedy Algorithm 持續減少
最後一點的預約量，讓 Greedy Algorithm 自己去跑出最大獲利時的預約，
詳細步驟如下:
利用Greedy Algorithm 求 Group 的最多獲利
步驟一: 給定Group 內的所有變數:
預約點: m 個
預約量: Z1~Zm
保留量: X1-Xm
第 23 頁，共 23 頁
提前時間:T
值得注意的是，為什麼只有一個提前時間(T) 。因為 Group 的每一個預約
點均需為後續的預約保留車位，也就是現場臨時停車在最後一個預約點結束
後才會再開啟。再來，Group 中間任何一個預約點的空車位若大於預約量加
上保留量，多出來的車位將由現場臨時停車補滿。另外，我們將每一預約點
將來會被預約的數量當作預約量，所以，每一個預約點的預約量是可以減少
的。例如 圖五 Group 內總共有 4 個預約點 7:30 ~ 9:30 ，預約量分別
為: Z1、Z2、Z3、Z4，保留量為: X1、X2、X3、X4 ，提前時間是 T。
步驟二: 減少最後一點的預約量，來找尋最大獲利
之後，我們開始減少最後一點的預約量，再丟給 Greedy Algorithm 讓
Greedy Algorithm 改變 T、X1~Xm 的變數，求得 Group 的最大獲利。所以，
我們就可以知道最後一個預約點該減少多少的預約量，才能讓停車場擁有最
大的獲利。
步驟三: 找尋下一個預約過量點
在決定最後一個預約點該減少多少的預約量後，我們必須再找尋下一個預約
過量點，然後減少該點的預約量以增加停車場的獲利。那，到底那一個預約
點的預約數目過量了。我們如何找到它? 其實很簡單，我們只需由後往前，
減少每一預約點的預約量，若發現減少該點的預約量能使 Group 的獲利增
加，該點就是下一個預約過量點。
7:00 7:30 8:30 9:00 9:30
保留量
預約量
圖 五; Gr o u p 的預約過量; 7: 30 ~9: 30 為一 Group，預約
量: Z1~Zm ，X1-Xm
T
X1
Z1
Z2 Z3
Z4
X4
X2
X3
第 24 頁，共 24 頁
步驟四: 忽略新預約過量點以後的預約
當我們由後往前減少每一個預約的預約量，然後檢查 Group 的獲利是否增
加。若發現減少某預約點 P 的預約量後，能使 Group 的獲利上升，那 P
點就是下一個預約過量點。很重要的一件事情是，我們將不再考慮 P 的後
面的預約量了，為什麼呢? 因為P 點後面的預約量將無需再改變，Group 即
可得到最多獲利? 那為何會如此呢? 因為:
1. 不可能增加: P 點是一個預約過量點，所以我們將會減少該點的預約
量以增 Group 的獲利，所以將會減少P 點的預約量。我們回想在§
2.1.5 影響預約量的因素，”寧願接受前面預約點的預約” ，將可得
知，我們不可能減少 P 點的預約，只是為了滿足後面的預約，也就
是說，P 點後面的預約量，不會因 P 點的減少而增加，所以不可能
增加。
2. 不可能減少: 因為Ｐ點的預約量減少了，所以可以接受更多的保留
車位，後續的預約點將可接受更多的預約量。也就是說，後續的預
約點不可能因 P 點預約量的減少反而只能接受更少的預約量。所以
不可能減少。
因此，我們根本無須變更後續預約點的預約量。
所以 P 點以後的預約點將由 Group 中剔除。然後我們重新執行 步驟二.
減少最後一個預約點的預約量，之後再找下一個預約過量點。直到 Group 內
沒有預約過量點。此外，我們必須注意到， 步驟四: 忽略P 點以後的預約
量，這樣會導致 P 點的保留量不正確，但此時 P 點所需的保留量極小，因
為 P 點預約過量點，表示所有的空車位幾乎全部都給了預約量，因此根本
沒有多餘的空車位可以給保留量。故誤差極小。
第 25 頁，共 25 頁
第二節 演算法(Parking Algorithm)
本篇論文的目的，就是要讓停車場知道: 若要擁有最多獲利，每一個預約點要接
受幾個預約，保留幾個車位，提前多久關閉現場臨時停車。經過了這麼多的準備
後，我們終於可以真正踏入主題了。在此，將提出一套演算法 Parking Algorithm
來求得停車場擁有最多獲利時，每個預約點的預約量、保留量及提前時間。
§ 2.2.1 :Parking Algorithm
Parking Algorithm 分為兩部分: 第一部份，先預估每一個預約點將來會被預約的
數量。第二部分，利用 Greedy Algorithm 來求得獲利最多時，每個預約點應接
受幾個預約，保留幾個車位，提前多久關閉現場臨時停車。整個演算法都是架構
在 Group 上，以 Group 為一個討論的範圍。
2.1.1.a 估算每個預約點的預約量
首先，將先估算每一個預約點將來會被預約幾個車位也就是每一個預約點的起始
預約量。 預約量來自於已經預約車位的數量加上將來可能會再預約的數量。
預約量 = 已預約量 + 未來預約量
已預約量是指程式執行時已最被預約的車位數目; 未來預約量是指該預約點將
來有可能會再被預約的數量。我們需小心的是，已經預約的數量是不可以減少
的，所以當利用 Greedy Algorithm 減少Group 最後一個預約點的預約量，以找
尋最多獲利時，這些已預約的車位是不可以減少的。那未來預約量要如何求得呢?
首先，我們對每一個預約點作如下表的時間及預約速度的對照表;
距離第 i 個預約點的時間 第 i 個預約點 的預約速度(個/分)
0:00 - 1:00 R1
1:00 – 2:00 R2
2:00 – 3:00 R3
3:00 – 4:00 R4
針對每一個預約點，例如第i 點，找出距離此預約點的時間及預約速度的對照表。
在上表中，距離第 i 點的時間是指，程式執行時間到第 i 個預約點的時間。假
設程式執行時，距離第 i 個預約點的時間為 3 時40 分。那，第i 點的未來預約
量為何?
未來預約量 =
Rj * 60 R4 * 40
j 1, 2 ,3
å +
=
第 26 頁，共 26 頁
如此，我們就可很容易的預估出所有預約點的未來預約量。
第 27 頁，共 27 頁
2.1.1.b 程式的流程
再來將解釋整個程式的流程:
程式的目的:
求得停車場獲利最多時，每個預約點應該接受預約的數量、要保留的車位數目、
及何時關閉現場臨時停車。
先給定兩的變數: S、E
S: Group 的第一個預約點
E: Group 的最後一個預約點
步驟一: 估算所有預約點的預約量
必須取得每一預約點已經被預約的車位數目，然後各自算出每一預約點將來還會
在被預約的車位數目，然後將兩者相加，即為該點的預約量。
步驟二:
將所有預約點的最後一點加入 Group
2 . S = E = L a s t Poi nt of a l l
步驟三:
然後減少 Group 最後一點的預約量，找尋 Group 獲利的最大值。並求得每一預
約點在最多獲利時的預約量、保留量、提前時間。
3 . Gr e e dy a l g or i t h求m出 Gr o u p 的 Z , X , T
步驟四:
由後往前找尋 Group 中，下一個預約過量的預約點，然後設定新預約過量點為
Group 的最後一點。也就是說，我們忽略的新預約過量點以後的預約點。
4 . f or ( i = E t o S )
i f ( Poi nt i Ov e r k ooi ng ) E = i ;
步驟五:
若發現，經由 Greedy Algorithm 所求得的提前時間 T 大於預約間隔，也就是
說，前一個預約點需要為後續的預約保留車位，程式將往前將此點加到 Group，
然後跳到步驟二: 否則，程式將找尋下一個 Group 。 找尋的方法很簡單，只要
把 S 的前一個預約點設定為Group 即可 。
5 . i f T >預= 約間格 t he n S- -; ( Add ne w poi nt t o Gr o u p)
e l s e S =- -S; E = S ; ( New Gr ou p)
步驟六:
然後，將所有的預約點處理完畢。這樣就能夠得到再最佳獲利時，每一個預約點
第 28 頁，共 28 頁
要保留幾個車位。當處理完畢之後，這時已經有新的預約被接受，所以我們必須
再從新估算預約量，再重新處理所有的預約點。 所以，整個預約的全程，程式
需不停的求出每個時間點的最大獲利，因為預約量一值在變，不同的預約量就會
導致不同的獲利。
最後還需修改的地方是，因為程式的預約量包含了已經預約的車位數量及未來可
能會預約的數量。未來還會在預約的數量，我們可以不接受，但已經接受的預約
是不可以反悔的。所以，當 Greedy Algorithm 減少Group 最後一個預約點的預
約量時，若該點只剩下已預約車位數，那 Greedy Algorithm 就把它視為已經找
到最多獲利了。
程式虛擬碼:
1.估算預約量
2. S = E = Last Point of all
3. Greedy algorithm 求出 Group 的 Z,X,T
4. for (i =E to S)
if (Point i Overkooing) E = i;
5. if T >= 預約間格 then S --; (Add new point to Group)
else S = S--; E = S;(New Group)
6. If E>0 Jump 3. else Jump 1.
第 29 頁，共 29 頁
§ 2.2.2 :範例討論
以下將以一個簡單的例子，討論程式的執行結果;
時間: 6:00 ~ 9:00
程式一開始，將先求得每個預約點的預約量，所以，我們去必須取得已經預約的
車位數目及未來可能預約的車位數目:
預約量 = 已預約量 + 未來預約量
執行完一次 Parking Algorithm 之後，我們得到每一個預約點在最多獲利時的預
約量，保留量及提前時間。
預約點 6:00 6:30 7:00 7:30 8:00 8:30 9:00
已預約量 0 1 10 30 53 40 10
未來預約量 3 4 10 20 47 80 20
變數
停車場車位數: 200 個
平均停車時間; 100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
保留量
預約量
5
6:00 6:30 7:00 7:30 8:00 8:30 9:00
46
50 53
20
5 30
6 18 22
15
13
3
5
3 個小時
6:00 6:30 7:00 7:30 8:00 8:30 9:00
100 120
50
3 5 20 30
預約量
第 30 頁，共 30 頁
最重要的是，停車場要如何依據所得到的資料來處理現場臨時停車以及預約停車
呢? 在此，將以預約點為主角: 預約點6:00 的提前時間是 5 ，所以停車場於5:55
關閉現場臨時停車，6: 30 之後在開啟; 預約量是5 ，但已經被預約了一個車位
所以還可再接受 4 個預約; 不需要保留車位。再來是討論，預約點 7:00，提前
時間是18 ，所以於 6:42 關閉現場停車，7:00 再開啟;預約量是 20，但已經有
10 個車位被預約了，所以還能再接受 10 個預約; 保留量是 15 ，所以需要保
留 15 個車位。再來是預約點 7:30，提前時間是 30 ，於 7:00 關閉現場停車;
7:30 在開啟; 預約量是50 ，已經接受了 30 個預約，所以還可再接受 20 個預
約; 保留量是 13 ，所以需要保留 13 個車位。其他每一個預約點均是如此處
理。那停車場任何時候都可由上述資料得知該做那些相對的動作。
第 31 頁，共 31 頁
第三章 演算法的加速及數學式
第一節 演算法的加速
在演算法的流程中，我們會利用 Greedy Algorithm 來找尋獲利最多時，Group
預約量、保留量及提前時間。若T 大於約間格，我們將會往前加入一個的預約
點到Group 中，然後重新跑 Greedy Algorithm 再次找尋新Group獲利最多時，
Group 預約量、保留量及提前時間。所以，此演算法將會持續的使用 Greedy
Algorithm。也就是說，此演算法的速度取決於 Greedy Algorithm 的快慢。若我
們想加快演算法的速度，就必須有效的加快 Greedy Algorithm 的速度。
方法: 有效的預估每一預約點該保留多少車位(Xi)
當我們往前加入一個預約點到Group 後，會再次利用 Greedy Algorithm 減少新
預約群最後一個預約點的預約量，以找尋獲利最多的預約。所以原有的預約量只
會減少，也就是說，保留車位的數目也只會減小。因此，當我們再次利用 Greedy
Algorithm 找尋獲利最多的預約情況時， 每一個預約點的保留量可以用原有保留
量為初始值，然後以遞減的方法找尋新的保留量，如此將可快速的找到新Group
獲利最多的預約狀態。
圖六; 原有的保留量只可能減少; 當加入新預約量到 Group 時，原有的
預約量只可能減少，所以保留量也只可能減少
時間軸
T
X1
X2 X3
保留量
預約量
第 32 頁，共 32 頁
第二節 數學式
在演算法的流程中， 我們會利用 Greedy Algorithm 來找尋獲利最多的預約。所
以，演算法必需求得每種預約情況Group 的獲利。因此，我們將討論的數學式，
其目的就是要求出 Group 獲利的期望值。
目的: 求出Group 獲利的期望值
整個運算的過程分為四個步驟:
1. 求得單一個預約點的獲利
2. 求得整個 Group 的獲利
3. 考慮保留車位的浪費
4. 算出Group 獲利的期望值
首先，先給定預約的相關變數:
如圖:
步驟一、求得單一個預約點的獲利
假設在第i-1 個預約點，停車場保留μ i-1 個車位，此時停車場有α -μ i-1 輛車，之
變數
停車場總車位數:α 個
平均停車時間; β 分鐘
預約加價: γ 倍
預約賠償: δ 元
每分鐘停車費: 1 元
預約間格 t 分
G r o u p
共 m 個預約點
預約量: Z1 ~ Zm
保留量: X1 ~ Xm
提前關閉現場停車的時間: T
時間軸
…
Z1
Z2
Z3
Zm
X1
X2
X3
Xm
T
保留量
預約量
第 33 頁，共 33 頁
後關閉現場臨時停車，到第i個預約點時，停車場共空出 Li 個停車位。如圖:
在此，計算所求得的獲利，將先不考慮空車位的浪費。第 i 個預約點將會因預約
功能而多出 Ei 的獲利:
Ei :第i 個預約點相較於無預約功能而多出來的收入。
Pi: 出現的機率
μ i : 第 i 點停車場實際保留的車位數
當 Li 小於 Zi 時，停車場車輛離開的速度太慢，所以空車位嚴重不足，無法
滿足預約停車，因此要負擔 Li- Zi 個預約賠償。所以此種情況可因滿足 Li 個預
約，而多賺 Li*β *(γ -1) ，但有 (Zi- Li) 個預約無法滿足，所以虧了(Zi- Li)*
δ ，而且，根本沒有多出來的空車位可以滿足保留量，此種情窗出現的機率為
Pi。 同樣的道理，若 Zi<Li<=Xi+Zi 則可以滿足Zi 個預約，多賺Zi*β *(γ
-1) ，且多出Li – Zi 個車位可留給保留量，出現機率是Pi。第三種情況是
Li>Xi+Z 也就是說停車場車輛的離開速度太快空車位太多，可以滿足Zi 個預
約，多賺 Zi*β *(γ -1) 還有足夠的空車位可留給保留量 Xi，最後多出來的
空車位將由現場臨時停車補滿。
可分為三種情況 ，如表所列:
步驟二、求得Group 的獲利
在此所求得的獲利將先不考慮空車位的浪費，因為 Group 內共有 m 個預約
獲利 (Ei) 保留量(μ i) 出現的機率 Pi
Li<Zi Li*β *(γ -1) – (Zi- Li)* δ 0
Zi<Li<=Xi+Zi Zi*β *(γ -1) Li - Zi
Li>Xi+Zi Zi*β *(γ -1) Xi
t Li t Li
Li
C i e i e
i
- - - - -
- - -
-
a m b m b a
m (1 ) ( ) 1 / /
1
Zi
Xi
Li
μ i-1
t 分鐘
保留量
預約量
圖七 單一個預約點的停車情況: 停車場餘第 i - 1 個
預約點保留μ i-1 個車位，經過 t 分鐘後 於第 i 個預
約點共空出Li 個空車位
第 34 頁，共 34 頁
點，所以Group 的獲利，就等於這 m 個獲利的總和，出現的機率就是這 m 個
預約點各自出現機率的積。因此，只要我們將所有可能出現的獲利及向對應的機
率求出，然後累加獲利乘以機率就可得到 Group 獲利的期望值。
考慮整個Group ( 共 m 個預約點):
總獲利: å
<=i<=m
Ei
1
出現的機率: Õ
<=i<=m
Pi
1
獲利期望值 為:
å å Õ
<= <= <= <= 所有可能的停車狀況
( * )
1 i m 1 i m
Ei Pi
我們必須注意到的是，在計算第一個預約獲利時，此時 t = T( 提前時間) 。
第 35 頁，共 35 頁
步驟三、保留車位的浪費
停車場為了滿足預約停車，必需要保留車位，也因此也造成了保留車位的浪費。
在 步驟一、二中， 我們並未考慮到空車位的浪費，所以本小節將會加入保留車
位的浪費。
如圖，我們假設停車場在t 分鐘內將有 a 輛車子離開。但只需要再離開b 輛，
停車場所保留的車位就足以滿足預約量及保留量。因此，當離開的車輛大於 b
時，馬上就由現場臨時停車補滿。也就是說，停車場最多只會空出預約量+保留
量個停車位。我們可以很簡單的求出保留車位的浪費:
保留車位的浪費: μ i-1* t + Mi
Mi: 前 b 輛離開停車場車輛所造成的保留車位浪費。
所以，只要我只要能夠求得曲線面積 Mi，就可求得保留車位的浪費
a
t 分鐘
b
μ i-1
由現場臨時停車補滿
Mi
圖八 多出的空車位將現場臨時停車補滿 ; 因每個預約
點的空車位只需滿竹預約量及保留量，多出來的空車位將
由場臨時停車補滿
第 36 頁，共 36 頁
如何求Mi:
我們知道，t 秒內共有 a 輛車離開停車場，t’
內共有 b 量離開。有 a –b 個車位
由現場臨時停車補滿。
如圖
若有一車輛於 x 分鐘時離開停車場，則:
1. 浪費: t-x
2. 出現的機率:
dx
b a e
e
t
x
/ * ( 1 )
*
1
/
/
b
b
b
-
-
-
在求出現機率時，我們利用到條件機率: P( x| 在 t 秒內離開，且為離開者的前 b/a)
= P(x)/P(在 t 秒內離開， 且為離開者的前 b/a ) ，先求出 P(在 t 秒內離開)再
求出 x 點出現的機率。
3. 共 b 輛
b
b a e
t x e dx
Mi
t
t
t
*
/ * ( 1 )
*
1
( )
/
0
/
'
b
b
b
-
-
-
-
=
ò
a
t 分鐘
b
t’
x
μ i-1
Mi
*[( 1) *(1 ) * ] /(1 ) / ' / / t ' b t ' b t b = a t - - e- + t e- - e-
第 37 頁，共 37 頁
我們假設，由現場臨時停車補滿的 a-b 輛，在第 i 個預約點前將不會離開。因
為，我們求 t 分鐘內離開幾個的機率時，是不考慮這 a-b 個離開的情況。所以
說，我們只要在求得 t’ ，就可以求出保留車位的浪費。
第 38 頁，共 38 頁
如何求 t’
我們知道，t 秒內共有 a 輛車離開停車場，t’
內共有 b 輛離開。所以t’ 分內離
開的機率比上 t 分鐘內離開的機率，等於 b : a
如圖:
所以 t’ 秒內離開的機率/ t 秒內離開的機率 = b/a
b a
e dx
e dx
t x
t x
/
1 / *
1 / *
0
0
'
=
ò
ò
-
-
b
b
b
b
b b (1 * (1 )) * ' t / e
a
b
t = - Ln - - -
t
t’
時間軸
離開的機率
第 39 頁，共 39 頁
步驟四、算出Group 獲利的期望值
所以考慮保留車位的浪費時，我們只需再將每個預約點的獲利扣除保留車位浪
費，然後總和所有情況的獲利乘以出現機率:
此Group 的獲利的期望值:
å å Õ
<= <= <= <=
- -
所有可能的停車狀況
( ( * )* )
1 1 i m
i
i m
Ei Mi m t Pi
必須注意到的是，當 i=1， 即 Group 第一個預約點，此時 t=T。
第 40 頁，共 40 頁
第三節 結果比較
在此，我們將觀察，停車場能夠經由預約服務而多得的獲利。還有比較 Parking
Algorithm 和另一種預約方法，放任法，在獲利上的比較。我們將觀察，當預約
量太少及太多，此兩種方法在獲利上的表現。
首先，介紹預約的環境:
時間: 6:00 ~ 9:00
預約量太少的情況:
先給定預約量: 預約量= 已預約量 + 未來預約量
6:00 ~ 9:00 每個預約點的預約量都只有 20 個
執行完一次 Parking Algorithm 之後:
放任法: 不限制預約，不保留車位， 只調整 T
我們可以看到， Parking Algorithm 和 放任法 都有多出近 3 成的獲利。這時候
因為預約量很少，所以根本不需要減少預約，也不需要保留車位，所以看不出
Parking Algorithm 的功力。
預約點 6:00 6:30 7:00 7:30 8:00 8:30 9:00
已預約量 ０ ０ ０ ０ ０ ０ ０
未來預約量 ２０ ２０ ２０ ２０ ２０ ２０ ２０
總獲利 多賺 多賺/B
無預約 36000 (B) 0 0
放任法 46511.78 10551.78 0.29
Parking Algorithm 46511.78 10551.78 0.29
變數
停車場車位數: 200 個
平均停車時間; 100 分鐘
預約加價: 兩倍
預約賠償: 800 元
每分鐘停車費: 1 元
第 41 頁，共 41 頁
預約量太多的情況:
先給定預約量: 預約量= 已預約量 + 未來預約量
6:00 ~ 9:00 每個預約點的預約量都有 200 個，也就是說，所有的車位都已經被
預約光。
總獲利 多賺 多賺/B
無預約 36000 (B) 0 0
放任法 -293389.14 -329389.14 -9.15
Parking
Algorithm
57083.42 21083.42 0.586
放任法: 不限制預約，不保留車位， 只調整 T
Parking Algorithm 多出了近六成的獲利，但 放任法 卻虧了近 9 倍。因為 放
任法 接受了所有的預約，導致空車位無法負荷，造成大量的預約賠償。
預約點 6:00 6:30 7:00 7:30 8:00 8:30 9:00
已預約量 ０ ０ ０ ０ ０ ０ ０
未來預約量 ２０0 ２０0 ２０0 ２０0 ２０0 ２０0 ２０0
第 42 頁，共 42 頁
第四章 未來工作及結論
第一節 未來工作
在論文的一開始 ，我們就對預約環境作了一些假設，若將這些假設也考
慮進去，則會有更大的獲利空間。
假設:
任何時後均有車輛等待要進入停車場。
有預約的車輛一定會到。
n 當停車場要關閉現場臨時停車時，此時，停車場並非全滿。
我們假設任何時候均有車輛等待進入停車，所以這時候停車場應該
是全滿，但實際上已經有空車位。所以，我們必須把這些空車位用
掉，因此可適度的延後關閉現場臨時停車讓現場停車輛來補滿這些
空車位。
n 預約的車輛，不可能在所預約的時刻一次全部到齊。
例如，若7:00 有 30 輛預約停車，不可能 30 輛都在 7:00 的時後
到達停車場。所以停車場可適度的偷偷讓現場停車來遞補空缺。
n 預約未到:
不可能百分之百的預約都會到，所以，我們也可適度的讓現場停車
來遞補預約未到的車位。
第 43 頁，共 43 頁
第二節 結論
本篇論文一開始制定了預約規則，並探討預約的特性；詳細的討論，預約量
(Z)，保留量(X)及提前時間(T)，並分析三者之間的關係。所有的考量均以取
得最大獲利為宗旨。假定每個預約點會被預約的數量已知，反推該接受幾個
預約，保留幾個車位以及何時該關閉現場臨時停車。程式不斷的執行，算出
每個時間點的最大獲利，並求出每個預約點的預約量，保留量及提前時間。
停車場只需依據此三個變數即可控管車流量。
為了簡化討論，我們定義了 Group，將討論的範圍限定在 Group 內。並架
構在 Group 上，推演出 Parking Algorithm。論文中並提出了 Parking
Algorithm 的加速方法，並解析了相關的數學式，最後比較此演算法在獲利
上的表現。
預約規則:
預約時間: 開放 24 小時預約，每 30 分鐘一個預約點。
預約加價: 提高預約停車的費用。
預約賠償: 發生無法滿足預約車位時，停車場要付的賠償費。
變數定義:
預約量: 每個預約點可接受的預約數量。
保留量: 每個預約點該保留的車位數目。
提前時間: 每個預約點提前關閉現場臨時停車的時間。
Group
連續的 M 個預約點
前面的預約點需要為後續預約保留的車位
Parking Algorithm 是利用 Greedy Algorithm 由後往前減少 Group 最後一點
的預約量，找尋最大獲利。並利用機率的觀念求出 Group 獲利的期望值。
Parking Algorithm 可很有效率並以極為簡單的方式，決定停車場對於預約流
量及現場車流量的處理。值得一提的是，因預約而得到的獲利非常可觀，在
預約加價為兩倍的情況下，停車場可以多到近六成的獲利。這對停車場的業
者而言，可說是一大福音。
其他應用
此預約系統的應用面極廣，可套用到其它非常多類似的系統。例:
頻寬的預約
當在網路上傳大量的即時資料時，例如視訊會議，此時應用軟體為保證有良
好的 QOS，將會向路由器(Router)要求保留頻寬。但在一些黃金時段，跟本
保留不到。 所以, 若路由器(Router)也開放頻寬的預約，則預約情況將和停
車場極為相似。
諸如此類的預約不勝枚舉，就等待您的發覺囉!
