陳 亞,楊佳衡,沈偉東,鐘浩翔,朱亞東,鄧?yán)杳?/p>
(1.北京石油化工學(xué)院機(jī)械工程學(xué)院,北京 102617; 2.中國(guó)聯(lián)合網(wǎng)絡(luò)通信有限公司勃利縣分公司, 黑龍江 勃利 154500;3.北京化工大學(xué)機(jī)電工程學(xué)院,北京 100029)
隨著我國(guó)汽車保有量的急劇增加,“停車難”問題日益突出,而立體車庫是解決停車難的有效途徑[1-2]。立體車庫調(diào)度策略是影響立體車庫工作效率的關(guān)鍵,因此研究立體車庫調(diào)度策略對(duì)提升車庫服務(wù)能力、客戶滿意度及車庫的競(jìng)爭(zhēng)力具有重要的現(xiàn)實(shí)意義[3]。
常見的車庫存取調(diào)度優(yōu)化算法有遺傳算法、蟻群算法、粒子群算法等,很多學(xué)者基于以上算法對(duì)立體車庫調(diào)度問題進(jìn)行了深入研究。Manzini R等[4]提出了適用于智能倉(cāng)儲(chǔ)系統(tǒng)的多參數(shù)動(dòng)態(tài)優(yōu)化模型,對(duì)立體車庫的分區(qū)存儲(chǔ)具有一定的參考意義。Potrco I等[5]對(duì)巷道堆垛式立體車庫建立了時(shí)間模型,基于時(shí)間模型優(yōu)化了車輛出入庫順序。日本學(xué)者M(jìn)otoji等[6]研究了巷道堆垛式立體車庫服務(wù)時(shí)間與入庫位置的正相關(guān)性,給出了多任務(wù)狀態(tài)下庫位的最短路徑。Tone L等[7]在多巷道立體車庫的庫位存取任務(wù)方面提出了一種啟發(fā)式服務(wù)規(guī)則。Chen等[8]使用遺傳算法確定好存取目標(biāo)車位后,利用Petri網(wǎng)進(jìn)行路徑規(guī)劃,以節(jié)省存取時(shí)間。李劍鋒等[9]采用改進(jìn)遺傳算法對(duì)巷道堆垛式立體車庫存取車時(shí)間進(jìn)行建模優(yōu)化,得到最優(yōu)的存取車耗時(shí)。孫軍艷等[10]利用改進(jìn)的交叉算子遺傳算法,分別對(duì)3種不同庫容的升降橫移式與巷道堆垛式立體車庫進(jìn)行存取車調(diào)度優(yōu)化。周雪松等[11]采用融合遺傳算法和蟻群算法的GAAA算法來搜索立體車庫存取車的最短路徑。李建國(guó)等[12]以排隊(duì)論為基礎(chǔ),使用分區(qū)調(diào)度的策略進(jìn)行編程仿真,為立體車庫選擇合理的調(diào)度策略提供了量化分析的依據(jù)和理論參考。陳桂蘭等[13]提出一種改進(jìn)混合粒子群算法,應(yīng)用于立體車庫存取策略時(shí)間模型,尋找存取車最優(yōu)時(shí)間和最優(yōu)排序。
對(duì)存取車任務(wù)進(jìn)行車位分配的實(shí)質(zhì)是規(guī)劃升降機(jī)與泊車機(jī)器人的運(yùn)動(dòng)路徑,使存取車總時(shí)長(zhǎng)最小,因此可以將立體車庫車位分配問題看作旅行商(Traveling Salesman Problem, TSP)問題進(jìn)行研究。旅行商問題的研究廣泛應(yīng)用于車間調(diào)度、網(wǎng)絡(luò)路由、車輛路徑、航跡規(guī)劃等領(lǐng)域。筆者通過分析存取車詳細(xì)的流程,建立車庫存取時(shí)間模型,利用遺傳算法對(duì)車位分配進(jìn)行優(yōu)化,通過仿真及實(shí)驗(yàn)得出算法對(duì)時(shí)間的優(yōu)化結(jié)果。
平面移動(dòng)式立體車庫是采用智能泊車機(jī)器人與升降機(jī)配合,將載車板與汽車搬運(yùn)至指定車位或者搬運(yùn)至進(jìn)出口實(shí)現(xiàn)車輛存取的機(jī)械式停車設(shè)備。該類車庫的特點(diǎn)為,升降機(jī)實(shí)現(xiàn)車輛垂直方向的運(yùn)動(dòng),泊車機(jī)器人實(shí)現(xiàn)車輛水平方向的運(yùn)動(dòng)。車庫中采用的泊車機(jī)器人為全向移動(dòng)式泊車機(jī)器人,因此存取車更為靈活,效率更為高效。
平面移動(dòng)式立體車庫結(jié)構(gòu)如圖1所示,車庫為M層N排K列,第 1 排的 1 列與 2 列為升降機(jī)所在位置,2 排至N-1 排的第 1 列位置為泊車機(jī)器人通過的巷道,每排車位之間也是巷道,因此,車庫共設(shè)有M×N×(K-1)個(gè)車位。車庫的出入口設(shè)置在 1 層 1 排升降機(jī)所在位置。
圖1 平面移動(dòng)式立體車庫結(jié)構(gòu)示意圖
TSP問題是已知n個(gè)城市兩兩之間的路徑,商人從某個(gè)城市出發(fā)遍歷所有的城市且每個(gè)城市只能拜訪1次,求其安排的旅行順序使商人總路徑最短。用圖論對(duì)其描述即為:假設(shè)有1個(gè)無向圖G=(V,W),其中V={V1,V2,…,Vn}是節(jié)點(diǎn)集,W={WViVj},(Vi,Vj∈V)是節(jié)點(diǎn)Vi與Vj之間對(duì)應(yīng)的代價(jià)所組成的代價(jià)矩陣。所以TSP問題即為求1個(gè)排序:
O={O1,O2,…,On},On∈V(i=1,2,…,n)使式(1)最小,其中On+1=O1。
(1)
在立體車庫中,起點(diǎn)車位與終止點(diǎn)車位均為車廳位置車位,車位與車位之間執(zhí)行任務(wù)的時(shí)間為對(duì)應(yīng)節(jié)點(diǎn)的代價(jià),對(duì)于立體車庫存車任務(wù)分配的車位也只能分配該車位1次,單次取車任務(wù)車位固定,在本次存取任務(wù)序列中也只能分配1次,因此可以將立體車庫車位分配問題看成典型的TSP問題進(jìn)行研究。
平面移動(dòng)式立體車庫運(yùn)行過程中,存取車是由泊車機(jī)器人與升降機(jī)配合完成。根據(jù)平面移動(dòng)式立體車庫的存取車運(yùn)行過程,車位的分配直接決定了存取車時(shí)升降機(jī)與泊車機(jī)器人行駛距離的長(zhǎng)短,升降機(jī)與泊車機(jī)器人的待命位置也同時(shí)影響了存取車時(shí)泊車機(jī)器人與升降機(jī)的運(yùn)動(dòng)路徑,從而影響完成任務(wù)的時(shí)間。因此,升降機(jī)、泊車機(jī)器人的待命位置選擇與車位的分配是立體車庫存取車優(yōu)化的關(guān)鍵。
常見的立體車庫存取調(diào)度策略有4種,如表1所示。
表1 調(diào)度策略分類
綜上所述,存車優(yōu)先和取車優(yōu)先分別適合存車高峰期與取車高峰期,存取車效率比較高,但是泊車機(jī)器人與升降機(jī)空載路程較長(zhǎng),而交叉存取與原地待命策略能有效避免泊車機(jī)器人與升降機(jī)產(chǎn)生多余的空載動(dòng)作,從而達(dá)到節(jié)能的目的。而交叉存取本質(zhì)上是以原地待命為基礎(chǔ)對(duì)存取車任務(wù)進(jìn)行兩兩分組,前后搭配進(jìn)行存取,當(dāng)存取車任務(wù)量相差較大,分組將會(huì)陷入被動(dòng)。因此,選擇原地待命調(diào)度策略進(jìn)行建模。
為了建立一個(gè)合適的符合實(shí)際的數(shù)學(xué)模型,進(jìn)行了如下假設(shè):
(1)車庫初始為空,升降機(jī)和泊車機(jī)器人初始位于車庫車廳出入口位置;
(2)存取車的車輛都能通過車輛安全檢測(cè),順利出入庫;
(3)提升系統(tǒng)電機(jī)抱閘減速距離忽略不計(jì);
(4)忽略泊車機(jī)器人加速時(shí)間和減速時(shí)間;
(5)泊車機(jī)器人和升降機(jī)無論是否負(fù)載,速度一致;
根據(jù)車庫實(shí)際實(shí)驗(yàn)情況所建立的模型參數(shù)設(shè)置如表2所示。
表2 立體車庫參數(shù)設(shè)置
根據(jù)任務(wù)分配的優(yōu)化原則,選擇存取車時(shí)間最短作為調(diào)度優(yōu)化的的目標(biāo),建立存取車總時(shí)間數(shù)學(xué)模型。
存取車總時(shí)間的計(jì)算式為:
T=Te+Tr
(2)
其中:Te為升降機(jī)運(yùn)行時(shí)間;Tr為泊車機(jī)器人運(yùn)行時(shí)間。升降機(jī)運(yùn)行過程分加速、勻速、減速的過程,則升降機(jī)將車輛和泊車機(jī)器人從i層運(yùn)至第m層或從m層運(yùn)至i層所需時(shí)間為:
(3)
但當(dāng)m=1且i=1時(shí)t1?1=te。
泊車機(jī)器人在某車位[ni,kj]和指定車位[n,k]之間運(yùn)動(dòng)所需時(shí)間為:
t[ni,kj]?[n,k]=
(4)
其中,升降機(jī)可以看成是車位[1,1],但當(dāng)ni=n時(shí)
(5)
根據(jù)上次任務(wù)原地待命的位置和此次存取車任務(wù)的不同,可分為4種情況進(jìn)行討論:
(1)當(dāng)上次任務(wù)為取車任務(wù),則泊車機(jī)器人與升降機(jī)都在車廳位置待命,此次為存車入庫任務(wù),任務(wù)執(zhí)行總時(shí)間為:
T=t1?m+t[1,1]?[n,k]
(2)當(dāng)上次任務(wù)為取車任務(wù),此次也為取車任務(wù)時(shí),同理可得:
T=2t1?m+t[1,1]?[nz,kz]+t[nz,kz]?[n,k]+t[1,1]?[n,k]
其中:nz、kz分別為放置載車板的目標(biāo)空車位所在排和列。
(3)當(dāng)上次任務(wù)為存車任務(wù),此次為取車任務(wù)時(shí),取車車位與待命車位分為同層與不同層2種情況:
①當(dāng)取車車位與待命車位同層時(shí),取車出庫任務(wù)執(zhí)行總時(shí)間為:
T=t1?m+t[nd,kd]?[n,k]+t[1,1]?[n,k]
其中:nd、kd分別為待命車位所在排和列。
②當(dāng)取車車位與待命車位不同層時(shí),取車出庫工作總時(shí)間為:
T=tmd?m+t[1,1]?[nd,kd]+2t[1,1]?[n,k]
其中:md、nd、kd分別為待命車位所在層、排和列。
(4)當(dāng)上次為存車任務(wù),此次仍為存車任務(wù),存車車位與待命車位分為同層與不同層2種情況:
①當(dāng)存車車位與待命車位同層時(shí),存車入庫任務(wù)執(zhí)行總時(shí)間為:
T=2t1?m+t[nd,kd]?[n,k]+2t[1,1]?[n,k]
②當(dāng)存車車位與待命車位不同層時(shí),存車入庫工作總時(shí)間為:
T=tmd?m+2t1?m+t[1,1]?[nd,kd]+3t[1,1]?[n,k]
因此,總存取車時(shí)間最短的目標(biāo)函數(shù)為:
(6)
其中:Ti為第i次存取車任務(wù)所用時(shí)間;R為存取車任務(wù)總數(shù)。
遺傳算法是一種基于概率的搜索最優(yōu)值算法,是模擬生物染色體遺傳變異進(jìn)化過程進(jìn)行迭代,其具有較強(qiáng)的全局搜索能力與自適應(yīng)性。使用遺傳算法進(jìn)行尋優(yōu)計(jì)算的主要優(yōu)勢(shì)在于,遺傳算法使用大量并行計(jì)算提高計(jì)算速度,并且尋優(yōu)過程并非隨機(jī)試探,而是通過概率實(shí)現(xiàn),本身具有良好的靈活性,通過交叉變異操作產(chǎn)生優(yōu)良個(gè)體,因此十分適合求解大規(guī)模的復(fù)雜優(yōu)化問題。
遺傳算法實(shí)現(xiàn)涉及的主要因素包括參數(shù)的編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作、算法控制參數(shù)的設(shè)定和約束條件的處理。
(1)在立體車庫車位分配問題中選取整數(shù)編碼方式,首先對(duì)車庫中車位進(jìn)行絕對(duì)車位的編號(hào);然后對(duì)存取車的汽車數(shù)目進(jìn)行編號(hào);最后在車庫中隨機(jī)選取任務(wù)數(shù)目數(shù)值,即為存取車車位號(hào)。一條染色體編碼方式即為車位分配的可行解之一,染色體的長(zhǎng)度為存取車任務(wù)數(shù)目,基因就是空車位,基因與染色體位置上的車輛編號(hào)對(duì)應(yīng)。如車庫中有7輛車需要進(jìn)行存取,存取車車位按照從小到大排列為1~7染色體的基因隨機(jī)產(chǎn)生,具體的存取任務(wù)與存取車位編號(hào)如表3所示。
表3 存取車任務(wù)示例表
由表3可知,1號(hào)存車車輛分配到9號(hào)車位,2號(hào)取車車位在2號(hào)車位,即(9|2|13|5|8|11|17)為一條染色體,也即為一種車位分配方案。
(2)選擇的策略為原地等待策略,選取存取車總時(shí)間最短為目標(biāo),都是以最小值為目標(biāo)的優(yōu)化,函數(shù)值越小的個(gè)體適應(yīng)度值越大,因此,將函數(shù)值的倒數(shù)作為適應(yīng)度值。
存取車時(shí)間最短的適應(yīng)度函數(shù)為:
(7)
(3)采用最優(yōu)保存的選擇策略,其適應(yīng)度最高的個(gè)體直接替換子代交叉變異后適應(yīng)度最差的個(gè)體,因此可以確保其種群優(yōu)良性;使用單點(diǎn)交叉方式隨機(jī)在父代基因生成一個(gè)交叉點(diǎn);在隨機(jī)生成的變異的基因位置,互換其兩側(cè)的基因,生成新的子代個(gè)體。
以3層7列平面移動(dòng)式立體車庫為研究對(duì)象,其車位分布如圖2所示。
圖2 立體車庫車位分布
存車車輛可以放入路徑最短空車位中,取車車位固定。鑒于忙期分為存車高峰期與取車高峰期以及存取車任務(wù)量相等的情況,因此需要對(duì)不同情況進(jìn)行仿真分析,進(jìn)而求得最佳車位分配策略。經(jīng)過試驗(yàn)選擇遺傳算法控制參數(shù),如表4所示。
表4 遺傳算法參數(shù)
以存車任務(wù)為10,取車任務(wù)為4為例,具體存取車車位如表5所示。
表5 存車高峰時(shí)存取任務(wù)
使用遺傳算法對(duì)原地待命策略進(jìn)行優(yōu)化仿真,重復(fù)運(yùn)行10次,以平均值計(jì)數(shù),結(jié)果如表6所示。
表6 存車高峰仿真優(yōu)化結(jié)果
使用遺傳算法對(duì)時(shí)間進(jìn)行優(yōu)化后所得的存取順序?yàn)?11|12|2|3|1|6|4|10|7|5|13|14|9|8|1),仿真所得存取順序如圖3所示,圖中橫坐標(biāo)為樓層,縱坐標(biāo)為車位所在列。
圖3 存車高峰時(shí)優(yōu)化后的存取順序圖
以取車任務(wù)為10輛,存車任務(wù)為4輛為例,存取車車位如表7所示。
表7 取車高峰時(shí)存取任務(wù)
優(yōu)化后所用時(shí)間如表8所示。仿真所得存取順序如圖4所示。
表8 取車高峰仿真優(yōu)化結(jié)果
圖4 存車高峰時(shí)優(yōu)化后的存取順序圖
以取車任務(wù)為7輛,存車任務(wù)為7輛為例,存取車車位如表9所示。
表9 存取任務(wù)量相等時(shí)存取任務(wù)
優(yōu)化后所用時(shí)間如表10所示。仿真所得存取順序如圖5所示。
表10 存取任務(wù)相近情況仿真優(yōu)化結(jié)果
圖5 存取車任務(wù)量相等時(shí)優(yōu)化后的存取順序圖
對(duì)比隨機(jī)存取與優(yōu)化前后的時(shí)間,所得結(jié)果如表11所示。
表11 時(shí)間優(yōu)化結(jié)果對(duì)比
通過優(yōu)化前后的時(shí)間對(duì)比,可以得出存取車總時(shí)間相比優(yōu)化前縮短了33%以上,最高為存取任務(wù)數(shù)相等時(shí),達(dá)37.03%。
在仿真實(shí)驗(yàn)的基礎(chǔ)上,對(duì)實(shí)際立體車庫(見圖6)進(jìn)行了測(cè)試,隨機(jī)產(chǎn)生了5個(gè)車位的存取車任務(wù),如表12所示。
圖6 平面移動(dòng)式立體車庫實(shí)景圖
表12 存取車試驗(yàn)任務(wù)
根據(jù)原地等待策略,分別按照隨機(jī)分配車位的存取與經(jīng)過遺傳算法優(yōu)化后的存取順序執(zhí)行存取任務(wù),對(duì)比完成 5 次存取任務(wù)的總時(shí)間,結(jié)果如表13所示。
表13 實(shí)驗(yàn)存取總耗時(shí)對(duì)比
實(shí)驗(yàn)結(jié)果表明,僅對(duì)5次存取任務(wù)進(jìn)行優(yōu)化總耗時(shí)就可以節(jié)省166.44 s,效率提高15.68%。實(shí)驗(yàn)結(jié)果驗(yàn)證了該遺傳算法能有效提升車庫存取效率。
(1)根據(jù)平面移動(dòng)式立體車庫調(diào)度過程中車位分配特點(diǎn),將TSP應(yīng)用問題推廣到平面移動(dòng)式立體車庫存取車任務(wù)調(diào)度優(yōu)化中,在已有的立體車庫結(jié)構(gòu)與性能參數(shù)基礎(chǔ)上,選擇原地待命策略對(duì)立體車庫存取車時(shí)間進(jìn)行數(shù)學(xué)建模。
(2)使用遺傳算法對(duì)存取車車位分配進(jìn)行優(yōu)化,實(shí)驗(yàn)結(jié)果表明,該遺傳算法減少了平面移動(dòng)式立體車庫執(zhí)行任務(wù)的總耗時(shí),存取效率有了明顯的提高。
(3)驗(yàn)證了運(yùn)用遺傳算法的平面移動(dòng)式立體車庫調(diào)度系統(tǒng)對(duì)提升車庫運(yùn)行效率的有效性與可行性,從而為提高車庫運(yùn)營(yíng)效益與客戶滿意度方面提供參考依據(jù)。