基于緩沖時(shí)間的共享車(chē)位分配魯棒方法

薛召杰，袁秋芳，季楷豐

1）深圳大學(xué)土木與交通工程學(xué)院，廣東深圳 518061；2）深圳大學(xué)濱海城市韌性基礎(chǔ)設(shè)施教育部重點(diǎn)實(shí)驗(yàn)室，廣東深圳 518061；3）深圳大學(xué)未來(lái)地下城市研究院，廣東深圳 518061；4）深圳市前海智慧交通運(yùn)營(yíng)科技有限公司，廣東深圳 518052

隨著共享經(jīng)濟(jì)的快速發(fā)展，人們逐漸接受并認(rèn)可資源共享理念．通過(guò)車(chē)位共享平臺(tái)，可以充分利用車(chē)位的空閑時(shí)段，有效提升有限車(chē)位資源的利用效率，為緩解城市停車(chē)難問(wèn)題提供新思路．共享停車(chē)平臺(tái)的車(chē)位分配很大程度上決定著平臺(tái)收益和供需客戶(hù)服務(wù)質(zhì)量等，研究平臺(tái)車(chē)位分配問(wèn)題具有重要的經(jīng)濟(jì)價(jià)值和現(xiàn)實(shí)意義．

針對(duì)共享停車(chē)平臺(tái)車(chē)位分配問(wèn)題，LU［1］建立適合老社區(qū)的停車(chē)資源共享模型，以期緩解停車(chē)壓力．KASPI等［2］比較了部分停車(chē)預(yù)訂策略、停車(chē)位詳細(xì)預(yù)訂策略以及完整停車(chē)保留和非預(yù)訂策略，并給出每個(gè)策略的詳細(xì)用戶(hù)行為模型，通過(guò)離散事件仿真評(píng)估不同設(shè)置下的系統(tǒng)性能．SHAO等［3］在離散時(shí)間窗刻畫(huà)的停車(chē)供需基礎(chǔ)上，建立了使平臺(tái)收益最大化的二元整數(shù)線(xiàn)性規(guī)劃模型．YANG等［4］針對(duì)多個(gè)停車(chē)場(chǎng)的車(chē)位分配問(wèn)題，分析車(chē)位分配的主要影響因素，建立以總效益最大化為目標(biāo)的數(shù)學(xué)模型．孫會(huì)君等［5］以平臺(tái)運(yùn)營(yíng)商收益最大化為目標(biāo)，建立共享車(chē)位的租用與分配模型．張水潮等［6］提出一種以平臺(tái)收益與停車(chē)步行距離為優(yōu)化目標(biāo)的共享車(chē)位分配模型．

在預(yù)約停車(chē)的實(shí)際應(yīng)用中，需考慮停車(chē)不準(zhǔn)時(shí)問(wèn)題，即停車(chē)用戶(hù)相對(duì)于預(yù)約時(shí)間提前到達(dá)或延遲離開(kāi)的不確定性．JIANG等［7］考慮停車(chē)不準(zhǔn)時(shí)性的共享車(chē)位分配問(wèn)題，建立消費(fèi)者和車(chē)主在不同時(shí)段的停車(chē)概率函數(shù)和混合整數(shù)規(guī)劃模型來(lái)確定最優(yōu)解．RAN等［8］考慮停車(chē)者偏好、共享停車(chē)場(chǎng)景可行性、停車(chē)需求動(dòng)態(tài)分布及局部因素隨機(jī)性等因素，提出一種輔助決策的雙層模型．HUANG等［9］分析車(chē)輛到達(dá)數(shù)量和停車(chē)時(shí)間的隨機(jī)分布，建立以停車(chē)效益最大化為目標(biāo)的共享停車(chē)分配模型，并根據(jù)停車(chē)效益最大化原則，確定預(yù)留停車(chē)位的最佳比例及向居民購(gòu)買(mǎi)共享停車(chē)位的數(shù)量等．相較于預(yù)留停車(chē)位，本研究提出一種較為簡(jiǎn)單的緩沖時(shí)間預(yù)留方法，以車(chē)位共享平臺(tái)收益和分配魯棒性作為目標(biāo)，研究平臺(tái)車(chē)位的分配問(wèn)題．

1 車(chē)位分配問(wèn)題建模

本研究基于短時(shí)提前預(yù)約模式，即平臺(tái)在收集完所有停車(chē)需求、車(chē)位供給時(shí)間及數(shù)量等信息基礎(chǔ)上，再進(jìn)行車(chē)位資源的最優(yōu)分配．

1.1 平臺(tái)收益最大化模型

基于連續(xù)時(shí)間窗描述建立平臺(tái)收益最大化的車(chē)位分配模型．令S為供給停車(chē)位的總數(shù)，記停車(chē)位k的供給時(shí)間窗為[ak，bk]；令D為停車(chē)需求總數(shù)，記需求i的預(yù)約停車(chē)時(shí)間窗為[ci，di]；令ps和pb分別表示平臺(tái)對(duì)車(chē)位的售價(jià)（對(duì)停車(chē)用戶(hù)的單位時(shí)長(zhǎng)停車(chē)收費(fèi)價(jià)格）和進(jìn)價(jià)（從閑置車(chē)位出租方租入停車(chē)位的單位價(jià)格）．有限的車(chē)位資源一般不能滿(mǎn)足所有停車(chē)需求，μ為拒絕1個(gè)需求的懲罰成本．

定義0-1決策變量xik表示停車(chē)供需分配結(jié)果，若需求i被分配在停車(chē)位k，則xik=1，否則，xik=0；定義0-1決策變量yk表示平臺(tái)是否租入車(chē)位，yk=1為平臺(tái)租入車(chē)位k，否則，yk=0；定義0-1決策變量zij表示同一車(chē)位上不同停車(chē)需求之間的時(shí)序關(guān)系，zij=1表示需求i在j之前，否則，zij=0．

基于整數(shù)規(guī)劃模型的平臺(tái)收益最大化共享停車(chē)平臺(tái)車(chē)位分配問(wèn)題模型為

目標(biāo)函數(shù)（1）表示最大化平臺(tái)總收益，其中，第1項(xiàng)表示向停車(chē)用戶(hù)收費(fèi)的總收入；第2項(xiàng)表示租入停車(chē)位花費(fèi)的總費(fèi)用；第3項(xiàng)表示因拒絕部分需求造成的懲罰損失．約束（2）表示1個(gè)停車(chē)需求至多分配給1個(gè)停車(chē)位．約束（3）表示只有當(dāng)車(chē)位被平臺(tái)租入時(shí)，需求才能被分配到該車(chē)位上．約束（4）和（5）表示若需求i分配到停車(chē)位k，則應(yīng)滿(mǎn)足需求i的停車(chē)時(shí)間窗在停車(chē)位k的供給時(shí)間窗內(nèi)，否則，若ci＜ak或di＞bk，則xik=0．約束（6）限制了分配在同一車(chē)位上前后兩個(gè)停車(chē)需求之間的時(shí)間窗關(guān)系，其中，M為極大值．約束（7）至（9）表示當(dāng)zij=1時(shí)，需求i和j必須接受且分配給同一個(gè)停車(chē)位，即若zij=1，則xik=xjk且約束（10）表示當(dāng)需求i和j分配到同一停車(chē)位時(shí)，i在j的前面或后面，即若xik=xjk=1，則zij=1或zji=1．約束（11）定義0-1決策變量．

1.2 魯棒性最大化模型

當(dāng)停車(chē)需求相對(duì)預(yù)約時(shí)間提前到達(dá)或延遲離開(kāi)時(shí)，會(huì)將平臺(tái)根據(jù)預(yù)約時(shí)間生成的車(chē)位分配方案打亂，甚至導(dǎo)致方案不可行．因此，本研究通過(guò)預(yù)留緩沖時(shí)間應(yīng)對(duì)一定的時(shí)間不確定性，原理如圖1．假設(shè)需求i、j及j'均預(yù)約車(chē)位k，且j和j'的停車(chē)時(shí)長(zhǎng)相同，可行的分配結(jié)果如圖1．其中，圖1（a）的分配方案僅考慮平臺(tái)收益最大化，當(dāng)需求i延遲離開(kāi)或j提前到達(dá)時(shí)，可能會(huì)因?yàn)樾枨骿無(wú)法正常停車(chē)導(dǎo)致?lián)p失；圖1（b）方案預(yù)留一定的緩沖時(shí)間，這樣當(dāng)需求i短時(shí)間延遲離開(kāi)或j'提前到達(dá)時(shí)，方案依然可行．因此，圖1（b）方案較圖1（a）方案更優(yōu)．

圖1 緩沖時(shí)間原理示意Fig.1 Schematic diagram of buffer time

以下討論如何通過(guò)緩沖時(shí)間刻畫(huà)魯棒性大?。沨i為車(chē)位分配方案中需求i之后的緩沖時(shí)間長(zhǎng)度，考慮到邊際遞減效應(yīng)［10］，需求i的魯棒性g(hi)為

不同車(chē)輛在準(zhǔn)時(shí)方面具有不同聲譽(yù)，令需求i的不確定性系數(shù)為wi，則需求i的魯棒性變?yōu)閣ig(hi)，則魯棒性最大化目標(biāo)函數(shù)為

約束條件為

其中，約束（15）限定若需求i未被接受，則hi=0；約束（16）限定需求時(shí)間窗與緩沖時(shí)間和車(chē)位供給時(shí)間窗之間的關(guān)系；約束（17）限定同一車(chē)位上前后需求時(shí)間窗和緩沖時(shí)間之間的關(guān)系．

1.3 雙目標(biāo)優(yōu)化模型

引入目標(biāo)權(quán)重系數(shù)λ(0≤λ≤1)表示平臺(tái)對(duì)收益最大化和魯棒性最大化目標(biāo)函數(shù)的偏好，則雙目標(biāo)數(shù)學(xué)規(guī)劃模型可轉(zhuǎn)換為如下的單目標(biāo)數(shù)學(xué)模型，

2 數(shù)值實(shí)驗(yàn)

本節(jié)通過(guò)求解不同規(guī)模的隨機(jī)算例驗(yàn)證模型有效性．假設(shè)車(chē)位供給時(shí)間處于常規(guī)工作時(shí)間段09∶00—18∶00，具體的供給時(shí)間窗和需求時(shí)間窗通過(guò)Matlab生成，供給時(shí)間窗為均勻分布，需求到達(dá)符合泊松分布，停車(chē)時(shí)長(zhǎng)滿(mǎn)足負(fù)指數(shù)分布．參數(shù)ps=10、pb=5、μ=1，wi為1～10的隨機(jī)整數(shù)．

2.1 目標(biāo)函數(shù)線(xiàn)性化

由于目標(biāo)函數(shù)中包含的非線(xiàn)性項(xiàng)1-e-hi難以求解，采用分段線(xiàn)性函數(shù)近似擬合非線(xiàn)性曲線(xiàn)．根據(jù)單位時(shí)間長(zhǎng)度分段，則g(hi)的近似擬合表達(dá)式為

分段線(xiàn)性擬合曲線(xiàn)如圖2．實(shí)線(xiàn)表示原函數(shù)g(hi)=1-e-hi，虛線(xiàn)表示分段擬合線(xiàn)性函數(shù)．可見(jiàn)，hi=4后曲線(xiàn)基本可以完全重合．

圖2 非線(xiàn)性函數(shù)g(hi)=1-e-hi的線(xiàn)性擬合曲線(xiàn)Fig.2 Linear fitting plot of nonlinear function g(hi)=1-e-hi

為了將分段線(xiàn)性函數(shù)轉(zhuǎn)化為線(xiàn)性約束，將g(hi)以分點(diǎn)f0=0、f1=1、f2=2、f3=3、f4=4及f5=9的5段線(xiàn)性函數(shù)(m=5)，并引入變量uil，則hi和g(hi)可表示為

s.t.式（2）—式（5）、式（7）—式（11）、式（15）—式（17）及式（20）—式（26）.

2.2 不同規(guī)模算例求解

基于上述線(xiàn)性規(guī)劃模型，在配置為AMD 3.60 GHz CPU和16 GByte RAM電腦上采用商業(yè)求解軟件CPLEX對(duì)15組隨機(jī)生成的算例進(jìn)行求解．車(chē)位供給數(shù)從1遞增至15（步長(zhǎng)為1），停車(chē)需求數(shù)為對(duì)應(yīng)供給數(shù)的5倍，λ=0.8．求解得到的總目標(biāo)函數(shù)值、平臺(tái)收益、魯棒性、最優(yōu)分配方案的接受供給數(shù)、接受需求數(shù)、車(chē)位利用率指標(biāo)及計(jì)算時(shí)間見(jiàn)表1．其中，算例1-5表示供給車(chē)位數(shù)為1，停車(chē)需求數(shù)為5車(chē)位；利用率表示接受的需求總時(shí)長(zhǎng)與接受的供給總時(shí)長(zhǎng)之比；計(jì)算時(shí)間＜0.5 h．

表1 不同規(guī)模算例求解結(jié)果Table1 Solutionsof different scaleexamples

2.3 靈敏度分析

選擇算例5-25進(jìn)行靈敏度分析．保持其他參數(shù)不變，只改變?chǔ)耍é藦?.01到0.99，步長(zhǎng)為0.01），得到不同λ值下的平臺(tái)收益與魯棒性，及平臺(tái)收益-魯棒性的近似Pareto前沿分別如圖3和圖4．5個(gè)典型的車(chē)位分配方案見(jiàn)圖5．

圖3 不同λ值下的平臺(tái)收益與魯棒性Fig.3 Platform revenue and robustness with differentλ

圖4 平臺(tái)收益-魯棒性的近似Pareto前沿Fig.4 Approximate Pareto front of platform revenue-robustness

圖5 不同λ值下的匹配方案Fig.5 Allocation schemeswith differentλ

由圖3可見(jiàn)，隨著λ的增大，平臺(tái)收益分段增加，而魯棒性分段下降．當(dāng)λ=0.01時(shí)表示最注重魯棒性，當(dāng)λ=0.99時(shí)表示最注重平臺(tái)收益．在λ值變化范圍內(nèi)，平臺(tái)收益從-51.55升到84.85，魯棒性從51.07降到15.28．

圖4中的9個(gè)非支配解是當(dāng)λ從0.01變化到0.99這99個(gè)最優(yōu)解里篩選出的．非支配解擬合出的虛線(xiàn)表示近似Pareto前沿，靠近左上角的解偏向魯棒性，靠近右下角的解偏向平臺(tái)收益．從左上角到右下角，單位平臺(tái)收益增加引起的魯棒性減少量逐漸增加，減少量的變化范圍從0.02到6.75．

圖5中的空白矩形分別代表5個(gè)停車(chē)位S1—S5的供給時(shí)間窗，實(shí)心矩形代表接受的停車(chē)需求，用D1—D25表示．可見(jiàn)，隨著λ值的增大，矩形之間的間隙減?。?dāng)λ=0.01時(shí)，接受9個(gè)停車(chē)需求，拒絕16個(gè)；當(dāng)λ=0.20時(shí)，接受13個(gè)停車(chē)需求，拒絕12個(gè)；當(dāng)λ=0.40時(shí)，接受12個(gè)停車(chē)需求，拒絕13個(gè)；當(dāng)λ=0.60和0.80時(shí)，接受相同的11個(gè)停車(chē)需求，拒絕了14個(gè)；當(dāng)λ=0.99時(shí)，接受10個(gè)停車(chē)需求，拒絕15個(gè)．隨著λ值的增大，雖然平臺(tái)收益增加，但是應(yīng)對(duì)不確定性的能力（魯棒性）降低．根據(jù)不同λ值，平臺(tái)給出不同的匹配方案以達(dá)到平衡總收益和魯棒性的目的．

結(jié) 語(yǔ)

在共享車(chē)位分配中，通過(guò)預(yù)留緩沖時(shí)間的方法解決時(shí)間不確定性因素，建立平臺(tái)收益最大化與魯棒性最大化的雙目標(biāo)優(yōu)化模型．①通過(guò)雙目標(biāo)優(yōu)化模型，在合理時(shí)間內(nèi)可以求解出算例規(guī)模為15-75的最優(yōu)解及各項(xiàng)指標(biāo)值；②通過(guò)雙目標(biāo)調(diào)節(jié)系數(shù)λ可以平衡平臺(tái)收益與分配方案的魯棒性，隨著λ值的增大，平臺(tái)收益分段增加，而魯棒性分段下降；③基于特定算例，改變?chǔ)酥登蟮米顑?yōu)解，篩選非支配解并擬合出近似帕累托前沿曲線(xiàn)，算例5-25中增加單位平臺(tái)收益帶來(lái)的魯棒性的減少量的變化范圍為［0.02，6.75］．

本研究方法可以在保證分配方案穩(wěn)定運(yùn)行的前提下，較好應(yīng)對(duì)車(chē)輛提前到達(dá)或延遲離開(kāi)所導(dǎo)致的不確定性，提高共享停車(chē)位預(yù)訂與分配的合理性．今后研究?jī)?nèi)容可集中在非固定工作時(shí)間內(nèi)的私人停車(chē)位共享問(wèn)題，并設(shè)計(jì)計(jì)算效率更高的算法來(lái)求解大規(guī)模算例．