基于遺傳算法的平面移動式立體車庫存取調(diào)度優(yōu)化

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

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

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

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

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

1 車庫調(diào)度模型的建立

1.1 平面移動式立體車庫結(jié)構(gòu)

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

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

圖1 平面移動式立體車庫結(jié)構(gòu)示意圖

1.2 TSP問題描述

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

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

(1)

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

1.3 車庫存取車調(diào)度策略

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

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

表1 調(diào)度策略分類

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

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

為了建立一個合適的符合實際的數(shù)學(xué)模型，進行了如下假設(shè)：

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

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

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

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

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

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

表2 立體車庫參數(shù)設(shè)置

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

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

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)

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

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

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

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

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

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

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

①當取車車位與待命車位同層時，取車出庫任務(wù)執(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)當上次為存車任務(wù)，此次仍為存車任務(wù)，存車車位與待命車位分為同層與不同層2種情況：

①當存車車位與待命車位同層時，存車入庫任務(wù)執(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]

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

(6)

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

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

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

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

2.2 車位分配的遺傳算法實現(xiàn)

遺傳算法實現(xiàn)涉及的主要因素包括參數(shù)的編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計、遺傳操作、算法控制參數(shù)的設(shè)定和約束條件的處理。

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

表3 存取車任務(wù)示例表

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

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

存取車時間最短的適應(yīng)度函數(shù)為：

(7)

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

3 仿真與實驗分析

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

圖2 立體車庫車位分布

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

表4 遺傳算法參數(shù)

3.1 存車任務(wù)數(shù)大于取車任務(wù)數(shù)的情況

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

表5 存車高峰時存取任務(wù)

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

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

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

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

3.2 取車任務(wù)數(shù)大于存車任務(wù)數(shù)的情況

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

表7 取車高峰時存取任務(wù)

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

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

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

3.3 當存車取車任務(wù)量相近或相等的情況

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

表9 存取任務(wù)量相等時存取任務(wù)

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

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

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

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

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

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

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

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

表12 存取車試驗任務(wù)

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

表13 實驗存取總耗時對比

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

4 結(jié)論

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

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

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