ArcGIS Engine下三維倉庫存取貨路徑優化研究＊

趙 旭 池秀文 覃 瑜 崔 巍

（武漢理工大學資源與環境工程學院1） 武漢 430070） （中國地質大學土地科學技術學院2） 北京 100083）

三維倉庫的出現解決了倉庫管理中不夠直觀缺乏管理的靈活機動性的問題，但隨之而來的是貨物數據信息化、存取貨路徑不能充分優化等問題.地理信息系統（geographic information system，GIS）在立體倉庫中應用尚處在起步階段，仍需要對其進行相關研究和探索.針對倉庫模型建立GIS支持的應用還未見諸于報道.但對倉庫應用所涉及的關鍵技術，國內外學者均做了大量的研究.在三維方面，如李德仁等［1－2］的三維城市到田宜平［3］等三維社區；在數據模型方面，龔健雅等［4］以礦山地質為背景，提出矢量和柵格數據集成的新數據模型；Bhowmick［5］等在數據倉庫基礎上如何對WEB信息進行存儲和呈現，提出了結點、連接的高效數據模型；Jakimavicius等［6］在GIS基礎上計算車輛合理路徑問題；在路徑優化方面，王開義等［7］對Dijkstra最短路徑搜索算法的優化途徑進行分析，提出了直線優化Dijkstra算法，并應用到“全國主要城市間公路信息查詢”系統中；王江晴等［8］提出了動態網絡環境下的實時路徑評估模型，并上構造出改進的Dijkstra雙桶算法實現了靜態和動態的交通信息找出客戶之間的實時最短路徑的查詢；Vaughan［9］等對具有十字通道的倉庫進行分析，對通道個數進行優化，得出最短運輸距離；Pahlavani［10］等對于不確定位置信息，在城市多層面數據基礎上，建立了基于GIS的路徑優化方法.

本文首次借助GIS下ArcGIS Engine平臺利用編程對平面倉庫進行了模擬，將倉庫以三維效果進行顯示，并能對貨物信息進行增刪改查和分析，大大提高了管理的效率，降低了勞動強度；并利用改進的直線Dijkstra算法和劃分思想，簡化TSP的路徑優化問題，在求解該問題上取得了一定效果.

1 系統總體結構與功能設計介紹

利用包含著商品等貨物數據的數據庫，結合系統優化理論，考慮改進Dijkstra優化算法等組建起一個集圖文報表、三維空間、信息分析支持于一體的綜合信息系統.總體結構框架，如圖1.

圖1 系統結構框架圖

1.1 貨物存儲規則分析

倉庫中貨物的存放應以提高揀貨效率和降低倉庫操作成本為目的，保證貨位分布處在較為合理的狀態.一般貨位優化的分類原則為［11］：（1）滯銷的貨品或小、輕及容易處理的品項使用較遠儲區；（2）周轉率低的物品盡量遠離進貨、出貨區及倉庫較高的區域；（3）周轉率高的物品盡量放于接近出貨區及較低的區域.比如洗化用品，單件重量不大但存儲數量多，且周轉率高，因此宜將其置于較近儲區或較低的區域.

1.2 數據庫分析

要準確判定貨物的存儲位置，必須按照貨位優化規則進行實施，而且存取貨物搜索速率關系著整個系統的效率和精度.主要影響存取貨物搜索的是存儲規則的解譯和海量數據庫的操作.規則的解譯要考慮以上因素，因此在數據庫邏輯設計時，除了品名、數量、單價、質量、貨商等基本信息外，還有針對性的添加貨物類別、暢銷／滯銷（編碼分別為1／0）、流通率三項指標，并建立索引，再根據貨物名稱、個體重量、數量等一般信息就可以快速并準確的解譯，通過屬性數據連接空間數據，得到貨物存放位置.針對存儲貨物多、海量數據庫的頻繁操作，本研究用數據庫連接池技術，其以連接復用為核心，使得數據庫連接可以得到高效、安全的復用，避免了數據庫連接頻繁建立、關閉的開銷；降低了系統消耗，提高了開發效率和整個應用程序的伸縮性和健壯性.

2 三維可視化

三維可視化是本研究的創新點之一.本研究選擇以ArcGIS Engine為平臺解決三維倉庫有關問題.利用其強大的三維顯示功能，將倉庫的布局、巷道走向、貨架存貨等信息以三維形式直觀顯示，并提供三維瀏覽功能：放大、縮小、漫游、全圖，幫助管理人員建立起倉庫整體印象，并可以針對某個貨架進行信息查詢，如圖2所示.

圖2 系統界面及查詢效果

三維倉庫的顯示，是根據用戶輸入的貨架的單架高和行數實時計算建模生成的.本文中三維模型生成的流程為：（1）定義點、線或面的實體坐標（X，Y，Z）；（2）生成三維標記進行渲染，本文模型由ArcGIS Engine中MultiPatch完成的貨柜、地面和3DMax軟件的模型組合形成；（3）最后為三維標記賦予特定的實體屬性值，展現地物.圖3為倉庫顯示流程，直接顯示到界面上得到的效果如圖4.

圖3 倉庫顯示流程圖

圖4 建模流程界面效果圖

3 貨物路徑優化

3.1 貨物網絡結點提取

對貨物路徑優化的實現，首要的前提是得知目標貨源起點和運輸終點.和給定目標結點的GIS數據模型不同，本系統僅假設倉庫出口，對于貨物的存儲地點并不明確，即不清楚貨物網絡中結點，因此必須通過數據庫信息查詢，然后匹配空間數據，得到目標貨物的地址集合，用以確定起點和終點，為下一步存取的路徑計算和三維可視化顯示打下基礎.本文利用GIS分析功能將貨物屬性數據和空間數據一一匹配，完成貨物網絡結點的自動提取.根據存儲規則連接數據庫實時尋找目標貨架的流程如圖5所示.

圖5 目標貨物尋找流程

3.2 改進Dijkstra算法的應用

原始Dijkstra算法將網絡結點分為未標記結點、臨時標記結點和永久標記結點，網絡中所有結點首先初始化為未標記結點，在搜索過程中和最短路徑結點相連通的結點為臨時標記結點，每一次循環都是從臨時標記結點中搜索距源點路徑長度最短的結點作為永久標記結點，直至找到目標結點或者所有結點都成為永久標記結點才結束，這樣臨時結點無序地存儲在無序表中，每次搜索都要遍歷到表中的所有臨時結點，這樣勢必會帶來龐大的計算量，給系統的應用也會帶來很大不便.提高算法的效率一方面可以通過對臨時結點表建立索引，加快檢索速度；另一方面即減少搜索的臨時結點的數量，那么效率就可以大幅度的提高.

本文中倉庫的特點和普通GIS數據模型不同的是起點和終點為相同的結點，因此倉庫的路徑選擇就和旅行商（TSP）問題一樣，屬于具有NP（non－deterministic polynomial）難度的，不存在有效的多項式解法［12］.

本研究改進的Dijkstra算法在提高普通Dijkstra搜索能力的同時，也變相地解決了TSP問題.在所研究的結構下，將臨時標記結點到源點的最短路徑與本臨時結點到目標結點的直線距離之和作為該臨時結點的一個屬性值，則臨時標記結點集合中該值最小的點即為選定的永久標記結點.

如圖6所示，P1，Pn為臨時結點，L1、Ln、D1、Dn分別為對應臨時結點到源點和到終點的直線距離.原始Dijkstra算法的判斷原則是：如果L1＞Ln，則選取Pn為永久標記結點，接著以Pn為進行下一輪搜索的起點；相反則選取P1為永久結點，再以P1為源點進行下一輪搜索，而直線化Dijkstra算法的判斷方法為：如果L1＋D1＞Ln＋Dn，則選取Pn為永久標記結點，如果L1＋D1＜Ln＋Dn，則選取P1為永久標記結點.此舉使Dijkstra算法的搜索方向智能的趨向目標結點，減少了遍歷的結點數，從而提高了算法的效率.

圖6 直線化Dijkstra算法

為了將TSP問題轉化成Dijkstra算法能處理的兩點間多目標最短路徑問題，如圖6所示，確定一組貨物點為實驗集合，坐標（X，Y）分別為：1（4，1），2（2，8），3（3，5），4（5，2），5（6，6），6（9，5），7（10，3），8（10，8），9（11，6），10（13，2），11（14，5），12（14，8），13（17，1），14（18，6），15（18，10），16（19，3）.

優化算法解決TSP問題的步驟可以表述為：

1）以點1為起點，以其為圓心的同心圓搜索距離起點最遠的結點，搜索到點15，將其標注為本次運行的終點.連線1－15將所有結點分為2部分，將NP問題轉化成P問題進行求解.

圖7 算法迭代產生優化路徑

2）對于1－15線上結點而言，點1為起點、點15為終點，利用直線距離為權重的Dijkstra算法，得出去行優化路徑.

3）對于1－15線下結點而言，點15為起點、點1為終點，同樣利用改進算法，得出回行優化路徑.

最短路徑對應的結點順序：1→4→7→10→11→13→16→14→15→12→9→8→6→5→2→3→1.

本改進算法，路徑＝去行最優＋回行最優.如此在提高普通Dijkstra搜索能力的同時，也變相解決了TSP路徑優化問題.

4 結 束 語

將ArcGIS Engine平臺引入到倉庫管理與應用中，將倉庫和存儲效果三維化，利用GIS分析功能解譯貨物存儲規則，搜尋貨物潛在位置；并結合改進Dijkstra的算法和劃分思想，將TSP路徑優化問題降解為Dijkstra可以處理的范圍，擴展了Dijkstra算法的應用范圍，增強了本系統智能性和決策性.

尋找合適高效的三維顯示方式和管理決策方法，結合不斷成熟的空間數據顯示技術和倉庫管理技術，現代應用系統中的倉庫管理必然會發展到三維可視化智能管理階段，也必將成為該領域的發展方向.

［1］朱 茵，Duo Zhang.倉儲規劃與技術／企業物流技術培訓教材系列［M］.北京：清華大學出版社，2002.

［2］李德仁，劉 強，朱 慶.數碼城市GIS中建筑物室外與室內三維一體化表示與漫游［J］.武漢大學學報：信息科學版，2003（3）：253－258.

［3］田宜平，李偉忠，何珍文.數字城市中三維數字社區的解決方案［J］.計算機工程與應用，2004（1）：223－226.

［4］龔健雅，夏宗國.矢量與柵格集成的三維數據模型［J］.武漢測繪科技大學學報，1997，22：7－15.

［5］Bhowmick，Madria，Wee Keong.Representation of web data in a web warehouse［J］.Computer Journal，2003，46（3）：229－262.

［6］Jakimavicius，Macerinskiene.A gis－based modelling of vehicles rational routes［J］.Journal of Civil Engineering and Management，2006，12（4）：303－309.

［7］王開義，趙春江，胥桂仙，等.GIS領域最短路徑搜索問題的一種高效實現［J］.中國圖象圖形報，2003A（8）：951－956.

［8］王江晴，康立山.動態車輛路徑問題中的實時最短路徑算法研究［J］.武漢理工大學學報：交通科學與工程版，2007，31（1）：46－49.

［9］Vaughan，Petersen.Effect of warehouse cross aisles on order picking efficiency［J］.International Journal of Production Research，1999，37（4）：881－897.

［10］Pahlavani，Samadzadegan，Delavar.A GIS－based approach for urban multi－criteria quasi optimized route guidance by considering unspecified site satisfaction［M］／／Lecture Notes in Computer Science.Heidelberg：Springer Berlin，2006：287－303.

［11］鄭凌鶯，王紹宇.自動化立體倉庫的貨位優化管理［J］.商場現代化，2007（29）：96－99.

［12］鄭 歡.自動化立體倉庫路徑優化問題研究［D］.長春：吉林大學機械科學與工程學院，2006.