ArcGIS Engine下三維倉(cāng)庫(kù)存取貨路徑優(yōu)化研究＊

趙 旭 池秀文 覃 瑜 崔 巍

（武漢理工大學(xué)資源與環(huán)境工程學(xué)院1） 武漢 430070） （中國(guó)地質(zhì)大學(xué)土地科學(xué)技術(shù)學(xué)院2） 北京 100083）

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

本文首次借助GIS下ArcGIS Engine平臺(tái)利用編程對(duì)平面?zhèn)}庫(kù)進(jìn)行了模擬，將倉(cāng)庫(kù)以三維效果進(jìn)行顯示，并能對(duì)貨物信息進(jìn)行增刪改查和分析，大大提高了管理的效率，降低了勞動(dòng)強(qiáng)度；并利用改進(jìn)的直線Dijkstra算法和劃分思想，簡(jiǎn)化TSP的路徑優(yōu)化問(wèn)題，在求解該問(wèn)題上取得了一定效果.

1 系統(tǒng)總體結(jié)構(gòu)與功能設(shè)計(jì)介紹

利用包含著商品等貨物數(shù)據(jù)的數(shù)據(jù)庫(kù)，結(jié)合系統(tǒng)優(yōu)化理論，考慮改進(jìn)Dijkstra優(yōu)化算法等組建起一個(gè)集圖文報(bào)表、三維空間、信息分析支持于一體的綜合信息系統(tǒng).總體結(jié)構(gòu)框架，如圖1.

圖1 系統(tǒng)結(jié)構(gòu)框架圖

1.1 貨物存儲(chǔ)規(guī)則分析

倉(cāng)庫(kù)中貨物的存放應(yīng)以提高揀貨效率和降低倉(cāng)庫(kù)操作成本為目的，保證貨位分布處在較為合理的狀態(tài).一般貨位優(yōu)化的分類原則為［11］：（1）滯銷的貨品或小、輕及容易處理的品項(xiàng)使用較遠(yuǎn)儲(chǔ)區(qū)；（2）周轉(zhuǎn)率低的物品盡量遠(yuǎn)離進(jìn)貨、出貨區(qū)及倉(cāng)庫(kù)較高的區(qū)域；（3）周轉(zhuǎn)率高的物品盡量放于接近出貨區(qū)及較低的區(qū)域.比如洗化用品，單件重量不大但存儲(chǔ)數(shù)量多，且周轉(zhuǎn)率高，因此宜將其置于較近儲(chǔ)區(qū)或較低的區(qū)域.

1.2 數(shù)據(jù)庫(kù)分析

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

2 三維可視化

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

圖2 系統(tǒng)界面及查詢效果

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

圖3 倉(cāng)庫(kù)顯示流程圖

圖4 建模流程界面效果圖

3 貨物路徑優(yōu)化

3.1 貨物網(wǎng)絡(luò)結(jié)點(diǎn)提取

對(duì)貨物路徑優(yōu)化的實(shí)現(xiàn)，首要的前提是得知目標(biāo)貨源起點(diǎn)和運(yùn)輸終點(diǎn).和給定目標(biāo)結(jié)點(diǎn)的GIS數(shù)據(jù)模型不同，本系統(tǒng)僅假設(shè)倉(cāng)庫(kù)出口，對(duì)于貨物的存儲(chǔ)地點(diǎn)并不明確，即不清楚貨物網(wǎng)絡(luò)中結(jié)點(diǎn)，因此必須通過(guò)數(shù)據(jù)庫(kù)信息查詢，然后匹配空間數(shù)據(jù)，得到目標(biāo)貨物的地址集合，用以確定起點(diǎn)和終點(diǎn)，為下一步存取的路徑計(jì)算和三維可視化顯示打下基礎(chǔ).本文利用GIS分析功能將貨物屬性數(shù)據(jù)和空間數(shù)據(jù)一一匹配，完成貨物網(wǎng)絡(luò)結(jié)點(diǎn)的自動(dòng)提取.根據(jù)存儲(chǔ)規(guī)則連接數(shù)據(jù)庫(kù)實(shí)時(shí)尋找目標(biāo)貨架的流程如圖5所示.

圖5 目標(biāo)貨物尋找流程

3.2 改進(jìn)Dijkstra算法的應(yīng)用

原始Dijkstra算法將網(wǎng)絡(luò)結(jié)點(diǎn)分為未標(biāo)記結(jié)點(diǎn)、臨時(shí)標(biāo)記結(jié)點(diǎn)和永久標(biāo)記結(jié)點(diǎn)，網(wǎng)絡(luò)中所有結(jié)點(diǎn)首先初始化為未標(biāo)記結(jié)點(diǎn)，在搜索過(guò)程中和最短路徑結(jié)點(diǎn)相連通的結(jié)點(diǎn)為臨時(shí)標(biāo)記結(jié)點(diǎn)，每一次循環(huán)都是從臨時(shí)標(biāo)記結(jié)點(diǎn)中搜索距源點(diǎn)路徑長(zhǎng)度最短的結(jié)點(diǎn)作為永久標(biāo)記結(jié)點(diǎn)，直至找到目標(biāo)結(jié)點(diǎn)或者所有結(jié)點(diǎn)都成為永久標(biāo)記結(jié)點(diǎn)才結(jié)束，這樣臨時(shí)結(jié)點(diǎn)無(wú)序地存儲(chǔ)在無(wú)序表中，每次搜索都要遍歷到表中的所有臨時(shí)結(jié)點(diǎn)，這樣勢(shì)必會(huì)帶來(lái)龐大的計(jì)算量，給系統(tǒng)的應(yīng)用也會(huì)帶來(lái)很大不便.提高算法的效率一方面可以通過(guò)對(duì)臨時(shí)結(jié)點(diǎn)表建立索引，加快檢索速度；另一方面即減少搜索的臨時(shí)結(jié)點(diǎn)的數(shù)量，那么效率就可以大幅度的提高.

本文中倉(cāng)庫(kù)的特點(diǎn)和普通GIS數(shù)據(jù)模型不同的是起點(diǎn)和終點(diǎn)為相同的結(jié)點(diǎn)，因此倉(cāng)庫(kù)的路徑選擇就和旅行商（TSP）問(wèn)題一樣，屬于具有NP（non－deterministic polynomial）難度的，不存在有效的多項(xiàng)式解法［12］.

本研究改進(jìn)的Dijkstra算法在提高普通Dijkstra搜索能力的同時(shí)，也變相地解決了TSP問(wèn)題.在所研究的結(jié)構(gòu)下，將臨時(shí)標(biāo)記結(jié)點(diǎn)到源點(diǎn)的最短路徑與本臨時(shí)結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的直線距離之和作為該臨時(shí)結(jié)點(diǎn)的一個(gè)屬性值，則臨時(shí)標(biāo)記結(jié)點(diǎn)集合中該值最小的點(diǎn)即為選定的永久標(biāo)記結(jié)點(diǎn).

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

圖6 直線化Dijkstra算法

為了將TSP問(wèn)題轉(zhuǎn)化成Dijkstra算法能處理的兩點(diǎn)間多目標(biāo)最短路徑問(wèn)題，如圖6所示，確定一組貨物點(diǎn)為實(shí)驗(yàn)集合，坐標(biāo)（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）.

優(yōu)化算法解決TSP問(wèn)題的步驟可以表述為：

1）以點(diǎn)1為起點(diǎn)，以其為圓心的同心圓搜索距離起點(diǎn)最遠(yuǎn)的結(jié)點(diǎn)，搜索到點(diǎn)15，將其標(biāo)注為本次運(yùn)行的終點(diǎn).連線1－15將所有結(jié)點(diǎn)分為2部分，將NP問(wèn)題轉(zhuǎn)化成P問(wèn)題進(jìn)行求解.

圖7 算法迭代產(chǎn)生優(yōu)化路徑

2）對(duì)于1－15線上結(jié)點(diǎn)而言，點(diǎn)1為起點(diǎn)、點(diǎn)15為終點(diǎn)，利用直線距離為權(quán)重的Dijkstra算法，得出去行優(yōu)化路徑.

3）對(duì)于1－15線下結(jié)點(diǎn)而言，點(diǎn)15為起點(diǎn)、點(diǎn)1為終點(diǎn)，同樣利用改進(jìn)算法，得出回行優(yōu)化路徑.

最短路徑對(duì)應(yīng)的結(jié)點(diǎn)順序：1→4→7→10→11→13→16→14→15→12→9→8→6→5→2→3→1.

本改進(jìn)算法，路徑＝去行最優(yōu)＋回行最優(yōu).如此在提高普通Dijkstra搜索能力的同時(shí)，也變相解決了TSP路徑優(yōu)化問(wèn)題.

4 結(jié) 束 語(yǔ)

將ArcGIS Engine平臺(tái)引入到倉(cāng)庫(kù)管理與應(yīng)用中，將倉(cāng)庫(kù)和存儲(chǔ)效果三維化，利用GIS分析功能解譯貨物存儲(chǔ)規(guī)則，搜尋貨物潛在位置；并結(jié)合改進(jìn)Dijkstra的算法和劃分思想，將TSP路徑優(yōu)化問(wèn)題降解為Dijkstra可以處理的范圍，擴(kuò)展了Dijkstra算法的應(yīng)用范圍，增強(qiáng)了本系統(tǒng)智能性和決策性.

尋找合適高效的三維顯示方式和管理決策方法，結(jié)合不斷成熟的空間數(shù)據(jù)顯示技術(shù)和倉(cāng)庫(kù)管理技術(shù)，現(xiàn)代應(yīng)用系統(tǒng)中的倉(cāng)庫(kù)管理必然會(huì)發(fā)展到三維可視化智能管理階段，也必將成為該領(lǐng)域的發(fā)展方向.

［1］朱 茵，Duo Zhang.倉(cāng)儲(chǔ)規(guī)劃與技術(shù)／企業(yè)物流技術(shù)培訓(xùn)教材系列［M］.北京：清華大學(xué)出版社，2002.

［2］李德仁，劉 強(qiáng)，朱 慶.數(shù)碼城市GIS中建筑物室外與室內(nèi)三維一體化表示與漫游［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2003（3）：253－258.

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

［4］龔健雅，夏宗國(guó).矢量與柵格集成的三維數(shù)據(jù)模型［J］.武漢測(cè)繪科技大學(xué)學(xué)報(bào)，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］王開(kāi)義，趙春江，胥桂仙，等.GIS領(lǐng)域最短路徑搜索問(wèn)題的一種高效實(shí)現(xiàn)［J］.中國(guó)圖象圖形報(bào)，2003A（8）：951－956.

［8］王江晴，康立山.動(dòng)態(tài)車輛路徑問(wèn)題中的實(shí)時(shí)最短路徑算法研究［J］.武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，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］鄭凌鶯，王紹宇.自動(dòng)化立體倉(cāng)庫(kù)的貨位優(yōu)化管理［J］.商場(chǎng)現(xiàn)代化，2007（29）：96－99.

［12］鄭 歡.自動(dòng)化立體倉(cāng)庫(kù)路徑優(yōu)化問(wèn)題研究［D］.長(zhǎng)春：吉林大學(xué)機(jī)械科學(xué)與工程學(xué)院，2006.