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

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

0 引言

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

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

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

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

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

1 匹配模型

1.1 參變量介紹

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

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

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

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

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

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

1.2 優(yōu)化模型

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

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

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

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

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

匹配模型式(1)～式(4)屬于純整數(shù)二次規(guī)劃模型，是一類(lèi)特殊的二次分配模型?，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。為便于分析令所有車(chē)輛的懲罰性成本wv為100 km，而任意兩個(gè)泊位間的移車(chē)距離均取自區(qū)間[0.010，0.100]km上服從均勻分布的隨機(jī)數(shù)。上述假設(shè)將便于從最終匹配結(jié)果直接判斷需要移車(chē)的次數(shù)和總距離。例如，最終目標(biāo)函數(shù)值為200.142 km，則表明需要移車(chē)2次，移車(chē)的總距離為0.142 km。

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

表1 車(chē)輛停車(chē)需求Table 1 Parking demand of vehicles

表2 泊位共享開(kāi)放時(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í)段不開(kāi)放；“__”表示對(duì)應(yīng)泊位在對(duì)應(yīng)分割時(shí)段為共享停車(chē)開(kāi)放，但沒(méi)有被占用；數(shù)字“n”表示對(duì)應(yīng)泊位在對(duì)應(yīng)分割時(shí)段被序號(hào)為n的車(chē)輛占用。圖1 數(shù)據(jù)表明：無(wú)人車(chē)1 和4 各需移車(chē)1 次，利用E的數(shù)據(jù)可知，2 次移車(chē)的距離分別為0.064 km 和0.078 km；對(duì)應(yīng)最優(yōu)目標(biāo)函數(shù)值，存在多個(gè)可行匹配圖，如無(wú)人車(chē)11 除現(xiàn)在的泊位6，還可選擇停放在泊位3；無(wú)人車(chē)4 的需求無(wú)法被任何單一的開(kāi)放共享泊位滿足，若將無(wú)人車(chē)4轉(zhuǎn)化為有人車(chē)，其需求將無(wú)法得到滿足；無(wú)人車(chē)1的需求，在無(wú)人車(chē)4的停車(chē)需求被拒時(shí)，可被泊位1滿足。

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

表3 為在8 種車(chē)輛數(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ù)可知，最終匹配的車(chē)輛移位次數(shù)和總的移車(chē)距離。例如情景4 對(duì)應(yīng)的的值為1400.69 km，表示需移車(chē)14次，而總的移車(chē)距離為690 m。由于在生成算例時(shí)限定任意兩個(gè)車(chē)位間的移車(chē)距離小于100 m，因此每次移車(chē)的車(chē)輛行駛時(shí)間較小，對(duì)車(chē)輛和泊位的供需時(shí)段匹配影響較小。但是當(dāng)兩個(gè)車(chē)位間距離較大時(shí)，移車(chē)時(shí)間可能較長(zhǎng)，會(huì)對(duì)上述的匹配產(chǎn)生影響?？紤]到現(xiàn)實(shí)中每個(gè)停車(chē)需求和每個(gè)供給的時(shí)間跨度一般都在幾十分鐘以上，而移車(chē)的時(shí)間一般不超過(guò)幾分鐘，上述較短的移車(chē)時(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ú)人車(chē)靈活移位特征可以有效提升共享泊位利用率，減少可接受停車(chē)需求的拒絕率。從算例1的分析結(jié)果可知，共享泊位的利用時(shí)間增加了415 min，可接受的停車(chē)需求拒絕率由14.3%降為0。

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

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

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