基于組合拍賣與統(tǒng)一價格的停車位最優(yōu)分配研究

譚冰清，徐素秀*,2a,2b，許鋼焱，周耀明

(1.暨南大學，管理學院，廣州510632；2.暨南大學，a.物聯(lián)網與物流工程研究院，b.智能科學與工程學院，廣東珠海519070；3.哈爾濱工業(yè)大學，a.城市應急管理與交通安全中心，b.建筑學院，廣東深圳518055；4.上海交通大學，工業(yè)工程與管理系，上海200240)

0 引言

日益凸顯的停車難問題給本就擁堵的城市交通環(huán)境帶來了更為惡劣的負面影響。越來越多的學者關注如何利用科學有效的方式最大化利用現(xiàn)今有限的停車資源。其中，對停車位有效的分配與合理的定價成為研究重點。由于拍賣理論回答了經濟學中最基本的問題：誰應該以什么價格得到多少商品，許多學者利用拍賣機制實現(xiàn)停車位的分配與定價。Tan[1]等提出利用順序拍賣機制實現(xiàn)兩類車位的定價與分配；Xiao[2-3]等提出一種新式的雙邊拍賣機制從共享的角度實現(xiàn)停車位分配，并進一步提出一個公平循環(huán)的雙邊拍賣機制以解決共享停車位中新出現(xiàn)的管理問題；Kong[4]等將市場設計機制與拍賣機制結合實現(xiàn)停車位的分配與定價。

隨著物聯(lián)網等前沿技術的發(fā)展，Kong[4]等提出基于物聯(lián)網的城市停車位管理云平臺，期望作為“城市停車位共享、分配和定價”的通用框架，實現(xiàn)傳統(tǒng)停車模式向新型智慧停車模式的轉變。傳統(tǒng)即到即停的停車模式已不再是司機的唯一選擇，更多有精確出行計劃的司機利用平臺或軟件預約車位[5]。張水潮[6]等提出基于預約需求的停車平臺車位分配方法；何學勝[7]等在給定需求前提下建立雙層停車規(guī)劃模型及算法；段滿珍[8]等構建基于個性化誘導需求的停車場分配模型實現(xiàn)均衡利用停車資源；范文博[9]等研究3 種運營機制下兩類停車設施的最優(yōu)定價問題，給出不同運營模式中交通需求和社會福利的分析。

然而，鮮有考慮同時存在即到即停和預約停車模式的情況。本文針對當前市場中兩類停車需求共存的現(xiàn)象，考慮停車服務平臺提供兩類停車服務模式，平臺分別利用O-VCG 組合拍賣機制與統(tǒng)一價格對兩類模式進行定價。為實現(xiàn)平臺最優(yōu)分配兩類模式停車位，建立以最大化競標者與平臺的整體效用為目標的整數規(guī)劃模型。

1 問題描述與建模

1.1 問題描述

考慮停車服務平臺同時提供兩類停車服務模式：一類為預約模式，偏好這類模式的司機通常期望根據確定的停車需求提前預約車位，主要代表群體為工作日的通勤者；另一類為即到即停模式，偏好這類模式的司機通常在駕駛過程中才明確目的地或臨時更改目的地概率較高，主要代表群體為周末臨時起意的購物者及實時接單的業(yè)務員。預約模式中，司機作為競標者，平臺作為拍賣商利用O-VCG 組合拍賣機制對停車位進行分配與定價；即到即停模式中，平臺則通過統(tǒng)一價格收取司機的停車費用。

為研究平臺對兩類模式停車位的最優(yōu)分配，假設當前市場司機對停車位的需求現(xiàn)狀為供不應求，以最大化競標者與平臺的整體效用為目標，建立整數規(guī)劃模型。設平臺管理q0個車位，每個車位被均勻地劃分成J個停車時段，每個停車時段可用的停車時間相同(如15 min 或30 min)，且每個停車時段之間無重疊，將平臺中相同可用時間的停車時段視為同質。記預約模式的車位數量為q1，每個參與競標的司機i提交一個異或(exclusive OR,XOR)標——意味著每個司機在出多個標的情況下最多只有一個標勝出，每個投標包含該司機需要的停車時段組合hi及其對應的報價vi(hi)，司機根據自身需求向平臺投標，平臺則通過組合拍賣機制完成分配與定價。即到即停模式的停車位數量為q0-q1，平臺通過單個車位的統(tǒng)一價格p收取司機的停車費用。表1為涉及的變量符號及相應定義。

表1 符號與定義Table 1 Notation and definitions

1.2 模型建立

根據以上描述，以最大化競標者與平臺的整體效用為目標，構建整數規(guī)劃模型為

式(1)表示最大化競標者與平臺的整體效用，第1 部分表示所有預約停車司機的總福利，等同于競標者的效用與預約模式的平臺收益之和，第2部分為即到即停模式的平臺收益。約束條件：式(2)保證參與競標的司機出標均為XOR 標，即所有投標中最多只有一個標被選中，xi(hi)=1 表示hi被分配給競標人i，否則為0；式(3)保證預約模式中所有車位的第j個停車時段被分配的次數總和不超過預約模式車位總數量，yj(hi)=1 表示第j停車時段被分配給hi，否則為0；式(4)保證兩類停車模式可分配的車位數量均不超過平臺的車位總數量。

2 拍賣機制與性質

2.1 O-VCG組合拍賣機制

采用O-VCG組合拍賣機制對預約停車模式進行分配與定價，平臺為拍賣商，司機為競標者，司機提交給平臺目標停車時段的組合及對應的報價，平臺根據參與競標者的出標并基于拍賣機制完成分配與定價。O-VCG組合拍賣機制規(guī)則如下：

(1)每個競標者i向平臺提交報價vi(hi)；

(2)平臺根據求解目標方程IP 選出最優(yōu)分配(I,q1)，停車時段組合hi被分配給競標勝出司機i∈I，其中{hi}i∈I實現(xiàn)了π(I,q1)的有效分配；

(3)每個競標者的效用為ui(hi)=[π(I,q1)-π(Ii,q1′) ]，最終支付價格為實際報價與效用之差：pi(hi)=vi(hi)-[π(I,q1)-π(Ii,q′1) ]。

2.2 主要性質

傳統(tǒng)VCG 拍賣通常只考慮競價與效用的關系，本文提出的O-VCG 拍賣機制融合競價與統(tǒng)一價格等因素，以預約司機與平臺的整體效用最大化為目標，同時實現(xiàn)激勵相容與個體理性。主要性質歸納如下。

定理1激勵相容。即在O-VCG 組合拍賣中，真實報價為最優(yōu)策略。

證明：根據目標方程IP，得出最優(yōu)分配(I,q1)，競標者與平臺的整體效用為

假設真實報價vi(hi)不是最優(yōu)策略，那么對于競標者i存在報價更優(yōu)于vi(hi)。當停車時段組合為時，最終支付的價格為，即到即停模式停車位數量將由q1變?yōu)椤Ｍ瑫r假設當競標者i的報價由vi(hi)變?yōu)闀r，其余{Ii} 競標者的出價保持不變。

假設

可表示為

將式(9)代入式(8)，得到

此時，與選出最優(yōu)分配 (I,q1)，為目標方程IP的最優(yōu)解相矛盾，故定理1成立。

推論1配置效率和個體理性。本文提出的以最大化競標者與平臺的整體效用為目標的O-VCG組合拍賣機制實現(xiàn)以上兩個性質。

定理1 已經證明O-VCG 組合拍賣機制可以實現(xiàn)激勵相容。事實上，真實報價在很大程度上簡化了投標策略，因此會吸引更多的競標者參與拍賣。此外，該拍賣機制實現(xiàn)了系統(tǒng)的配置效率，尤其在互聯(lián)網環(huán)境下彌足珍貴，在一定程度上保證其實際可行性。

3 數值算例與結果分析

設定停車位總數為50 個，每個車位被劃分為12 個停車時段，即q0=50，J=12。參與拍賣的競標者的出價服從方差為均值5%的正態(tài)分布，在求解時所得數據結果均為20組隨機生成實例的平均值。為進一步說明各個參數對競標者效用、停車位最優(yōu)分配以及競標者與平臺整體效用的影響，我們對部分參數進行敏感性分析。

3.1 競標者對單個停車時段出價均值及競標人數的敏感性分析

為定量分析競標者對單個停車時段出價均值(投標均值)對競標者效用、兩類模式停車位分配及競標者與平臺整體效用的影響，考慮競標者投標均值E(vi)在[9.5,10.5]以Δ[E(vi)]=0.25的幅度連續(xù)變化，單個停車位統(tǒng)一價格p=120(即單個停車時段的統(tǒng)一價格為pj=p/J=10)時，且競標人數分別為I=200和I=250的情況。

(1)競標者投標均值及競標人數對競標者效用的影響

如圖1所示，當其余參數不變，參與人數由200人變?yōu)?50 人時，贏得競標的司機總效用增加，說明參與競拍的人數越多，競標勝出者的總效用越大。并且當競標人數足夠多時，即I=250，競標者總效用在均值變化區(qū)間[9.75,10.25]內增加的趨勢優(yōu)于其余區(qū)間，說明當單個停車時段統(tǒng)一價格pj=10 時出價均值集中在[9.75,10.25]內更具有競標優(yōu)勢。同時，僅競標者投標均值在[9.5,10.5]內逐漸增大時，競標者的總效用增加趨勢明顯，說明競標者出價均值越高，預約模式在分配過程中越占優(yōu)勢，平臺更愿意通過預約模式將車位分配給司機以保證更高的總收益。

圖1 競標者投標均值及競標人數對競標者總效用的影響Fig.1 Effect of average bid value and number of bidders on bidders'total utility

(2)競標者投標均值及競標人數對兩類模式停車位最優(yōu)分配的影響

由圖2可知：當Δ[E(vi)]=pj=10 時，平臺分配給預約模式的停車位數量大于分配給即到即停模式的車位數量；兩類模式分配車位數量相等時，即兩條曲線的交點(都位于[9.75,10.0])對應的投標均值都小于單個停車時段統(tǒng)一價格pj=10，說明預約模式更具有優(yōu)勢，也說明拍賣機制的有效性；當競標者出價均值E(vi)=10.5 且參與競標的人數足夠多(I=250)時，基于目標方程，平臺為保證兩類模式總收益最大，期望將50 個停車位全部通過拍賣以預約模式分配給司機，此時q0=q1=50，這也說明投標均值一旦超過某一閾值(E(vi)=10.5) 且參與競標的人數足夠多時，平臺更傾向于通過預約模式分配停車位。

圖2 競標者投標均值及競標人數對停車位最優(yōu)分配的影響Fig.2 Effect of average bid value and bidders'number on optimal allocation of parking spaces

(3)競標者投標均值及競標人數對競標者與平臺整體效用的影響

由圖3可知，隨著競標者投標均值和競標人數的增加，競標者與平臺整體效用增加。但值得注意的是，當人數足夠多時(I=250)，競標者與平臺整體效用增加速率更快，說明參與競標的人數越多對平臺越有益。而且，當競標者出價均值E(vi)=9.5時，根據圖2和圖3，雖然I=200和I=250 時預約模式被分配的車位數量不同，但總效益幾乎相同，說明當競標者出價均值較低時，競標人數對競標者與平臺整體效用影響較小。

圖3 競標者投標均值及競標人數對競標者與平臺整體效用的影響Fig.3 Effect of average bid value and number of bidders on total utility of bidders and platform

3.2 競標者投標均值及單個停車時段統(tǒng)一價格的敏感性分析

為定量分析競標者的投標均值及單個停車時段統(tǒng)一價格對競標者效用和兩類模式停車位分配的影響，考慮單個車位的統(tǒng)一價格p在[115,125](對應pj∈[9.6,10.4])內以Δp=2.5(對應Δpj=0.2)的幅度連續(xù)變化，且投標均值分別為E(vi)=9.75和E(vi)=10.25的情況。為與投標均值單位統(tǒng)一以及得到更為直觀的結果，以下分析根據對應的單個停車時段統(tǒng)一價格pj的變化進行描述。

(1)競標者投標均值及單個停車時段統(tǒng)一價格對競標者效用的影響

由圖4可知，當單個停車時段統(tǒng)一價格逐漸升高時，競標者效用下降，說明此時在分配過程中即到即停模式更占優(yōu)勢。尤其當單個停車時段統(tǒng)一價格較高且競標者投標均值較低時(E(vi)=9.75，pj=10.4)，競標者獲得的總效用非常小，這是因為勝出拍賣的競標者數量較少。值得注意的是，當投標均值及單個停車時段統(tǒng)一價格相近時，平臺合理劃分兩類模式的停車位數量，同時保證了競標者效用，再次體現(xiàn)了所提出拍賣機制的有效性。

圖4 競標者投標均值及單個停車時段統(tǒng)一價格對競標者效用的影響Fig.4 Effect of average bid value and uniform price of one parking time slot on bidders'utility

(2)競標者投標均值及單個停車時段統(tǒng)一價格對兩類模式停車位最優(yōu)分配的影響

由圖5可知，當單個停車時段統(tǒng)一價格逐漸升高時，平臺為保證總收益最大化將分配更多的車位給即到即停模式，故即到即停模式的車位數量與單個停車時段統(tǒng)一價格成正比，而預約模式則和單個停車時段統(tǒng)一價格成反比。圖5(a)中兩條曲線交點的橫坐標位于[9.8,9.9]內，略大于此時競標者投標均值[E(vi)]=9.75；圖5(b)中兩條曲線交點的橫坐標位于[10.3,10.4]內，也略大于此時競標者投標均值[E(vi)]=10.25。從平臺的角度出發(fā)，將停車位根據可用時間劃分為停車時段，基于O-VCG 組合拍賣機制通過預約模式以收取略低于統(tǒng)一價格的競標價能夠獲取與即到即停模式相同的收益。這也表明與統(tǒng)一價格分配相結合的新式單O-VCG組合拍賣機制不僅實現(xiàn)兩類模式的停車位最優(yōu)分配，還實現(xiàn)最大化競標者與平臺的整體效用。

綜合圖1～圖5可知，當選擇預約模式中競標者對單個停車時段出價均值與單個停車時段統(tǒng)一價格接近時，本文提出的基于組合拍賣與統(tǒng)一價格的停車位最優(yōu)分配整數規(guī)劃模型對停車位服務平臺分配兩類模式停車位以及實現(xiàn)最大化競標者與平臺整體效用的優(yōu)勢十分明顯。

圖5 競標者投標均值及單個停車時段統(tǒng)一價格對停車位最優(yōu)分配的影響Fig.5 Effect of average bid value and uniform price of one parking time slot on optimal allocation of parking spaces

4 結論

本文將統(tǒng)一價格與傳統(tǒng)的拍賣機制相結合，創(chuàng)新地提出新式O-VCG組合拍賣機制實現(xiàn)停車的分配與定價，建立整數規(guī)劃模型實現(xiàn)競標者與停車服務平臺整體效用最大化。通過理論證明定性分析所提出的機制能夠找到最優(yōu)分配以及競標者出真實價為最優(yōu)策略，進一步通過數值算例定量討論競標者對單個停車時段出價均值、競標人數與單個停車時段統(tǒng)一價格對競標者效用、平臺最優(yōu)分配以及競標者與平臺整體效用的影響。驗證了拍賣機制的有效性與必要性，尤其當競標者對單個停車時段出價均值與單個停車時段統(tǒng)一價格接近時，新式拍賣機制對平臺合理分配兩類模式停車位具有優(yōu)勢。因此，在兩類停車模式共存的情況下，所提機制不僅激勵司機提交真實報價，還指導平臺運營者均衡有效地分配停車位，在改善停車難方面具有較強應用價值和廣闊前景。