基于TransCAD的固定貨架立體倉庫揀選路徑優化

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

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

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

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

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

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

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

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

式中D表示總路線距離，T表示揀選時堆垛機行駛總時間，n為揀選需要經過的所有經過的包含工作在在內的貨位點的數量（由單次的揀選任務單決定），ki表示揀選需要經過第i個貨位點，其中第1個點為工作臺。d（ki，ki+1）表示經過貨位點 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規劃立體倉庫揀選路徑的方法

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

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

2.1.1 貨位點的表達

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

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

圖1 貨架貨格平面示意圖

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

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

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

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

2.1.2 揀選屬性特征的表達

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

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

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

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

（3）添加堆垛機運行速度等屬性。激活立體倉庫地圖線層，修改其屬性，增加數據字段分別用于存儲堆垛機水平和垂直方向兩貨位間的距離（由于任何兩貨位間都是連通的，該距離實際對應單位貨格的距離長與高，如果H與L都不是1，即與2.1.1中貨位坐標抽象的距離有差異，則需要添加字段，并通過H、L、現有“Length”字段間的公式轉換存儲為實際距離）、運行速度、單位貨格的行駛時間，并根據實際堆垛機的運行速度轉化后填充數據，對應的單位貨格的行駛時間為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”兩個新字段分別存儲水平方向的速度和單位貨格的行駛時間，為后面優化做好了參數定義準備。

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

2.1.3 揀選優化問題的表達

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

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

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

圖5 創建網絡

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

圖6 求取揀選路徑方法

3 應用實例

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

3.1 實例背景及數據

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

圖7 倉庫平面示意圖

表1 貨位及庫存信息表

表2 下架作業單1

表3 下架作業單2

3.2 實驗過程及分析

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

3.2.1 單巷道的距離最短的揀選優化過程

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

圖8 下架作業單1普通揀選作業路徑

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

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

圖9 揀選路徑及揀選結果

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

表4 下架作業單1實驗結果比較

3.2.2 多巷道的時間最短的揀選優化過程

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

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

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

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

圖11 揀貨單2的最短時間揀選優化路徑

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

表5 下架作業單2實驗結果比較

4 結束語

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

[1]劉增曉.揀選式自動化倉庫堆垛機作業路徑簡易優化算法[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]蔣麗琳，張 弛.基于圖論的自動化立體倉庫堆垛機揀選路徑優化[J].物流科技，2010（7）：97-99.

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

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

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

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

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

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