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.