無(wú)人駕駛條件下共享停車匹配模型及算法

何勝學(xué)，馬思涵，程朝中，崔允汀，郁奇凡

(上海理工大學(xué)，管理學(xué)院，上海200093)

0 引言

共享停車在城市停車難問(wèn)題日益嚴(yán)峻的今天受到越來(lái)越多的關(guān)注。各種共享停車平臺(tái)紛紛涌現(xiàn)，預(yù)約式共享停車實(shí)踐也在許多城市出現(xiàn)。共享停車中泊位擁有者將空閑時(shí)段的泊位通過(guò)共享平臺(tái)出租以獲取收益，而其他車輛使用者向平臺(tái)預(yù)約特定區(qū)域內(nèi)一定時(shí)段的共享泊位以便停車。在最大化滿足停車需求，并提高泊位利用率的條件下，如何將上述具有差異化時(shí)間窗限制的需求與供給加以合理匹配就成為共享停車實(shí)踐的首要問(wèn)題。

與此同時(shí)，無(wú)人駕駛技術(shù)日益成熟，以無(wú)人公交、無(wú)人出租車和無(wú)人清掃車為先導(dǎo)的無(wú)人駕駛實(shí)踐紛紛涌現(xiàn)。無(wú)人駕駛對(duì)共享停車也帶來(lái)了諸多影響。一方面，無(wú)人駕駛需要更多通信和AI 技術(shù)的支持，因此有必要進(jìn)一步提升現(xiàn)有停車設(shè)施；另一方面，無(wú)人駕駛車輛在泊車過(guò)程中可自主改變泊位的特征也為提高泊位的利用率帶來(lái)了新契機(jī)。如果是有人駕駛車輛，當(dāng)車輛的停車需求時(shí)間段與泊位的開放時(shí)間段不匹配時(shí)，兩者的共享停車匹配不能成立；如果是無(wú)人駕駛車輛，只要停車需求與泊位供給在時(shí)間上有交集，兩者間的匹配就有可能成立。因?yàn)闊o(wú)人駕駛車輛可以在該時(shí)間交集上停放在該泊位，而在其他時(shí)間段通過(guò)自主移動(dòng)停放到其他泊位。無(wú)人駕駛車輛的上述優(yōu)勢(shì)，為充分利用有限的共享泊位資源提供了條件，但是不合理的匹配也可能造成無(wú)人車的頻繁移位，增加用車成本，并引發(fā)交通事故。

為在利用無(wú)人駕駛特征提升泊位利用率的同時(shí)減少無(wú)人車頻繁改變泊位帶來(lái)的用車成本和潛在交通事故風(fēng)險(xiǎn)，本文以泊車過(guò)程中的車輛移位次數(shù)和距離最小化作為優(yōu)化目標(biāo)建立相應(yīng)的車輛與泊位時(shí)空匹配優(yōu)化模型，并設(shè)計(jì)有效的求解方法。

在共享停車需求分析方面，研究者分別從平臺(tái)收益與步行距離平衡[1]、停車需求分布與路徑選擇的關(guān)聯(lián)性[2]、泊位擁有者參與共享停車的意愿[3]和共享無(wú)人車對(duì)泊位需求的影響[4]等角度進(jìn)行了深入分析。文獻(xiàn)[5]在綜合租用車位成本、提供停車服務(wù)收入和拒絕潛在用戶損失的基礎(chǔ)上，以平臺(tái)收益最大化為目標(biāo)，構(gòu)建了車位租用和停車需求分配的統(tǒng)一決策模型。文獻(xiàn)[6]以步行距離的差異定義共享車位的異質(zhì)性，構(gòu)建了跨區(qū)域泊位分配的隨機(jī)動(dòng)態(tài)規(guī)劃模型。文獻(xiàn)[7]利用滾動(dòng)時(shí)域方法對(duì)實(shí)時(shí)獲得的共享停車供需進(jìn)行滾動(dòng)式動(dòng)態(tài)匹配。文獻(xiàn)[8]以最大化泊位利用率和減少步行距離為目標(biāo)，建立共享停車的泊位分配模型。文獻(xiàn)[9]通過(guò)分析停車需求的到達(dá)時(shí)間和停泊時(shí)長(zhǎng)分布，確定最佳共享泊位和保留非共享泊位的數(shù)量。文獻(xiàn)[10]提出了一種基于序列拍賣的共享停車泊位分配和定價(jià)方法。文獻(xiàn)[11]構(gòu)建了基于拍賣機(jī)制的共享停車泊位分配、定價(jià)和收益機(jī)制。針對(duì)無(wú)人駕駛對(duì)停車供需匹配的影響，文獻(xiàn)[12]分析了無(wú)人車市場(chǎng)占有率、燃油費(fèi)和停車費(fèi)對(duì)無(wú)人車在完成載客后選擇停車場(chǎng)的影響。文獻(xiàn)[13]分析了在不同的停車能力限制條件下共享無(wú)人車的市場(chǎng)占有率對(duì)早上通勤出行的影響。文獻(xiàn)[14]利用仿真模型對(duì)共享無(wú)人車、私有無(wú)人車、共享有人車和非共享有人車共存情況下的停車需求變化進(jìn)行分析，發(fā)現(xiàn)共享車輛的存在可降低總體停車需求，但也會(huì)增加部分敏感區(qū)域的停車需求。文獻(xiàn)[15]分析了停車管理策略對(duì)需求響應(yīng)式共享無(wú)人車規(guī)模、服務(wù)效率和公平性的影響。對(duì)于無(wú)人駕駛條件下的共享停車，現(xiàn)有研究多關(guān)注無(wú)人車的市場(chǎng)占有率和其影響，對(duì)停車期間無(wú)人車在停車區(qū)域內(nèi)可靈活移位特征的應(yīng)用與影響缺乏研究。本研究將關(guān)注無(wú)人車這一具體特征對(duì)共享停車匹配的影響，通過(guò)構(gòu)建優(yōu)化模型，并給出有效算法，以期實(shí)現(xiàn)泊位資源的進(jìn)一步優(yōu)化匹配。

與現(xiàn)有研究相比，本文的特色表現(xiàn)為：與現(xiàn)有無(wú)人駕駛研究多關(guān)注車輛的路線選擇、停車目的地選擇和停車自動(dòng)繳費(fèi)技術(shù)不同，本文關(guān)注無(wú)人駕駛特征對(duì)停車服務(wù)的影響，并以優(yōu)化泊車中的車輛移位為重點(diǎn)；通過(guò)分析車輛與泊位的時(shí)空匹配結(jié)構(gòu)特征，合理定義可行匹配的鄰域，從而實(shí)現(xiàn)利用模擬退火算法對(duì)匹配模型的有效求解。

1 匹配模型

1.1 參變量介紹

V——具有共享停車需求的無(wú)人車集合，v為其中的一輛無(wú)人車，v∈V；

P——提供可共享服務(wù)的泊位集合，p為其中的一個(gè)泊位，p∈P；

tv,enter、tv,leave——無(wú)人駕駛車輛v共享停車需求的開始時(shí)刻、結(jié)束時(shí)刻；

tp,start、tp,end——共享泊位p提供共享停車服務(wù)的開始時(shí)刻、結(jié)束時(shí)刻；

k——將總的共享停車時(shí)間劃分為K個(gè)連續(xù)分割時(shí)間段后其中的一段，；

wv——無(wú)人車v一次移位的懲罰性成本，假設(shè)其單位與相同；

1.2 優(yōu)化模型

模型構(gòu)建的基本假設(shè)條件包括：①在預(yù)約式共享停車服務(wù)中，已知停車需求的具體時(shí)間段和泊位供給的具體時(shí)間段；②為避免無(wú)法提供服務(wù)，假設(shè)任一時(shí)刻泊位的總供給大于該時(shí)刻總的停車需求；③共享停車中，有人車在停放后一般不會(huì)改變其泊車位置；④無(wú)人車可通過(guò)遠(yuǎn)程控制或自主與平臺(tái)交互，在停放中自主調(diào)換其泊位，但僅在供需時(shí)段的首末時(shí)間點(diǎn)進(jìn)行車輛移位。

為刻畫無(wú)人車可自主變換泊位的特征，將每個(gè)泊位的共享時(shí)段和每輛車的停車需求時(shí)段按下述方法加以分割：將所有停車供需時(shí)段的首末時(shí)間點(diǎn)放入一個(gè)集合，并按升序?qū)r(shí)間點(diǎn)排序；將所有車輛的共享需求時(shí)間與泊位的共享時(shí)間以上述時(shí)間序列的時(shí)刻為分割點(diǎn)加以劃分，得到相應(yīng)的分割時(shí)間段。如果無(wú)人車在兩個(gè)連續(xù)的小時(shí)間段分別停放于不同的泊位，代表其進(jìn)行了移位。而有人車則必須在其停車需求時(shí)間內(nèi)停放在同一泊位上。

滿足共享停車需求條件下，以最小化車輛移位距離和移位懲罰成本為目標(biāo)的無(wú)人車與泊位時(shí)空匹配模型為

式(1)為目標(biāo)函數(shù)，第1個(gè)加和項(xiàng)為共享泊車過(guò)程中車輛總的移位距離，第2個(gè)加和項(xiàng)是泊車過(guò)程中車輛移位的總懲罰成本。式(2)保證泊位在任一分割時(shí)段最多只能被1 輛車占用。式(3)表示無(wú)人車在任一時(shí)段的共享停車需求必須得到滿足。式(4)是決策變量的0-1 特征約束。對(duì)式(2)和式(3)進(jìn)行加和，可得

式(5)表明所有的可接受停車需求必須得到滿足。這里的“可接受”是指任一時(shí)刻泊位的總供給大于該時(shí)刻的總停車需求。

匹配模型式(1)～式(4)屬于純整數(shù)二次規(guī)劃模型，是一類特殊的二次分配模型?，F(xiàn)有研究表明二次分配屬于極難的NP-hard 問(wèn)題，目前不存在可在現(xiàn)實(shí)可行時(shí)間內(nèi)確定較大規(guī)模二次分配問(wèn)題精確解的方法。因此，需利用式(1)～式(4)解的結(jié)構(gòu)特征設(shè)計(jì)對(duì)應(yīng)的啟發(fā)式求解算法。

2 模擬退化算法

2.1 解的鄰域

下面通過(guò)定義匹配圖的鄰域來(lái)確定對(duì)應(yīng)可行解的鄰域。

Mi的k時(shí)段鄰域定義為

2.2 算法流程

模擬退火算法(Simulated Annealing Algorithm,SA)是一種通用的啟發(fā)式算法。該算法具有跳出局部最優(yōu)解，且在理論上以概率1漸進(jìn)收斂于全局最優(yōu)解的特征。下面給出針對(duì)模型式(1)～式(4)的SA具體操作步驟。

Step 1 初始化。給定初始溫度Γ、最大鄰域搜索次數(shù)β、降溫系數(shù)ε。令當(dāng)前溫度G=Γ，當(dāng)前迭代次數(shù)n=1，當(dāng)前鄰域搜索次數(shù)τ=0。

Step 2 生成初始匹配。由匹配圖定義，隨機(jī)生成一個(gè)匹配圖。令當(dāng)前匹配圖和最優(yōu)匹配均等于。

Step 3 生成M(n)的鄰居。如果τ ＞β，轉(zhuǎn)Step 5；否則，令τ:=τ+1，并執(zhí)行如下操作，從所有分割時(shí)段中隨機(jī)選擇一個(gè)時(shí)段k，隨機(jī)生成一個(gè)Sk，用Sk替代中時(shí)段k的匹配組，得到的一個(gè)鄰居。

Step 4.2 生成在[0,1]區(qū)間內(nèi)的均勻分布的一個(gè)隨機(jī)數(shù)δ。

Step 4.3 如果δ≤Pr，用代替，并轉(zhuǎn)Step 3；否則，直接轉(zhuǎn)Step 3。

Step 6 終止判斷。如果G≤1 或Mˉ對(duì)應(yīng)的目標(biāo)函數(shù)值為0，算法終止，輸出Mˉ；否則，轉(zhuǎn)Step 3。

3 算例分析

求解算法利用Java語(yǔ)言實(shí)現(xiàn)，執(zhí)行程序的計(jì)算機(jī)處理器為Intel?Core i3-3120M CPU。為便于分析令所有車輛的懲罰性成本wv為100 km，而任意兩個(gè)泊位間的移車距離均取自區(qū)間[0.010，0.100]km上服從均勻分布的隨機(jī)數(shù)。上述假設(shè)將便于從最終匹配結(jié)果直接判斷需要移車的次數(shù)和總距離。例如，最終目標(biāo)函數(shù)值為200.142 km，則表明需要移車2次，移車的總距離為0.142 km。

首先分析一個(gè)有10個(gè)泊位和14輛車的共享停車匹配問(wèn)題。該問(wèn)題的停車需求和泊位開放時(shí)間如表1和表2所示。無(wú)人車在泊位間變換停放位置的行駛路線長(zhǎng)度在矩陣E中給出。E中第i行第j列的元素值表示從第i個(gè)泊位移車到第j個(gè)泊位的無(wú)人車行駛路線長(zhǎng)度。按式計(jì)算得到的名義泊位利用率φ=0.795。

表1 車輛停車需求Table 1 Parking demand of vehicles

表2 泊位共享開放時(shí)間Table 2 Opening times of sharing slots

圖1 用矩陣形式給出算法得到的最佳匹配結(jié)果，矩陣中第1列第1行的“sn”表示第1列為泊位的序號(hào)，矩陣的第1行數(shù)字表示分割時(shí)段的序號(hào)。矩陣圖中其他元素的定義如下：“/”表示對(duì)應(yīng)泊位在對(duì)應(yīng)分割時(shí)段不開放；“__”表示對(duì)應(yīng)泊位在對(duì)應(yīng)分割時(shí)段為共享停車開放，但沒有被占用；數(shù)字“n”表示對(duì)應(yīng)泊位在對(duì)應(yīng)分割時(shí)段被序號(hào)為n的車輛占用。圖1 數(shù)據(jù)表明：無(wú)人車1 和4 各需移車1 次，利用E的數(shù)據(jù)可知，2 次移車的距離分別為0.064 km 和0.078 km；對(duì)應(yīng)最優(yōu)目標(biāo)函數(shù)值，存在多個(gè)可行匹配圖，如無(wú)人車11 除現(xiàn)在的泊位6，還可選擇停放在泊位3；無(wú)人車4 的需求無(wú)法被任何單一的開放共享泊位滿足，若將無(wú)人車4轉(zhuǎn)化為有人車，其需求將無(wú)法得到滿足；無(wú)人車1的需求，在無(wú)人車4的停車需求被拒時(shí)，可被泊位1滿足。

圖1 最佳匹配的矩陣圖Fig.1 Matrix of the best matches

表3 為在8 種車輛數(shù)、泊位數(shù)和名義泊位占用率組合條件下，匹配優(yōu)化的部分結(jié)果。表中，CT表示計(jì)算時(shí)間，φ為名義泊位利用率，和分別表示算法迭代過(guò)程中最優(yōu)目標(biāo)函數(shù)的初值和終值。從表3 的結(jié)果可知：隨問(wèn)題規(guī)模增大，計(jì)算耗時(shí)增加，目標(biāo)函數(shù)值也顯著增加；同一情景下最終的目標(biāo)值可縮小到不到初值的5%，在問(wèn)題規(guī)模較小時(shí)甚至接近2.5%；從計(jì)算耗時(shí)來(lái)看，新算法可應(yīng)用于求解實(shí)際規(guī)模的共享匹配問(wèn)題。

表3 不同情境下算法的計(jì)算結(jié)果Table 3 Results from different scenarios

從表3最后一列數(shù)據(jù)可知，最終匹配的車輛移位次數(shù)和總的移車距離。例如情景4 對(duì)應(yīng)的的值為1400.69 km，表示需移車14次，而總的移車距離為690 m。由于在生成算例時(shí)限定任意兩個(gè)車位間的移車距離小于100 m，因此每次移車的車輛行駛時(shí)間較小，對(duì)車輛和泊位的供需時(shí)段匹配影響較小。但是當(dāng)兩個(gè)車位間距離較大時(shí)，移車時(shí)間可能較長(zhǎng)，會(huì)對(duì)上述的匹配產(chǎn)生影響。考慮到現(xiàn)實(shí)中每個(gè)停車需求和每個(gè)供給的時(shí)間跨度一般都在幾十分鐘以上，而移車的時(shí)間一般不超過(guò)幾分鐘，上述較短的移車時(shí)間一般對(duì)實(shí)際的匹配影響甚微，因此，在構(gòu)建本文優(yōu)化模型時(shí)忽略了上述可能的影響。

另一方面，考慮到啟發(fā)式方法一般只能給出問(wèn)題的一個(gè)局部最優(yōu)解，且每次執(zhí)行可能給出不同的解，要得到一個(gè)較好的匹配結(jié)果，有必要多次運(yùn)行算法，比較后確定一個(gè)滿意的最終結(jié)果。從表3給出的程序運(yùn)行時(shí)間數(shù)據(jù)可知，模擬退火算法運(yùn)行一次的時(shí)間很短，故在多次反復(fù)執(zhí)行的要求下，也可滿足實(shí)際的運(yùn)行需要。

上述計(jì)算所設(shè)初始溫度Γ=1000，鄰域搜索次數(shù)β=2，降溫系數(shù)ε=0.03。假設(shè)溫度低于1 時(shí)，算法終止。為驗(yàn)證算法的有效性，以匹配問(wèn)題1為基礎(chǔ)對(duì)算法的兩個(gè)主要參數(shù)β和ε進(jìn)行靈敏度分析。圖2 為鄰域搜索次數(shù)β分別為1，2，4 和6 時(shí)，目標(biāo)函數(shù)隨迭代次數(shù)增加的變化情況。圖1 數(shù)據(jù)顯示4 種情況下目標(biāo)函數(shù)均隨迭代增加而降低，β值越大，算法前期的收斂越快，最終的目標(biāo)函數(shù)值也較優(yōu)。但4種情況的收斂趨勢(shì)一致，說(shuō)明算法具有較高的可靠性。當(dāng)鄰域搜索次數(shù)較大時(shí)，算法在迭代初期可能得到較好的初始目標(biāo)函數(shù)值。

圖2 鄰域搜索次數(shù)β 對(duì)算法迭代的影響Fig.2 Impact of search number β in neighborhood on algorithm

圖3 為當(dāng)降溫系數(shù)分別為0.100、0.075、0.050和0.025時(shí)算法的收斂表現(xiàn)。在初始溫度相同條件下，隨著降溫系數(shù)減小，算法的迭代次數(shù)增加。數(shù)據(jù)顯示，降溫速度慢會(huì)增加迭代次數(shù)，但也會(huì)改善算法得到的最終優(yōu)化目標(biāo)。降溫系數(shù)較大時(shí)算法在前期的表現(xiàn)較差。盡管降溫系數(shù)差異較大，算法的收斂表現(xiàn)一致，說(shuō)明算法的魯棒性較強(qiáng)。

圖3 降溫系數(shù)ε 對(duì)算法的影響Fig.3 Impact of temperature reduce rate ε of on algorithm

4 結(jié)論

本文主要結(jié)論如下：

(1)利用無(wú)人車靈活移位特征可以有效提升共享泊位利用率，減少可接受停車需求的拒絕率。從算例1的分析結(jié)果可知，共享泊位的利用時(shí)間增加了415 min，可接受的停車需求拒絕率由14.3%降為0。

(2)將停車需求和泊位供給在時(shí)間上加以分割來(lái)反映無(wú)人車泊車中靈活移位的特征，進(jìn)而實(shí)現(xiàn)基于解的時(shí)空特征定義匹配圖和匹配圖鄰域。

(3)經(jīng)模型求解優(yōu)化，無(wú)人車的移位次數(shù)可減少到不足初值的5%，實(shí)現(xiàn)降低移車成本和風(fēng)險(xiǎn)的目的。

(4)隨著問(wèn)題規(guī)模增大，求解模型的耗時(shí)有所增加，但是求解時(shí)間均小于1 s，可保證算法的實(shí)用性。