考慮車位異質(zhì)性的共享停車平臺(tái)最優(yōu)分配機(jī)制研究①

張利鳳，慕銀平，樊鵬英

（1.電子科技大學(xué) 經(jīng)濟(jì)與管理學(xué)院，成都 611731；2.北京工商大學(xué) 經(jīng)濟(jì)學(xué)院，北京 100048）

截至2015 年底，北京機(jī)動(dòng)車保有量達(dá)560 余萬(wàn)輛，機(jī)動(dòng)車停車位約290 萬(wàn)個(gè)，基本車位缺口達(dá)350 萬(wàn)個(gè)［1］。停車難成為困擾車主出行的一大難題。為了緩解停車難問(wèn)題，在物聯(lián)網(wǎng)、互聯(lián)網(wǎng)等技術(shù)的支持下，可將由于出差、上班等原因長(zhǎng)期處于閑置的私家車位停車時(shí)段共享出來(lái)，供其他需求者使用。車位共享平臺(tái)應(yīng)運(yùn)而生，如ECTP（engelhart commodities trading partners）、ywpark、pnpark 等。通過(guò)這些共享平臺(tái)，車位擁有者可以發(fā)布車位空閑時(shí)段信息，車位需求者可以通過(guò)平臺(tái)尋找合適的停車位置和時(shí)段。因此，共享平臺(tái)使稀有的車位資源得到了有效的利用，不僅可以緩解停車難問(wèn)題，還可以增加私家車位擁有者的收入。在平臺(tái)的運(yùn)營(yíng)過(guò)程中，由于車位擁有者所發(fā)布的車位空閑時(shí)段及位置信息與車位需求者發(fā)布的需求時(shí)段及位置需要進(jìn)行高效的匹配，因而產(chǎn)生了大量的科學(xué)問(wèn)題需要解決，如車位分配、車位定價(jià)等問(wèn)題。

一、文獻(xiàn)綜述

關(guān)于車位管理有大量的研究問(wèn)題，其中大多數(shù)研究集中在車位的動(dòng)態(tài)定價(jià)和分配方面。Shiftan 和Golani［2］研究發(fā)現(xiàn)通過(guò)調(diào)整定價(jià)策略，可以影響出行方式從而減少停車需求，以緩解停車難問(wèn)題；Qian 和Rajagopal［3］運(yùn)用動(dòng)態(tài)規(guī)劃模型求解停車位隨機(jī)定價(jià)問(wèn)題，給出車位占有率的閾值，當(dāng)車位占用率超過(guò)該閾值則應(yīng)該進(jìn)行收費(fèi)；Nourinejad 和Roorda［4］提出了按道路收費(fèi)和按小時(shí)收費(fèi)兩種機(jī)制，并得出按道路收費(fèi)將嚴(yán)格地減少需求，但是按小時(shí)收費(fèi)則可以根據(jù)停留時(shí)間彈性減少或誘導(dǎo)需求。除此之外，還有很多學(xué)者對(duì)停車位定價(jià)進(jìn)行了相關(guān)研究［59］。雖然大量研究表明，通過(guò)定價(jià)策略可以在一定程度上緩解停車難問(wèn)題，但是隨著汽車保有量的快速增加，定價(jià)策略對(duì)緩解停車難的作用逐漸減弱。智能停車系統(tǒng)的出現(xiàn)為優(yōu)化停車位分配提供了技術(shù)支持。通過(guò)智能停車系統(tǒng)，需求者可提前預(yù)約車位，停車場(chǎng)經(jīng)營(yíng)者可以根據(jù)預(yù)約信息進(jìn)行車位優(yōu)化分配。Teodorovic 和Lucic［10］構(gòu)建整數(shù)規(guī)劃模型研究了多個(gè)價(jià)格等級(jí)下，停車位可預(yù)約的收益管理問(wèn)題；Geng 和Cassandras［11］構(gòu)建混合整數(shù)規(guī)劃模型研究了智能預(yù)約系統(tǒng)下的停車位分配策略；Boudali 和Ouada［12］提出了一種基于多智能體的智能停車系統(tǒng)，通過(guò)處理駕駛員的偏好，進(jìn)行車位分配，為駕駛員提供實(shí)時(shí)決策輔助；Lei 和Ouang［13］提出運(yùn)用拉格朗日松弛設(shè)計(jì)近似算法對(duì)智能停車的動(dòng)態(tài)定價(jià)和預(yù)約分配問(wèn)題進(jìn)行求解；Martha 等［14］以收益最大化為目標(biāo)構(gòu)建了多個(gè)停車場(chǎng)下的車位分配問(wèn)題，并通過(guò)人工神經(jīng)網(wǎng)絡(luò)進(jìn)行實(shí)時(shí)在線預(yù)訂決策。上述學(xué)者的研究大多針對(duì)傳統(tǒng)的停車場(chǎng)車位定價(jià)或者分配進(jìn)行研究?？紤]到傳統(tǒng)的停車場(chǎng)的停車位數(shù)量固定，且每個(gè)車位可供停車時(shí)長(zhǎng)也是固定的，因此實(shí)際上該類問(wèn)題屬于供給確定，需求隨機(jī)下的能力優(yōu)化分配。由于車位共享平臺(tái)的車位是由私家車位擁有者提供，而私家車位擁有者的車位空閑時(shí)間不同，導(dǎo)致車位可供停車的時(shí)長(zhǎng)具有隨機(jī)性。同時(shí)每個(gè)時(shí)間段提供的車位數(shù)量也依賴于私家車位的空閑時(shí)間，因此每個(gè)時(shí)間段共享平臺(tái)的車位數(shù)量也具有隨機(jī)性。即車位共享平臺(tái)所提供的停車位數(shù)量隨機(jī)，且每個(gè)車位可供停車的時(shí)長(zhǎng)也是隨機(jī)的，因此車位共享平臺(tái)所面臨的車位分配比傳統(tǒng)停車場(chǎng)的車位分配決策更為復(fù)雜。傳統(tǒng)的車位分配模型將不再適用于共享平臺(tái)的車位分配，車位共享平臺(tái)面臨的將是隨機(jī)的供給和需求下的車位分配決策問(wèn)題。

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，共享經(jīng)濟(jì)出現(xiàn)，提高了閑置資源的利用率，各領(lǐng)域也出現(xiàn)了大量的共享平臺(tái)［15］。關(guān)于車位共享問(wèn)題的研究，李濤和關(guān)宏志［16］研究了車位外部使用者和內(nèi)部使用者時(shí)間相沖突的情況下，通過(guò)需求調(diào)節(jié)共享終止時(shí)刻、停車位供應(yīng)率等設(shè)計(jì)停車共享優(yōu)化方案以實(shí)現(xiàn)停車管理者的收益最大化；Guo 等［17］構(gòu)建高斯混合模型刻畫了停車位管理者向車位擁有者回購(gòu)車位并出租給需求者的情況下，實(shí)現(xiàn)利潤(rùn)最大化的隨機(jī)優(yōu)化問(wèn)題，并通過(guò)仿真得到最優(yōu)回購(gòu)量；Zou 等［18］以最大化社會(huì)福利為目標(biāo)函數(shù)，構(gòu)建整數(shù)規(guī)劃模型分別研究了靜態(tài)和動(dòng)態(tài)的車位分配機(jī)制；Shao 等［19］運(yùn)用0 1 規(guī)劃模型研究了當(dāng)車位共享信息與需求信息已知的情況下的車位分配問(wèn)題；Su 等［20］設(shè)計(jì)了兩種機(jī)制研究私家車位既可以交換也可以出租兩種情況下的車位分配問(wèn)題，得到所提出的機(jī)制可以顯著提高社會(huì)福利；林小圍等［21］構(gòu)建整數(shù)規(guī)劃模型，研究了帶不同時(shí)間窗口的共享平臺(tái)下私家車位的動(dòng)態(tài)預(yù)約與分配策略。雖然上述文獻(xiàn)對(duì)車位共享平臺(tái)下的車位分配問(wèn)題進(jìn)行了研究，但是目前對(duì)共享車位的研究均假設(shè)停車位對(duì)于車位需求者具有同等效用，即平臺(tái)用任意一個(gè)車位去滿足顧客需求所獲得的收益均相同。由于車位的供給者為私家車位擁有者，因此共享平臺(tái)提供的停車位位置可能會(huì)出現(xiàn)差異性較大的問(wèn)題。當(dāng)停車位位置差異性較大時(shí)，用不同的車位位置去滿足顧客，將會(huì)影響顧客停車后的行走距離。云美萍等［22］的研究表明步行距離是停車者優(yōu)先考慮的因素之一。此時(shí)，對(duì)于顧客而言，用不同的車位去滿足顧客的需求將產(chǎn)生不同的效用，從而影響平臺(tái)的收益，所以車位分配決策應(yīng)該考慮車位的異質(zhì)性。

綜上，本文以車位共享為背景，研究了隨機(jī)供給和需求的情況下，車位共享平臺(tái)在考慮車位異質(zhì)性情況時(shí)的車位分配機(jī)制，為共享平臺(tái)的預(yù)訂分配提供決策支持。

二、問(wèn)題描述

在實(shí)際中，顧客到達(dá)目的地的步行距離（簡(jiǎn)稱“步行距離”）是影響顧客滿意度的重要因素，步行距離越遠(yuǎn)，顧客的滿意度越低，反之，則越高。當(dāng)兩個(gè)車位的距離較近，顧客的步行距離差異較小時(shí)，可以認(rèn)為兩個(gè)車位不具有異質(zhì)性；當(dāng)兩個(gè)車位距離較遠(yuǎn)，步行距離的差異較大時(shí)，可以認(rèn)為兩個(gè)車位具有異質(zhì)性?；诖?，本文利用顧客的步行距離對(duì)車位的異質(zhì)性進(jìn)行刻畫。進(jìn)一步，平臺(tái)可根據(jù)車位之間的距離將停車位劃分為不同的區(qū)域。同一個(gè)區(qū)域車位間的距離較近，不具有異質(zhì)性，而不同區(qū)域車位間的距離較遠(yuǎn)，則具有異質(zhì)性（實(shí)際中的劃分標(biāo)準(zhǔn)：以同一個(gè)小區(qū)作為一個(gè)區(qū)域或以一定的公里范圍作為一個(gè)區(qū)域）。因此，不同區(qū)域車位的差異可用步行距離來(lái)刻畫。當(dāng)車位供給（需求）用戶在平臺(tái)上發(fā)布停車位信息時(shí)，需包含以下信息：車位的供給（需求）時(shí)間段，車位的供給（需求）位置區(qū)域。本文所考慮的車位屬于稀缺資源，當(dāng)顧客需求停車區(qū)域的車位不足時(shí)，平臺(tái)可能會(huì)用其他區(qū)域的車位去滿足需求。此時(shí)，顧客停車后的步行距離會(huì)增加，導(dǎo)致顧客滿意度下降，從而會(huì)為平臺(tái)帶來(lái)?yè)p失，因此平臺(tái)需要根據(jù)不同用戶提供的車位信息對(duì)車位進(jìn)行優(yōu)化分配。

由于車位供給者可能提供的時(shí)間段有限，因此將決策周期離散化為T個(gè)周期。假設(shè)供給者最多可以提供T個(gè)周期的停車時(shí)段，需求者也最多可以連續(xù)停留T個(gè)周期。由于出行時(shí)間的隨機(jī)性，車位供給者和車位需求者可能隨時(shí)將供給信息和需求信息提供給平臺(tái)，因此共享平臺(tái)應(yīng)該根據(jù)時(shí)變的供給信息和需求信息，更新決策，動(dòng)態(tài)地分配停車位。

（一）停車位的動(dòng)態(tài)模型構(gòu)建

假設(shè)平臺(tái)存在J個(gè)具有異質(zhì)性的區(qū)域，每個(gè)區(qū)域有Nj（j=1，2，…，J）個(gè)停車位。因此共有車位。不同區(qū)域之間的距離為D=（dij）J×J，其中dij表示第i個(gè)區(qū)域到第j個(gè)區(qū)域的距離，假設(shè)dij=dji。由于涉及多個(gè)異質(zhì)區(qū)域，因此車位位置的劃分狀態(tài)用變量C=（cnj）N×J表示，其中：

考慮到每個(gè)周期都可能有車位供給者和車位需求者將車位信息提供到平臺(tái)上，因此τ周期新增的車位供給信息應(yīng)包含車位的可用時(shí)間段、車位的位置狀態(tài)等。τ周期新增的車位可用時(shí)間段用變量表示，其中：

如若Aτ中第n行=（1，1，0，…，0），則表示τ周期第n個(gè)車位新增第1、2 個(gè)周期可以用于停車。假設(shè)τ周期新增的停車位需求有Mτ個(gè)，由于停車位的需求信息包含顧客預(yù)約的停車時(shí)間及車位位置，因此顧客的預(yù)約時(shí)間用變量來(lái)表示：

為了更能夠反映現(xiàn)實(shí)情況，分配車位時(shí)不考慮在中途挪動(dòng)車輛到另一個(gè)停車位，即不允許用多個(gè)供給滿足一個(gè)需求。定義τ周期的分配決策變量為；m=1，2，…，Mτ；n=1，2，…，N。其中=1 表示τ周期新增的第m個(gè)需求被分配到第n個(gè)停車位，=0 表示τ周期新增的第m個(gè)需求未分配到第n個(gè)停車位。根據(jù)決策變量可以給出τ周期停車位的使用情況記為

假設(shè)平臺(tái)每成功出租一個(gè)車位，單位時(shí)間固定支付p0給車位供給者。平臺(tái)每成功出租一個(gè)車位平臺(tái)所獲得的單位收益為p，則τ周期平臺(tái)的總利潤(rùn)為。用表示顧客分配到各區(qū)域的狀態(tài)，其中。若=1，表示τ周期第m個(gè)需求被分配到第j個(gè)區(qū)域；若=0，表示τ周期第m個(gè)需求未被分配到第j個(gè)區(qū)域。因此車位位置的需求與供給匹配矩陣為，其 中=1 表示τ周期顧客預(yù)約的是第j個(gè)區(qū)域被實(shí)際分配到第i個(gè)區(qū)域；=0 表示顧客預(yù)約的是第j個(gè)區(qū)域未被實(shí)際分配到第i個(gè)區(qū)域。由于車位的稀缺性，可能會(huì)出現(xiàn)顧客預(yù)訂區(qū)域車位已經(jīng)停滿的情況，此時(shí)，平臺(tái)可能會(huì)用其他區(qū)域的車位去滿足顧客的預(yù)訂需求。不同區(qū)域的車位具有異質(zhì)性，分配其他區(qū)域的車位給顧客會(huì)改變步行距離，從而影響顧客的滿意度。步行距離越遠(yuǎn)，顧客的滿意度越低，平臺(tái)面臨的懲罰成本越高，因此，車位異質(zhì)性對(duì)平臺(tái)決策的影響可用步行距離帶來(lái)的懲罰成本進(jìn)行量化。若每增加一單位步行距離為平臺(tái)帶來(lái)的懲罰成本為π，則τ周期分配第i個(gè)區(qū)域的車位給需求為第j個(gè)區(qū)域的顧客所帶來(lái)的懲罰成本為。不同區(qū)域的車位所帶來(lái)的懲罰成本不同，因此不同區(qū)域車位的異質(zhì)性差異程度可由量化。由于τ周期顧客總的行走距離，因此平臺(tái)在分配中因車位異質(zhì)性帶來(lái)的總的懲罰成本為。綜上可得，τ周期平臺(tái)獲得的總利潤(rùn)由車位出租的利潤(rùn)和車位異質(zhì)性帶來(lái)的懲罰成本構(gòu)成，具體表達(dá)式如式（1）所示：

記τ周期剩余的車位為表示τ周期第n個(gè)車位在第t個(gè)周期有效；=0 時(shí)表示τ周期第n個(gè)車位在第t個(gè)周期不可使用。在τ周期剩余車位為Iτ，新增車位信息為Aτ、Qτ、Lτ的前提下，τ周期到T周期的總利潤(rùn)記為Gτ（Iτ|Aτ，Qτ，Lτ），則隨機(jī)動(dòng)態(tài)車位分配模型（random dynamic parking space allocation model，RDP）為

當(dāng)在τ周期進(jìn)行決策后，剩余的車位Iτ+1=Iτ+Aτ-Zτ，其中。因此，RDP模型在τ周期進(jìn)行決策時(shí)應(yīng)該滿足的可行停車位分配策略集為

定理1：當(dāng)時(shí)，=0。

證明：根據(jù)，顯然對(duì)于平臺(tái)而言，其分配一個(gè)車位的目的是希望獲得收益。當(dāng)τ周期面臨的需求信息和供給信息分別為Iτ、Aτ、Qτ、Lτ時(shí)，將決策變量Xτ展開(kāi)為向量。τ周期將第m個(gè)需求分配到第n個(gè)車位所獲得的利潤(rùn)為，而當(dāng)平臺(tái)將第m個(gè)需求分配到第n個(gè)車位所帶來(lái)的懲罰成本為。當(dāng)=1，則平臺(tái)得到的利潤(rùn)為。顯然若，平臺(tái)得到的利潤(rùn)為負(fù)，此時(shí)平臺(tái)不會(huì)將τ周期的第m個(gè)需求分配到第n個(gè)車位。所以有時(shí)，則平臺(tái)不愿意將第m個(gè)需求分配到第n個(gè)車位，即=0。

定理1 給出了車位分配的基本原則，即當(dāng)懲罰成本和單位租賃利潤(rùn)滿足定理1 所給的條件時(shí)，平臺(tái)不會(huì)將第m個(gè)需求分配到第n個(gè)車位。

性質(zhì)1：若用表示第m個(gè)顧客的需求向量，有且=1，則=0，j≠i。其中1T×1=（1，1，…，1）′。

證明：因假設(shè)不允許部分滿足顧客的需求，所以若滿足顧客的需求，則對(duì)于平臺(tái)而言，租賃車位的總時(shí)間為，因此其總收益為。顧客希望停在第i個(gè)區(qū)域而被分配到第j個(gè)區(qū)域則面臨的懲罰成本為πdij。當(dāng)滿足顧客m的需求獲得的利潤(rùn)時(shí)，平臺(tái)將不愿意采用該分配方案去滿足顧客。

性質(zhì)1 給出了區(qū)域分配的基本原則。通過(guò)性質(zhì)1 可以得到，平臺(tái)在用其他區(qū)域的車位去滿足顧客的需求（跨區(qū)域分配）時(shí)，需要權(quán)衡租賃車位帶來(lái)的懲罰成本與單位租賃利潤(rùn)之間的關(guān)系。定理1 和性質(zhì)1 在進(jìn)行模型求解時(shí)，可以排除掉一部分可行解，即將約束條件0 ≤≤1 中滿足定理1 和性質(zhì)1 的決策變量范圍改為0，從而簡(jiǎn)化求解過(guò)程。

盡管定理1 和性質(zhì)1 可以在一定程度上簡(jiǎn)化求解過(guò)程，但是并未實(shí)現(xiàn)決策變量或者狀態(tài)變量的降維，因此并未從本質(zhì)上解決RDP模型的計(jì)算復(fù)雜度。由于供給和需求信息在每個(gè)周期具有隨機(jī)性，因此在τ周期進(jìn)行決策時(shí)，其可能出現(xiàn)的狀態(tài)有以下結(jié)論：

性質(zhì)2：若At、Qt、Lt的狀態(tài)相互獨(dú)立且分別有Ut、Vt、Wt個(gè)，則τ周期進(jìn)行最優(yōu)決策時(shí)，τ+1 到T周期RDP模型可能出現(xiàn)的狀態(tài)變量（車位可用時(shí)間狀態(tài)）最多可達(dá)到種，其中；t=τ+2，…，T；特別的，=1。

證明：由于At、Qt、Lt均為矩陣，其維度較高。在RDP模型進(jìn)行決策時(shí)，需要考慮后續(xù)周期可能出現(xiàn)的狀態(tài)。若假設(shè)每個(gè)周期At、Qt、Lt的狀態(tài)分別有Ut、Vt、Wt個(gè)，則當(dāng)τ周期進(jìn)行最優(yōu)決策時(shí)，需考慮τ+1 到T周期的期望利潤(rùn)。當(dāng)τ周期進(jìn)行決策后，τ+1 周期的車位狀態(tài)為Iτ+1?？紤]到τ+1 周期出現(xiàn)的Aτ+1、Qτ+1、Lτ+1將會(huì)影響τ+2 周期的狀態(tài)變量，若假設(shè)t周期的狀態(tài)變量個(gè)數(shù)為，則τ+2 周期Iτ+2可能出現(xiàn)的狀態(tài)為個(gè)，τ+3 周期Iτ+3可能出現(xiàn)的狀態(tài)個(gè)數(shù)為。以此類推，t+1 周期的狀態(tài)變量個(gè)數(shù)為。特別的若每個(gè)周期可能出現(xiàn)的狀態(tài)個(gè)數(shù)相等，則狀態(tài)變量呈指數(shù)增長(zhǎng)。

由于需求和供給為連續(xù)周期，在τ+1周期時(shí)，任意一個(gè)車位的供給時(shí)間的狀態(tài)有種可能。假設(shè)有N個(gè)車位，不同車位可用時(shí)間狀態(tài)為獨(dú)立狀態(tài)。考慮車位數(shù)量和決策周期的限制，則狀態(tài)變量在τ周期進(jìn)行決策后，最多可能出現(xiàn)種狀態(tài)。綜上，RDP模型進(jìn)行決策時(shí)，后續(xù)周期狀態(tài)變量的可能狀態(tài)數(shù)量將急劇增加，最多可能出現(xiàn)種狀態(tài)。

根據(jù)性質(zhì)2，可得即使只有5 個(gè)停車位，共劃分為5 個(gè)周期。若當(dāng)前決策周期τ=2 且每個(gè)周期的Ut、Vt、Wt均相等，Ut=Vt=Wt=2，則后續(xù)周期可能會(huì)出現(xiàn)的狀態(tài)變量為16807 種，因此式（2）的計(jì)算復(fù)雜度非常高，無(wú)法直接進(jìn)行求解。為能夠在有效時(shí)間內(nèi)解決該問(wèn)題，接下來(lái)將設(shè)計(jì)近似算法以給出近似分配策略。

（二）單周期分配策略

由于模型RDP的計(jì)算復(fù)雜度很高，其車位分配決策難度大，無(wú)法在有效時(shí)間進(jìn)行求解。又因?yàn)檐囄坏膬r(jià)值較低，所以平臺(tái)在做決策時(shí)，更強(qiáng)調(diào)決策的高效性。為實(shí)現(xiàn)決策的高效性，平臺(tái)在實(shí)際決策中通常以某一個(gè)時(shí)段，如一天或者一個(gè)小時(shí)，進(jìn)行收益最大化決策。此時(shí)平臺(tái)不會(huì)考慮將現(xiàn)有車位預(yù)留到后期，以獲得更高的收益。即進(jìn)行決策時(shí)，平臺(tái)僅考慮當(dāng)前周期目標(biāo)函數(shù)最大化。由于τ周期進(jìn)行決策時(shí)是基于Aτ、Qτ、Lτ已知的前提下進(jìn)行車位的分配，因此以單周期的收益最大化為目標(biāo)函數(shù)的停車位分配模型（parking space allocation model，PSA）可構(gòu)建如下：

約束條件（5）說(shuō)明一位顧客只能分配到一個(gè)車位；約束條件（6）說(shuō)明車位分配的時(shí)間不能超過(guò)車位的供給時(shí)間，當(dāng)進(jìn)入τ周期決策時(shí)，應(yīng)該是對(duì)τ到T周期的車位時(shí)間有效時(shí)間進(jìn)行分配，所以t≥τ；約束條件（7）表示顧客是否分配到車位的狀態(tài)。由于PSA模型考慮單周期收益最大化，因此在每個(gè)周期進(jìn)行決策后，當(dāng)前周期的剩余車位將留到下一個(gè)周期，且滿足Iτ+1=Iτ+Aτ-Zτ。τ周期的優(yōu)化模型記為PSAτ，可將PSAτ模型改寫為矩陣的形式。PSAτ模型的決策變量為，因?yàn)?，所以決策變量關(guān)于的系數(shù)向量為

將PSAτ模型中約束條件構(gòu)造為不等式約束矩陣，具體形式如下：

因此PSAτ模型的矩陣形式為

具體的算法步驟如下：

Step1：初始化決策周期T，區(qū)域的基本信息J、Nj、C、D。

Step2：給定τ=1 時(shí)，供給和需求信息A1、Q1、L1、I1，以及區(qū)域的基本狀態(tài)信息，狀態(tài)變量I1=A1，根據(jù)Q1、L1、I1，計(jì)算c1，CA1，b1以及滿足定理1 和性質(zhì)1 的決策變量，將=0 作為新增約束條件，再根據(jù)整數(shù)規(guī)劃的求解方法計(jì)算給出第1 個(gè)決策周期的分配方案X1。

Step3：若τ＜T，則：

（1）計(jì)算τ周期的狀態(tài)變量Iτ=Iτ-1+Aτ-1-Zτ-1，根據(jù)Aτ，Qτ，Lτ，計(jì)算cτ，CAτ，bτ。

（3）重復(fù)步驟（1）～（2），直到τ=T，輸出第T個(gè)決策周期的分配方案XT，計(jì)算終止。

（三）模型的拓展

平臺(tái)在實(shí)際決策中考慮收益最大化的同時(shí)，通常還需要考慮保障平臺(tái)的服務(wù)水平。服務(wù)水平由顧客的平均行走距離和被拒絕的顧客數(shù)量來(lái)衡量。由于共享平臺(tái)的提出是為了充分利用閑置的車位以提高車位利用率，緩解停車難問(wèn)題。因此當(dāng)平臺(tái)在進(jìn)行τ周期決策時(shí)，需要考慮多目標(biāo)決策。在綜合考慮多個(gè)目標(biāo)的情況下，將式（1）中的目標(biāo)函數(shù)拓展為

其中：α1，α2，α3，α4分別表示平臺(tái)利潤(rùn)、步行距離的懲罰成本、被拒絕的顧客數(shù)以及車位利用率在決策中的權(quán)重。當(dāng)單周期的目標(biāo)函數(shù)為時(shí)，τ周期到T周期的總期望利潤(rùn)記為，則RDP的拓展模型為

顯然RDP的拓展模型維度也很高，很難進(jìn)行精確計(jì)算，因此同樣采用單周期分配策略進(jìn)行近似計(jì)算，可得PSA的拓展模型為以下形式：

在拓展模型中既能保證顧客的滿意度也能保證車位的利用率，因此拓展模型更具有現(xiàn)實(shí)意義。由于拓展模型的目標(biāo)函數(shù)包含了各指標(biāo)的權(quán)重，而權(quán)重的取值將會(huì)影響拓展模型的分配策略，因此權(quán)重的設(shè)定顯得尤為重要。在實(shí)際問(wèn)題中，權(quán)重的設(shè)定主要依賴于平臺(tái)的經(jīng)驗(yàn)和真實(shí)數(shù)據(jù)的收集，因此可以根據(jù)真實(shí)數(shù)據(jù)確定權(quán)重，再研究拓展模型的分配策略。

三、數(shù)值仿真

（一）算法有效性檢驗(yàn)

由于RDP模型的維度較高，難以在有效時(shí)間內(nèi)計(jì)算得到其最優(yōu)解，無(wú)法與PSA模型進(jìn)行對(duì)比檢驗(yàn)，又由于PSA模型是假設(shè)平臺(tái)不會(huì)將車位預(yù)留到后期以獲得更高的收益，因此為檢驗(yàn)該模型的有效性，本節(jié)將討論確定性情況下（即假設(shè)在期初，平臺(tái)已經(jīng)知道后面每個(gè)周期新增的供給與需求信息）允許將車位預(yù)留到后期以獲得更高收益的分配策略。若平臺(tái)提前已知每個(gè)周期會(huì)新增的停車位供給與需求信息，則平臺(tái)進(jìn)行分配時(shí)將考慮是否將車位預(yù)留到后期以獲得更高的利潤(rùn)。因此接下來(lái)首先構(gòu)造一個(gè)模型對(duì)PSA的有效性進(jìn)行檢驗(yàn)。

1.檢驗(yàn)?zāi)Ｐ偷臉?gòu)建

若平臺(tái)提前已知每個(gè)周期會(huì)新增的停車位供給與需求信息，則平臺(tái)分配時(shí)可以考慮將車位預(yù)留到后期以獲得更高的收益。若在τ周期，τ到T周期每個(gè)周期新增的停車位的供給與需求的相關(guān)信息Ak、Qk、Lk、k=τ，τ+1，…，T為已知信息，引用第二大節(jié)第（二）節(jié)的相關(guān)符號(hào)，則確定性分配策略模型為以下確定性線性規(guī)劃模型（deterministic linear programming，DLP）：

其中：m=1，2，…，Mτ；n=1，2，…，N；t=τ，τ+1，…，T；τ=1，2，…，T。

若令G=，分別用表示3 種模型最優(yōu)策略下的G值。由于在DLP模型中，平臺(tái)已經(jīng)知道每個(gè)周期將新增的車位供給信息與需求信息，則平臺(tái)在進(jìn)行決策時(shí)可以根據(jù)所有的車位信息進(jìn)行分配，因此，其分配策略集包含了PSA與RDP的分配策略集，所以有成立。在DLP模型中，每個(gè)周期的決策會(huì)影響下一個(gè)周期的決策，因此較PSA模型約束條件有所增加。根據(jù)PSA模型的矩陣形式很容易得到DLP模型的矩陣形式，不再贅述。接下來(lái)將采用數(shù)值仿真對(duì)PSA模型的有效性進(jìn)行檢驗(yàn)。

2.模型的有效性檢驗(yàn)

為了探討近似算法的有效性，將設(shè)計(jì)一系列的數(shù)值實(shí)驗(yàn)來(lái)驗(yàn)證單日近似分配算法的有效性。這里將DLP模型作為PSA模型有效性的檢驗(yàn)。首先初始化參數(shù)，假設(shè)劃分的區(qū)域共有3 個(gè)，3 個(gè)區(qū)域的停車位數(shù)量約為1/1/1，且每個(gè)周期車位供給的可能性是獨(dú)立同分布的。假設(shè)dij=dji，且任意兩個(gè)停車場(chǎng)的距離是服從［10，50］內(nèi)的均勻分布。令s=p-p0表示停車位每成功出租一個(gè)周期平臺(tái)獲得的凈利潤(rùn)，設(shè)置參數(shù)s=3，π=1。每個(gè)周期車位的需求和供給的開(kāi)始時(shí)刻服從等可能分布，需求周期長(zhǎng)度也服從等可能分布，在此假設(shè)下構(gòu)造供給矩陣以及需求矩陣。

在驗(yàn)證算法有效性時(shí)，這里還考慮了DLP模型的極端情況，即所有的供給和需求均在進(jìn)入決策周期之前已經(jīng)全部提供，此時(shí)每周期不再有新增的供給和需求。平臺(tái)在進(jìn)行分配時(shí)，只需要根據(jù)供給與需求的信息進(jìn)行靜態(tài)車位分配（static parking space allocation，SP）。接下來(lái)將隨機(jī)生成車位的供給和需求信息，分別在PSA模型、DLP模型、SP模型下分析不同的決策周期數(shù)以及車位數(shù)對(duì)目標(biāo)函數(shù)的影響，圖1～圖4 均為運(yùn)行50次后取均值得到的結(jié)果。

圖1 不同決策周期數(shù)下不同模型的利潤(rùn)

圖2 不同決策周期數(shù)下不同模型的利潤(rùn)比

圖3 不同車位數(shù)下不同模型的利潤(rùn)

圖4 不同車位數(shù)下不同模型的利潤(rùn)比

根據(jù)圖1～圖4，看出SP模型的利潤(rùn)總是高于DLP模型和PSA模型獲得的利潤(rùn)，說(shuō)明對(duì)于平臺(tái)而言，若供給信息和需求信息能夠提前提供，則可以減少?zèng)Q策時(shí)的不確定性，提高平臺(tái)的利潤(rùn)，因此平臺(tái)可以制訂一些激勵(lì)策略以促使需求者和供給者提前將信息發(fā)布到平臺(tái)上，增加平臺(tái)的收益。

（二）參數(shù)的靈敏度分析

由于PSA模型并未考慮車位利用率、顧客接受率、服務(wù)水平等，為從多個(gè)角度分析相關(guān)參數(shù)對(duì)PSA模型下分配策略的影響，接下來(lái)引入以下指標(biāo)作為檢驗(yàn)分配效果的標(biāo)準(zhǔn)。

（1）顧客接受率：接受率是指接受的顧客數(shù)與總的需求數(shù)的比率，因此接受率為。

（2）平均行走距離：由于行走距離會(huì)影響到顧客使用停車位的便利性，因此引入平均行走距離dˉ=來(lái)評(píng)估服務(wù)質(zhì)量。

（3）停車位利用率：共享停車位提出的目的之一是為提高車位使用率，將顧客使用車位的總時(shí)間與供給者提供的總供給時(shí)間的比值作為停車位利用率的衡量指標(biāo)，即。

（4）供需位置不同的車位指派率：由于本文考慮了行走距離帶來(lái)的懲罰成本較低時(shí)，平臺(tái)會(huì)將顧客指派到其他區(qū)域，因此引入供需位置不同的車位指派率（簡(jiǎn)稱“車位指派率”）r=來(lái)刻畫分配策略。

1.單位租賃利潤(rùn)對(duì)車位分配的影響

為研究單位周期凈利潤(rùn)對(duì)車位分配的影響，將s取不同的值，重新參數(shù)設(shè)置如下：J=3，N1=35，N2=35，N3=25。距離為［10，50］上的均勻分布。取上述4 個(gè)指標(biāo)的多次模擬的均值研究?jī)衾麧?rùn)變化對(duì)目標(biāo)函數(shù)、接受率、平均行走距離、停車位利用率、車位指派率的影響。為研究考慮跨區(qū)域分配的有效性，選擇顧客不接受步行的情況（即不允許需求為第i個(gè)區(qū)域的顧客分配到第j個(gè)區(qū)域）作為對(duì)比，結(jié)果見(jiàn)表1、表2。

表1 凈利潤(rùn)對(duì)分配策略的影響（T=15）

表2 凈利潤(rùn)對(duì)分配策略的影響（T=30）

根據(jù)表1、表2 可以看出PSA模型所獲得的利潤(rùn)遠(yuǎn)高于僅將同一個(gè)區(qū)域的車位進(jìn)行匹配時(shí)的利潤(rùn)。通過(guò)進(jìn)行跨區(qū)域的匹配，有效地提高了車位的利用率和顧客的接受率，從而緩解了停車難的問(wèn)題。在決策周期較短的情況下，隨著價(jià)格的增加，車位指派率、接受率、車位利用率、行走距離會(huì)有所上升，且當(dāng)價(jià)格對(duì)懲罰成本有絕對(duì)的優(yōu)勢(shì)時(shí)，其跨區(qū)域分配策略將不再受到價(jià)格的影響。由于PSA模型考慮的是當(dāng)前周期收益最大化，在決策時(shí)未考慮后面的周期。因?yàn)楫?dāng)前周期的最大化決策可能會(huì)影響后面的周期，所以當(dāng)周期較長(zhǎng)時(shí)，車位指派率和停車位利用率并不完全是價(jià)格的單調(diào)函數(shù)，而是會(huì)受到每個(gè)周期的需求和供給的影響。

2.懲罰成本對(duì)車位分配的影響

考慮到車位異質(zhì)性會(huì)影響顧客的滿意度，而顧客的滿意度以步行距離帶來(lái)的懲罰成本衡量，懲罰成本越大，則說(shuō)明車位的異質(zhì)性程度越強(qiáng)，對(duì)顧客滿意度的影響也越大。為研究車位異質(zhì)性對(duì)分配策略的影響，這里將懲罰成本取不同的值，研究其對(duì)接受率，平均行走距離和車位利用率的影響。具體仿真結(jié)果整理見(jiàn)表3、表4。

表3 懲罰成本對(duì)車位分配的影響（T=15）

表4 懲罰成本對(duì)車位分配的影響（T=30）

根據(jù)表3、表4 可以看出，隨著周期的增加，跨區(qū)域分配（PSA模型）的效果逐漸顯著優(yōu)于未進(jìn)行跨區(qū)域分配的效果。當(dāng)T=30 時(shí)，跨區(qū)域分配后得到的利潤(rùn)、顧客接受率、車位利用率均遠(yuǎn)高于未進(jìn)行跨區(qū)域時(shí)的值。因此，當(dāng)步行引起的懲罰成本較低時(shí)，采用跨區(qū)域分配優(yōu)于直接根據(jù)區(qū)域進(jìn)行匹配。隨著懲罰成本的增加，即車位異質(zhì)性增強(qiáng)，不同的車位對(duì)顧客的差異較大，則跨區(qū)域分配的收益逐漸減少，最終懲罰成本將會(huì)存在一個(gè)臨界值，使得當(dāng)超過(guò)該臨界時(shí)，平臺(tái)不會(huì)愿意進(jìn)行跨區(qū)域分配。定理1 和性質(zhì)1 給出了該臨界值的下界，因此平臺(tái)可以根據(jù)其下界，減少其分配方案，再進(jìn)行決策。

平臺(tái)每出租一個(gè)停車位的凈利潤(rùn)與懲罰成本顯著地影響了平臺(tái)的分配策略。為進(jìn)一步分析二者同時(shí)變化為平臺(tái)決策帶來(lái)的影響，下面將s與π同時(shí)變化，平臺(tái)所獲得利潤(rùn)以及跨區(qū)域分配比例的變化趨勢(shì)如圖5、圖6 所示。

圖5 T=15 時(shí)各指標(biāo)變化趨勢(shì)

圖6 T=30 時(shí)各指標(biāo)變化趨勢(shì)

根據(jù)圖5、圖6 可以得到，隨著懲罰成本的增加，即不同位置車位對(duì)顧客的差異較大時(shí)，車位指派率將逼近于0，車位利用率以及車位指派率總體呈下降趨勢(shì)。顯然只考慮單周期決策時(shí)，車位利用率以及車位指派率是懲罰成本和單位收益的單調(diào)函數(shù)，但是隨著決策周期的增加，車位利用率，車位指派率不再是懲罰成本和單位收益的單調(diào)函數(shù)。

在PSA模型中，當(dāng)懲罰成本較低時(shí)，即不同位置車位對(duì)顧客差異較小時(shí)，車位利用率較高；不考慮跨區(qū)域分配時(shí)，車位利用率顯著低于PSA模型的車位利用率，因此考慮跨區(qū)域分配能夠有效地提高車位利用率緩解停車難問(wèn)題，同時(shí)也可以有效地提高顧客接受率，減少顧客被拒絕的損失，因此平臺(tái)在對(duì)顧客步行距離產(chǎn)生的懲罰成本進(jìn)行較為精確的估計(jì)后，可以選擇跨區(qū)域分配算法（該算法包含不進(jìn)行跨區(qū)域分配的策略），該分配算法既可以提高平臺(tái)的收益和顧客的接受率，也可以提高車位的利用率從而緩解停車難問(wèn)題。

四、結(jié)論及展望

隨著智能技術(shù)的出現(xiàn)，共享停車逐漸出現(xiàn)在人們的日常生活中。本文首先根據(jù)車位異質(zhì)性對(duì)顧客的影響，對(duì)車位位置劃分區(qū)域，構(gòu)建了當(dāng)供給者和需求者動(dòng)態(tài)地向平臺(tái)提供信息時(shí)的隨機(jī)動(dòng)態(tài)規(guī)劃模型，并分析得到了車位分配的基本原則。由于原始模型求解的復(fù)雜度過(guò)高，因此根據(jù)車位基本分配原則設(shè)計(jì)單周期近似分配算法對(duì)問(wèn)題進(jìn)行求解，最后構(gòu)建檢驗(yàn)?zāi)Ｐ?，采用?shù)值仿真驗(yàn)證了近似分配算法的有效性以及異質(zhì)性對(duì)分配策略的影響程度。研究得到若供給信息和需求信息可以提前提供給平臺(tái)，則可以減少?zèng)Q策時(shí)的不確定性，提高平臺(tái)的利潤(rùn)；在決策周期較短的情況下，隨著懲罰成本的降低或者單位租賃凈利潤(rùn)的增加，車位的利用率和車位的指派率等均會(huì)上升；隨著決策周期的增加，車位利用率、車位指派率和平均行走距離卻并非懲罰成本與單位租賃凈利潤(rùn)的單調(diào)函數(shù)?？紤]跨區(qū)域分配能夠有效地提高車位利用率、顧客接受率以及平臺(tái)的收益，從而既保障了平臺(tái)的收益也緩解了停車難問(wèn)題，對(duì)于共享平臺(tái)的管理實(shí)踐具有一定的指導(dǎo)意義。但是值得注意的是若懲罰成本較大，即車位異質(zhì)性較強(qiáng)時(shí)，平臺(tái)將不愿意進(jìn)行跨區(qū)域分配。

除此之外，還可以從以下3 個(gè)方面進(jìn)行拓展研究：

（1）車位需求者的異質(zhì)性。實(shí)際上，顧客對(duì)于車位異質(zhì)性的敏感程度也具有差異性。如有的顧客對(duì)于停車后的行走距離敏感性較強(qiáng)，用較遠(yuǎn)車位去滿足該顧客，其不滿意度較大；而有的顧客對(duì)于停車后的行走距離敏感性較弱，則用較遠(yuǎn)車位滿足該顧客時(shí)，不滿意度將小于敏感性較強(qiáng)的顧客。因此，顧客對(duì)車位異質(zhì)性的敏感程度將影響車位的分配決策，接下來(lái)可進(jìn)一步研究車位需求者具有異質(zhì)性的前提下，車位的分配決策策略。

（2）總車位供給量隨機(jī)。在總車位供給量已知的前提下，研究不同時(shí)間段提供的車位具有隨機(jī)性的車位分配。因此，總車位供給量隨機(jī)時(shí)的車位的分配決策問(wèn)題可作為進(jìn)一步研究的方向。

（3）動(dòng)態(tài)定價(jià)。假設(shè)車位的價(jià)格是固定的，在實(shí)際生活中，價(jià)格是影響顧客需求的重要因素，平臺(tái)可通過(guò)設(shè)置不同時(shí)間的車位價(jià)格來(lái)調(diào)節(jié)車位的供需匹配問(wèn)題，因此車位動(dòng)態(tài)定價(jià)與車位分配的聯(lián)合決策問(wèn)題也是未來(lái)的研究方向。