陳 亞，楊佳衡，沈偉東，鐘浩翔，朱亞東，鄧黎明

(1.北京石油化工學院機械工程學院，北京 102617； 2.中國聯合網絡通信有限公司勃利縣分公司， 黑龍江 勃利 154500；3.北京化工大學機電工程學院，北京 100029)

隨著我國汽車保有量的急劇增加，“停車難”問題日益突出，而立體車庫是解決停車難的有效途徑[1-2]。立體車庫調度策略是影響立體車庫工作效率的關鍵，因此研究立體車庫調度策略對提升車庫服務能力、客戶滿意度及車庫的競爭力具有重要的現實意義[3]。

常見的車庫存取調度優(yōu)化算法有遺傳算法、蟻群算法、粒子群算法等，很多學者基于以上算法對立體車庫調度問題進行了深入研究。Manzini R等[4]提出了適用于智能倉儲系統(tǒng)的多參數動態(tài)優(yōu)化模型，對立體車庫的分區(qū)存儲具有一定的參考意義。Potrco I等[5]對巷道堆垛式立體車庫建立了時間模型，基于時間模型優(yōu)化了車輛出入庫順序。日本學者Motoji等[6]研究了巷道堆垛式立體車庫服務時間與入庫位置的正相關性，給出了多任務狀態(tài)下庫位的最短路徑。Tone L等[7]在多巷道立體車庫的庫位存取任務方面提出了一種啟發(fā)式服務規(guī)則。Chen等[8]使用遺傳算法確定好存取目標車位后，利用Petri網進行路徑規(guī)劃，以節(jié)省存取時間。李劍鋒等[9]采用改進遺傳算法對巷道堆垛式立體車庫存取車時間進行建模優(yōu)化，得到最優(yōu)的存取車耗時。孫軍艷等[10]利用改進的交叉算子遺傳算法，分別對3種不同庫容的升降橫移式與巷道堆垛式立體車庫進行存取車調度優(yōu)化。周雪松等[11]采用融合遺傳算法和蟻群算法的GAAA算法來搜索立體車庫存取車的最短路徑。李建國等[12]以排隊論為基礎，使用分區(qū)調度的策略進行編程仿真，為立體車庫選擇合理的調度策略提供了量化分析的依據和理論參考。陳桂蘭等[13]提出一種改進混合粒子群算法，應用于立體車庫存取策略時間模型，尋找存取車最優(yōu)時間和最優(yōu)排序。

對存取車任務進行車位分配的實質是規(guī)劃升降機與泊車機器人的運動路徑，使存取車總時長最小，因此可以將立體車庫車位分配問題看作旅行商(Traveling Salesman Problem， TSP)問題進行研究。旅行商問題的研究廣泛應用于車間調度、網絡路由、車輛路徑、航跡規(guī)劃等領域。筆者通過分析存取車詳細的流程，建立車庫存取時間模型，利用遺傳算法對車位分配進行優(yōu)化，通過仿真及實驗得出算法對時間的優(yōu)化結果。

1 車庫調度模型的建立

1.1 平面移動式立體車庫結構

平面移動式立體車庫是采用智能泊車機器人與升降機配合，將載車板與汽車搬運至指定車位或者搬運至進出口實現車輛存取的機械式停車設備。該類車庫的特點為，升降機實現車輛垂直方向的運動，泊車機器人實現車輛水平方向的運動。車庫中采用的泊車機器人為全向移動式泊車機器人，因此存取車更為靈活，效率更為高效。

平面移動式立體車庫結構如圖1所示，車庫為M層N排K列，第 1 排的 1 列與 2 列為升降機所在位置，2 排至N-1 排的第 1 列位置為泊車機器人通過的巷道，每排車位之間也是巷道，因此，車庫共設有M×N×(K-1)個車位。車庫的出入口設置在 1 層 1 排升降機所在位置。

圖1 平面移動式立體車庫結構示意圖

1.2 TSP問題描述

TSP問題是已知n個城市兩兩之間的路徑，商人從某個城市出發(fā)遍歷所有的城市且每個城市只能拜訪1次，求其安排的旅行順序使商人總路徑最短。用圖論對其描述即為：假設有1個無向圖G=(V，W)，其中V={V1，V2，…，Vn}是節(jié)點集，W={WViVj}，(Vi，Vj∈V)是節(jié)點Vi與Vj之間對應的代價所組成的代價矩陣。所以TSP問題即為求1個排序：

O={O1，O2，…，On}，On∈V(i=1，2，…，n)使式(1)最小，其中On+1=O1。

(1)

在立體車庫中，起點車位與終止點車位均為車廳位置車位，車位與車位之間執(zhí)行任務的時間為對應節(jié)點的代價，對于立體車庫存車任務分配的車位也只能分配該車位1次，單次取車任務車位固定，在本次存取任務序列中也只能分配1次，因此可以將立體車庫車位分配問題看成典型的TSP問題進行研究。

1.3 車庫存取車調度策略

平面移動式立體車庫運行過程中，存取車是由泊車機器人與升降機配合完成。根據平面移動式立體車庫的存取車運行過程，車位的分配直接決定了存取車時升降機與泊車機器人行駛距離的長短，升降機與泊車機器人的待命位置也同時影響了存取車時泊車機器人與升降機的運動路徑，從而影響完成任務的時間。因此，升降機、泊車機器人的待命位置選擇與車位的分配是立體車庫存取車優(yōu)化的關鍵。

常見的立體車庫存取調度策略有4種，如表1所示。

表1 調度策略分類

綜上所述，存車優(yōu)先和取車優(yōu)先分別適合存車高峰期與取車高峰期，存取車效率比較高，但是泊車機器人與升降機空載路程較長，而交叉存取與原地待命策略能有效避免泊車機器人與升降機產生多余的空載動作，從而達到節(jié)能的目的。而交叉存取本質上是以原地待命為基礎對存取車任務進行兩兩分組，前后搭配進行存取，當存取車任務量相差較大，分組將會陷入被動。因此，選擇原地待命調度策略進行建模。

1.4 原地待命策略的時間模型

為了建立一個合適的符合實際的數學模型，進行了如下假設：

(1)車庫初始為空，升降機和泊車機器人初始位于車庫車廳出入口位置；

(2)存取車的車輛都能通過車輛安全檢測，順利出入庫；

(3)提升系統(tǒng)電機抱閘減速距離忽略不計；

(4)忽略泊車機器人加速時間和減速時間；

(5)泊車機器人和升降機無論是否負載，速度一致；

根據車庫實際實驗情況所建立的模型參數設置如表2所示。

表2 立體車庫參數設置

根據任務分配的優(yōu)化原則，選擇存取車時間最短作為調度優(yōu)化的的目標，建立存取車總時間數學模型。

存取車總時間的計算式為：

T=Te+Tr

(2)

其中：Te為升降機運行時間；Tr為泊車機器人運行時間。升降機運行過程分加速、勻速、減速的過程，則升降機將車輛和泊車機器人從i層運至第m層或從m層運至i層所需時間為：

(3)

但當m=1且i=1時t1?1=te。

泊車機器人在某車位[ni，kj]和指定車位[n，k]之間運動所需時間為：

t[ni，kj]?[n，k]=

(4)

其中，升降機可以看成是車位[1，1]，但當ni=n時

(5)

根據上次任務原地待命的位置和此次存取車任務的不同，可分為4種情況進行討論：

(1)當上次任務為取車任務，則泊車機器人與升降機都在車廳位置待命，此次為存車入庫任務，任務執(zhí)行總時間為：

T=t1?m+t[1，1]?[n，k]

(2)當上次任務為取車任務，此次也為取車任務時，同理可得：

T=2t1?m+t[1，1]?[nz，kz]+t[nz，kz]?[n，k]+t[1，1]?[n，k]

其中：nz、kz分別為放置載車板的目標空車位所在排和列。

(3)當上次任務為存車任務，此次為取車任務時，取車車位與待命車位分為同層與不同層2種情況：

①當取車車位與待命車位同層時，取車出庫任務執(zhí)行總時間為：

T=t1?m+t[nd，kd]?[n，k]+t[1，1]?[n，k]

其中：nd、kd分別為待命車位所在排和列。

②當取車車位與待命車位不同層時，取車出庫工作總時間為：

T=tmd?m+t[1，1]?[nd，kd]+2t[1，1]?[n，k]

其中：md、nd、kd分別為待命車位所在層、排和列。

(4)當上次為存車任務，此次仍為存車任務，存車車位與待命車位分為同層與不同層2種情況：

①當存車車位與待命車位同層時，存車入庫任務執(zhí)行總時間為：

T=2t1?m+t[nd，kd]?[n，k]+2t[1，1]?[n，k]

②當存車車位與待命車位不同層時，存車入庫工作總時間為：

T=tmd?m+2t1?m+t[1，1]?[nd，kd]+3t[1，1]?[n，k]

因此，總存取車時間最短的目標函數為：

(6)

其中：Ti為第i次存取車任務所用時間；R為存取車任務總數。

2 基于遺傳算法車位分配優(yōu)化

2.1 遺傳算法優(yōu)化策略

遺傳算法是一種基于概率的搜索最優(yōu)值算法，是模擬生物染色體遺傳變異進化過程進行迭代，其具有較強的全局搜索能力與自適應性。使用遺傳算法進行尋優(yōu)計算的主要優(yōu)勢在于，遺傳算法使用大量并行計算提高計算速度，并且尋優(yōu)過程并非隨機試探，而是通過概率實現，本身具有良好的靈活性，通過交叉變異操作產生優(yōu)良個體，因此十分適合求解大規(guī)模的復雜優(yōu)化問題。

2.2 車位分配的遺傳算法實現

遺傳算法實現涉及的主要因素包括參數的編碼、初始群體的設定、適應度函數的設計、遺傳操作、算法控制參數的設定和約束條件的處理。

(1)在立體車庫車位分配問題中選取整數編碼方式，首先對車庫中車位進行絕對車位的編號；然后對存取車的汽車數目進行編號；最后在車庫中隨機選取任務數目數值，即為存取車車位號。一條染色體編碼方式即為車位分配的可行解之一，染色體的長度為存取車任務數目，基因就是空車位，基因與染色體位置上的車輛編號對應。如車庫中有7輛車需要進行存取，存取車車位按照從小到大排列為1～7染色體的基因隨機產生，具體的存取任務與存取車位編號如表3所示。

表3 存取車任務示例表

由表3可知，1號存車車輛分配到9號車位，2號取車車位在2號車位，即(9|2|13|5|8|11|17)為一條染色體，也即為一種車位分配方案。

(2)選擇的策略為原地等待策略，選取存取車總時間最短為目標，都是以最小值為目標的優(yōu)化，函數值越小的個體適應度值越大，因此，將函數值的倒數作為適應度值。

存取車時間最短的適應度函數為：

(7)

(3)采用最優(yōu)保存的選擇策略，其適應度最高的個體直接替換子代交叉變異后適應度最差的個體，因此可以確保其種群優(yōu)良性；使用單點交叉方式隨機在父代基因生成一個交叉點；在隨機生成的變異的基因位置，互換其兩側的基因，生成新的子代個體。

3 仿真與實驗分析

以3層7列平面移動式立體車庫為研究對象，其車位分布如圖2所示。

圖2 立體車庫車位分布

存車車輛可以放入路徑最短空車位中，取車車位固定。鑒于忙期分為存車高峰期與取車高峰期以及存取車任務量相等的情況，因此需要對不同情況進行仿真分析，進而求得最佳車位分配策略。經過試驗選擇遺傳算法控制參數，如表4所示。

表4 遺傳算法參數

3.1 存車任務數大于取車任務數的情況

以存車任務為10，取車任務為4為例，具體存取車車位如表5所示。

表5 存車高峰時存取任務

使用遺傳算法對原地待命策略進行優(yōu)化仿真，重復運行10次，以平均值計數，結果如表6所示。

表6 存車高峰仿真優(yōu)化結果

使用遺傳算法對時間進行優(yōu)化后所得的存取順序為(11|12|2|3|1|6|4|10|7|5|13|14|9|8|1)，仿真所得存取順序如圖3所示，圖中橫坐標為樓層，縱坐標為車位所在列。

圖3 存車高峰時優(yōu)化后的存取順序圖

3.2 取車任務數大于存車任務數的情況

以取車任務為10輛，存車任務為4輛為例，存取車車位如表7所示。

表7 取車高峰時存取任務

優(yōu)化后所用時間如表8所示。仿真所得存取順序如圖4所示。

表8 取車高峰仿真優(yōu)化結果

圖4 存車高峰時優(yōu)化后的存取順序圖

3.3 當存車取車任務量相近或相等的情況

以取車任務為7輛，存車任務為7輛為例，存取車車位如表9所示。

表9 存取任務量相等時存取任務

優(yōu)化后所用時間如表10所示。仿真所得存取順序如圖5所示。

表10 存取任務相近情況仿真優(yōu)化結果

圖5 存取車任務量相等時優(yōu)化后的存取順序圖

對比隨機存取與優(yōu)化前后的時間，所得結果如表11所示。

表11 時間優(yōu)化結果對比

通過優(yōu)化前后的時間對比，可以得出存取車總時間相比優(yōu)化前縮短了33%以上，最高為存取任務數相等時，達37.03%。

在仿真實驗的基礎上，對實際立體車庫(見圖6)進行了測試，隨機產生了5個車位的存取車任務，如表12所示。

圖6 平面移動式立體車庫實景圖

表12 存取車試驗任務

根據原地等待策略，分別按照隨機分配車位的存取與經過遺傳算法優(yōu)化后的存取順序執(zhí)行存取任務，對比完成 5 次存取任務的總時間，結果如表13所示。

表13 實驗存取總耗時對比

實驗結果表明，僅對5次存取任務進行優(yōu)化總耗時就可以節(jié)省166.44 s，效率提高15.68%。實驗結果驗證了該遺傳算法能有效提升車庫存取效率。

4 結論

(1)根據平面移動式立體車庫調度過程中車位分配特點，將TSP應用問題推廣到平面移動式立體車庫存取車任務調度優(yōu)化中，在已有的立體車庫結構與性能參數基礎上，選擇原地待命策略對立體車庫存取車時間進行數學建模。

(2)使用遺傳算法對存取車車位分配進行優(yōu)化，實驗結果表明，該遺傳算法減少了平面移動式立體車庫執(zhí)行任務的總耗時，存取效率有了明顯的提高。

(3)驗證了運用遺傳算法的平面移動式立體車庫調度系統(tǒng)對提升車庫運行效率的有效性與可行性，從而為提高車庫運營效益與客戶滿意度方面提供參考依據。