高云飛　朱霄霄　劉軍　徐耀婷　金耀花

摘 要：目前，伴隨著中國的發(fā)展，人們的生活質(zhì)量也有了顯著的提升，我國的私人汽車也越來越多。隨著我國城鎮(zhèn)私人汽車擁有量的不斷增加，我國城鎮(zhèn)居民的“停車難”問題已經(jīng)成為當(dāng)前急需解決的一大難題，也是當(dāng)前我國城鎮(zhèn)居民面臨的迫切需求。當(dāng)前，國內(nèi)的立體停車設(shè)施普遍面臨著停車周期長，運營效率低，維護成本高等問題，使其很難在中小城市得到普及。造成這一問題的主要原因是，立體停車場的自動測量和控制是一項集成了機電、光學(xué)和計算等多個領(lǐng)域的交叉技術(shù)，它的研究和實施都有很大的困難。在這些問題中，最重要的是對立體停車場進行有效的調(diào)控和優(yōu)化。另外，由于我國中小城鎮(zhèn)居民對立體停車設(shè)施的認可度較差，使得整個市場出現(xiàn)了“有價無市”的局面。為了改善和解決在現(xiàn)階段，在三維車庫的測控管理中存在的上述問題，本文就是要對三維車庫的測控方法和優(yōu)化策略進行討論和分析，重點是對排隊模型的構(gòu)建和路線優(yōu)化算法的實現(xiàn)進行研究。

關(guān)鍵詞：立體車庫 車庫數(shù)字化建模 最優(yōu)路徑規(guī)劃 融合算法 排隊調(diào)度

1 引言

“停車難”的問題會對城市居民的日常生活產(chǎn)生直接的影響，因此，為了更好地解決與之有關(guān)的“停車”問題，許多城市都采用了“立體車庫”來代替目前的“常規(guī)”方式[1]。當(dāng)前，我國的立體車庫的發(fā)展已經(jīng)步入到了一個新的時期，它使用的是自動控制車輛的出入，而且它的占地面積很小，可以很好的利用了城市的三維空間，還可以進行多層次的停車，對車輛的出庫和入庫管理非常方便快捷，車輛安全系數(shù)高，防盜措施好，可以靈活的分配資源等一系列的優(yōu)點。立體車庫屬于一種先進的停車設(shè)備，它占據(jù)的土地很少，所以它在現(xiàn)代化的停車設(shè)備中得到了大量的使用。不過，隨著人類社會的發(fā)展，這些技術(shù)的進步，對泊位的需求也會越來越大。從目前的計劃來看，整個計劃的進度已經(jīng)完成了50%。因此，操作的有效性對工作的有效性有很大的影響[2]。如何有效地降低算法的執(zhí)行速度，縮短算法的執(zhí)行速度，已成為當(dāng)前研究人員關(guān)注的重點。

2 建立數(shù)字化模型

此類車庫參照實際的泊車位分布信息，能夠準(zhǔn)確劃分成兩個基礎(chǔ)分類。我們用到立體車庫數(shù)字化模型建立地理拓撲結(jié)構(gòu)，需要建立一個拓撲結(jié)構(gòu)數(shù)字化模型，我們定義空間坐標(biāo)系xyz，車位為a，巷道為b，空余車位為c，層數(shù)為d，具體數(shù)字化模型結(jié)構(gòu)為（1，1，a，b，c，d），它可以準(zhǔn)確表述各個位置的地理拓撲結(jié)構(gòu)[3]。

3 立體車庫排隊模型分析

在研究過程中，由于系統(tǒng)內(nèi)排隊類型和系統(tǒng)外實際抵達車輛數(shù)量存在差異，因此，在研究過程中，選擇系統(tǒng)內(nèi)排隊模型。

根據(jù)目前的停車場模式，在兩種情況下，分別采用M/M/1/0/0 N客戶來源有限類型和M/M 1/1/N/0，建立了停車場中的隊列模式，并以客戶平均等候時間，平均等候長度，停車位空閑率為度量指標(biāo)，對其進行了模擬和分析[4]。

（1）在客戶來源數(shù)量為25，32，50，75，100的時候，對于客戶來源的數(shù)量是25，32，50，75，100個客戶來源是有限的，根據(jù)客戶來源數(shù)量的限制，分別對客戶來源的各種情形進行了仿真，得到了平均等待時間，平均等待隊長，堆垛機的空閑率，并與之比較。

（2）M/M/1 N/0無窮大的系統(tǒng)的能力限制類型。

對于網(wǎng)絡(luò)的服務(wù)能力為2，3，4，5的情形，在網(wǎng)絡(luò)的限制下，分別進行了網(wǎng)絡(luò)的仿真[5]。通過對客戶平均等候時間、平均等候隊長長度以及堆積器空閑率三個參數(shù)的仿真。

4 排隊論模型

排隊論（Queuing Theory），也被稱為“隨機狀態(tài)下的服務(wù)系統(tǒng)”，是一種用來研究服務(wù)對象中的隨機聚集與消融規(guī)則以及服務(wù)系統(tǒng)中的隨機工作過程的一種數(shù)學(xué)理論與方法。主要包括以下三個方面：

（1）性別差異。在不同的模式下，對不同的服務(wù)體系進行了討論。是對隊長隊列隨機分布、隊列等待時間隨機分布和忙期規(guī)律分布等進行的研究，主要包含了兩種情況：即時時態(tài)和平穩(wěn)時態(tài)。

（2）最優(yōu)解。一種是對隊列系統(tǒng)進行最優(yōu)的靜態(tài)最優(yōu)。二指在已有的隊列中，對最優(yōu)操作進行了動態(tài)最優(yōu)優(yōu)化。

（3）基于概率論的隊列模型。為了確定特定的排隊系統(tǒng)的統(tǒng)計規(guī)則與何種特定的排隊模型相一致，可以依據(jù)對應(yīng)的排隊系統(tǒng)的對應(yīng)的排隊理論，對其進行統(tǒng)計分析和研究。排隊理論中的最少控制問題由三個部分組成：輸入程序，排隊規(guī)則，服務(wù)組織。

3.1 排隊論系統(tǒng)組成函數(shù)

（1）輸入法：顧客進入隊列的規(guī)則。指在某一時段中，抵達該區(qū)域的顧客數(shù)目，或者是兩位顧客先后抵達的時間。程序大體可分為兩類：確定性程序和隨機程序。被判定為一段時間內(nèi)不連續(xù)的輸入。當(dāng)顧客抵達次數(shù)n（t）滿足某一特定條件時，顧客抵達次數(shù)n（t）滿足隨機分布。大多數(shù)情況下是齊次的Poisson型和負性的指標(biāo)型的情況。如果符合齊次Poisson分布，則在t時刻期間，達到n個顧客的可能性方程為：

（1）

相繼到達的客戶的間隔時間遵從負指數(shù)函數(shù)條件下分布函數(shù)如式（2）所示。

（2）

λ稱為客戶平均到達率，即單位時間內(nèi)客戶到達當(dāng)前服務(wù)系統(tǒng)數(shù)期望值；1/2即為客戶到達平均間隔時間。本文主要討論服從泊松分布的客戶輸入。

（2）隊列原則有三種：原地等候原則、顧客損失原則以及兩者的結(jié)合原則。

（a）“現(xiàn)場等”制度，即顧客抵達目前的隊列系統(tǒng)，在排隊時，所有能夠提供服務(wù)的服務(wù)點恰好被前面的顧客占據(jù)，或是該服務(wù)點還沒有提供目前顧客的服務(wù)，那么后面的顧客就必須在隊列中等待。在等待制中，服務(wù)的次序可以按照先到先服務(wù)，也就是先來后到，也可以設(shè)定后到先服務(wù)，或可以隨機地服務(wù)某一客戶，并給某些客戶有一定的優(yōu)先權(quán)服務(wù)。

（b）顧客流失法：顧客到達時，如果發(fā)現(xiàn)整個系統(tǒng)中的服務(wù)組織都處于待命狀態(tài)，則會立即退出現(xiàn)有的隊列。

（c）這兩種混合系統(tǒng)是一種等待系統(tǒng)和一種失去系統(tǒng)的結(jié)合[7]。由于系統(tǒng)為用戶預(yù)留的等候位置是有限制的，所以如果用戶數(shù)量超出了系統(tǒng)所允許的最大容量，那么用戶將會被強制退出目前的隊列。

（3）所述服務(wù)機構(gòu)可以是一個或者若干個獨立的服務(wù)平臺，在所述系統(tǒng)中，所述服務(wù)平臺也可以是一個疊置器?？梢圆⑿谢虼?lián)多個幫助平臺。通常情況下，服務(wù)時間可劃分為兩種類型：確定型和隨機型。大部分的隨機者的服役時間都符合負值的指數(shù)分布。

（3）

式中μ為服務(wù)組織服務(wù)率的期望，為服務(wù)組織的服務(wù)時間期望。

5 立體車庫路徑出入庫優(yōu)化算法研究

5.1 路徑規(guī)劃Floyd算法

Floyd演算法是在一個已知權(quán)重的圖譜上，在多個數(shù)據(jù)源中，找到一個數(shù)據(jù)源間的最短路，從而得到一個數(shù)據(jù)源間的最短路。航跡最優(yōu)是指航跡從起點i至終點j的一條最優(yōu)航跡。由任一結(jié)點i至任一結(jié)點j之間的最近距離只有兩個選擇：一是從任一結(jié)點i至任一結(jié)點j之間不需通過其他結(jié)點；二是由點i通過幾個結(jié)點k到達點j。該算法最初假定Dis（i，k）是從一個結(jié)點k到另一個結(jié)點的最短路徑的距離[6]。

（4）

在將該通路中的全部結(jié)點k遍歷完畢時，起始點i至目標(biāo)點j之間的最短通路的距離被記錄在Dis（ij）中。Floyd方法的主要思想是利用一條有向圖中權(quán)函數(shù)的通路矩陣來尋找兩條通路之間的最短路。從圖的帶權(quán)鄰接矩陣出發(fā)，對其進行n次路徑更新，那么從矩陣D（0）=4，根據(jù)公式，可以構(gòu)建出矩陣D（1）。然后，從D（n-1）出發(fā)，利用相同的計算方法，得到新的路徑矩陣D（n）。矩陣D（n）的i行j列的元素就是從i號起點到j(luò)號目標(biāo)點的最短路徑的長度，那么，將D（n）稱為圖的最短路徑距離矩陣[7]。在此基礎(chǔ)上，提出了一種計算兩點之間最短路的方法。狀態(tài)轉(zhuǎn)移方程見式（5）。

（5）

式中表示i到j(luò)的最短距離，k是窮舉i，j之間的全部斷點，初值應(yīng)該為0。

4.2 融合算法設(shè)計

（1）融合算法設(shè)計步驟。

（a）按照Floyd的現(xiàn)有狀態(tài)，按照三維車庫模型設(shè)置了該融合算法的操作參數(shù)，并在Floyd的現(xiàn)有狀態(tài)下，隨機生成一個初值解x。在禁止列表中清除全部的數(shù)據(jù)[8]。

（b）對目前的狀況進行判定，在期望的狀況下，最短路的狀況是否符合最短路的狀況。如果是的話，那么該算法就會被終止并且被跳出來，從而得到最優(yōu)的結(jié)果；如果沒有，請按照下面的方法執(zhí)行。

（c）使用目前的融合態(tài)數(shù)值的鄰居函數(shù)，求出它的全部（或多個）可獲得的鄰居數(shù)值，并在目前的融合態(tài)中求出幾個最優(yōu)候選數(shù)值。

（d）對于在目前的融合狀態(tài)中的候選者，判定在目前的融合狀態(tài)中的通路是否比最初的通路S0小。如果該問題成立，那么將在初始態(tài)下的最優(yōu)值x替換為在現(xiàn)有條件下滿足蔑視標(biāo)準(zhǔn)的候補的最優(yōu)狀態(tài)值y，從而得到新的最優(yōu)當(dāng)前解，即x=y。在此基礎(chǔ)上，將上一階段中的“best so far”態(tài)的解決方案用上一階段中的解決方案替代上一階段中的解決方案，接著進行到第（6）步；反之，接著進行下面的操作。

（e）在目前的情況下，根據(jù)目前的情況，確定每一種被試的情況下所對應(yīng)的所有被試的相同的禁制特性，并選取目前的融合狀態(tài)候試的解集，以目前的不受試的被試的最好的狀態(tài)，為新的融合狀態(tài)下的解集。并且將原本在禁止列表中的所有被禁止的目標(biāo)，都用相同的狀態(tài)下所對應(yīng)的目標(biāo)代替。修訂禁止使用的表格。

（f）在目前的情況下，對該融合解決方案是否符合最短路條件進行判定。如果是，那么在目前的情況下，該算法將立即終止，并且在融合后的運行中輸出最優(yōu)的結(jié)果；如果沒有，那就回到第三步，然后重新開始。融合算法流程圖如圖4所示。

車輛停放過程中，車輛的橫向移動和縱向移動必須同步進行，也就是本課題所討論的車輛裝載問題，多個車輛停放在同一泊位上。提出了在保證每個泊位的情況下，以最小的總運程為目標(biāo)的原則[9]。根據(jù)這個推論，我們可以做出如下的假設(shè)：

（a）每個停車位的進出門和每個停車位的真實位置是知道的，每個停車位是空的還是滿的。（b）對于每個分揀堆積器在進站和進站過程中的存放和取車的時間和泊車就位所需要的時間是沒有任何考量的。（c）在一個運輸期間，所有的堆疊器都以同樣的速度，以同樣的速度，以同樣的方式前進，而不用擔(dān)心電力供應(yīng)的問題，確保了每個運輸過程都能持續(xù)地進行。（d）在各存儲位置上，各存儲位置上的時間是相同的。（e）一次只能有一部車輛通過該通道。（f）無論車輛的型號或牌子，停車場的車位都是一樣的，并且一個車位只能?？恳慌_滿足進站要求的車輛。（g）當(dāng)所述疊置器工作時，所述疊置器能夠沿豎直提升和橫向移動兩個方向進行裝卸動作[10]。

6 結(jié)語

本文研究立體車庫存取車路徑優(yōu)化，選擇單出入口巷道堆垛式立體車庫作為研究對象，圍繞著排隊模型的建立及路徑規(guī)劃優(yōu)化算法兩個層面展開研究，論文的研究工作可以概括為以下幾個方面。

（1）進行巷道堆垛式智能立體車庫的總體測控方案設(shè)計。確定了排隊論建模方式。完成了立體車庫控制策略研究，包括立體車庫衡量指標(biāo)平均隊長、平均排隊長、平均等待時間與平均逗留時間的設(shè)定，立體車庫布局的設(shè)置，確定了存車優(yōu)先策略，確定了車位分配策略。完成了立體車庫客流分布研究，建立了排隊模型，完成了立體車庫單出入口下多服務(wù)臺排隊模型分析。

（2）進行了常用路徑優(yōu)化算法研究，確定了基于Floyd算法和禁忌算法的融合算法作為立體車庫路徑優(yōu)化算法，進行算法設(shè)計及軟件編程調(diào)試，完成了路徑優(yōu)化后數(shù)據(jù)處理數(shù)據(jù)比對分析。

參考文獻：

[1]韓艷，李婉瑩，楊光，張?zhí)鹛?居住區(qū)停車場立體化改造決策機理[J].北京工業(yè)大學(xué)學(xué)報，2019，45（09）：879-885.

[2]周柳娜.立體車庫智能控制系統(tǒng)研究[J].電子測試，2020（17）：26-27.

[3]臧赤丁，李廣，吳杭.雙模車牌識別系統(tǒng)探析[J].中國交通信息化，2019（03）：109-111.

[4]姚剛，吳斌，趙雪剛.機械式立體車庫在既有住區(qū)改造中的應(yīng)用[J].住宅科技，2019，39（07）：43-46.

[5]賀云鵬，李建國，張海飛.基于改進遺傳算法的立體車庫布局及配置優(yōu)化[J].武漢大學(xué)學(xué)報（工學(xué)版），2020，53（05）：464-470.

[6]孟廣耀，穆國振，王文濤，李正.新型立體車庫設(shè)計及分析[J].中國工程機械學(xué)報，2019，17（04）：340-344.

[7]邱玉琢，張磊.碳排放規(guī)制下生鮮農(nóng)產(chǎn)品配送車輛路徑優(yōu)化問題[J].南京財經(jīng)大學(xué)學(xué)報，2021（01）：68-78.

[8]方景芳，袁沖.基于車間道路約束的物料配送模型及算法研究[J].電子設(shè)計工程，2020，28（23）：18-24.

[9]楊明.機械式立體車庫的發(fā)展現(xiàn)狀及實際運用分析[J].內(nèi)燃機與配件，2020（15）：180-181.

[10]郭中旺，陳大寧，楊旭，賀濤濤，郭永靈，于周斐.智能立體車庫設(shè)計[J].智能計算機與應(yīng)用，2020，10（04）：199-202.