何勝學(xué)
(上海理工大學(xué)管理學(xué)院 上海 200093)
隨著泊車(chē)服務(wù)機(jī)器人(parking valet robot,PVR)的推廣應(yīng)用和無(wú)人駕駛技術(shù)的不斷發(fā)展,過(guò)去車(chē)輛和泊位在車(chē)輛停泊期間固定搭配的共享停車(chē)供需匹配方式亟待調(diào)整改變以適應(yīng)時(shí)代的發(fā)展需要.PVR和無(wú)人駕駛車(chē)輛(autonomous vehicle,AV)一方面使車(chē)輛在停泊期間變換車(chē)位成為可能,從而實(shí)現(xiàn)車(chē)輛停放時(shí)空布局的合理化,減少泊位閑置的時(shí)間碎片,提升泊位利用率.另一方面也提出了“如何合理規(guī)劃PVR和AV的移車(chē)操作避免不必要的車(chē)輛移位,從而減少相關(guān)的運(yùn)行成本,并降低在車(chē)輛移位過(guò)程中發(fā)生事故的風(fēng)險(xiǎn)”的問(wèn)題.為解決上述問(wèn)題,文中將以預(yù)約式共享停車(chē)中同時(shí)存在泊車(chē)期間不允許移位、允許利用PVR移位和AV自主移位三種差異化停車(chē)需求為背景,在滿(mǎn)足可接受的共享停車(chē)需求條件下,以最小化車(chē)輛移位次數(shù)和移車(chē)成本為目標(biāo)建構(gòu)共享停車(chē)供需匹配模型,并利用模型可行解(即車(chē)輛與泊位的時(shí)空匹配關(guān)系)結(jié)構(gòu)特征設(shè)計(jì)一種蜂群優(yōu)化算法對(duì)模型進(jìn)行求解.
近年來(lái)學(xué)者們針對(duì)共享停車(chē)進(jìn)行了居多研究:
1) 針對(duì)共享停車(chē)需求特征與影響方面 文獻(xiàn)[1]通過(guò)時(shí)間序列預(yù)測(cè)時(shí)間重要度,在匹配時(shí)盡量減少熱點(diǎn)時(shí)間的預(yù)約,從而減少泊位空閑時(shí)間碎片.文獻(xiàn)[2]提出停車(chē)設(shè)施的選擇概率依賴(lài)于設(shè)施的停車(chē)吸引力系數(shù)、停車(chē)收費(fèi)、相關(guān)步行時(shí)間和實(shí)際行程時(shí)間.文獻(xiàn)[3]提出將停車(chē)需求分布與路徑選擇決策相結(jié)合.文獻(xiàn)[4]分析了不同情境下泊位擁有者參與共享泊位的意愿.文獻(xiàn)[5]實(shí)證分析共享無(wú)人車(chē)的使用對(duì)停車(chē)泊位需求的影響.文獻(xiàn)[6]提出基于個(gè)人信用風(fēng)險(xiǎn)等級(jí)來(lái)匹配泊位.文獻(xiàn)[7]分析了共享停車(chē)供給與需求存在的不準(zhǔn)時(shí)特征.文獻(xiàn)[8]比較了泊位利用率和停車(chē)需求者滿(mǎn)意度對(duì)共享泊位匹配的影響.
2) 以構(gòu)建車(chē)輛與泊位的匹配模型和優(yōu)化共享停車(chē)服務(wù)平臺(tái)服務(wù)方面 文獻(xiàn)[9]以共享停車(chē)平臺(tái)收益及用戶(hù)步行距離為優(yōu)化目標(biāo),構(gòu)建了預(yù)約請(qǐng)求下共享泊位分配模型.從參與各方經(jīng)濟(jì)利益最大化角度出發(fā),文獻(xiàn)[10]構(gòu)建了基于拍賣(mài)機(jī)制的共享停車(chē)泊位分配、定價(jià)和收益機(jī)制.文獻(xiàn)[11]通過(guò)定義虛擬泊位概念建立了共享停車(chē)泊位匹配的優(yōu)化模型.文獻(xiàn)[12]在多個(gè)停車(chē)場(chǎng)的共享停車(chē)泊位匹配中考慮了停車(chē)需求的優(yōu)先級(jí)別差異.文獻(xiàn)[13]在綜合租用車(chē)位成本、提供停車(chē)服務(wù)收入和拒絕潛在用戶(hù)的損失基礎(chǔ)上,構(gòu)建了車(chē)位租用和停車(chē)需求分配的統(tǒng)一決策模型.文獻(xiàn)[14]以步行距離的差異定義共享車(chē)位的異質(zhì)性,構(gòu)建了跨區(qū)域泊位分配的隨機(jī)動(dòng)態(tài)規(guī)劃模型.文獻(xiàn)[15]利用滾動(dòng)時(shí)域方法對(duì)實(shí)時(shí)獲得的共享停車(chē)供需進(jìn)行滾動(dòng)式動(dòng)態(tài)匹配.文獻(xiàn)[16]以最大化泊位利用率和減少步行距離為目標(biāo),建立的共享停車(chē)的泊位分配模型.文獻(xiàn)[17]通過(guò)分析停車(chē)需求的到達(dá)時(shí)間和停泊時(shí)長(zhǎng)分布,確定最佳共享泊位與保留非共享泊位的數(shù)量.
3) 針對(duì)無(wú)人駕駛對(duì)共享停車(chē)的影響方面 文獻(xiàn)[18]分析了無(wú)人車(chē)市場(chǎng)占有率、燃油費(fèi)和停車(chē)費(fèi)對(duì)無(wú)人車(chē)在完成載客后選擇停車(chē)場(chǎng)的影響,建議通過(guò)差異化的區(qū)域收費(fèi)引導(dǎo)無(wú)人車(chē)的停車(chē)場(chǎng)選擇,從而在整體上實(shí)現(xiàn)停車(chē)的供需平衡.文獻(xiàn)[19]分析了在不同的停車(chē)能力限制條件下共享無(wú)人車(chē)的市場(chǎng)占有率對(duì)早上通勤出行的影響.文獻(xiàn)[20]利用仿真模型對(duì)共享無(wú)人車(chē)、私有無(wú)人車(chē)、共享有人車(chē)和非共享有人車(chē)共存情況下的停車(chē)需求變化進(jìn)行分析,發(fā)現(xiàn)共享車(chē)輛的存在可降低總體停車(chē)需求,但也會(huì)增加部分敏感區(qū)域的停車(chē)需求.文獻(xiàn)[21]分析了停車(chē)管理策略對(duì)需求響應(yīng)式共享無(wú)人車(chē)的規(guī)模、服務(wù)效率和公平性,以及相關(guān)的外部性影響.文獻(xiàn)[22]對(duì)智慧停車(chē)和自動(dòng)代客泊車(chē)?yán)碚摪l(fā)展與相關(guān)實(shí)踐進(jìn)行了系統(tǒng)梳理,明確了當(dāng)前相關(guān)領(lǐng)域需要關(guān)注和解決的主要問(wèn)題.
與現(xiàn)有研究相比,本研究的特色體現(xiàn)在:①首次在共享停車(chē)研究中同時(shí)引入PVR和AV的影響,為共享停車(chē)在新時(shí)代發(fā)展提供理論支持;②與現(xiàn)有研究主要關(guān)注停車(chē)場(chǎng)選擇和AV路線(xiàn)規(guī)劃不同,本研究則關(guān)注車(chē)輛停泊過(guò)程中的移位操作和相關(guān)的成本;③針對(duì)新建匹配模型的NP-hard特征,利用車(chē)輛與泊位時(shí)空匹配關(guān)系與蜜蜂基因序列進(jìn)行類(lèi)比,并通過(guò)匹配交換操作體現(xiàn)蜂群優(yōu)化中工蜂對(duì)幼蜂的撫育,最終實(shí)現(xiàn)針對(duì)本文匹配模型的蜂群優(yōu)化算法設(shè)計(jì).
本研究的基本假設(shè)條件如下:①研究針對(duì)預(yù)約式共享停車(chē)的需求與供給匹配,因此假設(shè)相關(guān)的車(chē)輛停車(chē)需求時(shí)間和泊位可供共享停車(chē)的開(kāi)放時(shí)間事先已知;②為了方便構(gòu)建模型,假設(shè)所有車(chē)輛的停車(chē)需求時(shí)間和共享泊位的開(kāi)放時(shí)間均是整塊連續(xù)的時(shí)間段;③假設(shè)不同類(lèi)別車(chē)輛對(duì)泊車(chē)過(guò)程中是否允許變換泊位的要求事先已知;④假設(shè)共享泊位之間進(jìn)行車(chē)輛泊位變換的行車(chē)路線(xiàn)長(zhǎng)度已知;⑤為了減少不必要的移車(chē)操作,假設(shè)不管是利用泊車(chē)機(jī)器人移車(chē)還是無(wú)人駕駛車(chē)輛的自主移位均只能在車(chē)輛停車(chē)需求時(shí)間和泊位共享開(kāi)放時(shí)間的起止時(shí)刻發(fā)生.
考慮到假設(shè)條件⑤,有必要將共享停車(chē)服務(wù)的總時(shí)間加以分割,形成長(zhǎng)度較短的分割時(shí)間段,進(jìn)而將車(chē)輛的停車(chē)需求和泊位的供給也對(duì)應(yīng)分割為小的時(shí)間段.具體的時(shí)間分割方法如下:①首先利用所有車(chē)輛停車(chē)需求時(shí)間的起止時(shí)刻和共享泊位開(kāi)放時(shí)間的起止時(shí)刻構(gòu)成一個(gè)起止時(shí)刻集合;②剔出上述起止時(shí)刻集合中的重復(fù)元素,并按照時(shí)間的升序?qū)κS嘣丶右耘判?,得到一個(gè)有序的起止時(shí)刻序列;③比照上述有序的時(shí)刻序列,以序列里的時(shí)刻作為起止時(shí)刻,將所有的車(chē)輛的停車(chē)需求時(shí)間和共享泊位的開(kāi)放時(shí)間劃分為連續(xù)相接的具有較小長(zhǎng)度的分割時(shí)間段.
下面給出具有多種車(chē)輛差異化停車(chē)需求的供需匹配優(yōu)化模型.
(1)
(2)
(3)
(4)
目標(biāo)函數(shù)(1)由兩個(gè)加和項(xiàng)構(gòu)成,其中第一個(gè)加和項(xiàng)是所有車(chē)輛發(fā)生移位的移位路線(xiàn)總長(zhǎng)度,第二項(xiàng)是不同車(chē)輛發(fā)生泊位改變時(shí)引發(fā)的懲罰性系統(tǒng)成本之和.為了滿(mǎn)足第一類(lèi)不允許在泊車(chē)過(guò)程中進(jìn)行泊位變換的停車(chē)需求,對(duì)應(yīng)的單次懲罰性系統(tǒng)成本w1的值應(yīng)該遠(yuǎn)大于其他兩個(gè)懲罰性成本量w2和w3.從共享停車(chē)服務(wù)平臺(tái)或管理者的角度出發(fā),w2的值應(yīng)大于w3,因?yàn)槔肞VR的成本一般是由平臺(tái)承擔(dān)的,而無(wú)人駕駛車(chē)輛的移位成本一般由車(chē)輛所有者承擔(dān).約束(2)為如果一個(gè)泊位在給定分割時(shí)段不提供共享停車(chē)服務(wù),則該時(shí)段沒(méi)有需要共享停車(chē)的車(chē)輛停于該泊位;而當(dāng)該泊位在該給定分割時(shí)段提供共享停車(chē)服務(wù)時(shí),至多只能有一輛需要共享停車(chē)的車(chē)輛停于該泊位.約束(3)為在給定時(shí)段任意給定車(chē)輛的共享停車(chē)需求應(yīng)得到滿(mǎn)足.約束(4)為對(duì)決策變量取值范圍的限定.由目標(biāo)函數(shù)(1)和約束(2)~(4)構(gòu)成的模型(1)~(4)完整描述了多車(chē)種條件下共享停車(chē)供需匹配問(wèn)題.
如果先對(duì)約束(2)和(3)分別在泊位集合P和車(chē)輛集合V上進(jìn)行加和,然后加以比較,為
(5)
式(5)為在任意給定分割時(shí)間段,車(chē)輛的停車(chē)需求小于泊位的供給.將滿(mǎn)足式(5)的車(chē)輛共享停車(chē)需求稱(chēng)為可接受的合理需求.顯然在允許對(duì)所有車(chē)輛進(jìn)行泊位變換的條件下,一定存在一個(gè)可行的供需匹配滿(mǎn)足約束(2)和(3).
利用定義在分割時(shí)間段上的車(chē)輛停車(chē)需求與泊位共享停車(chē)供給可定義相關(guān)的基于分割時(shí)段數(shù)量的泊位利用率φ為
(6)
模型(1)~(4)屬于純整數(shù)二次規(guī)劃.從約束和目標(biāo)函數(shù)的特征可知,也可將模型(1)~(4)視為一類(lèi)特殊的二次分配模型.已有研究表明二次分配問(wèn)題屬于一類(lèi)極難的NP-hard問(wèn)題,目前相關(guān)的一些線(xiàn)性化技術(shù)只能改善問(wèn)題求解過(guò)程中的目標(biāo)下界,不能在現(xiàn)實(shí)可接受的計(jì)算時(shí)間內(nèi)得到并確定較大規(guī)模二次分配問(wèn)題的全局最優(yōu)解.鑒于上述知識(shí),下文將針對(duì)模型(1)~(4)設(shè)計(jì)一種有效的啟發(fā)式算法,以期迅速高效地得到問(wèn)題的近似最優(yōu)解.
定義2(基因):如果為Vk中的每一輛車(chē)在集合Pk中選擇一個(gè)獨(dú)占的泊位來(lái)在分割時(shí)間段k停放該車(chē)輛,則將會(huì)在Vk和Pk之間建立一個(gè)可行的匹配關(guān)系,其中的匹配構(gòu)成一個(gè)對(duì)應(yīng)分割時(shí)間段k的匹配集合,記作e(Vk,Pk)或ek.在蜂群優(yōu)化里稱(chēng)ek為蜜蜂的第k個(gè)基因.
由基因的上述定義可知,如果兩個(gè)相異匹配m(k1,v1,p1)∈ek和m(k2,v2,p2)∈ek, 那么k1=k2=k,v1≠v2,p1≠p2.由于基因包含的匹配存在上述關(guān)系,因此易知ek對(duì)應(yīng)約束(2) 和(3).為了方便后續(xù)的表述,我們用Ek表示ek的取值范圍.
定義3(蜜蜂):對(duì)應(yīng)分割時(shí)段集合K={1,2,…,k,…,nK}的nK個(gè)基因序列組成一個(gè)向量,稱(chēng)為一個(gè)蜜蜂,記作h=(e1,e2,…,ek,…,enK).由匹配和基因的定義以及兩者與模型約束的關(guān)系可知,對(duì)于任意一只蜜蜂h存在一個(gè)唯一的模型可行解x與之對(duì)應(yīng).把對(duì)應(yīng)蜜蜂h的模型可行解記為x(h).而將利用式(1)計(jì)算得到的-z(x(h))稱(chēng)為蜜蜂h的適應(yīng)值.
(7)
ψnew=ψ-Δψ
(8)
λnew=αλ
(9)
當(dāng)基因集合已滿(mǎn)(已經(jīng)包含ρ只雄蜂的基因序列)或蜂王的能量接近0時(shí),一次繁育飛行結(jié)束,蜂王將返回蜂巢去孵化幼蜂.如果完成繁育飛行時(shí),蜂王的基因集合未滿(mǎn),則從當(dāng)前備選蜂集合中選取適應(yīng)值相對(duì)較大的備選蜂的基因序列來(lái)填滿(mǎn)基因集合.
(10)
蜂王返回蜂巢后孵化幼蜂包含兩種情況:一種情況為通過(guò)將蜂王基因序列與基因集合中雄蜂基因序列進(jìn)行類(lèi)似遺傳算法的交叉和變異操作得到一定數(shù)量新的幼蜂;另一種情況是僅對(duì)蜂王的基因?qū)嵤┳儺惒僮鞯玫揭欢〝?shù)量新的幼蜂.兩種情況下得到的幼蜂會(huì)形成幼蜂群.幼蜂群的規(guī)模限定為M.
蜂群優(yōu)化算法將工蜂的對(duì)幼蜂的撫育投射為對(duì)新生幼蜂實(shí)施特定的啟發(fā)式操作,以期改進(jìn)幼蜂的適應(yīng)值.基于上述基本理念,我們?cè)O(shè)計(jì)了如下的啟發(fā)式操作.假設(shè)存在兩個(gè)匹配m(k,v1,p1)∈ek和m(k,v2,p2)∈ek, 對(duì)其實(shí)施交換操作Γ,可得到交換后兩個(gè)新的匹配m(k,v2,p1)和m(k,v1,p2).上述交換操作Γ為
Γ(m(k,v1,p1),m(k,v2,p2))→
m(k,v2,p1),m(k,v1,p2)
(11)
(12)
在新設(shè)計(jì)的蜂群優(yōu)化算法中,將工蜂對(duì)一只幼蜂的撫育定義為從該幼蜂的基因序列中隨機(jī)選取一個(gè)基因,實(shí)施式(12)所示的多次交換操作,用每次操作得到的新基因替換幼蜂對(duì)應(yīng)的基因,并計(jì)算對(duì)應(yīng)的適應(yīng)值.選擇適應(yīng)值最大的交換操作序列作為最終的交換操作,并用得到的新基因替代幼蜂的原始基因.上述針對(duì)幼蜂基因的系列交換操作在蜂群優(yōu)化中對(duì)應(yīng)現(xiàn)實(shí)中工蜂對(duì)幼蜂的撫育.
基于2.1給出的概念和操作,下面給出蜂群優(yōu)化算法的具體操作步驟.
步驟4繁育飛行.令ψ=Rand(10,20)×Δψ和λ=500+Rand(0,500).這里Rand(a,b)為在區(qū)間[a,b]上均勻分布的一個(gè)隨機(jī)整數(shù).按照2.1介紹的繁育飛行操作,實(shí)施繁育飛行.
步驟5孵化幼蜂.將蜂王基因序列與基因集合中雄蜂基因序列進(jìn)行類(lèi)似遺傳算法的交叉和變異操作得到一定數(shù)量新的幼蜂;然后僅對(duì)蜂王的基因?qū)嵤┳儺惒僮鞯玫揭欢〝?shù)量新的幼蜂;將兩種情況下得到的蜜蜂組合形成規(guī)模為M的幼蜂群.
步驟6工蜂對(duì)幼蜂的撫育.按照2.1介紹的啟發(fā)式操作實(shí)現(xiàn)工蜂對(duì)幼蜂的撫育.
步驟7更新蜂群.用新生成的幼蜂群替代原有的蜂群,并清空蜂王的基因集合,轉(zhuǎn)步驟2.
算例為19輛車(chē)和12個(gè)泊位的共享停車(chē)匹配問(wèn)題.在19輛車(chē)中,前5輛屬于第一類(lèi)停泊中不允許移位的普通車(chē)輛,第6到第9輛屬于第二類(lèi)可利用泊車(chē)服務(wù)機(jī)器人進(jìn)行移位的普通車(chē)輛,其他車(chē)輛屬于第三類(lèi)無(wú)人駕駛車(chē)輛.車(chē)輛的停車(chē)需求時(shí)段的起止時(shí)間見(jiàn)表1,而泊位的共享停車(chē)開(kāi)放時(shí)段的起止時(shí)間見(jiàn)表2.假設(shè)對(duì)應(yīng)第一、第二和第三類(lèi)車(chē)的懲罰性系統(tǒng)成本分別為100,20,10 min.泊位之間的移位距離矩陣L見(jiàn)式(13).算例分析中,距離和懲罰性成本的單位均設(shè)為km.按2.1的時(shí)間分割法,共得到38段連續(xù)的分割時(shí)間段.基于分割時(shí)段的泊位利用率φ為0.789 7.
表1 車(chē)輛停車(chē)需求 單位:min
表2 泊位共享開(kāi)放時(shí)間 單位:min
(13)
設(shè)定蜂群優(yōu)化算法的相關(guān)參數(shù)值如下:M=20、ρ=10、Δψ=10、α=0.6、θ=20、Pmute=0.015、n=5和NIteration=500.利用Java語(yǔ)言實(shí)現(xiàn)蜂群優(yōu)化算法,并在NetBeans IDE平臺(tái)運(yùn)行,利用的計(jì)算機(jī)處理器具有intel Core i5 4 GB內(nèi)存,運(yùn)行具有500次迭代的算法一次所需要的計(jì)算時(shí)間小于(1/1 000) s.圖1為利用蜂群優(yōu)化求解上述問(wèn)題的3次典型運(yùn)算結(jié)果.在三次運(yùn)算中,最初的蜂王對(duì)應(yīng)的目標(biāo)函數(shù)值分別為4 285.53、4 264.87和4 345.66,而經(jīng)過(guò)500次迭代,最優(yōu)目標(biāo)函數(shù)值分別降至70.28、70.14和70.19.由圖1中最優(yōu)目標(biāo)函數(shù)值的變化可知:蜂群優(yōu)化具有較高的計(jì)算效率,可以在迭代的初期迅速得到較好的近似最優(yōu)解,但在算法迭代的后期,對(duì)目標(biāo)函數(shù)的改善幅度逐漸減少.由圖1可知:三次運(yùn)算具有相似的收斂特征,因此說(shuō)明蜂群優(yōu)化算法具有很高的可靠性.由于啟發(fā)式算法的計(jì)算效果會(huì)隨著相關(guān)參數(shù)值的改變而變化,也與具體的問(wèn)題相關(guān),因此要在實(shí)際應(yīng)用時(shí)得到好的算法表現(xiàn),就需要對(duì)參數(shù)進(jìn)行靈敏度分析.鑒于目前尚缺乏實(shí)證數(shù)據(jù),將在后續(xù)研究中在這方面再作深入分析.
圖1 隨迭代次數(shù)τ增加而變化的最優(yōu)目標(biāo)函數(shù)值z(mì)(x(hbest))
與圖1中系列1的數(shù)據(jù)對(duì)應(yīng),最終的車(chē)輛與車(chē)位時(shí)空匹配結(jié)果見(jiàn)圖2.圖中第一列第一行的“sn”為第一列為泊位的序號(hào).該矩陣圖的第一行的數(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可知:車(chē)輛7、8、9均需移位一次,對(duì)應(yīng)的總懲罰性成本為60;而車(chē)輛10也需要移位一次,對(duì)應(yīng)的懲罰性成本為10.上述結(jié)果與最終的70.28的目標(biāo)函數(shù)值一致.進(jìn)一步觀(guān)察可知,車(chē)輛9的需求必須通過(guò)泊車(chē)機(jī)器人的移位操作才能得以滿(mǎn)足.
圖2 最佳匹配的矩陣圖
表3為程序運(yùn)行12次的統(tǒng)計(jì)學(xué)結(jié)果.將12次結(jié)果的最終目標(biāo)函數(shù)值進(jìn)行升序排列,從而使出現(xiàn)的相同結(jié)果更易被觀(guān)察.從12次結(jié)果的均值和標(biāo)準(zhǔn)方差可知蜂群優(yōu)化算法具有很高的可靠性.
表3 程序運(yùn)行12次的統(tǒng)計(jì)學(xué)結(jié)果
1) 通過(guò)時(shí)段劃分和設(shè)定恰當(dāng)?shù)囊莆粦土P性系統(tǒng)成本,可以將復(fù)雜的停車(chē)供需時(shí)間匹配關(guān)系簡(jiǎn)化為分割時(shí)段上的供需匹配,從而使建立的預(yù)約式共享停車(chē)的供需匹配模型簡(jiǎn)潔有效.
2) 新設(shè)計(jì)的蜂群優(yōu)化算法可以有效求解本文的共享停車(chē)模型,優(yōu)化的最終結(jié)果僅為初值的1/60.
3) 泊車(chē)機(jī)器人的使用可以使原本無(wú)法滿(mǎn)足的停車(chē)需求得以滿(mǎn)足,進(jìn)而提升泊位的利用率.
4) 設(shè)定不同的懲罰性系統(tǒng)成本可以在最終匹配結(jié)果中滿(mǎn)足各類(lèi)車(chē)輛不同的停車(chē)需求.