李燕剛 ，鄧建新 ，賀秋瑤 ，馮巖捷 ，王偉杰

自動化立體倉庫是物流和生產(chǎn)中的基礎裝備，具有存儲量大、占地空間小、自動化程度高等優(yōu)點，通常由高層貨架組成，它的應用在一定程度上提高了倉庫（或倉儲環(huán)節(jié)）的作業(yè)效率和水平。自動化立體倉庫的貨架有固定式和旋轉(zhuǎn)式兩種，并以前者居多。但無論哪種貨架，為了從立體倉庫的貨架中取出貨物，必須進行揀選。尤其是對固定式貨架，揀選作業(yè)更是對應自動化立體倉庫的調(diào)度的核心。固定式貨架揀選必須設定揀選路徑。因此揀選路徑的優(yōu)化不但影響貨物存取作業(yè)效率，也決定了揀選環(huán)節(jié)堆垛機的能耗。為此人們越來越重視對揀選路徑調(diào)度的優(yōu)化。尤其是隨著生產(chǎn)往即時化方向發(fā)展，及基于時間的競爭趨勢下，無論是生產(chǎn)和服務的節(jié)拍都不斷提高，這對自動化立體倉庫的揀貨速度提出了更高要求。比如電子商務行業(yè)的揀貨速度決定了訂單、配送的履約服務水平，已經(jīng)成為重要的競爭手段，面向生產(chǎn)流水線的立體倉庫揀貨決定了對生產(chǎn)線節(jié)拍的支持水平。

立體倉庫貨架揀選貨物的路徑優(yōu)化本質(zhì)上是路徑規(guī)劃問題，所以對其揀選過程的優(yōu)化也通常將其轉(zhuǎn)化為路徑優(yōu)化問題來解決，如將其視為旅行商問題來解決[1]，Sarker等提出了一種基于控制和調(diào)度系統(tǒng)立體倉庫優(yōu)化揀選的混合智能方法[2]。以這種思路，國內(nèi)外圍繞固定式貨架立體倉庫的揀選問題進行了大量研究，提出和應用了一系列優(yōu)化方法和算法。包括有分支定界法[2]、遺傳算法[3]、粒子群算法[4]、禁忌搜索算法、模擬退火算法。由于各種算法求解復雜度和耗費時間有差異，為了提高工程實用性，圍繞求解效率和優(yōu)化程度，不同學者又提出了新優(yōu)化思路或進行了一系列改進和算法優(yōu)化。如方彥軍等采用最大最小蟻群算法改進基本蟻群算法過早陷入局部最優(yōu)的缺陷，并用于自動化立體倉庫揀選作業(yè)優(yōu)化問題取得較好效果[5]；田國會等采用了一種結(jié)合HoPfield網(wǎng)絡模型的遺傳算法，該算法利用了遺傳算法的全局尋優(yōu)特性和Hopfield/Tank神經(jīng)網(wǎng)絡的局部快速搜索能力，獲得了全局優(yōu)化的揀選作業(yè)路徑[3]。靳萌[6]等提出了一種結(jié)合動態(tài)規(guī)劃方法的啟發(fā)式搜索算法生成揀選路徑；該方法調(diào)和了動態(tài)規(guī)劃空間開銷大與啟發(fā)式搜索時間開銷大的矛盾，有效解決了多穿越巷道布局下的揀選路徑規(guī)劃問題，算法有效節(jié)約了計算機空間資源。

這些算法各有千秋，但隨著改進，越來越復雜，需要復雜的編程實現(xiàn)才能應用，不適合普通工人和簡單的實驗仿真、教學中應用。

TransCAD是美國Caliper公司設計研發(fā)的一款基于GIS（Geographic Information System）的交通規(guī)劃軟件，目前它得到許多國家和地區(qū)廣泛的應用。其簡單易學，具有強大的繪圖功能和編輯功能[7]。TransCAD軟件具有強大的規(guī)劃功能，內(nèi)置路徑優(yōu)化算法，能實現(xiàn)路徑規(guī)劃優(yōu)化，可用于尋找交通路徑、道路的需求量的預測和分析，物流中心和倉庫的選址規(guī)劃等。近年也有少數(shù)幾個研究將其應用到了立體倉庫貨架揀選作業(yè)路徑優(yōu)化問題中[8]，但對立體倉庫簡化過多，與實際立體倉庫模型差異較大；且限于模擬，而不是直接利用其進行路徑規(guī)劃。

鑒于此，本文研究了通過TransCAD的路徑優(yōu)化功能對固定式貨架自動化立體倉庫（為表述簡單，簡稱為“立體倉庫”）的揀貨路徑優(yōu)化的應用方法。通過將立體倉庫的貨位和路徑信息直接轉(zhuǎn)化為TransCAD地圖，然后利用TransCAD路徑規(guī)劃功能，實現(xiàn)了自動化立體倉庫的揀貨路徑的優(yōu)化。提高了立體倉庫的揀貨路徑規(guī)劃的和揀選效率，減少了能耗，節(jié)約成本。從而可以提高對訂單的響應速度和企業(yè)的競爭力。

1 立體倉庫的揀選路徑問題

固定式貨架自動化立體倉庫主要由固定式貨架（構(gòu)成貨位）、巷道堆垛機、輸送系統(tǒng)、出入庫工作臺、控制系統(tǒng)（包含中央控制計算機）等構(gòu)成。揀選作業(yè)時，倉庫管理員根據(jù)貨物的出入庫需求，將出入庫貨物信息輸入到中央計算機中，中央計算機將揀選的作業(yè)任務的任務單傳送給控制系統(tǒng)，控制系統(tǒng)再傳輸給執(zhí)行系統(tǒng)，巷道堆垛機根據(jù)執(zhí)行系統(tǒng)的相關(guān)執(zhí)行指令到貨架上的相應的貨位點進行貨物的存取作業(yè)（具體存取也可由人完成），在存取作業(yè)完成后，并回到出入庫工作臺。通常每次要進行一系列貨位揀選任務，因此涉及路徑問題。路徑不但決定了路徑的長短，也決定了所耗費的時間、能耗。因此，對揀選路徑優(yōu)化也對應的有路徑最短和時間最短[4]兩類目標。揀選的路徑距離可通過式（1）來表示，對應的行駛時間可通過式（2）來表示。

式中D表示總路線距離，T表示揀選時堆垛機行駛總時間，n為揀選需要經(jīng)過的所有經(jīng)過的包含工作在在內(nèi)的貨位點的數(shù)量（由單次的揀選任務單決定），ki表示揀選需要經(jīng)過第i個貨位點，其中第1個點為工作臺。d（ki，ki+1）表示經(jīng)過貨位點 ki，ki+1堆垛機行駛的距離，t（ki，ki+1）為對應的行駛時間，ty（ki，ki+1），tz（ki，ki+1）分別表示堆垛機在兩貨位點間水平和垂直方向的行駛時間，vy、vz為堆垛機的水平和垂直方向的勻速行駛速度，L、H分別代表貨架的單位寬度、高度，yki、zki為第 i個貨位點的 y、z坐標。

2 TransCAD規(guī)劃立體倉庫揀選路徑的方法

TransCAD有強大的路徑規(guī)劃功能，可以在路線網(wǎng)絡中得到任意起點到終點的最短路徑或最優(yōu)路徑，但都基于其內(nèi)置地圖和生成的網(wǎng)絡來實現(xiàn)的。因此，如果要應用TransCAD來進行立體倉庫的揀選路徑優(yōu)化，涉及兩個層次性問題：（1）自動化立體倉庫在TransCAD中的表達，即必須將立體倉庫的定位信息轉(zhuǎn)化表示為TransCAD的地圖信息；（2）揀選優(yōu)化問題的表達。將立體倉庫的揀選路徑問題轉(zhuǎn)化TransCAD的路徑規(guī)劃問題。顯然，第（1）個問題的解決是第（2）問題解決的基礎。以下只闡述要點，涉及的TransCAD的一些通用操作，如增加屬性字段等，可參考文獻[7]。

2.1 自動化立體倉庫在TransCAD中的表達

2.1.1 貨位點的表達

立體倉庫由一系列貨架構(gòu)成的貨位（或貨格）組成，根據(jù)其構(gòu)成原理，對揀選的調(diào)度尋址，每個貨位點位置信息實際上包含貨位所處的巷道、層和列信息，則可用（x，y，z）三維坐標來表示，對應代表貨位在第x巷道第y列第z層的位置，但TransCAD的規(guī)劃使用的位置坐標是二維的。為此，可如下轉(zhuǎn)換：以x坐標將立體倉庫分層，稱為貨位點層，層號為x坐標，這樣立體倉庫就可以直接轉(zhuǎn)化為多個層次的二維庫位組合，然后將立體倉庫的貨位點位置的（y，z）坐直接轉(zhuǎn)為TransCAD的坐標（即實現(xiàn)一一對應）。為了實現(xiàn)以上轉(zhuǎn)化，需要在TransCAD中新的二維立體倉庫貨位點增加屬性來區(qū)分其本身的層次，以表示原先的x坐標。這樣就可以的將自動化立體倉庫的三維坐標轉(zhuǎn)換為TransCAD中的二維坐標，完成了立體倉庫在TransCAD的地圖信息表達，為后期路線規(guī)劃奠定基礎。主要操作步驟如下：

（1）建立立體倉庫貨位點的平面示意圖?？墒褂贸Ｓ玫腃AD繪圖軟件來完成。繪制時，按前面的立體貨位按巷道分割的思路，分巷道繪制二維平面圖，保持其x、y、z坐標相對位置、間距與立體倉庫中的一致，如（1，1，1）與（1，1，2）為 z方向相鄰的貨位，在二維地圖上也應相鄰。圖1為在AutoCAD中繪制的兩條巷道的自動化立體倉庫貨架的平面表達圖形，粗實線標出的為巷道分界線。完成后，將其保存為dxf格式。

圖1 貨架貨格平面示意圖

（2）導入到TransCAD中。將以上的dxf格式文件導入到TransCAD中，并檢查網(wǎng)絡的連通性（使用Check Line Layer Connectivity命令），修改錯誤未連通的節(jié)點，必須修改到保證圖中的任意相鄰點的網(wǎng)絡連通，因為TransCAD將根據(jù)網(wǎng)絡的連通性來確定路徑，不保證任意相鄰點連通，則表達的路徑將與實際的立體倉庫揀選有區(qū)別，因為實際的立體倉庫任意兩個相鄰貨位是相通的。

（3）為 TransCAD中的貨位添加坐標。在TransCAD中激活建立的貨位點層，修改點的屬性（Modify Table），增加記錄 x、y、z坐標屬性的字段，為理解簡單，可命名為巷道號、y坐標，z坐標。并用原先立體倉庫的坐標對應填充。填充后的結(jié)果如圖2示意。圖中當x為負時，表示在x巷道左側(cè)貨架；當x為正表示在x巷道的右側(cè)貨架。

圖2 TransCAD中的貨位點坐標示意

經(jīng)過以上三個步驟就把立體倉庫的貨位信息在TransCAD中轉(zhuǎn)換為了地圖信息，簡稱立體倉庫地圖。立體倉庫地圖的每一個點代表原立體倉庫中的一個貨位，但相鄰兩貨位之間的距離都被抽象為了1，實際信息在2.1.2中表達。

2.1.2 揀選屬性特征的表達

在確定自動化立體倉庫的貨位點之后，還要根據(jù)實際，表達巷道堆垛機的出發(fā)點以及巷道堆垛機的揀選運行速度以及在貨位之間的運行時間。一般地，在自動化立體倉庫中都選擇同一類型的巷道堆垛機，其在貨架間的巷道中行走時，設其先進行水平方向的移動，然后再進行垂直方向的運動。為簡化，忽視負載對堆垛機運行速度的影響。表達方法如下：

（1）根據(jù)立體倉庫的層數(shù)和前面的轉(zhuǎn)換原理，得到堆垛機的出發(fā)點坐標，如，設第一巷道堆垛機出發(fā)坐標為（0，1），第二巷道堆垛機的出發(fā)坐標為（0，11），如只有1個堆垛機則出發(fā)點相同，優(yōu)化時每次額外增加巷道的運行時間和距離即可。根據(jù)坐標，在得到的TransCAD立體倉庫地圖中對應點，并將其單獨保存為地理文件。即通過點擊TransCAD中的TOOLS-Export輸出，具體可參見TransCAD的使用說明書。

（2）將以上保存的堆垛機的地理信息以新圖層的方式添加到原立體倉庫地圖文件中，可添加不同樣式（style）標記來區(qū)分。如圖3所示為添加堆垛機位置的立體倉庫地圖示意圖。

圖3 添加堆垛機位置的立體倉庫地圖

（3）添加堆垛機運行速度等屬性。激活立體倉庫地圖線層，修改其屬性，增加數(shù)據(jù)字段分別用于存儲堆垛機水平和垂直方向兩貨位間的距離（由于任何兩貨位間都是連通的，該距離實際對應單位貨格的距離長與高，如果H與L都不是1，即與2.1.1中貨位坐標抽象的距離有差異，則需要添加字段，并通過H、L、現(xiàn)有“Length”字段間的公式轉(zhuǎn)換存儲為實際距離）、運行速度、單位貨格的行駛時間，并根據(jù)實際堆垛機的運行速度轉(zhuǎn)化后填充數(shù)據(jù)，對應的單位貨格的行駛時間為L/vy或H/vz.如圖4為添加的實例片段，設定H=L=1 m，已知巷道堆垛機在水平方向上的速度為vy=2 m/s，垂直方向上的速度為vz=1 m/s，則水平方向的單位時間距離0.5 s，垂直方向的單位時間距離為1 s，圖中添加“speed”和“time dis－tance”兩個新字段分別存儲水平方向的速度和單位貨格的行駛時間，為后面優(yōu)化做好了參數(shù)定義準備。

圖4 添加堆垛機運行時間屬性片段

2.1.3 揀選優(yōu)化問題的表達

在TransCAD完整表達自動化立體倉庫之后，就具備了可利用TransCAD中技術(shù)特征和功能進行路徑求解的條件，但仍需要確定揀選路徑規(guī)劃的路線網(wǎng)絡、具體的揀選任務貨物點和優(yōu)化目標等。

將自動化立體倉庫貨架的揀選近似看成是旅行商問題。即堆垛機從出入庫臺出發(fā)，歷經(jīng)所有需要經(jīng)過的n個貨位點揀選后，最后返回到出入庫臺的過程，為此尋找總揀選作業(yè)距離最短或總作業(yè)時間最短的路徑。TransCAD提供了兩種方法來解決最短路徑問題：使用”shortest path”工具箱和創(chuàng)建最短路徑矩陣，本處使用前者提高操作和實驗交互性。該工具只需要指定起點和終點，就可自動得到最短路徑。主要步驟主要如下：

（1）激活立體倉庫貨架地圖的線層，創(chuàng)建網(wǎng)絡（Create Network）。選中所有字段，主要應包括2.1.2中創(chuàng)建的兩貨位間的距離、運行速度、單位貨格的行駛時間等字段，如圖 4 的“speed”、“time distance”字段；如果前面兩貨位間的距離用新字段表示，此時創(chuàng)建網(wǎng)絡對話中的“Read Length from”輸入應選擇對應字段（默認為“Length”字段），如圖5所示。并將創(chuàng)建的網(wǎng)絡文件設為當前激活的網(wǎng)絡。

圖5 創(chuàng)建網(wǎng)絡

（2）利用TransCAD尋找最短路徑。執(zhí)行“Networks/Paths-Shortest Path”，打開“Shortest Path Toolbox”工具箱，按揀選貨位在立體倉庫地圖上選中要經(jīng)過的點（即貨位），并確定起點和終點。分別設定最小目標為距離（Length）和時間（即設定的單位貨格的行駛時間字段，示例中為“time distance”），則可分別得到最短揀選回路和時間最短的揀選回路。如圖6所示。

圖6 求取揀選路徑方法

3 應用實例

以下通過揀選實例分析基于TransCAD的立體倉庫揀選路徑優(yōu)化的方法，并分析效果。實驗內(nèi)容包括：（1）基于總作業(yè)路線距離最短的單巷道揀選作業(yè)路徑的優(yōu)化；（2）基于總作業(yè)時間最短的多巷道揀選作業(yè)路徑的優(yōu)化。

3.1 實例背景及數(shù)據(jù)

設一自動化立體倉庫有固定貨架8排，每排固定貨架有 10層30列，總共 2 400個貨位，平面示意圖如圖7所示。貨架中貨格的寬度（L）、高度（H）都為1 m.每條巷道都有一臺堆垛機，每一排的貨架都有一個出入庫臺。其第1、2兩條巷道的貨位信息、存放貨物信息如表1所示，其中的貨位號編號格式為“H巷道號-層號-列位置”，如H1-01-02表示在第一巷道的第一層第二列位置?，F(xiàn)有兩張下架作業(yè)單，分別如表2、表3所示。已知巷道堆垛機在巷道的軌道上水平方向的運行速度為Vy=2 m/s，垂直方向上的升降速度為Vz=1 m/s，巷道堆垛機貨叉平均存貨或取貨的時間為8 s，自動化立體倉庫每日平均訂單量為400個。假定貨箱足夠大，每次能將每個巷道的任務一次揀完，巷道堆垛機都以整托的方式進行貨物的存取作業(yè)，其水平方向單位距離能耗為10個單位，垂直方向單位距離耗為15個單位。

圖7 倉庫平面示意圖

表1 貨位及庫存信息表

表2 下架作業(yè)單1

表3 下架作業(yè)單2

3.2 實驗過程及分析

按前面的思路，在TransCAD建立案例中立體倉庫的TransCAD地圖模型。為了便于分析和計算，只建立倉庫第一巷道和第二巷道的貨架地圖，如圖2所示。

3.2.1 單巷道的距離最短的揀選優(yōu)化過程

已知表2下架作業(yè)單1都是在第二巷道的貨架的貨格上。普通揀選作業(yè)方式為從遠離巷道堆垛機出入庫臺開始從右往左依次開始揀選，下架作業(yè)單1揀選的路徑如圖8所示。

圖8 下架作業(yè)單1普通揀選作業(yè)路徑

由圖8中知，該方式下揀選總作業(yè)距離為56 m，水平方向距離30 m，垂直方向距離26 m，總行走時間41 s，貨叉存貨或取貨的單位時間為8 s，則總作業(yè)時間為121 s.

應用TransCAD對其進行優(yōu)化，同樣根據(jù)表1信息在地圖上選中要經(jīng)過的點，并確定起點和終點，以距離最短為目標，得到下架作業(yè)單1的最短揀選回路如圖9所示。

圖9 揀選路徑及揀選結(jié)果

由圖9可知，優(yōu)化后的總作業(yè)距離為52 m，減少4 m.其中水平方向距離30 m，垂直方向距離22，下架作業(yè)單1優(yōu)化前和優(yōu)化后的分析比較表4所示。

表4 下架作業(yè)單1實驗結(jié)果比較

3.2.2 多巷道的時間最短的揀選優(yōu)化過程

表3下架作業(yè)單2包括在第一巷道和第二巷道的貨架貨格上，普通的揀選作業(yè)方式為從遠離巷道堆垛機出入庫臺開始從右往左依次開始揀選，揀選的路徑如圖10所示。

由圖10中得，總作業(yè)距離為89 m，其中水平方向距離48 m，垂直方向距離41 m，揀選作業(yè)的行走時間62 s，巷道堆垛機總共經(jīng)過9個貨位點，同時巷道堆垛機還把貨物放貨在出庫臺，則總共11個點，則多巷道傳統(tǒng)揀選的總作業(yè)時間為150 s.

圖10 揀貨單2的普通揀選路徑

對下架作業(yè)單2的貨架揀選路徑進行優(yōu)化，求解總作業(yè)時間最短的揀選路徑。根據(jù)表2分別在第一、二巷道選中要經(jīng)過的點，并確定起點和終點，和在“shortest path”工具箱選擇時間為優(yōu)化目標，顯示的最短揀選回路和揀選結(jié)果如圖11所示。

圖11 揀貨單2的最短時間揀選優(yōu)化路徑

從圖11計算出優(yōu)化揀選水平距離為48 m，垂直方向為36 m，基于TransCAD的多巷道揀選作業(yè)的總作業(yè)時間為131 s.下架作業(yè)單2優(yōu)化前后的分析比較如表5所示。

表5 下架作業(yè)單2實驗結(jié)果比較

4 結(jié)束語

立體倉庫作為物流的先進裝備應用越來越廣泛，但面對日益增長的揀選需求，節(jié)約時間、路線和能耗成為企業(yè)關(guān)注的問題。本文應用TransCAD的路線規(guī)劃功能，基于位置信息和立體倉庫的作業(yè)原理，將立體倉庫通過轉(zhuǎn)換降為二維圖形信息，并導入到TransCAD生成為地理信息，從而可以利用TransCAD的路線規(guī)劃功能。轉(zhuǎn)化中涉及立體倉庫貨位點表達，堆垛機表達和揀選問題表達3個主要問題。一旦建立模型后，就可以快速獲取每次的優(yōu)化揀選路徑。論文的方法為立體高層貨架簡單直觀優(yōu)化揀選路徑和進行揀選優(yōu)化實驗、仿真提供了一種新的選擇，也拓展了TransCAD的應用。該方法已經(jīng)成功用到了《物流運籌學》等的優(yōu)化教學實驗中。

[1]劉增曉.揀選式自動化倉庫堆垛機作業(yè)路徑簡易優(yōu)化算法[J].起重運輸機械，2006（8）：49-51.

[2]Sarker R ，Omar M ，Hasan SMK，etal.Hybrid Evolutionary Algorithm for job scheduling under machine maintenance[J].Applied Soft Computing，2013，13（3）：1440-1447.

[2]蔣麗琳，張 弛.基于圖論的自動化立體倉庫堆垛機揀選路徑優(yōu)化[J].物流科技，2010（7）：97-99.

[3]田國會，張 攀.基于混合遺傳算法的固定貨架揀選優(yōu)化問題研究[J].機械工程學報，2004，40（2）：141-144.

[4]楊 瑋，李 程，傅衛(wèi)平，等.自動化立體倉庫固定貨架揀選路徑問題研究[J].上海理工大學學報，2015，37（1）：84-88.

[5]方彥軍，謝宜凈．基于MMAS算法的計量檢定中心倉儲堆垛機揀選路徑優(yōu)化[J]．武漢大學學報（工學版），2013，46（5）：645-648.

[6]靳 萌，穆希輝，杜峰坡，等.基于動態(tài)規(guī)劃與免疫遺傳算法的多穿越巷道揀選路徑規(guī)劃研究[J].計算機測量與控制，2013，21（11）：3120-3123.

[7]章 玉，胡興華，王 佳.交通規(guī)劃模型—TransCAD的操作與應用[M].北京：中國建筑工業(yè)出版社，2013.

[8]王玉峰.配送中心高層貨架揀選路徑作業(yè)優(yōu)化研究[D].長春：吉林大學，2009.