陳 亞，楊佳衡，沈偉東，鐘浩翔，朱亞東，鄧?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é)果。

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

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

平面移動(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)示意圖

1.2 TSP問題描述

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)行研究。

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

平面移動(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)行建模。

1.4 原地待命策略的時(shí)間模型

為了建立一個(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ù)。

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

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

遺傳算法是一種基于概率的搜索最優(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)化問題。

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

遺傳算法實(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 仿真與實(shí)驗(yàn)分析

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

圖2 立體車庫車位分布

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

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

3.1 存車任務(wù)數(shù)大于取車任務(wù)數(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)化后的存取順序圖

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

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

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

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

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

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

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

以取車任務(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)證了該遺傳算法能有效提升車庫存取效率。

4 結(jié)論

(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ù)。