基于GIS与Steiner树问题的配送中心选址研究.doc

基于GIS与Steiner树问题的配送中心选址研究摘要:选择科学有效的位置是电子商务配送中心经营发展的先决条件,地理信息系统依靠其强大的空间分析和可视化功能使电子商务配送中心选址更具有直观性和科学性.针对建立在GIS软件封装好的算法上的传统选址模型,提出Steiner树问题的选址模型,给出了该模型基于多Agent系统的启发式算法.在此基础上,编程工具和GIS软件相结合共同分析和实现了配送中心的选址问题,并验证了该选址方案的可行性.关键词: GIS;Steiner树问题;电子商务;配送中心;选址;AgentStudy on Location-selection of Distribution Center Based on GIS and Steiner Tree ProblemShi Zhan_jiang1,Ma Jun1,2(1. Computer and Information Technology School of Henan University, Henan Kaifeng 475004,China)(2. Data and Knowledge Engineering Institue of Henan University, Henan Kaifeng 475004,China)Abstract: Choosing a location in a scientific and effedtive way is a precondition for development of E-commerces distribution center. Geographic Information System (GIS), relying on its versatile tools in spatial analysis and visualization, makes Location-selection of Distribution Center more precise and more perceptilble. In allusion to the traditional location model based on the algorithm encapsuled by GIS software, this paper proposed a location model of Steiner tree problem and gave its improved algorithm based on multi-agent system (MAS).Then the combination of programming tools and GIS software has analyzed and carried out location problem for distribution center based on this model, and some tests have been made to prove the feasibility of this model.Key words:GIS;Steiner tree problem;E-commerce;Distribution Center;location-seletion;agent0 引言现代电子商务是现代化生产的重要组成部分.电子商务配送中心在现代商品流通中的作用极大.它是作为商品周转、配货、保管等活动的据点,克服在流通过程中所产生的时间和空间障碍,促进商品按顾客要求顺利转移.配送中心的合理布局是电子商务系统中具有战略意义的投资决策问题.配送中心布局是否合理,将对整个系统的运转合理化和商品流通的社会效益有着决定性的影响1.本文的配送中心选址方法较传统的选址方法有两点改进:一是用GIS工具和一般的编程工具相结合,用一般的算法程序实现选址;二是在算法运用上使用了图的Steiner树问题.1 问题描述及建模当当网欲在某市几个待选地址开设几家电子商务配送中心,以适应该市居民和学生的生活需求,并希望总的配送运输成本最少(影响电子商务配送中心选址的因素非常多,本文只考虑路径因素).要求确定配送中心的个数及其位置.由于电子商务环境下企业面对的是分散的客户,企业不可能直接考虑每个客户的需求,因此,本文将采用如下方式处理: 根据查看本市的电子地图上人口分布状况,确定几个人口比较密集并且对该网的商品的需求量比较大的需求点,再在需求点周围根据交通状况等条件筛选出几个备选地点作为配送中心的位置,然后根据地图上的比例尺确定需求点与备选地点组成的所有点之间的距离(若从地图上看到两个点之间的距离明显过长,就不用计算两点之间的距离,直接视为无穷大).这些操作要用到GIS方面的知识. 通过第一步的处理,就得到一个网络图的选址模型.如果将配送中心设置到需求区域,那么直接求这个网络图的最小生成树即可,但这不一定是最优的,这就要在需求区域以外,引入几个外点作为配送中心备选点,这样得到模型就是Steiner树问题的选址模型,需求点作为Steiner树问题中的给定点,备选地点作为Steiner树问题中的非给定点.下面将介绍GIS和Steiner树问题.2 GIS介绍随着计算机科学和信息科学的发展,地理信息系统(GIS)在人们生产和生活中的应用日益广泛.而将地理信息系统等现代信息技术应用于电子商务配送中心选址问题,可以更方便、更准确地解决该问题.与传统的选址方法相比,基于GIS的选址分析具有以下几个方面的特点:一是决策者可以在电子地图上更加直观地看到人口分布、商业布局及交通道路情况等选址要素的信息,从而更有助于决策者进行科学的分析和决策2.二是用户可以通过对不同地图图层的控制,对需要的信息进行分层和叠加,同时还可以自由设置这些要素显示的风格和样式,有利于决策的科学化.三是通过专题地图的分析,用户能够快速发现可利用的市场空间,用户在确定预选位置后,系统可根据用户输入信息的不同进行模拟分析和评估预测,找出优选方案,并以定性和定量的方式将结果反馈给用户,极大地提高了用户的决策效率3. 3 图的Steiner树问题的概念及其求解方法3.1 概念定义4 给定无向连通图设G=(V,E),其中,V为点集,E为边集,在边集E(G)上定义费用函数f:E(G)Z+,构成网络N(G,f).在点集V中有一特定子集 PV,要求在网络上寻找一棵子树T=(Y,u),使得PYV,uE 且 最小.称T为图G关于P的Steiner最小树,其中,不属于P的点称为Steiner点(简称s-点).求图的Steiner最小树的问题称为Steiner树问题.3.2 求解方法Steiner树问题的求解算法大体可以分为精确型算法和启发式(近似)算法两类.但精确型算法的计算量都是随结点数的增加而指数增加,并不适用于求解实际问题.而启发式算法虽然在绝大多数的情况下都不能得到最优Steiner树,但它们能够在较短的时间内找到费用接近最优的准Steiner树,因此它们在选址优化中更有实际意义5.所以下面将用启发式算法求解Steiner树问题.3.2.1 Agent介绍Agent是一个具有自适应性和智能性的软件实体,能代表用户或其它程序,以主动服务的方式完成一项工作.Agent具备自主性、交互性、反应性、主动性等属性.若将多个自主或半自主的Agent构成一体,称为多Agent系统(MAS).每个Agent或者履行自己的职责,或者与其他Agent通信获取信息互相协作完成整个问题的求解.与单Agent相比,MAS有如下特点:社会性:Agent处于由多个Agent构成的社会环境中,通过某种Agent语言与其他Agent实施灵活多样的交互和通讯,实现与其他Agent的合作、协同、协商、竞争等. 自制性:在多Agent系统中一个Agent发出请求后,其他Agent只有同时具备提供此服务的能力与兴趣时才能接受动作委托,即一个Agent不能强制另一个Agent提供某种服务.协作性:在多Agent系统中,具有不同目标的各个Agent必须相互协作、协同、协商对未完成问题的求解6.下面的求解Steiner树问题过程中将会用到MAS.3.2.2 求解步骤令集合P为给定点集,S为待选点集,集合V=PS,顶点Vi与Vj间的距离记为d(Vi,Vj).初始状态为给定的原点集P及P内顶点间的连接关系(边长,边集),若存在边(Vi,Vj),则两点间的距离d(Vi,Vj)即为此边的长度,否则为无穷大(任意一个s-点的度都应大于等于2).求解步骤如下:设置若干个agent,其初始状态均为inactive,每个agent所包含的s-点集hyp为空,每个agent状态下添加s-点前后树长之差sum_difference为0;计算P中任意两个原点pi与pj之间的最短距离,记为Old_D(pi, pj).反复执行下述操作至每个agent的状态都为active为止:Test操作每个agent检查:从集合S-hyp中任意选取一个点Vs,存在边(Vs,Vi),(Vs,Vj),Vi, VjP,且d(Vs, Vi) + d(Vs, Vj) d(Vi, Vj)则将该agent的状态置为active.用新路径替换原来的路径(将边(Vs, Vi),(Vs, Vj)加入,此时构成环,去掉环中最长的一条边),将Vs并入P,并将Vs添加到集合hyp中,S=S-Vs.在此状态下,重新计算P中任意两个原点pi与pj之间的最短距离,记为New_D(pi, pj),然后计算,记为sum_difference.Diffuse操作每个active的agent A随机的选择一个agent B通信,若B为active且与A的s-点集hyp相等,则B的状态置为inactive且s-点集置为空集;若不等但s-点个数相同且A.sum_difference小于B.sum_difference,则A 复制 B的hyp及Steiner点数;若s-点个数相同且A.sum_difference大于B.sum_difference,则B 复制 A的hyp及Steiner点数. 在所有状态为active的agent中找出sum_difference值最大且s-点个数尽量最少的agent,此状态下的树长即为所求.此算法已在VC+ 6.0上实现.4 图的Steiner树问题在GIS选址中的应用本文基于Windows Xp操作系统,采用ESRI公司的ArcGIS Engine和ArcMap软件,结合Visual C+可视化环境,实现了在给定地图上提出一套电子商务配送中心选址方案的功能.GIS选址分析的步骤如下:第一步:用GIS软件ArcMap制作一幅地图,通过调查分析在地图上标记出人口分布密度,把明显不符合选址要求的区域排除在外,选出大致合适的地区做进一步的分析.第二步:根据人口密集程度在已经筛选出的地区中再筛选出几个点作为给定点.再根据调查和一些相关因素在给定点以外筛选几个备选点作为将来配送中心的备选地点,并在地图上标示.第三步:用ArcGIS Engine调用地图,并和编程工具Visual C+关联起来,将Steiner树问题的算法程序添加到Visual C+中,从编程环境中调用ArcGIS Engine中GIS相关部分,运行程序实现选址功能.5 算例假设利用GIS相关软件在某一区域确定了三个需求点V1,V2,V3,三个备选点S1,S2,S3,构成的网络图G,如图1所示.经过Steiner树问题的算法求解,得出Steiner最小树,如图2所示.从图2可以看出在这个区域建两个配送中心,地址分别为S2,S3,它们的位置可以从地图上看到.图1 网络图G(边权的单位为公里)图2 图G的Steiner最小树5 结论电子商务配送中心选址策划具有重要的意义,在进行选址分析时要以便利消费者为首要原则,否则就失去了消费者的支持和信赖,配送中心也就失去了存在的基础.本文以电子商务配送中心选址为例介绍了图的Steiner树问题与GIS相结合的选址方案,较传统的选址算法有较大的改进.该方法简单,时间复杂度不高,比较适用于开设小型设施的情况,但也存在不足之处,例如结点的权值没有考虑,影响配送中心很多因素考虑的比较少等等.后续研究工作将在模型的细化完善和算法的进一步优化方面展开.参考文献:1 万莉,黄挚雄. 基于GIS优化Dijkatra算法在物