何勝學(xué)

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

0 引言

傳統(tǒng)的自動代客泊車(Autonomous Valet Parking,AVP)研究更多關(guān)注無人駕駛車輛如何合理規(guī)劃行車路線和選擇停車場，從而減少乘客的總的乘車時間和步行時間。也有一些研究考慮無人駕駛對共享停車供需量的影響，但是很少有研究涉及無人駕駛在共享停車中如何通過變換泊位進一步發(fā)掘有限的共享泊位資源。一方面，在泊車過程中通過變換泊位可以減少共享泊位空閑的碎片時間，滿足更多的停車需求；另一方面，如果頻繁進行泊位變換勢必增加車輛的運行成本，同時提高發(fā)生事故的風(fēng)險。為了化解上述矛盾，有必要對共享停車的需求和供給加以合理的匹配優(yōu)化。針對上述問題，本研究將嘗試建立在滿足預(yù)約停車需求條件下最小化無人車變換泊位次數(shù)與移車總距離的匹配優(yōu)化模型，并給出模型的有效算法，從而為AVP在共享停車中的進一步應(yīng)用提供理論支持。

在共享停車需求分析方面，研究者分別從預(yù)約時間段的重要性、平臺收益與步行距離平衡、停車需求分布與路徑選擇的關(guān)聯(lián)性、泊位擁有者參與共享停車的意愿、共享無人車對泊位需求量的影響、基于個人信用等級減少泊車違約風(fēng)險和停車需求信息的準(zhǔn)確性等多個方面進行了深入分析[1-7]。在共享停車匹配優(yōu)化模型構(gòu)建和平臺設(shè)計方面，研究者也進行了大量研究。通過定義虛擬泊位概念和考慮停車需求的優(yōu)先級別差異，文獻[8-9]建立了共享停車泊位匹配的優(yōu)化模型。文獻[10]在綜合租用車位成本、提供停車服務(wù)收入和拒絕潛在用戶的損失基礎(chǔ)上，以平臺收益最大化為目標(biāo)，構(gòu)建了車位租用和停車需求分配的統(tǒng)一決策模型。文獻[11]以步行距離的差異定義共享車位的異質(zhì)性，構(gòu)建了跨區(qū)域泊位分配的隨機動態(tài)規(guī)劃模型。文獻[12]利用滾動時域方法對實時獲得的共享停車供給與需求進行滾動式動態(tài)匹配。文獻[13]以最大化泊位利用率和減少步行距離為目標(biāo)，建立了共享停車的泊位分配模型。文獻[14]通過分析停車需求的到達(dá)時間和停泊時長分布，構(gòu)建模型來優(yōu)化共享停車收益，確定最佳共享泊位與保留非共享泊位的數(shù)量。文獻[15]提出了一種基于序列拍賣的共享停車泊位分配和定價方法。從參與各方經(jīng)濟利益最大化角度出發(fā)，文獻[16]構(gòu)建了基于拍賣機制的共享停車泊位分配、定價和收益機制。文獻[17-20]也對共享停車平臺收益、泊位分配和平臺構(gòu)建進行了深入分析。研究者也針對無人駕駛對停車供需匹配的影響進行了研究。文獻[21]分析了無人車市場占有率、燃油費和停車費對無人車在完成載客后選擇停車場的影響。文獻[22]分析了在不同的停車能力限制條件下共享無人車的市場占有率對早上通勤出行的影響。文獻[23]利用仿真模型對共享無人車、私有無人車、共享有人車和非共享有人車共存情況下的停車需求變化進行分析，發(fā)現(xiàn)共享車輛的存在可降低總體停車需求，但也會增加部分敏感區(qū)域的停車需求。文獻[24]分析了停車管理策略對需求響應(yīng)式共享無人車的規(guī)模、服務(wù)效率和公平性的影響。

與現(xiàn)有研究相比，本研究的特色表現(xiàn)在：(1) 在共享停車中考慮無人駕駛車輛的特征，在提高泊位利用率的同時最小化無人車進行泊位變換所帶來的風(fēng)險與成本。(2)利用可行匹配圖的結(jié)構(gòu)特征，分析得出對可行解實施持續(xù)改進的直接方法。(3) 通過引入變異操作，使得新算法在求解具有NP-hard特征的匹配模型過程中不會過早地局部收斂。

1 匹配模型

1.1 問題引入

共享停車的實施需要多方的參與，包括具有停車需求的車主、共享泊位的所有人、共享停車服務(wù)平臺、政府相關(guān)管理部門、停車區(qū)域的服務(wù)管理者等。其中，具有共享停車需求的車主向服務(wù)平臺提供停車的具體時間信息；共享泊位所有人提供泊位可供利用的空閑時間信息；共享停車服務(wù)平臺在匯總上述信息后，對停車需求與泊位供給加以合理匹配，并通知各方完成后續(xù)的停車服務(wù)。當(dāng)然，服務(wù)平臺需要事先與停車區(qū)域的其他服務(wù)管理者和政府相關(guān)部門協(xié)調(diào)，明確相關(guān)的法律、法規(guī)、制度和規(guī)則，并對利益的分配達(dá)成一致意見。停車需求者需為所享受的停車服務(wù)支付停車費，而服務(wù)平臺需要與其他各方協(xié)調(diào)各自的利益所得。由于共享停車主要關(guān)注從長期來看可重現(xiàn)的停車需求和泊位供給，因此目前的共享停車以預(yù)約式為主，即停車的需求與供給是事先已知的。本研究將以預(yù)約式共享停車中的停車需求與泊位供給匹配對研究對象。

無人駕駛車輛的出現(xiàn)對共享停車服務(wù)提出了新的挑戰(zhàn)與機遇。研究者和實踐者都亟需回答：如何充分發(fā)揮無人車的特征優(yōu)勢進一步發(fā)掘有限的停車資源？可以從多個方面對上述問題加以回答，如考慮無人車的自主遠(yuǎn)程停車場搜索和停泊。本研究將從無人車可以自主移位的特點出發(fā)，通過無人車的移位改變過去在泊車需求時間段內(nèi)普通有人駕駛車輛僅能停泊于一個固定車位的現(xiàn)狀，增加供需匹配的可能性，從而提高泊位的利用率。

原則上講，只要有空閑的共享泊位，無人車就可以隨時自主移位，但是這種有可能造成車輛的頻繁移位，進而增加車主的用車成本。為此本研究限定無人車僅可在停車需求與供給時間段的首末時間點進行移位。利用供需時間段的首末時間點可以將所有的停車需求與泊位供給劃分為一些較短時間段上的需求與供給，從而方便后續(xù)的建模分析。下面給出具體的分割時段劃分方法：

1.2 基本參變量介紹

v∈V為一輛具有共享停車需求的無人駕駛車輛，V為所有相關(guān)車輛的集合。

p∈P為一個提供共享停車服務(wù)的泊位，P為所有相關(guān)泊位的集合。

tv,start為車輛v的停車需求開始時刻。

tv,end為車輛v的停車需求結(jié)束時刻。

tp,start為泊位p提供的共享停車服務(wù)時段的開始時刻。

tp,end為泊位p可以被用于共享停車的結(jié)束時刻。

k∈K為一個分割時間段，集合K={1,2,3,...,nK}是所有分割時間段的集合。

lpi,pj為無人駕駛車輛從共享泊位pi移位至共享泊位pj所需要行駛的距離。

wv為對車輛v而言，在其泊車過程中一次泊位改變所帶來的懲罰性成本，假設(shè)其計量單位與距離的計量單位一致。

1.3 共享泊位與車輛的匹配模型

利用前面給出的參變量和分割時段概念，構(gòu)建滿足停車需求條件下的車輛與泊位的匹配優(yōu)化模型如下：

(1)

(2)

(3)

(4)

式(1)為目標(biāo)函數(shù)，其構(gòu)成的第1個加和項是給定供需匹配x后，無人駕駛車輛泊車過程中進行泊位變換總共需要的行駛距離；目標(biāo)函數(shù)構(gòu)成的第2個加和項是無人駕駛車輛總的泊位變換次數(shù)。式(2)為給定分割時段停泊在給定泊位的車輛數(shù)必須等于或少于該泊位在該給定分割時段的供給。式(3)為給定分割時段給定車輛的共享停車需求必須得到滿足。約束式(4)是對匹配決策變量的取值范圍約束。如果先對約束式(2)和(3)分別進行加和，然后加以比較，可以得到下面的隱含約束條件：

(5)

式(5)為模型的約束條件下，所有可接受的預(yù)約式共享停車需求都將得到滿足。這里的“可接受”指的是在任意時刻的停車需求總量小于等于該時刻的泊位供給總量。

與現(xiàn)有的針對有人駕駛車輛的共享停車匹配模型相比，上述模型的約束條件更加簡潔。由于本研究將共享停車的供需劃分為統(tǒng)一的較小時間段上的停車供給與需求，因此避免了以往研究中各種繁復(fù)的與需求和供給的時間段的前后時間點匹配相關(guān)的約束。同時，新模型的目標(biāo)函數(shù)式(1)以泊車中無人車的移位次數(shù)和移位距離最小化為目標(biāo)，也與過去以最大化供需匹配數(shù)目或泊位利用率不同。式(5)表明新模型是對可接受的預(yù)約式共享停車需求的匹配，匹配結(jié)果必須滿足所有可接受的停車需求。而可接受的預(yù)約式共享停車需求只要滿足在任意時刻停車的供給大于等于該時刻停車的需求即可，而不必像處理有人駕駛車輛停車時需考慮車輛停車需求時間是否被泊位的供給時間所涵蓋，因此易知新模型得到的泊位利用率將高于過去僅考慮有人駕駛車輛停車需求的情況。

匹配模型屬于純整數(shù)二次規(guī)劃模型，由約束和目標(biāo)函數(shù)的特殊形式，也可視為一類特殊的二次分配問題模型。現(xiàn)有研究證實二次分配問題是一類極難的NP-hard問題，目前還沒有確定較大規(guī)模相關(guān)問題全局精確最優(yōu)解的有效方法。一般的線性化技術(shù)方法只能提供問題較好的目標(biāo)值下界，而啟發(fā)式方法也只能保證給出問題的局部最優(yōu)或近似最優(yōu)解。

2 自適應(yīng)演化算法

2.1 可行匹配結(jié)構(gòu)分析

定義2 (匹配組)：令Vk和Pk分別為分割時間段k具有共享停車需求的無人駕駛車輛集合和在時間段k提供共享停車服務(wù)的泊位集合。如果為Vk中的每輛車在Pk中指定一個排他的獨占泊位，就構(gòu)成了在分割時間段k上的一個匹配組，簡記為S(Vk,Pk)或Sk。

定義3 (匹配圖)：對應(yīng)集合K={1,2,3,…,nK}中的各分割時間段，分別存在對應(yīng)的匹配組S1,S2,S3,…,SnK。把上述nK個匹配組放入一個集合A={S1,S2,S3,…,SnK}，稱該集合為一個匹配圖。利用匹配和匹配組的概念可以推出任何一個匹配圖都對應(yīng)模型(1～4)的一個可行解。

2.2 有益交換操作

定義 4 (交換): 設(shè)存在兩個匹配m(k,v,p)和m(k′,v′,p′)。將上述兩個匹配包含的車輛進行交換，可得到兩個新的匹配m(k,v′,p)和m(k,v,p′)。將上述操作稱為匹配交換，簡單為E[m(k,v,p),m(k,v′,p′)]。

按照上述交換定義，可得E[m(k,v,p),m(k,□,p′)]?m(k,□,p)和m(k,v,p′)。為了簡化表達(dá)式，如果已知m(k,v′,p′)，則交換E[m(k,v,p),p′]?m(k,v′,p)和m(k,v,p′)。對交換E[m(k,v,p),p′]而言，我們稱m(k,v,p)為其顯式交換內(nèi)容，p′為其目標(biāo)交換泊位。 我們也用Ek為對應(yīng)分割時間段k的一個交換操作。設(shè)M是一個由不同匹配構(gòu)成的匹配集合，m∈M為M包含的一個匹配。則表達(dá)式E(M,p)為進行所有相關(guān)操作E(m,p),?m∈M。在E(M,p)中，稱M為其顯式交換內(nèi)容，稱p為其目標(biāo)交換泊位。

給定兩個匹配組Sk和Sk+1，兩者之間由于無人駕駛車輛變換泊位產(chǎn)生的移車距離與移車懲罰性成本之和記為c(Sk,Sk+1)或c(Sk+1,Sk)。由于車輛只能在相鄰的兩個分割時間段之間進行移位，因此規(guī)定c(Si,Sj)=0,?|i-j|≠1。為了后續(xù)公式表達(dá)方便，規(guī)定：如果k<1或k+1>nK，則c(Sk,Sk+1)=0。c(Sk,Sk+1)的具體計算公式如下：

(6)

(7)

如果Δc(Ek)>0，我們稱Ek為有益交換。如果Δc(Ek)≤0，我們稱Ek為無益交換。

定義 6 (有益連續(xù)交換組): 將一組在時間上連續(xù)的交換操作{Ek,Ek+1,…,Ek+n}定義為連續(xù)交換Ek→(k+n)。與上述連續(xù)交換對應(yīng)的匹配組集合為{Sk,Sk+1,…,Sk+n}。在未實施交換前，{Sk,Sk+1,…,Sk+n}在其內(nèi)部和與外部緊鄰的其他匹配組之間由于無人駕駛車輛的移位產(chǎn)生的移車距離與移車懲罰性成本之和計算公式如下：

(8)

而實施Ek→(k+n)帶來的成本變化量Δc(Ek→(k+n))計算如下：

(9)

如果Δc(Ek→(k+n))>0，我們稱Ek→(k+n)為有益連續(xù)交換組；否則，稱Ek→(k+n)為無益連續(xù)交換組。

假設(shè)對于v∈V，其對應(yīng)兩個連續(xù)分割時間段的匹配分別為m(k,v,p)與m(k+1,v,p′)。如果p≠p′，可知車輛v在兩個連續(xù)分割時間段之間需要進行泊位變換，對應(yīng)的移車成本為cv(k,k+1)=lp,p′+wv；如果p=p′，則顯然有cv(k,k+1)=0。在給定一個匹配圖A的條件下，如果希望對其進行調(diào)整，從而減少對應(yīng)的目標(biāo)函數(shù)值z[x(A)]，就需要確定是否存在有益交換或有益連續(xù)交換組。而實施交換的觸發(fā)條件是車輛在兩個連續(xù)的分割時間段停泊在不同的泊位。如上面條件p≠p′成立時，可以通過嘗試實施交換E[m(k,v,p),p′]或E[m(k+1,v,p′),p]來得到新的匹配圖，從而減少總的移車成本。

2.3 自適應(yīng)式優(yōu)化的實現(xiàn)

利用上面2.1和2.2節(jié)給出的概念和定義，下面給出對一個給定匹配圖進行一次自適應(yīng)式優(yōu)化的流程：

步驟2：如果k已經(jīng)是車輛v的最晚的分割時間段，轉(zhuǎn)步驟4；否則，依次確定對應(yīng)當(dāng)前分割時段k和后續(xù)分割時段k+1停放v的兩個泊位p和q。

步驟3：如果p=q，則令k:=k+1，并轉(zhuǎn)步驟2；否則實施下列操作：

步驟3.1：分別以k和k+1為起始時段，分別向前和向后在兩個泊位p和q上搜索停放v的相鄰時間段，并將分別得到的與v相關(guān)的匹配組成兩個集合Mp和Mq。

步驟3.2：將集合Mp里的匹配作為顯式交換內(nèi)容，而將泊位q作為目標(biāo)交換泊位，確定連續(xù)交換E(Mp,q)的成本Δc[E(Mp,q)]；同理確定Δc[E(Mq,p)]。

步驟3.3：如果Δc[E(Mp,q)]≥max{0,Δc[E(Mq,p)]}，實施交換操作E(Mp,q)。

步驟3.4：如果Δc[E(Mq,p)]>max{0,Δc[E(Mp,q)]}，實施交換操作E(Mq,p)。

步驟3.5：令k:=k+1，并轉(zhuǎn)步驟2。

2.4 帶有變異操作的自適應(yīng)演化算法

下面給出帶有變異操作的自適應(yīng)演化算法的具體操作流程：

步驟 1：初始化。設(shè)定算法的最大執(zhí)行次數(shù)Nout、對給定匹配圖實施個體自適應(yīng)式優(yōu)化的最大次數(shù)Nin，以及變異操作系數(shù)α。令當(dāng)前的迭代次數(shù)τ:=0。隨機生成一個可行匹配圖，并將其賦予當(dāng)前匹配圖Aτ和最優(yōu)匹配圖A*。

步驟 2：匹配圖的自適應(yīng)優(yōu)化。令A(yù)τ:=ENin(Aτ)。如果z[x(Aτ)]

步驟 4：終止條件判斷。如果z[x(A*)]=0或τ=Nout，算法終止，輸出最優(yōu)匹配圖A*；否則，令A(yù)τ:=Aτ-1，轉(zhuǎn)步驟2。

3 算例分析

下面分析一個具有20輛車和12個泊位的共享停車匹配問題。該問題的車輛停車需求信息和共享泊位的共享時間信息分別在表1和表2中給出。假設(shè)最早提供共享停車服務(wù)的泊位開放時間是0，而其他的時間以分鐘作為時間計量單位。表格1和2中的時刻表達(dá)方式是將實際時刻以共享停車的開始時刻為基準(zhǔn)轉(zhuǎn)化為以分鐘為單位后得到的數(shù)值。泊位間的移車距離矩陣在矩陣L中給出。矩陣L中的第i行第j列元素的值表示從第i個泊位移車到第j個泊位車輛需要行駛的距離(單位:km)。

表1 車輛停車需求

表2 泊位共享開放時間

算法運行所需的參數(shù)設(shè)定如下：Nout=200，Nin=100 和α=0.015。設(shè)無人車移位1次的懲罰性成本為10 km。圖1給出了典型的3次程序運行結(jié)果。3次運行結(jié)果具有相似的算法收斂特征，即在算法迭代的初期，最優(yōu)目標(biāo)函數(shù)值會出現(xiàn)一個突降，隨后最優(yōu)目標(biāo)函數(shù)值的降低速度明顯減緩，而在算法迭代的后期，最優(yōu)目標(biāo)函數(shù)值的改變很少。基本相似的收斂特征說明了新提出的自適應(yīng)演化算法具有較強的穩(wěn)定性和可靠性。對應(yīng)3次程序運行的最終目標(biāo)函數(shù)值分別為50.20,60.27和60.21。圖2給出了對應(yīng)圖1中數(shù)據(jù)系列1的最佳匹配圖的矩陣圖。該圖中第1列第1行的“sn”為第1列為泊位的序號。圖2的矩陣圖的第1行的數(shù)字為分割時段的序號。矩陣圖中其他元素的意義規(guī)定如下：“/”為對應(yīng)泊位在對應(yīng)分割時段不開放；“—”為對應(yīng)泊位在對應(yīng)分割時段為共享停車開放，但是沒有被占用；數(shù)字“n” 為對應(yīng)泊位在對應(yīng)分割時段被序號為n的車輛占用。圖2給出的結(jié)果并非問題2的全局最優(yōu)解，通過多次嘗試算法可以將目標(biāo)函數(shù)值降低到40.20左右。如需進一步優(yōu)化結(jié)果，需要調(diào)整算法的參數(shù)，并增大算法允許的最大迭代次數(shù)。鑒于啟發(fā)式算法本身的近似最優(yōu)解求解特征，在此不再進行更深入的分析。

圖1 隨迭代次數(shù)增加，最優(yōu)目標(biāo)函數(shù)值的變化

圖2 對應(yīng)系列1的最佳匹配圖的矩陣圖

從圖2的結(jié)果可知，車輛1,8,9,11和12各需移位1次，移位的總距離為0.2 km。而進一步分析可知，假設(shè)車輛1和8為有人駕駛車輛，即通常情況下兩輛車只能各選擇一個固定車位停放時，現(xiàn)有的共享泊位供給將不能滿足兩車的停車需求；而在兩輛車為無人車時，通過自動代客泊車技術(shù)，可以合理有效化解上述停車?yán)Ь常跐M足上述停車需求條件下，增加泊位的利用率。

表3 不同泊位數(shù)、車輛數(shù)和泊位利用率組合下算法的計算結(jié)果比較

4 結(jié)論

以AVP為背景，給出了預(yù)約式共享停車供需匹配的二次分配模型，并利用可行匹配圖的結(jié)構(gòu)特征設(shè)計了帶有變異操作的自適應(yīng)式演化算法。通過定義匹配、匹配組、匹配圖、交換、交換成本、有益連續(xù)交換組等概念，明確了對給定匹配圖進行合理調(diào)整的方法步驟，從而實現(xiàn)了對模型可行解的持續(xù)改進。引入變異操作可以有效避免過早的算法局部收斂。數(shù)值算例表明新算法不僅計算效率高，而且具有較高的可靠性?？紤]到模型本身的NP-hard特征，算法極短的計算時間說明新算法具有處理實際規(guī)模問題的能力。本研究的結(jié)果可以有力推進智慧停車?yán)碚撛谖磥砀鼜V泛深入的實踐。