AVP條件下的共享停車供需匹配模型及自適應演化算法

何勝學

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

0 引言

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

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

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

1 匹配模型

1.1 問題引入

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

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

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

1.2 基本參變量介紹

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

p∈P為一個提供共享停車服務的泊位，P為所有相關泊位的集合。

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

(4)

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

(5)

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

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

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

2 自適應演化算法

2.1 可行匹配結構分析

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

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

2.2 有益交換操作

定義 4 (交換): 設存在兩個匹配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′)。為了簡化表達式，如果已知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)為其顯式交換內容，p′為其目標交換泊位。 我們也用Ek為對應分割時間段k的一個交換操作。設M是一個由不同匹配構成的匹配集合，m∈M為M包含的一個匹配。則表達式E(M,p)為進行所有相關操作E(m,p),?m∈M。在E(M,p)中，稱M為其顯式交換內容，稱p為其目標交換泊位。

給定兩個匹配組Sk和Sk+1，兩者之間由于無人駕駛車輛變換泊位產生的移車距離與移車懲罰性成本之和記為c(Sk,Sk+1)或c(Sk+1,Sk)。由于車輛只能在相鄰的兩個分割時間段之間進行移位，因此規定c(Si,Sj)=0,?|i-j|≠1。為了后續公式表達方便，規定：如果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 (有益連續交換組): 將一組在時間上連續的交換操作{Ek,Ek+1,…,Ek+n}定義為連續交換Ek→(k+n)。與上述連續交換對應的匹配組集合為{Sk,Sk+1,…,Sk+n}。在未實施交換前，{Sk,Sk+1,…,Sk+n}在其內部和與外部緊鄰的其他匹配組之間由于無人駕駛車輛的移位產生的移車距離與移車懲罰性成本之和計算公式如下：

(8)

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

(9)

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

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

2.3 自適應式優化的實現

利用上面2.1和2.2節給出的概念和定義，下面給出對一個給定匹配圖進行一次自適應式優化的流程：

步驟2：如果k已經是車輛v的最晚的分割時間段，轉步驟4；否則，依次確定對應當前分割時段k和后續分割時段k+1停放v的兩個泊位p和q。

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

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

步驟3.2：將集合Mp里的匹配作為顯式交換內容，而將泊位q作為目標交換泊位，確定連續交換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，并轉步驟2。

2.4 帶有變異操作的自適應演化算法

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

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

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

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

3 算例分析

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

表1 車輛停車需求

表2 泊位共享開放時間

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

圖1 隨迭代次數增加，最優目標函數值的變化

圖2 對應系列1的最佳匹配圖的矩陣圖

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

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

4 結論

以AVP為背景，給出了預約式共享停車供需匹配的二次分配模型，并利用可行匹配圖的結構特征設計了帶有變異操作的自適應式演化算法。通過定義匹配、匹配組、匹配圖、交換、交換成本、有益連續交換組等概念，明確了對給定匹配圖進行合理調整的方法步驟，從而實現了對模型可行解的持續改進。引入變異操作可以有效避免過早的算法局部收斂。數值算例表明新算法不僅計算效率高，而且具有較高的可靠性。考慮到模型本身的NP-hard特征，算法極短的計算時間說明新算法具有處理實際規模問題的能力。本研究的結果可以有力推進智慧停車理論在未來更廣泛深入的實踐。