高云飛 朱霄霄 劉軍 徐耀婷 金耀花
摘 要:目前,伴隨著中國(guó)的發(fā)展,人們的生活質(zhì)量也有了顯著的提升,我國(guó)的私人汽車也越來(lái)越多。隨著我國(guó)城鎮(zhèn)私人汽車擁有量的不斷增加,我國(guó)城鎮(zhèn)居民的“停車難”問(wèn)題已經(jīng)成為當(dāng)前急需解決的一大難題,也是當(dāng)前我國(guó)城鎮(zhèn)居民面臨的迫切需求。當(dāng)前,國(guó)內(nèi)的立體停車設(shè)施普遍面臨著停車周期長(zhǎng),運(yùn)營(yíng)效率低,維護(hù)成本高等問(wèn)題,使其很難在中小城市得到普及。造成這一問(wèn)題的主要原因是,立體停車場(chǎng)的自動(dòng)測(cè)量和控制是一項(xiàng)集成了機(jī)電、光學(xué)和計(jì)算等多個(gè)領(lǐng)域的交叉技術(shù),它的研究和實(shí)施都有很大的困難。在這些問(wèn)題中,最重要的是對(duì)立體停車場(chǎng)進(jìn)行有效的調(diào)控和優(yōu)化。另外,由于我國(guó)中小城鎮(zhèn)居民對(duì)立體停車設(shè)施的認(rèn)可度較差,使得整個(gè)市場(chǎng)出現(xiàn)了“有價(jià)無(wú)市”的局面。為了改善和解決在現(xiàn)階段,在三維車庫(kù)的測(cè)控管理中存在的上述問(wèn)題,本文就是要對(duì)三維車庫(kù)的測(cè)控方法和優(yōu)化策略進(jìn)行討論和分析,重點(diǎn)是對(duì)排隊(duì)模型的構(gòu)建和路線優(yōu)化算法的實(shí)現(xiàn)進(jìn)行研究。
關(guān)鍵詞:立體車庫(kù) 車庫(kù)數(shù)字化建模 最優(yōu)路徑規(guī)劃 融合算法 排隊(duì)調(diào)度
1 引言
“停車難”的問(wèn)題會(huì)對(duì)城市居民的日常生活產(chǎn)生直接的影響,因此,為了更好地解決與之有關(guān)的“停車”問(wèn)題,許多城市都采用了“立體車庫(kù)”來(lái)代替目前的“常規(guī)”方式[1]。當(dāng)前,我國(guó)的立體車庫(kù)的發(fā)展已經(jīng)步入到了一個(gè)新的時(shí)期,它使用的是自動(dòng)控制車輛的出入,而且它的占地面積很小,可以很好的利用了城市的三維空間,還可以進(jìn)行多層次的停車,對(duì)車輛的出庫(kù)和入庫(kù)管理非常方便快捷,車輛安全系數(shù)高,防盜措施好,可以靈活的分配資源等一系列的優(yōu)點(diǎn)。立體車庫(kù)屬于一種先進(jìn)的停車設(shè)備,它占據(jù)的土地很少,所以它在現(xiàn)代化的停車設(shè)備中得到了大量的使用。不過(guò),隨著人類社會(huì)的發(fā)展,這些技術(shù)的進(jìn)步,對(duì)泊位的需求也會(huì)越來(lái)越大。從目前的計(jì)劃來(lái)看,整個(gè)計(jì)劃的進(jìn)度已經(jīng)完成了50%。因此,操作的有效性對(duì)工作的有效性有很大的影響[2]。如何有效地降低算法的執(zhí)行速度,縮短算法的執(zhí)行速度,已成為當(dāng)前研究人員關(guān)注的重點(diǎn)。
2 建立數(shù)字化模型
此類車庫(kù)參照實(shí)際的泊車位分布信息,能夠準(zhǔn)確劃分成兩個(gè)基礎(chǔ)分類。我們用到立體車庫(kù)數(shù)字化模型建立地理拓?fù)浣Y(jié)構(gòu),需要建立一個(gè)拓?fù)浣Y(jié)構(gòu)數(shù)字化模型,我們定義空間坐標(biāo)系xyz,車位為a,巷道為b,空余車位為c,層數(shù)為d,具體數(shù)字化模型結(jié)構(gòu)為(1,1,a,b,c,d),它可以準(zhǔn)確表述各個(gè)位置的地理拓?fù)浣Y(jié)構(gòu)[3]。
3 立體車庫(kù)排隊(duì)模型分析
在研究過(guò)程中,由于系統(tǒng)內(nèi)排隊(duì)類型和系統(tǒng)外實(shí)際抵達(dá)車輛數(shù)量存在差異,因此,在研究過(guò)程中,選擇系統(tǒng)內(nèi)排隊(duì)模型。
根據(jù)目前的停車場(chǎng)模式,在兩種情況下,分別采用M/M/1/0/0 N客戶來(lái)源有限類型和M/M 1/1/N/0,建立了停車場(chǎng)中的隊(duì)列模式,并以客戶平均等候時(shí)間,平均等候長(zhǎng)度,停車位空閑率為度量指標(biāo),對(duì)其進(jìn)行了模擬和分析[4]。
(1)在客戶來(lái)源數(shù)量為25,32,50,75,100的時(shí)候,對(duì)于客戶來(lái)源的數(shù)量是25,32,50,75,100個(gè)客戶來(lái)源是有限的,根據(jù)客戶來(lái)源數(shù)量的限制,分別對(duì)客戶來(lái)源的各種情形進(jìn)行了仿真,得到了平均等待時(shí)間,平均等待隊(duì)長(zhǎng),堆垛機(jī)的空閑率,并與之比較。
(2)M/M/1 N/0無(wú)窮大的系統(tǒng)的能力限制類型。
對(duì)于網(wǎng)絡(luò)的服務(wù)能力為2,3,4,5的情形,在網(wǎng)絡(luò)的限制下,分別進(jìn)行了網(wǎng)絡(luò)的仿真[5]。通過(guò)對(duì)客戶平均等候時(shí)間、平均等候隊(duì)長(zhǎng)長(zhǎng)度以及堆積器空閑率三個(gè)參數(shù)的仿真。
4 排隊(duì)論模型
排隊(duì)論(Queuing Theory),也被稱為“隨機(jī)狀態(tài)下的服務(wù)系統(tǒng)”,是一種用來(lái)研究服務(wù)對(duì)象中的隨機(jī)聚集與消融規(guī)則以及服務(wù)系統(tǒng)中的隨機(jī)工作過(guò)程的一種數(shù)學(xué)理論與方法。主要包括以下三個(gè)方面:
(1)性別差異。在不同的模式下,對(duì)不同的服務(wù)體系進(jìn)行了討論。是對(duì)隊(duì)長(zhǎng)隊(duì)列隨機(jī)分布、隊(duì)列等待時(shí)間隨機(jī)分布和忙期規(guī)律分布等進(jìn)行的研究,主要包含了兩種情況:即時(shí)時(shí)態(tài)和平穩(wěn)時(shí)態(tài)。
(2)最優(yōu)解。一種是對(duì)隊(duì)列系統(tǒng)進(jìn)行最優(yōu)的靜態(tài)最優(yōu)。二指在已有的隊(duì)列中,對(duì)最優(yōu)操作進(jìn)行了動(dòng)態(tài)最優(yōu)優(yōu)化。
(3)基于概率論的隊(duì)列模型。為了確定特定的排隊(duì)系統(tǒng)的統(tǒng)計(jì)規(guī)則與何種特定的排隊(duì)模型相一致,可以依據(jù)對(duì)應(yīng)的排隊(duì)系統(tǒng)的對(duì)應(yīng)的排隊(duì)理論,對(duì)其進(jìn)行統(tǒng)計(jì)分析和研究。排隊(duì)理論中的最少控制問(wèn)題由三個(gè)部分組成:輸入程序,排隊(duì)規(guī)則,服務(wù)組織。
3.1 排隊(duì)論系統(tǒng)組成函數(shù)
(1)輸入法:顧客進(jìn)入隊(duì)列的規(guī)則。指在某一時(shí)段中,抵達(dá)該區(qū)域的顧客數(shù)目,或者是兩位顧客先后抵達(dá)的時(shí)間。程序大體可分為兩類:確定性程序和隨機(jī)程序。被判定為一段時(shí)間內(nèi)不連續(xù)的輸入。當(dāng)顧客抵達(dá)次數(shù)n(t)滿足某一特定條件時(shí),顧客抵達(dá)次數(shù)n(t)滿足隨機(jī)分布。大多數(shù)情況下是齊次的Poisson型和負(fù)性的指標(biāo)型的情況。如果符合齊次Poisson分布,則在t時(shí)刻期間,達(dá)到n個(gè)顧客的可能性方程為:
(1)
相繼到達(dá)的客戶的間隔時(shí)間遵從負(fù)指數(shù)函數(shù)條件下分布函數(shù)如式(2)所示。
(2)
λ稱為客戶平均到達(dá)率,即單位時(shí)間內(nèi)客戶到達(dá)當(dāng)前服務(wù)系統(tǒng)數(shù)期望值;1/2即為客戶到達(dá)平均間隔時(shí)間。本文主要討論服從泊松分布的客戶輸入。
(2)隊(duì)列原則有三種:原地等候原則、顧客損失原則以及兩者的結(jié)合原則。
(a)“現(xiàn)場(chǎng)等”制度,即顧客抵達(dá)目前的隊(duì)列系統(tǒng),在排隊(duì)時(shí),所有能夠提供服務(wù)的服務(wù)點(diǎn)恰好被前面的顧客占據(jù),或是該服務(wù)點(diǎn)還沒(méi)有提供目前顧客的服務(wù),那么后面的顧客就必須在隊(duì)列中等待。在等待制中,服務(wù)的次序可以按照先到先服務(wù),也就是先來(lái)后到,也可以設(shè)定后到先服務(wù),或可以隨機(jī)地服務(wù)某一客戶,并給某些客戶有一定的優(yōu)先權(quán)服務(wù)。
(b)顧客流失法:顧客到達(dá)時(shí),如果發(fā)現(xiàn)整個(gè)系統(tǒng)中的服務(wù)組織都處于待命狀態(tài),則會(huì)立即退出現(xiàn)有的隊(duì)列。
(c)這兩種混合系統(tǒng)是一種等待系統(tǒng)和一種失去系統(tǒng)的結(jié)合[7]。由于系統(tǒng)為用戶預(yù)留的等候位置是有限制的,所以如果用戶數(shù)量超出了系統(tǒng)所允許的最大容量,那么用戶將會(huì)被強(qiáng)制退出目前的隊(duì)列。
(3)所述服務(wù)機(jī)構(gòu)可以是一個(gè)或者若干個(gè)獨(dú)立的服務(wù)平臺(tái),在所述系統(tǒng)中,所述服務(wù)平臺(tái)也可以是一個(gè)疊置器。可以并行或串聯(lián)多個(gè)幫助平臺(tái)。通常情況下,服務(wù)時(shí)間可劃分為兩種類型:確定型和隨機(jī)型。大部分的隨機(jī)者的服役時(shí)間都符合負(fù)值的指數(shù)分布。
(3)
式中μ為服務(wù)組織服務(wù)率的期望,為服務(wù)組織的服務(wù)時(shí)間期望。
5 立體車庫(kù)路徑出入庫(kù)優(yōu)化算法研究
5.1 路徑規(guī)劃Floyd算法
Floyd演算法是在一個(gè)已知權(quán)重的圖譜上,在多個(gè)數(shù)據(jù)源中,找到一個(gè)數(shù)據(jù)源間的最短路,從而得到一個(gè)數(shù)據(jù)源間的最短路。航跡最優(yōu)是指航跡從起點(diǎn)i至終點(diǎn)j的一條最優(yōu)航跡。由任一結(jié)點(diǎn)i至任一結(jié)點(diǎn)j之間的最近距離只有兩個(gè)選擇:一是從任一結(jié)點(diǎn)i至任一結(jié)點(diǎn)j之間不需通過(guò)其他結(jié)點(diǎn);二是由點(diǎn)i通過(guò)幾個(gè)結(jié)點(diǎn)k到達(dá)點(diǎn)j。該算法最初假定Dis(i,k)是從一個(gè)結(jié)點(diǎn)k到另一個(gè)結(jié)點(diǎn)的最短路徑的距離[6]。
(4)
在將該通路中的全部結(jié)點(diǎn)k遍歷完畢時(shí),起始點(diǎn)i至目標(biāo)點(diǎn)j之間的最短通路的距離被記錄在Dis(ij)中。Floyd方法的主要思想是利用一條有向圖中權(quán)函數(shù)的通路矩陣來(lái)尋找兩條通路之間的最短路。從圖的帶權(quán)鄰接矩陣出發(fā),對(duì)其進(jìn)行n次路徑更新,那么從矩陣D(0)=4,根據(jù)公式,可以構(gòu)建出矩陣D(1)。然后,從D(n-1)出發(fā),利用相同的計(jì)算方法,得到新的路徑矩陣D(n)。矩陣D(n)的i行j列的元素就是從i號(hào)起點(diǎn)到j(luò)號(hào)目標(biāo)點(diǎn)的最短路徑的長(zhǎng)度,那么,將D(n)稱為圖的最短路徑距離矩陣[7]。在此基礎(chǔ)上,提出了一種計(jì)算兩點(diǎn)之間最短路的方法。狀態(tài)轉(zhuǎn)移方程見(jiàn)式(5)。
(5)
式中表示i到j(luò)的最短距離,k是窮舉i,j之間的全部斷點(diǎn),初值應(yīng)該為0。
4.2 融合算法設(shè)計(jì)
(1)融合算法設(shè)計(jì)步驟。
(a)按照Floyd的現(xiàn)有狀態(tài),按照三維車庫(kù)模型設(shè)置了該融合算法的操作參數(shù),并在Floyd的現(xiàn)有狀態(tài)下,隨機(jī)生成一個(gè)初值解x。在禁止列表中清除全部的數(shù)據(jù)[8]。
(b)對(duì)目前的狀況進(jìn)行判定,在期望的狀況下,最短路的狀況是否符合最短路的狀況。如果是的話,那么該算法就會(huì)被終止并且被跳出來(lái),從而得到最優(yōu)的結(jié)果;如果沒(méi)有,請(qǐng)按照下面的方法執(zhí)行。
(c)使用目前的融合態(tài)數(shù)值的鄰居函數(shù),求出它的全部(或多個(gè))可獲得的鄰居數(shù)值,并在目前的融合態(tài)中求出幾個(gè)最優(yōu)候選數(shù)值。
(d)對(duì)于在目前的融合狀態(tài)中的候選者,判定在目前的融合狀態(tài)中的通路是否比最初的通路S0小。如果該問(wèn)題成立,那么將在初始態(tài)下的最優(yōu)值x替換為在現(xiàn)有條件下滿足蔑視標(biāo)準(zhǔn)的候補(bǔ)的最優(yōu)狀態(tài)值y,從而得到新的最優(yōu)當(dāng)前解,即x=y。在此基礎(chǔ)上,將上一階段中的“best so far”態(tài)的解決方案用上一階段中的解決方案替代上一階段中的解決方案,接著進(jìn)行到第(6)步;反之,接著進(jìn)行下面的操作。
(e)在目前的情況下,根據(jù)目前的情況,確定每一種被試的情況下所對(duì)應(yīng)的所有被試的相同的禁制特性,并選取目前的融合狀態(tài)候試的解集,以目前的不受試的被試的最好的狀態(tài),為新的融合狀態(tài)下的解集。并且將原本在禁止列表中的所有被禁止的目標(biāo),都用相同的狀態(tài)下所對(duì)應(yīng)的目標(biāo)代替。修訂禁止使用的表格。
(f)在目前的情況下,對(duì)該融合解決方案是否符合最短路條件進(jìn)行判定。如果是,那么在目前的情況下,該算法將立即終止,并且在融合后的運(yùn)行中輸出最優(yōu)的結(jié)果;如果沒(méi)有,那就回到第三步,然后重新開(kāi)始。融合算法流程圖如圖4所示。
車輛停放過(guò)程中,車輛的橫向移動(dòng)和縱向移動(dòng)必須同步進(jìn)行,也就是本課題所討論的車輛裝載問(wèn)題,多個(gè)車輛停放在同一泊位上。提出了在保證每個(gè)泊位的情況下,以最小的總運(yùn)程為目標(biāo)的原則[9]。根據(jù)這個(gè)推論,我們可以做出如下的假設(shè):
(a)每個(gè)停車位的進(jìn)出門和每個(gè)停車位的真實(shí)位置是知道的,每個(gè)停車位是空的還是滿的。(b)對(duì)于每個(gè)分揀堆積器在進(jìn)站和進(jìn)站過(guò)程中的存放和取車的時(shí)間和泊車就位所需要的時(shí)間是沒(méi)有任何考量的。(c)在一個(gè)運(yùn)輸期間,所有的堆疊器都以同樣的速度,以同樣的速度,以同樣的方式前進(jìn),而不用擔(dān)心電力供應(yīng)的問(wèn)題,確保了每個(gè)運(yùn)輸過(guò)程都能持續(xù)地進(jìn)行。(d)在各存儲(chǔ)位置上,各存儲(chǔ)位置上的時(shí)間是相同的。(e)一次只能有一部車輛通過(guò)該通道。(f)無(wú)論車輛的型號(hào)或牌子,停車場(chǎng)的車位都是一樣的,并且一個(gè)車位只能??恳慌_(tái)滿足進(jìn)站要求的車輛。(g)當(dāng)所述疊置器工作時(shí),所述疊置器能夠沿豎直提升和橫向移動(dòng)兩個(gè)方向進(jìn)行裝卸動(dòng)作[10]。
6 結(jié)語(yǔ)
本文研究立體車庫(kù)存取車路徑優(yōu)化,選擇單出入口巷道堆垛式立體車庫(kù)作為研究對(duì)象,圍繞著排隊(duì)模型的建立及路徑規(guī)劃優(yōu)化算法兩個(gè)層面展開(kāi)研究,論文的研究工作可以概括為以下幾個(gè)方面。
(1)進(jìn)行巷道堆垛式智能立體車庫(kù)的總體測(cè)控方案設(shè)計(jì)。確定了排隊(duì)論建模方式。完成了立體車庫(kù)控制策略研究,包括立體車庫(kù)衡量指標(biāo)平均隊(duì)長(zhǎng)、平均排隊(duì)長(zhǎng)、平均等待時(shí)間與平均逗留時(shí)間的設(shè)定,立體車庫(kù)布局的設(shè)置,確定了存車優(yōu)先策略,確定了車位分配策略。完成了立體車庫(kù)客流分布研究,建立了排隊(duì)模型,完成了立體車庫(kù)單出入口下多服務(wù)臺(tái)排隊(duì)模型分析。
(2)進(jìn)行了常用路徑優(yōu)化算法研究,確定了基于Floyd算法和禁忌算法的融合算法作為立體車庫(kù)路徑優(yōu)化算法,進(jìn)行算法設(shè)計(jì)及軟件編程調(diào)試,完成了路徑優(yōu)化后數(shù)據(jù)處理數(shù)據(jù)比對(duì)分析。
參考文獻(xiàn):
[1]韓艷,李婉瑩,楊光,張?zhí)鹛?居住區(qū)停車場(chǎng)立體化改造決策機(jī)理[J].北京工業(yè)大學(xué)學(xué)報(bào),2019,45(09):879-885.
[2]周柳娜.立體車庫(kù)智能控制系統(tǒng)研究[J].電子測(cè)試,2020(17):26-27.
[3]臧赤丁,李廣,吳杭.雙模車牌識(shí)別系統(tǒng)探析[J].中國(guó)交通信息化,2019(03):109-111.
[4]姚剛,吳斌,趙雪剛.機(jī)械式立體車庫(kù)在既有住區(qū)改造中的應(yīng)用[J].住宅科技,2019,39(07):43-46.
[5]賀云鵬,李建國(guó),張海飛.基于改進(jìn)遺傳算法的立體車庫(kù)布局及配置優(yōu)化[J].武漢大學(xué)學(xué)報(bào)(工學(xué)版),2020,53(05):464-470.
[6]孟廣耀,穆國(guó)振,王文濤,李正.新型立體車庫(kù)設(shè)計(jì)及分析[J].中國(guó)工程機(jī)械學(xué)報(bào),2019,17(04):340-344.
[7]邱玉琢,張磊.碳排放規(guī)制下生鮮農(nóng)產(chǎn)品配送車輛路徑優(yōu)化問(wèn)題[J].南京財(cái)經(jīng)大學(xué)學(xué)報(bào),2021(01):68-78.
[8]方景芳,袁沖.基于車間道路約束的物料配送模型及算法研究[J].電子設(shè)計(jì)工程,2020,28(23):18-24.
[9]楊明.機(jī)械式立體車庫(kù)的發(fā)展現(xiàn)狀及實(shí)際運(yùn)用分析[J].內(nèi)燃機(jī)與配件,2020(15):180-181.
[10]郭中旺,陳大寧,楊旭,賀濤濤,郭永靈,于周斐.智能立體車庫(kù)設(shè)計(jì)[J].智能計(jì)算機(jī)與應(yīng)用,2020,10(04):199-202.