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

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

0 引言

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

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

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

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

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

1 匹配模型

1.1 參變量介紹

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

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

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

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

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

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

1.2 優(yōu)化模型

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

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

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

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

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

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

2 模擬退化算法

2.1 解的鄰域

下面通過定義匹配圖的鄰域來確定對(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語言實(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輛車的共享停車匹配問題。該問題的停車需求和泊位開放時(shí)間如表1和表2所示。無人車在泊位間變換停放位置的行駛路線長度在矩陣E中給出。E中第i行第j列的元素值表示從第i個(gè)泊位移車到第j個(gè)泊位的無人車行駛路線長度。按式計(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ù)表明：無人車1 和4 各需移車1 次，利用E的數(shù)據(jù)可知，2 次移車的距離分別為0.064 km 和0.078 km；對(duì)應(yīng)最優(yōu)目標(biāo)函數(shù)值，存在多個(gè)可行匹配圖，如無人車11 除現(xiàn)在的泊位6，還可選擇停放在泊位3；無人車4 的需求無法被任何單一的開放共享泊位滿足，若將無人車4轉(zhuǎn)化為有人車，其需求將無法得到滿足；無人車1的需求，在無人車4的停車需求被拒時(shí)，可被泊位1滿足。

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

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

表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í)間可能較長，會(huì)對(duì)上述的匹配產(chǎn)生影響。考慮到現(xiàn)實(shí)中每個(gè)停車需求和每個(gè)供給的時(shí)間跨度一般都在幾十分鐘以上，而移車的時(shí)間一般不超過幾分鐘，上述較短的移車時(shí)間一般對(duì)實(shí)際的匹配影響甚微，因此，在構(gòu)建本文優(yōu)化模型時(shí)忽略了上述可能的影響。

另一方面，考慮到啟發(fā)式方法一般只能給出問題的一個(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)證算法的有效性，以匹配問題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ì)一致，說明算法具有較高的可靠性。當(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)一致，說明算法的魯棒性較強(qiáng)。

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

4 結(jié)論

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

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

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

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

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