智能共享停車供需匹配優(yōu)化模型及改進(jìn)蜂群算法

何勝學(xué)

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

0 引 言

隨著泊車服務(wù)機(jī)器人(parking valet robot，PVR)的推廣應(yīng)用和無人駕駛技術(shù)的不斷發(fā)展，過去車輛和泊位在車輛停泊期間固定搭配的共享停車供需匹配方式亟待調(diào)整改變以適應(yīng)時(shí)代的發(fā)展需要．PVR和無人駕駛車輛(autonomous vehicle，AV)一方面使車輛在停泊期間變換車位成為可能，從而實(shí)現(xiàn)車輛停放時(shí)空布局的合理化，減少泊位閑置的時(shí)間碎片，提升泊位利用率．另一方面也提出了“如何合理規(guī)劃PVR和AV的移車操作避免不必要的車輛移位，從而減少相關(guān)的運(yùn)行成本，并降低在車輛移位過程中發(fā)生事故的風(fēng)險(xiǎn)”的問題．為解決上述問題，文中將以預(yù)約式共享停車中同時(shí)存在泊車期間不允許移位、允許利用PVR移位和AV自主移位三種差異化停車需求為背景，在滿足可接受的共享停車需求條件下，以最小化車輛移位次數(shù)和移車成本為目標(biāo)建構(gòu)共享停車供需匹配模型，并利用模型可行解(即車輛與泊位的時(shí)空匹配關(guān)系)結(jié)構(gòu)特征設(shè)計(jì)一種蜂群優(yōu)化算法對(duì)模型進(jìn)行求解．

近年來學(xué)者們針對(duì)共享停車進(jìn)行了居多研究：

1) 針對(duì)共享停車需求特征與影響方面 文獻(xiàn)[1]通過時(shí)間序列預(yù)測(cè)時(shí)間重要度，在匹配時(shí)盡量減少熱點(diǎn)時(shí)間的預(yù)約，從而減少泊位空閑時(shí)間碎片．文獻(xiàn)[2]提出停車設(shè)施的選擇概率依賴于設(shè)施的停車吸引力系數(shù)、停車收費(fèi)、相關(guān)步行時(shí)間和實(shí)際行程時(shí)間．文獻(xiàn)[3]提出將停車需求分布與路徑選擇決策相結(jié)合．文獻(xiàn)[4]分析了不同情境下泊位擁有者參與共享泊位的意愿．文獻(xiàn)[5]實(shí)證分析共享無人車的使用對(duì)停車泊位需求的影響．文獻(xiàn)[6]提出基于個(gè)人信用風(fēng)險(xiǎn)等級(jí)來匹配泊位．文獻(xiàn)[7]分析了共享停車供給與需求存在的不準(zhǔn)時(shí)特征．文獻(xiàn)[8]比較了泊位利用率和停車需求者滿意度對(duì)共享泊位匹配的影響．

2) 以構(gòu)建車輛與泊位的匹配模型和優(yōu)化共享停車服務(wù)平臺(tái)服務(wù)方面 文獻(xiàn)[9]以共享停車平臺(tái)收益及用戶步行距離為優(yōu)化目標(biāo)，構(gòu)建了預(yù)約請(qǐng)求下共享泊位分配模型．從參與各方經(jīng)濟(jì)利益最大化角度出發(fā)，文獻(xiàn)[10]構(gòu)建了基于拍賣機(jī)制的共享停車泊位分配、定價(jià)和收益機(jī)制．文獻(xiàn)[11]通過定義虛擬泊位概念建立了共享停車泊位匹配的優(yōu)化模型．文獻(xiàn)[12]在多個(gè)停車場(chǎng)的共享停車泊位匹配中考慮了停車需求的優(yōu)先級(jí)別差異．文獻(xiàn)[13]在綜合租用車位成本、提供停車服務(wù)收入和拒絕潛在用戶的損失基礎(chǔ)上，構(gòu)建了車位租用和停車需求分配的統(tǒng)一決策模型．文獻(xiàn)[14]以步行距離的差異定義共享車位的異質(zhì)性，構(gòu)建了跨區(qū)域泊位分配的隨機(jī)動(dòng)態(tài)規(guī)劃模型．文獻(xiàn)[15]利用滾動(dòng)時(shí)域方法對(duì)實(shí)時(shí)獲得的共享停車供需進(jìn)行滾動(dòng)式動(dòng)態(tài)匹配．文獻(xiàn)[16]以最大化泊位利用率和減少步行距離為目標(biāo)，建立的共享停車的泊位分配模型．文獻(xiàn)[17]通過分析停車需求的到達(dá)時(shí)間和停泊時(shí)長分布，確定最佳共享泊位與保留非共享泊位的數(shù)量．

3) 針對(duì)無人駕駛對(duì)共享停車的影響方面 文獻(xiàn)[18]分析了無人車市場(chǎng)占有率、燃油費(fèi)和停車費(fèi)對(duì)無人車在完成載客后選擇停車場(chǎng)的影響，建議通過差異化的區(qū)域收費(fèi)引導(dǎo)無人車的停車場(chǎng)選擇，從而在整體上實(shí)現(xiàn)停車的供需平衡．文獻(xiàn)[19]分析了在不同的停車能力限制條件下共享無人車的市場(chǎng)占有率對(duì)早上通勤出行的影響．文獻(xiàn)[20]利用仿真模型對(duì)共享無人車、私有無人車、共享有人車和非共享有人車共存情況下的停車需求變化進(jìn)行分析，發(fā)現(xiàn)共享車輛的存在可降低總體停車需求，但也會(huì)增加部分敏感區(qū)域的停車需求．文獻(xiàn)[21]分析了停車管理策略對(duì)需求響應(yīng)式共享無人車的規(guī)模、服務(wù)效率和公平性，以及相關(guān)的外部性影響．文獻(xiàn)[22]對(duì)智慧停車和自動(dòng)代客泊車?yán)碚摪l(fā)展與相關(guān)實(shí)踐進(jìn)行了系統(tǒng)梳理，明確了當(dāng)前相關(guān)領(lǐng)域需要關(guān)注和解決的主要問題．

與現(xiàn)有研究相比，本研究的特色體現(xiàn)在：①首次在共享停車研究中同時(shí)引入PVR和AV的影響，為共享停車在新時(shí)代發(fā)展提供理論支持；②與現(xiàn)有研究主要關(guān)注停車場(chǎng)選擇和AV路線規(guī)劃不同，本研究則關(guān)注車輛停泊過程中的移位操作和相關(guān)的成本；③針對(duì)新建匹配模型的NP-hard特征，利用車輛與泊位時(shí)空匹配關(guān)系與蜜蜂基因序列進(jìn)行類比，并通過匹配交換操作體現(xiàn)蜂群優(yōu)化中工蜂對(duì)幼蜂的撫育，最終實(shí)現(xiàn)針對(duì)本文匹配模型的蜂群優(yōu)化算法設(shè)計(jì)．

1 模型建構(gòu)

1.1 基本假設(shè)條件

本研究的基本假設(shè)條件如下：①研究針對(duì)預(yù)約式共享停車的需求與供給匹配，因此假設(shè)相關(guān)的車輛停車需求時(shí)間和泊位可供共享停車的開放時(shí)間事先已知；②為了方便構(gòu)建模型，假設(shè)所有車輛的停車需求時(shí)間和共享泊位的開放時(shí)間均是整塊連續(xù)的時(shí)間段；③假設(shè)不同類別車輛對(duì)泊車過程中是否允許變換泊位的要求事先已知；④假設(shè)共享泊位之間進(jìn)行車輛泊位變換的行車路線長度已知；⑤為了減少不必要的移車操作，假設(shè)不管是利用泊車機(jī)器人移車還是無人駕駛車輛的自主移位均只能在車輛停車需求時(shí)間和泊位共享開放時(shí)間的起止時(shí)刻發(fā)生．

考慮到假設(shè)條件⑤，有必要將共享停車服務(wù)的總時(shí)間加以分割，形成長度較短的分割時(shí)間段，進(jìn)而將車輛的停車需求和泊位的供給也對(duì)應(yīng)分割為小的時(shí)間段．具體的時(shí)間分割方法如下：①首先利用所有車輛停車需求時(shí)間的起止時(shí)刻和共享泊位開放時(shí)間的起止時(shí)刻構(gòu)成一個(gè)起止時(shí)刻集合；②剔出上述起止時(shí)刻集合中的重復(fù)元素，并按照時(shí)間的升序?qū)κＳ嘣丶右耘判颍玫揭粋€(gè)有序的起止時(shí)刻序列；③比照上述有序的時(shí)刻序列，以序列里的時(shí)刻作為起止時(shí)刻，將所有的車輛的停車需求時(shí)間和共享泊位的開放時(shí)間劃分為連續(xù)相接的具有較小長度的分割時(shí)間段．

1.2 參變量簡介

1.3 匹配模型

下面給出具有多種車輛差異化停車需求的供需匹配優(yōu)化模型.

(1)

(2)

(3)

(4)

目標(biāo)函數(shù)(1)由兩個(gè)加和項(xiàng)構(gòu)成，其中第一個(gè)加和項(xiàng)是所有車輛發(fā)生移位的移位路線總長度，第二項(xiàng)是不同車輛發(fā)生泊位改變時(shí)引發(fā)的懲罰性系統(tǒng)成本之和．為了滿足第一類不允許在泊車過程中進(jìn)行泊位變換的停車需求，對(duì)應(yīng)的單次懲罰性系統(tǒng)成本w1的值應(yīng)該遠(yuǎn)大于其他兩個(gè)懲罰性成本量w2和w3．從共享停車服務(wù)平臺(tái)或管理者的角度出發(fā)，w2的值應(yīng)大于w3，因?yàn)槔肞VR的成本一般是由平臺(tái)承擔(dān)的，而無人駕駛車輛的移位成本一般由車輛所有者承擔(dān)．約束(2)為如果一個(gè)泊位在給定分割時(shí)段不提供共享停車服務(wù)，則該時(shí)段沒有需要共享停車的車輛停于該泊位；而當(dāng)該泊位在該給定分割時(shí)段提供共享停車服務(wù)時(shí)，至多只能有一輛需要共享停車的車輛停于該泊位．約束(3)為在給定時(shí)段任意給定車輛的共享停車需求應(yīng)得到滿足．約束(4)為對(duì)決策變量取值范圍的限定．由目標(biāo)函數(shù)(1)和約束(2)～(4)構(gòu)成的模型(1)～(4)完整描述了多車種條件下共享停車供需匹配問題．

如果先對(duì)約束(2)和(3)分別在泊位集合P和車輛集合V上進(jìn)行加和，然后加以比較，為

(5)

式(5)為在任意給定分割時(shí)間段，車輛的停車需求小于泊位的供給．將滿足式(5)的車輛共享停車需求稱為可接受的合理需求．顯然在允許對(duì)所有車輛進(jìn)行泊位變換的條件下，一定存在一個(gè)可行的供需匹配滿足約束(2)和(3)．

利用定義在分割時(shí)間段上的車輛停車需求與泊位共享停車供給可定義相關(guān)的基于分割時(shí)段數(shù)量的泊位利用率φ為

(6)

模型(1)～(4)屬于純整數(shù)二次規(guī)劃．從約束和目標(biāo)函數(shù)的特征可知，也可將模型(1)～(4)視為一類特殊的二次分配模型．已有研究表明二次分配問題屬于一類極難的NP-hard問題，目前相關(guān)的一些線性化技術(shù)只能改善問題求解過程中的目標(biāo)下界，不能在現(xiàn)實(shí)可接受的計(jì)算時(shí)間內(nèi)得到并確定較大規(guī)模二次分配問題的全局最優(yōu)解．鑒于上述知識(shí)，下文將針對(duì)模型(1)～(4)設(shè)計(jì)一種有效的啟發(fā)式算法，以期迅速高效地得到問題的近似最優(yōu)解．

2 啟發(fā)式算法設(shè)計(jì)

2.1 模型解與蜂群優(yōu)化概念的映射關(guān)系

定義2(基因):如果為Vk中的每一輛車在集合Pk中選擇一個(gè)獨(dú)占的泊位來在分割時(shí)間段k停放該車輛，則將會(huì)在Vk和Pk之間建立一個(gè)可行的匹配關(guān)系，其中的匹配構(gòu)成一個(gè)對(duì)應(yīng)分割時(shí)間段k的匹配集合，記作e(Vk,Pk)或ek．在蜂群優(yōu)化里稱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è)向量，稱為一個(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))稱為蜜蜂h的適應(yīng)值．

(7)

ψnew=ψ-Δψ

(8)

λnew=αλ

(9)

當(dāng)基因集合已滿(已經(jīng)包含ρ只雄蜂的基因序列)或蜂王的能量接近0時(shí)，一次繁育飛行結(jié)束，蜂王將返回蜂巢去孵化幼蜂．如果完成繁育飛行時(shí)，蜂王的基因集合未滿，則從當(dāng)前備選蜂集合中選取適應(yīng)值相對(duì)較大的備選蜂的基因序列來填滿基因集合．

(10)

蜂王返回蜂巢后孵化幼蜂包含兩種情況:一種情況為通過將蜂王基因序列與基因集合中雄蜂基因序列進(jìn)行類似遺傳算法的交叉和變異操作得到一定數(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.2 蜂群優(yōu)化求解步驟

基于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)行類似遺傳算法的交叉和變異操作得到一定數(shù)量新的幼蜂；然后僅對(duì)蜂王的基因?qū)嵤┳儺惒僮鞯玫揭欢〝?shù)量新的幼蜂；將兩種情況下得到的蜜蜂組合形成規(guī)模為M的幼蜂群．

步驟6工蜂對(duì)幼蜂的撫育．按照2.1介紹的啟發(fā)式操作實(shí)現(xiàn)工蜂對(duì)幼蜂的撫育．

步驟7更新蜂群．用新生成的幼蜂群替代原有的蜂群，并清空蜂王的基因集合，轉(zhuǎn)步驟2．

3 算例分析

算例為19輛車和12個(gè)泊位的共享停車匹配問題．在19輛車中，前5輛屬于第一類停泊中不允許移位的普通車輛，第6到第9輛屬于第二類可利用泊車服務(wù)機(jī)器人進(jìn)行移位的普通車輛，其他車輛屬于第三類無人駕駛車輛．車輛的停車需求時(shí)段的起止時(shí)間見表1，而泊位的共享停車開放時(shí)段的起止時(shí)間見表2．假設(shè)對(duì)應(yīng)第一、第二和第三類車的懲罰性系統(tǒng)成本分別為100，20，10 min．泊位之間的移位距離矩陣L見式(13)．算例分析中，距離和懲罰性成本的單位均設(shè)為km．按2.1的時(shí)間分割法，共得到38段連續(xù)的分割時(shí)間段．基于分割時(shí)段的泊位利用率φ為0.789 7．

表1 車輛停車需求 單位：min

表2 泊位共享開放時(shí)間 單位：min

(13)

設(shè)定蜂群優(yōu)化算法的相關(guān)參數(shù)值如下：M=20、ρ=10、Δψ=10、α=0.6、θ=20、Pmute=0.015、n=5和NIteration=500．利用Java語言實(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)化求解上述問題的3次典型運(yùn)算結(jié)果．在三次運(yùn)算中，最初的蜂王對(duì)應(yīng)的目標(biāo)函數(shù)值分別為4 285.53、4 264.87和4 345.66，而經(jīng)過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)算具有相似的收斂特征，因此說明蜂群優(yōu)化算法具有很高的可靠性．由于啟發(fā)式算法的計(jì)算效果會(huì)隨著相關(guān)參數(shù)值的改變而變化，也與具體的問題相關(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)，最終的車輛與車位時(shí)空匹配結(jié)果見圖2．圖中第一列第一行的“sn”為第一列為泊位的序號(hào)．該矩陣圖的第一行的數(shù)字表示分割時(shí)段的序號(hào)．矩陣圖中其他元素的意義規(guī)定如下：“/”為對(duì)應(yīng)泊位在對(duì)應(yīng)分割時(shí)段不開放；“_”為對(duì)應(yīng)泊位在對(duì)應(yīng)分割時(shí)段為共享停車開放，但是沒有被占用；數(shù)字“n” 為對(duì)應(yīng)泊位在對(duì)應(yīng)分割時(shí)段被序號(hào)為n的車輛占用．由圖2可知:車輛7、8、9均需移位一次，對(duì)應(yīng)的總懲罰性成本為60；而車輛10也需要移位一次，對(duì)應(yīng)的懲罰性成本為10．上述結(jié)果與最終的70.28的目標(biāo)函數(shù)值一致．進(jìn)一步觀察可知，車輛9的需求必須通過泊車機(jī)器人的移位操作才能得以滿足．

圖2 最佳匹配的矩陣圖

表3為程序運(yùn)行12次的統(tǒng)計(jì)學(xué)結(jié)果．將12次結(jié)果的最終目標(biāo)函數(shù)值進(jìn)行升序排列，從而使出現(xiàn)的相同結(jié)果更易被觀察．從12次結(jié)果的均值和標(biāo)準(zhǔn)方差可知蜂群優(yōu)化算法具有很高的可靠性．

表3 程序運(yùn)行12次的統(tǒng)計(jì)學(xué)結(jié)果

4 結(jié) 論

1) 通過時(shí)段劃分和設(shè)定恰當(dāng)?shù)囊莆粦土P性系統(tǒng)成本，可以將復(fù)雜的停車供需時(shí)間匹配關(guān)系簡化為分割時(shí)段上的供需匹配，從而使建立的預(yù)約式共享停車的供需匹配模型簡潔有效．

2) 新設(shè)計(jì)的蜂群優(yōu)化算法可以有效求解本文的共享停車模型，優(yōu)化的最終結(jié)果僅為初值的1/60．

3) 泊車機(jī)器人的使用可以使原本無法滿足的停車需求得以滿足，進(jìn)而提升泊位的利用率．

4) 設(shè)定不同的懲罰性系統(tǒng)成本可以在最終匹配結(jié)果中滿足各類車輛不同的停車需求．