何勝學(xué)

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

0 引言

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

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

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

1 匹配模型

1.1 問(wèn)題引入

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

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

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

1.2 基本參變量介紹

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

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

tv,start為車(chē)輛v的停車(chē)需求開(kāi)始時(shí)刻。

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

tp,start為泊位p提供的共享停車(chē)服務(wù)時(shí)段的開(kāi)始時(shí)刻。

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

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

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

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

1.3 共享泊位與車(chē)輛的匹配模型

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

(1)

(2)

(3)

(4)

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

(5)

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

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

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

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

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

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

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

2.2 有益交換操作

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

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

給定兩個(gè)匹配組Sk和Sk+1，兩者之間由于無(wú)人駕駛車(chē)輛變換泊位產(chǎn)生的移車(chē)距離與移車(chē)懲罰性成本之和記為c(Sk,Sk+1)或c(Sk+1,Sk)。由于車(chē)輛只能在相鄰的兩個(gè)分割時(shí)間段之間進(jìn)行移位，因此規(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)的具體計(jì)算公式如下：

(6)

(7)

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

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

(8)

而實(shí)施Ek→(k+n)帶來(lái)的成本變化量Δc(Ek→(k+n))計(jì)算如下：

(9)

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

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

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

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

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

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

步驟3.1：分別以k和k+1為起始時(shí)段，分別向前和向后在兩個(gè)泊位p和q上搜索停放v的相鄰時(shí)間段，并將分別得到的與v相關(guān)的匹配組成兩個(gè)集合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)]}，實(shí)施交換操作E(Mp,q)。

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

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

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

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

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

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

表1 車(chē)輛停車(chē)需求

表2 泊位共享開(kāi)放時(shí)間

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

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

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

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

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

4 結(jié)論

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