基于遺傳算法的自動化立體車庫庫位分配

陳 楨，楊 旻

（1.上汽大眾汽車有限公司 上海，201805；2.殼牌（中國）有限公司，上海 200336）

0 引言

隨著我國汽車保有量越來越高，停車日益困難，自動化立體車庫容量大、占地面積少、停車方便，是解決停車問題的一個有效方法[1]，常見的自動化立體車庫有升降橫移式、巷道堆垛式、垂直升降式、垂直循環式等[2]，近年來出現了許多新型立體車庫，例如倉儲平面移動式停車設備，其特點是車庫密度高、安全可靠、自動化程度高、具有自動對中裝置、存取車效率高[3]。隨著立體車庫的發展，有很多學者研究其存取車策略[4]，由于各種立體車庫的結構及選取目標函數的不同，各種存取車策略在實際的應用中有許多的不同點。

常見的立體車庫存取車策略研究大多針對只有一個升降機的自動化立體車庫，如李劍鋒等人利用改進遺傳算法研究了巷道堆垛式立體車庫調度策略[5]；魯立等人對出入庫的策略提出了一種基于社會最小等待時間的出入庫優化算法，將其應用于存取車優化[6]；孫軍艷等人利用改進的交叉算子遺傳算法對三種不同庫容的升降橫移式與巷道堆垛式立體車庫進行存取車調度優化[7]。

本文的研究對象是具有兩臺汽車升降機的存取分離式倉儲平面移動式立體車庫，相對于只布置一臺汽車升降機的倉儲平面移動式立體車庫，其整體用戶存取車等待時間更短。由于在車庫的結構確定的情況下，存取車由升降機和搬運機完成，因此車庫的存取車效率與存取策略有密切的聯系，本文將針對具有兩臺升降機即具有單獨的入庫口和出庫口的立體車庫進行存取車策略優化并比較各策略的存取車效率。

1 立體車庫結構

本文所研究立體車庫的結構如圖1所示，其中1～3層為SUV等大型汽車存放區，4～9層為中小型汽車存放區。左右分別設置兩臺汽車升降機，每臺升降機配備一臺汽車搬運器。在本立體車庫中若進行存車任務，則控制系統控制1號升降機開門，汽車駛入升降機內的搬運器，等待駕駛員及乘客離開。升降機根據控制系統分配的具體車庫位置停到對應的樓層。搬運器連同車輛從升降機內離開，運輸汽車到指定位置后，返回升降機內，升降機1返回初始位置。若執行取車任務，汽車升降機2升到對應樓層，搬運器從升降機內離開將汽車取出后運入升降機，升降機降至出口，等待駕駛員將車輛開離即完成取車。

圖1 立體車庫示意圖

2 庫位分配策略設計

在進行車輛存取的過程中，控制系統需要為每一輛進入車庫的汽車分配庫位，目前常用的庫位分配方法為自然排序存取法、存車優先策略和取車優先策略：自然排序存取法對車庫的所有庫位依次編號，并對當前空余的庫位統計并排序，依次配對給的需要存車的車輛[8]。取車方法類似，查詢到客戶車輛存放的實際庫位編號，而后依次執行取車操作。這種傳統存取模式優點是簡單可靠，控制系統簡單，缺點是車庫存取效率不高；存車優先策略即將汽車放在樓層較低且靠近入口處的庫位；取車優先策略即將車存在樓層較低靠近出口處的庫位，這兩個目標在汽車存放位置上存在矛盾；同時本車庫采用會員制，會員等級越高，其車輛的存取車優先級越高。

因此綜合用戶存車體驗及現場存車秩序，本文設計的自動化立體車庫庫位分配策略如下：

1）用戶存取車：存車時用戶按照到達車庫的先后順序將汽車開入升降機后離開，取車時用戶按照啟動取車任務的先后順序將汽車從升降機開走完成取車。

2）庫位樓層分配：1～3層大型車輛存放區和4～9層中小型車輛存放區在庫位分配時相互獨立。即若下一輛要存放的轎車為中小型車輛，則只考慮4～9層的庫位。

圖2 平面立體式立體車庫二維坐標圖

3）庫位分配：考慮存車優先、取車優先以及車庫用戶會員制，本文設計一種策略可調的自動化立體車庫庫位分配方法。在有大量汽車需要入庫的時采用存車優先策略，快速存車，緩解車庫入口擁堵情況；在正常情況下采用取車優先策略，將車輛停放在出庫口附近，減少出庫時間同時將靠近入口的庫位空出來以備存車集中時減少存車等待；會員等級高的用戶無論是在存車優先還是取車優先的策略下，其汽車存放位置都需要相對靠近出口，以減少會員取車等待時間。

3 庫位分配策略實現

3.1 數學模型建立

為實現，上述庫位分配策略，本文以最小化總出庫、入庫時間為目標分別建立數學模型，為便于建立系統數學模型，現做出如下設定：

1）本仿真過程中所有需要存放的車輛均為中小型汽車，即本文只以4～9層為例進行庫位分配，1～3層的庫位分配方法與4～9層類似；

2）由于本車庫前后為對稱結構，所以本文只考慮4～9層的前區庫位，庫位編號如圖2所示，后區庫位分配方法與前區類似；

3）在整個仿真過程中，立體車庫運行正常，不考慮其余非正常影響因素；

4）設某時刻共有Nm輛車需要入庫，共有Ns個空余庫位，若Nm>Ns，則取Nm=Ns，剩余未能被分配的汽車放到立體車庫后區空余庫位上分配。

建模過程中的相關變量設定如下，設庫位坐標號為（i，j），i為樓層號，j為庫位列號；設升降機沿y軸的平均運行速度為v1，搬運器沿x軸的平均移動速度為v2；庫位在x軸方向的寬度為s，1～3層的平均層高為h1，4～9層的平均層高為h2；設司機將車駛入/駛出汽車升降機的時間為T0，搬運器從汽車升降機移出或移入的時間為T2，搬運器將車輛存入/取出庫位的時間為T3。

3.1.1 存車優先模型

只考慮某時刻的存在的Nm輛需入庫車輛，存車優先策略要求存車所需要的總時間最短。編號為k的車輛要存到（i，j）（i>3，0

將Nm輛車全部存入立體車庫所需要的時間如式(2)所示。

存車優先策略的目標函數即如式(3)所示。

式中，GI為最少總存車時間，s。

3.1.2 取車優先模型

取車優先策略要求將所有待取車輛從車庫取出所需要的總時間最短。設編號為k的車輛要從（i，j）（i>3，0

將Nm輛車全部取出所需要的時間如式(5)所示。

取車優先策略的目標函數即如式(6)所示。

式中，GO為最少總取車時間，s。

3.1.3 會員制度模型

會員制度即為把會員等級高的用戶車輛停放在相對同一批入庫車輛更靠近出庫口的位置，這個目標可以與出庫優先策略合并。若某車的VIP等級為u，則參考會員制度的出庫優先目標函數可以表達如式(7)所示。

VIP等級越高，u的值就會越大，Pk被放大的倍數越大，這輛車的取車時間相對于其他VIP等級低的用戶對總取車時間的影響就會越大。為了降低取車總時間，只能盡量減少Pk的值，即會把該VIP等級高的車停放的越靠近出口。

3.1.4 系統數學模型

綜合考慮以上因素，為實現在庫位分配過程中能夠根據實際情況靈活調整庫位分配策略的需求，本文采用權重系數法來建立系統數學模型，將權重w1分配給存車優先模型，將權重w2分配給綜合了會員制度的取車優先模型，有大量車輛需要入庫時，增大權重w1，正常情況則增大權重w2。則若將Nm個車輛存入車庫，則庫位分配的系統數學模型如式(8)所示。

3.2 遺傳算法求解

遺傳算法借鑒生物進化的過程來解決問題，在種群中通過交叉、變異等操作逐步找到更優的解，并淘汰較差的解，多次進化后得到近似最優解[9]，其計算過程如圖3所示。

圖3 遺傳算法計算過程

3.2.1 染色體編碼與解碼

編碼是遺傳算法設計的關鍵步驟之一，它是解空間與問題空間轉換的橋梁，編碼方式直接影響遺傳算法的運算結果。目前常用的編碼方式有實數編碼、二進制編碼、浮點數編碼等。

本文采用浮點數編碼將待入庫車輛與遺傳算法的染色體結合，設有Ns個空閑庫位（n1，n2，n3，……，nNs）和Nm個待入庫的車輛（m1，m2，m3，……，mNm），經過選擇交叉變異后得到一條浮點數組成的染色體（β1，β2，β3，……，βNs），該染色體與空閑庫位一一對應，即βi對應庫位ni，將庫位按照其對應β_i的數值從小到大排序，取前Nm個庫位分別對應于待入庫車輛。舉例說明：此時共有6個空閑庫位[15，16，18，25，29，57]和5個要入庫的車輛[1，2，3，4，5]，這五輛車的VIP等級為[0.56，0.12，0.32，0.86，0.19]，若有一條染色體G=[0.4，0.7，0.03，0.1，0.21，066]，即基因0.4對應15號庫位、0.7對應16號庫位……以此類推。將庫位按照G排序后得到[18，25，29，15，57，16]，即1號車輛存入18號庫位，2號車輛存入25號庫位，以此類推，而后根據車輛的VIP等級及其對應的庫位去計算該條染色體的適應度信息。

3.2.2 遺傳運算

本文使用MATLAB的遺傳算法優化工具箱，在選取下一代個體時，采用輪盤賭選擇法，代溝值設為0.9，在產生新個體時使用單點交叉。本文給定最大遺傳代數Maxgen，當遺傳運算次數等于Maxgen后，停止運算并輸出適應度最優的個體，通過多次的運算發現，設最大遺傳代數為30代完全能夠得到系統的最優解，如圖4所示，這里為留有一定的余量設最大遺傳代數為50代。遺傳算法優化過程如下：

1）設定基本參數值，選擇權重w1和w2的值，最大遺傳代數為50，遺傳代數初始值為1，種群容量為70；

2）根據空閑庫位的數量設定染色體的長度，按照浮點數編碼產生70條染色體，作為遺傳算法的初始種群；

3）根據編碼方式解碼出每條染色體對應的庫位排列信息和車輛信息，根據式(8)，計算每條染色體的適應度；

4）按照適應度對染色體進行排列，根據代溝值使用輪盤賭選擇染色體，并對未被選中的染色體進行交叉操作得到新的染色體，重新組成下一代種群；

5）遺傳代數加一，并判斷是否達到了最大遺傳代數，如果達到了則輸出目前適應度函數最低的那條染色體，對這條染色體進行解碼，得到庫位分配信息；若未達到則返回步驟3）繼續計算。

4 優化結果分析

圖4 遺傳算法收斂情況

本文對立體車庫的存取策略進行了三種分析，假定現在4～9層的立體車庫60個庫位，已經在編號為[37，43，45，47，61，67，73，75，87，88]的庫位上存放了10輛車，有20輛車需進行空余庫位分配，且其VIP等級按照序號排為[0.13，0.29，0.17，0.02，0.33，0.88，0.25，0.37，0.38，0.01，0.95，0.85，0.15，0.45，0.23，0.25，0.52，0.67，0.99，0.33]。計算過程中其余相關參數設置如表1所示。

按照表1所述參數取不同的權重值進行遺傳算法求解，得到如下結果。

1）w1=0.9，w1=0.1

按照上述權重值即存車優先，得到的庫位分配結果如圖5中藍色色塊所示，色塊內數字代表入庫車輛的編號，即1號汽車分配在42號庫位，2號汽車分配在33號庫位……以此類推，可看到這20輛車的庫位分配情況為存車優先時車輛存放位置多集中在入口處，并且VIP等級較高的6號、11號、12號、18號車及19號車相對靠近車庫出口。

2）w1=0.1，w1=0.9

取上述參數即為取車優先，算法的收斂情況與上述情況類似，這里不再贅述。遺傳迭代計算出來的庫位分配結果如圖中粉色色塊所示，1號汽車存放在66號庫位，2號汽車存放在76號庫位等。由圖可知，取車優先時，車輛存放位置多集中在出口處，且VIP等級較高的6、11、12、18及19號車相對靠近車庫出口。

表1 基本仿真數據設定

圖5 庫位分配情況

3）常規入庫

常規入庫即按照空余車庫編號從小到大依次存入，如圖5中棕色色塊所示。

下面計算三種不同的存車策略將20輛車存入車庫所用的存、取車時間，如表2所示。

表2 存取車各策略的遺傳算法結果比較

采用存車優先模式，存車時間相對于常規入庫減少了4.35%，相對于取車優先提高了14.272%。采用取車優先模式分配庫位，取車時間相對于常規入庫分配減少了14.431%，相對于存車優先模式減少了15.078%。因此采用本文設計的庫位分配方法能夠在特定情況下有效減少存、取車時間，以適應不同時段的需求。

5 結語

本文使用遺傳算法求解自動化立體車庫庫位分配問題，在考慮會員優先策略的同時，設計了一種通過調整權重來改變庫位分配策略的方法，以適應立體車庫不同時段的需求。在存在50個空余庫位、20輛待入庫車輛的的情況下，得出以下結論：相對于常規入庫方法，本文所設計的方法在存車優先時能夠減少4.35%的存車時間，在取車優先時能夠減少14.431%的取車時間，并且相對于同批入庫的其他車輛，會員級別高的用戶車輛被安排在更靠近車庫出口的庫位，實現了縮短高級會員取車等待時間的目標。