何勝學(xué)
(上海理工大學(xué) 管理學(xué)院,上海 200093)
傳統(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ò)早地局部收斂。
共享停車(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í)段劃分方法:
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ì)量單位一致。
利用前面給出的參變量和分割時(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 (匹配組):令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è)可行解。
定義 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.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。
下面給出帶有變異操作的自適應(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。 下面分析一個(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é)果比較 以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í)踐。3 算例分析
4 結(jié)論