（系统工程专业论文）配送网络拓扑构建研究及应用.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责 任由本人承担。 论文作者签名：! 牢业 日期： 型五竺_ 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校 保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文 和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：翌幽导师签名： 期： 山东大学硕士学位论文 摘要 配送网络是合理安排配送路线的前提基础，对降低配送中心成本起着至关重 要的作用。目前国内外对配送网络构建方面的研究还不够深入，本文利用图论和一 g i s 技术对配送网络拓扑结构的构建方法进行研究，实现其自动化构建功能，建 立物流配送系统所需韵空间属性数据库，并应用于个基于g i s 的面向大规模城 市物流配送的线路优化系统。 本文首先介绍了国内外网络拓扑构建和基于g i s 物流配送系统的研究现状， 提出现在g i s 在配送线路优化应用中存在的问题，分析了物流配送系统所需的地 理空间属性数据。然后，深入城市配送问题实践，针对城市物流配送和城市交通 道路网的特点，研究道路网的矢量表达、网络拓扑结构的提取和构建、客户点与 道路网的匹配等关键技术，提出一套将客户点添加进城市配送道路网络的规则， 对地理信息和交通信息进行提取，构建了配送线路优化所需的包含客户资源信息 和道路信息的拓扑网络。 在此基础上，结合烟草配送中心的实际情况，介绍了实际应用背景和问题模 型算法，分析网络拓扑构建在配送中心线路优化系统中的应用。在m a p h 面平台 上实现算法与g i s 的整合，对基于g 略的配送线路优化系统及网络拓扑构建模 块的实现进行介绍。 本文的研究结果，成功应用在济南市烟草物流配送线路优化中，构建了覆盖 辖区内2 8 0 0 0 个客户点的配送网络，取得了一定的经济效益同时，本文研究同 样适用于其它领域大规模城市物流配送，具有重要的实用价值 关键词：物流配送；地理信息系统；网络拓扑构建：线路优化 山东大学硕士学位论文 a b s t r a c t d e l i v rn c t w o r ki st h eb 蠲锄e n to f u t i n g 锄a l y s i s 锄dv 枷c l e h e d u l i n g w i l i e hi s s i g l l i f i c 觚t i nc o s t - c u t t i n go fd i s n 曲砸伽伏m e r n 0 1 矾- d a y ss t i l d yi n c o 璐衄l 甜o f d c l i v e r yn 咖o d 【 c o u l d n tm e np m d u c t i 帅r i s 髓a n d c o 姗e i a l 曲t c r p r i s 船p m c t i c a ln d s t 1 1 i sp 印盯u s 端g r a p ht h a n dg i s t e c i l n o l o 盯i ne x p s s i n g 孤d 璐咄t i i l gd c h v e r yn e t 比柚da p p l y 8i t t oa g i s - b 勰e dl o g i s t i c sd i s 伍b 砸s y s t e m f i r s t l yt h i sp a p e rs t i l d i 嚣n 圮d e v e l 叩m c n ts t a t eo f s p a t i a lt o p o l o 影s t i l d y 心 ( v e c h j c l er o u t i n gp d o b l 锄s ) 柚dg i s _ b a 耐l o g i s t i d i s 硼咖s y s t c m ， i n 嘴t i g 栅l h ek e yt l l l l o l o g ya n d 呻b l 锄t ob e l v e d mt h c 如n o w i l l gp a 噶 n s i d t ：r i n gt h e 岛a t m 伪o fl l l b 锄l o g i s d cd i 矧b i m 柚dp r a c d c a l 印p l i c a t i ，t h i s r 妫e a 劬佑c l i s 髂o nt l l e 羽i k h n a t i o no f 伽咀s t m c t i o no fd i 鲥b u t i 埘时w o r l 已n 印p l i 髓 t l 坞蛐l o g yo fg i s ( g 鲫h y 础b 皿崩伽s y g t 黜) t oh e l p 璐t o 甑鲫翳n ” u i b 舭a d sn 融o fg o d sd c l i v e r yw h i c hi sm cb 雒i so fm 嘶n go p 血n i 刎o n a 埘捌n g t h eu 卯a i 孕印hc 锄o tm e e tt h ed 即豫n do f t l l e 锄叩l ef 幻t i l s ，舭眦鼯 孤d i n p l c x 衄o ft h em a dm t w o 呔，t h e a p p e 盯n o d e - l i n l cm o d e l m b i n e d 谢也 他谢c t i 切l b l e w h i c h c 锄a l d c 蹦i l 粥也e p a l t t r a n s p o n 懈嫡c t i 伽a l l d o n t h e b a s i s o f m a t c h i n gp r i n c i p l 鹤，w em a l c hm e 伽l s t 嘲盯l o c a l i t o 也e a d s a n d 托p i 髂饥tt h e r e a lw o r l do b j e c t si i it h es p 砸a ln 咖o r i ( a n dt h e ni m 加i d u c eas p i 丘e d 麟p l a 删 o f t h c w a y s 柚d m 锄ss t c p b ys t 印 a f i 盯t h a l t h e m l 髂w e 血i a l l y t l l a l i z e d 谢t h m a lb a s i c 锄dm 印m f o ， m a p xp l a t f o 】1 kp 印盯坞a 嘲t h es t o r a g e 锄d 础眦i g 锄c n lo fs p a l i a l 孤d 砒啊h i t 出胁弱e ，p v t 诅i t su d h t yb yr 印n t i n gt h e0 i 姬m i z 嘶m o d 【c lf b r v 出c l cm 毗& e s t _ a b l i s h i l l gt l l em 劬c m a d c sm o d e l 觚dd 韶i 孕1 i i l gt l l e 碰t l l m e 吐c d e t a i l s ，b i i i l d i n gm ei i l i t i a l 缸n e w o r i 【f b rl o g i s t i c sd i s 仃i b 嘶u 曲g 叩曲l i z 撕o n s y s t e l 捌l i i i gt h ed a _ bi n t e g r a 矗o n 缸df i 】n c 矗o ni n t c g 硼。几 t h er 踟n w 勰丘n a l l y l l s e d i na t o b a c c o m s 由删m p 锄y 、i t ha a l eo f 2 8 0 0 0c 璐t o m e 陪n 啪a l s ob ea p p l i c a b l ei no t h 盯锄i c a l l yd i s t r i b u 缸c 唧觚y 谢i hi ；o u 蛀n gp f o b l e m s k e yw o r d s ：傩；l o g i s t i c sd i s 扛i b 埘；1 o p o o l 鲥c o n s 仇l c t i ；r o 硼h go p t i i l l i z a l i 饥 4 山东大学硕士学位论文 第一章绪论 1 1 课题背景与意义 1 1 1 课题背景 我国加入1 盯o 以来，市场经济体制不断深入发展并日趋完善，同时中国烟草 行业的改革逐步深化，传统的流通模式越来越不能适应新形势的要求，烟草流通 企业纷纷准备或开始筹建配送中心，以降低成本，提高服务质量和水平，扩大经 营规模，改进物流与信息流系统在2 0 0 2 年的上海烟草网建会上，国家局明确 提出了“烟草行业要加快实现传统商业向现代流通的转变”2 0 0 5 年4 月，国家 烟草专卖局国烟办下发了 2 0 0 5 2 1 5 号文件一全国卷烟销售网络建设整体推 进、全面提升的工作方案对烟草物流配送提出了明确的要求m ，总结起来就是 要实现“五化管理”，即：仓储管理数字化、卷烟库存合理化、卷烟分拣电子化、 配送线路最优化、车辆配载经济化。 物流配送系统作为现代流通的一个重要组成部分，必然成为烟草行业网络建 设的核心任务之一如何建立现代烟草配送模式，来满足市场经济条件下的运作 模式，就显得尤为重要。 烟草行业配送的最重要环节在于直接面向用户的末端配送，卷烟能否及时送 达、客户是否满意与配送环节有很大的关系。烟草物流配送企业，在实现城市物 流配送的环节中，作为一个流通型经济实体，一方面为了提高客户满意度，要求 及时地向顾客提供满意的配送服务、提高配送效率，需要保持较高的时效性；另 一方面为了提高配送经济性，要求尽可能的安排合理的行驶路径、使用尽可能少 的车辆、提高配送车辆的装载率，来降低配送的运输成本。也就是说，企业要实 现满足客户服务要求和降低配送成本两个目标。在物流“效益背反”说原则下， 以尽可能少的资源和成本提供尽可能满足客户要求的服务，是关系配送企业利润 水平的关键。 烟草行业的城乡配送具有小批量、多批次、送货点分散等特点，对配送工作 提出了更高的要求。但是，目前国内烟草行业城乡配送还存在手工安排作业和粗 放经营现象，造成车辆利用率低、配送成本高、管理人员无法有效监控配送过程、 山东大学硕士学位论文 客户满意度低等问题。运用g i s 和g p s 等与物流配送密切相关的技术辅助车辆配 送线路的安排，对于解决当前配送中存在的问题是非常有意义的 基于客户和道路地图关系的拓扑结构是配送线路优化一个非常重要的部分， 配送线路优化工作中的网络分析和算法实现都是在配送网络拓扑结构的基础上 来完成的，而目前所能购买到的地图大多数是交通地图，通常只包含了地图道路 问简单的拓扑关系，用于配送线路优化中不仅精度不够，还无法提供线路优化要 考虑客户和地图的拓扑关系以及单行线、隔离带、左转右转等限制。当大规模配 送中心要求车辆配送到户时问题就变得较为复杂，以往的实现中依靠人工来完成 的这部分工作数据量大，需要人员相对较多，且容易出错，显然不适应解决实际 问题的需要。虽然在矢量地图中计算机程序可以实现拓扑关系的识别，但图形矢 量数据量非常庞大，关系异常错综复杂，且线路优化问题算法本身是计算量庞大， 在算法中再加入拓扑识别的过程势必更加影响计算的效率和开销。综上所述，事 先构建配送网络的拓扑结构等基础数据对于线路优化工作的进行至关重要 1 1 2 课题意义 本文致力于拓扑网络构建的研究，作为物流企业配送线路优化可靠的信息依 据，并为企业的管理信息平台作为技术支持 一、现实意义 本课题的提出来自于企业的现实需求，并且结合某城市烟草行业物流配送线 路优化的背景，具有较大的应用价值。主要表现在以下几点： l 、为物流企业集成了配送道路和客户资源 城市配送道路网络和自己企业的客户资源之间的相互独立，使得物流企业在 进行信息化建设、资源优化配置、车辆调度及线路优化中相关的分析无法直接进 行。拓扑结构的构建为运用g i s 强大的可视化功能、地理空间数据管理、地理分 析和空间分析的能力搭建了一个桥梁。本文对城市道路网络和企业客户信息进行 分析，构建配送网络拓扑，为配送资源优化分析搭建信息基础平台，对企业的客 户资源等信息和配送资源信息进行集成，真正为配送网络优化所用。 2 、计算机辅助工作，提高工作效率 将g i s 用于物流配送优化系统已经成为物流行业研究的一个热点，基于g i s 的物流配送问题的优化软件也开始应用于实践。但是在基础信息的构建上，多数 采取将客户点绑定到相近的网络节点上，对于客户群规模较小的情况( 如干线运 6 二 山东大学硕士学位论文 输车辆调度) 比较适用，实现的工作量和准确性也可以接受，但是对于客户群规 模较大的客户就是一件工作量具大而准确性难以保障的工作。目前对于这种大规 模客户群的处理方式还是不外乎绑定到路口点或者重新手工构建配送网络的方 式本文运用科学的方法、工具、技术，对于将客户信息匹配到相应的道路的规 则和方法进行研究，构建客户与道路相关联的配送网络系统，计算配送线路的最 优方案，提高工作效率和准确率、降低工作强度 3 、提供更为全面的信息，满足线路优化工作的需要 本文研究不仅提供客户点和道路间的拓扑关系，还提供了客户点、道路的非 空间属性信息，配送线路优化中需要综合考虑的道路状况：单双向、隔离带、左 右转限制等信息，满足生成合理的最优化线路的需要 二、理论意义 本课题除了有较大的应用价值外，在理论研究方面也在前人研究的基础上做 出了一定的创新性工作 + l 、采用单线对道路交通信息进行表达 本课题尝试利用单线模型对城市道路和路口的交通信息中的单行、双行、转 向限制进行表达，满足线路优化模型中考虑交通信息的约束要求。 2 、客户点到道路匹配规则的研究 本课题结合城市道路网络和客户点位置信息，对客户点和道路的匹配规则进：i 行研究，将客户点信息集成到道路网络中。这也是进行配送网络拓扑的构建的关 键技术。 3 、拓扑结构的提取和生成 本课题在拓扑结构的提取和生成中，不仅仅是简单的构建点和线的拓扑关 系，同时进行冗余节点的剔除，只保留对网络分析起作用的关键点，保障数据的 精简和准确。 本课题所作研究，与很多大规模客户群物流企业具有相同或相似的特点和规 律，因此本课题的研究成果对这些企业进行配送线路优化的研究和应用，具有很 大的参考和借鉴意义 1 2 国内外研究现状 1 2 1 网络拓扑构建研究现状 一、拓扑空间关系研究现状 7 山东大学硕士学位论文 在地理信息系统中，空间分析是建立在空间对象位置和属性表达以及对象间 复杂空间关系表达的基础上。拓扑空间关系实际上是一种对空间结构进行明确定 义的数学方法，具有拓扑关系的矢量数据结构就是拓扑数据结构。拓扑数据结构 是地理信息系统分析和应用功能所必需的，它描述了空间目标点、线、面之间的 关联、邻接和包含关系。拓扑空间关系信息是空间分析、辅助决策等的基础，也 是g i s 区别于c a d ( 计算机辅助设计) 等的主要因素，是图形空问关系的核心【2 l 。 1 9 8 8 年g l l t i n g 【3 1 以点集为基础，运用集合运算= 、n ，给出了相等( c q u a l ) ， 不相等佃q u a l ) ，包含( 幽d c ) ，相离( 伽t s i d e ) 和相交( i n l 删等拓扑空间关系 的定义p l l l l 缸1 9 8 8 ) 【4 j 将点集方法加以扩充，运用拓扑学理论中点集的边界 ( b o 咖d a r y ) 和内部( i n - t 叫i 哪的概念，给出了覆盖( o v c d 动和相邻( n e i g h b o r ) 两个 关系定义；w 啦c f ( 1 9 8 8 ) 5 】定义了相邻、相离、严格包含、相交四种拓扑空间关 系。e g e i l l l o 矗玎和f r 趾s a ( 1 9 9 1 ) 【6 】提出了一个四元组表达的拓扑空间关系描述 框架e 皇：h o f 呱1 9 9 3 ) 川引进了点集的“余”，构造了一个由点集的边界、内部、 余之间的交集组成的九元组，以此作为描述两个点集间拓扑空间关系的框架。 c l 锄钮曲i e 等人( 1 9 9 3 ) 吲在e 础f 打所定义的四元组基础上，运用维数扩展法 ( d 眦e 璐i 既t 锄d c dm g i h o d ) 即用两个空间目标内部与边界之间交集的维数，作 为描述两个点集间拓扑空间关系的框架。进一步，他们给出了二维拓扑空间关系 的最小集，这种方法形式化地描述了二维空间目标之间的拓扑空间关系【9 】。 一 目前，拓扑空间关系描述已有三种基本的方法【m l ：基于点集拓扑的四元组、 九元组和维扩展法【l l 】。这些方法已能够较好地描述两个空间对象的交集不为空的 拓扑关系，但是还不能比较好地描述两个空间对象的交集为空的拓扑关系，多种 拓扑关系描述方法在这3 种基本描述方法的基础发展起来上 在国内拓扑空间关系的描述一直是研究的重点和热点。中科院、国家基础地 理信息中心、浙江大学、武汉测绘科技大学等单位都作过大量的研究。如蔡少华 等人【1 2 1 基于4 交模型、9 交模型的g i s 中基础空间表达；李成名、陈军提出的 基于点集拓扑学的三维拓扑空间关系形式化描述，基于i 图的9 交模型【1 4 l 以及度量关系描述模型【1 5 】。潘云鹤、陈军等1 0 l 【1 6 1 等分别提出的基于m i 图 的维扩展法来描述g 塔中的拓扑空间关系。刘文宝和邓敏等基于随机目标的空间 概率分布和目标间的距离研究不确定性空间关系描述模型【l 刀。 二、网络拓扑关系自动构建研究现状 山东大学硕士学位论文 拓扑构建问题一直是g i s 中的一个难点与重点，其关键就在于图形矢量数据 量非常庞大，关系异常错综复杂，而我们在构建这些数据的拓扑关系时，不仅要 保证关系的正确建立，而且在构建过程的时间和开销方面也必须全面考虑。、由于 这一问题的复杂性，加上矢量数据拓扑关系在空间数据的查询与分析中的重要 性，国内、外对该问题一直在进行研究，研究的焦点一般主要集中是如何提高算 法与过程的效率和自动化问题。 拓扑技术是g 略中的核心技术，在大数据量中的快速拓扑技术直接决定一个 g i s 软件的优劣。中国地大的m 印g i s 软件，以它在大数据量的缓冲区分析( 即 拓扑分析) 速度为美国加汹软件的1 4 倍而倍受用户好评，从而使自己进入 国际先进g 玛软件行列【i 明 史与正等人【1 9 】论述了数据中点、线、面之间的关系，制定判定法则，判定它 们的拓扑关系或添加一定的关系，使大量杂乱无章的数据建立或转换成另一种拓 扑关系以达到处理信息的目的。根据判别规则和方法，可以实现”缓冲区分析? 、 咱动裁剪线”，咱动形成封闭面”等拓扑处理功能。 卢照敢，杨天行【2 0 】描述了空间关系自动构建技术的一般方法，从图形数据中 提取图形的拓扑关系方法的一般过程为：( 1 ) 弧段自动断开，使整幅图形无相 交或自相交弧段；( 2 ) 节点匹配：建立点、弧段关系；( 3 ) 建立多边形：以左转 算法或右转算法跟踪，生成多边形，建立多边形与弧段的关系；( 4 ) 多边形内浅 自动生成；( 5 ) 多边形嵌套关系生成，建立多边形嵌套关系树，即找出多边形包 含的“岛屿”，建立多边形与多边形之间的关系；( 6 ) 具有嵌套关系多边形的关 联弧段的左右面号调整。 张锦明，何成【2 1 铡用分区思路优化了拓扑关系自动生成的算法。杨海宏等瞄】 利用双邻点判断法对点与多边形的包含关系进行拓扑自动构建。李光辉、陈雄波、 孟遂民【2 3 1 介绍了一种基于图论的输电线路动态拓扑的构建方法。涂美义，李星c 2 4 l 介绍了以拓扑关系数据为基础的g i s 空间点、线、面对象实体模型并给出了基于 对象实体模型的自动拓扑关系模型。万程鹏，邵平凡等人【2 5 1 对公路交通网拓扑结 构进行研究并利用d e l p l l i ，m 印x 组件和a 铭s 2 0 0 3 验证了方法的准确性。张小国， 王庆，王宁【2 6 1 在分析了面向r r s 的电子地图对道路信息需求的基础上，提出了基 于路段节点连接的单路线电子地图道路网络模型，该模型可以很好地表述现实道 路网络，同时还重点研究了电子地图制作中的道路网络数据库自动生成算法。白 9 山东大学硕士学位论文 玲，谢露蓉，齐华等人【2 7 l 【2 8 】【2 9 1 分别对拓扑关系的建立算法和自动生成从不同的 方面进行了研究和改进。 这些关于拓扑关系构建的理论和自动生成算法的研究，有的为通用软件拓 扑分析提出改进，作为通用拓扑分析的参考方法，有的弥补了通用软件不能满足 针对具体某一方面需要时的缺陷，如公路网规划、道路分析、智能交通导航、电 力通信行业的管线布置等。往往不同的行业，不同的用途，会根据自己不同的需 要获得针对性的拓扑结构。拓扑构建方法正好迎合了这种需要，在具体的情况下 也需要进行相应的改进。 1 2 2 线路优化问题研究现状 国外一些学者对物流配送车辆优化调度问题作了大量而深入的研究，一般可 以归结为、仅腼c k r o u t i r 喀p r o b l 锄s ( 冲) 和v c 舡c k s c h c d u l i i l g p b l 锄( v s p ) 。 d 锄t z i g 和黜删斌【3 0 l1 9 5 9 年首次将运筹学理论研究和物流配送活动紧密联系 起来，提出了车辆配送模型( v c 晒d cr o 嘶p m b l 锄，冲) ，很快地，引起了运 筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的 专家与管理决策者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问 题【3 l 】。 目前国内外用于解决该问题的数学方法可以分为以下几类： ( 1 ) 精确优化方法运用线性规划( 包括专门处理的分枝定界法、割平面 法、标号法等) 和非线性规划技术，来求取最优决策在对冲问题研究的早 期，主要从单源点( s i n g l e d 印o t ) 派车如何用最短路线或在最短时间内对一定 数量需求点运输的调度问题，主要着眼于最优算法。但随着运输系统复杂化和对 调度的目标数目要求增加，问题的求解运算复杂度呈指数级增长，使得对系统精 确解的求解越来越困难，甚至不可能。因此，精确优化方法及其算法现在多只用 于运输调度的局部优化问题的求解 ( 2 ) 启发式方法。它是指通过经验法则来求取运输过程满意解的数学方法 启发式方法能同时满足详细描绘问题和求解的需要，较精确优化方法更为实用 其中最具代表性的是6 0 年代由c l a r l 和w 啦汪【3 2 1 提出的节约法( s a v i i l g m c i h o d ) 许多成功的车辆调度软件就是根据该方法或其改进方法来开发的。【缸 和k 册1 i n g l l 缸【3 3 1 提出，并由c m s t o f i d 髓闪和g i l b e r tia 刚e 【3 5 1 等人所推广的分 支交换探索法，该算法始终保持解的可行性面又力图向最优化目标逼近。g i l l e t 1 0 山东大学硕士学位论文 和m i l l e r ( 3 6 蟪出的扫描法( s w e 印m 锄o d ) 先把节点或弧的需求进行分组或划群， 然后对每一组按旅行商问题( t s p ) 求解，设计出一条经济的线路。西南交大的 李掣3 7 】针对有时问窗的车辆路线安排问题提出了一种利用节约法的启发式算法 ( 3 ) 模拟方法。利用数学公式、逻辑表达式、图表、坐标图形等抽象概念 表示实际运输系统内部状态和输入输出的关系，以便通过计算机对模型进行实 验，通过实验取得改送善运输系统或设计新运输系统所需信息，虽然模拟方法在 模型构造、程序调试、数据整理方面工作量大，但由于运输系统结构复杂，不确 定情形多，模拟方法仍以其描述和求解问题的能力优势，成为复杂运输调度系统 建模的主要方法。 ( 4 ) 人工智能方法主要有模拟退火算法、人工神经网络、遗传算法、蚂 蚁算法、粒子群算法等新技术。它们为解决大规模、多目标车辆调度问题提供了 新了辅助手段。浙江大学蔡延光【3 8 l 等人运用模拟退火算法和遗传算法求解多重车 辆调度问题，并将其集成为智能算法库，作为设计智能运输调度系统的依据；! ：东 北大学的张潜【3 9 l 等人提出一种先用优先级综合聚类分析法将客户分类，再用带有 控制开关系统的改进遗传算法求解多目标v l 坤的优化方法；党国英【柏】等人利用 蚁群算法进行模糊运算，以寻求最小成本的最佳车辆路径；华中科技大学李宁【4 1 l 等人将粒子群算法运用于车辆路径优化问题，并进行了实验研究，证明了粒子算 法在求解车辆路径问题的有较好的性能。 ? 黩 由于在物流分析决策过程中，8 0 以上的决策信息与空间地理有关，而g i s 具有强大空间数据处理和分析能力，以及独有的空间分析决策功能，并在实践中 证明了，g i s 可以在其中发挥重要的作用。 目前最成熟的基于g i s 技术的物流配送管理软件是e s m 公司开发的 a r c l o g i s t i c ，在国外物流企业已经得到广泛应用并为企业取得明显效益。其方案 便于企业基于属性数据和图形数据的结合对分区进行科学、规范的管理，并且可 以优化车辆与人员的调度，最大限度地利用人力、物力资源，使货物配送达到最 优化。 在国内，大部分还处于理论上研究阶段，也有一些研究者从实用开发角度出 发对心进行了研究，提出了以g i s 为平台通过集成v 】冲算法开发车辆路径系 统的设计思想。北京杰合伟业软件公司构建了国内第一个城市物流配送解决方 案，综合了g i s 、g p s 等技术，适用于销售企业、超市配送中心、区域物流配 山东大学硕士学位论文 送等。比较成熟的是国内以“零库存”而闻名的海尔集团，采用g i s 等技术建 立了自己的“海尔物流监控调度系统”，工作人员在调度中心，就能够监控全国 范围内所有集团内部物流车辆，实现车辆实时定位、运单动态跟踪、远程调度等， 成功运用了b o r l 锄d e n t e r p r i s e s e n ，盱( b e s ) 的j 2 e e 、c o r b a 、g i s 和g p s 技 术。还有一些公司开发的许多基于g i s 的系统，如物流配送车辆优化调度系统、 物流配送系统信息平台，以及对物流配送系统的综合研究等等。目前已经投放市 场的路径软件有：武汉测绘科技大学奥发公司的“商业送配货地理信息系统”和 北大方正的“路径规划系统”，它们只能满足用户最基本的需要，难以解决出现 不确定性信息或问题约束较为复杂时的问题【4 2 】。 目前比较具有代表性的配送路径优化方面的软件还有金启元公司开发的金 启元城市物流配送路径优化解决方案、白沙物流的白沙物流烟草配送综合g i s 及路径优化系统、杭州商学院的企业物流配送线路优化信息系统等，都是针对城 市物流配送中的车辆调度和线路行程问题提出的解决方案，在实践中也体现出了 一定的成效。 耳前的研究在解决小批量客户问题中效果较为明显，在大规模客户群优化的 计算效率上还有待进一步研究寻找高效、实用的算法。此外与g i s 的结合方面存 在着诸多问题，大多只是把g i s 作为一个显示的背景，并没有有效的利用g i s 提供的信息。 1 3 本文主要研究内容 1 3 1 主要研究内容 纵观国内外配送车辆路径问题，都是在配送点和道路拓扑网络信息的基础上弘 进行网络分析和优化。本文在分析城市配送特点基础上，研究配送网络拓扑结构 的构建方法，并应用于一个基于g i s 的面向大规模城市物流配送的线路优化系 统。具体可以分为如下两部分工作： 一、配送道路网络拓扑构建研究 主要任务是在充分分析城市道路特点和客户分布情况、配送线路优化对拓扑 结构信息的需求以及学习已有研究成果的基础上，将点到线的匹配技术应用于配 送网络拓扑结构，对自动构建的方法进行研究，并在拓扑结构提珞生程结合实际 情况进行部分改进。主要研究内容为： l 、城市道路网络模型表达的研究； 山东大学硕士学位论文 2 、配送网络拓扑构建的算法研究，探讨客户点集成到道路网的拓扑构建方 法和实现步骤，以及对拓扑提取和生成方法的改进； 3 、采用v i m a lb 勰i c 语言和m 即x 控件实现网络拓扑结构自动构建模块 二、配送网络拓扑结构在配送线路优化中的应用研究 另外一项任务是结合烟草行业特点，分析城市物流配送中线路优化问题模型 ， 和求解方法基础上，通过系统流程的分析，提出切合实际系统集成方案，对拓扑 结构构建功能在配送线路优化系统中的应用进行了深入探讨，实现了空间和属性 数据库的统一存储管理、电子地图基本操作功能、最短路径查找功能组件模块。 具体工作如下： ， l ，系统的开发方式和开发环境的确定： 2 ，配送线路优化数学模型及求解方法； 3 ，配送线路优化系统的集成方案的设计，模块的编程实现。 1 3 2 本文组织结构 第一章绪论：论述了本文研究的背景、研究意义、国内外研究现状和本文 研究内容； 第二章城市道路网络模型研究。对图论中的网络模型和g i s 中的网络数据 模型进行研究，提出单线表达城市道路网络的模型； 第三章本文的重点部分。配送网络拓扑构建的算法研究，探讨客户点集成 到道路网的拓扑构建方法和实现步骤，以及对拓扑提取和生成方法的改进； 第四章配送道路网络拓扑自动构建模块开发。分析配送道路网络拓扑自动 妁建的开发环境，设计模块功能，并进行实现； 第五章网络拓扑构建在物流配送线路优化系统集成方案中的应用分析。以 某配送中心线路优化项目为实例介绍配送线路优化系统集成模块和系统流程，及 系统模块的实现； 第六章总结及展望。对论文的研究工作进行总结，提出进一步工作方向 山东丈学硕士学位论文 第二章城市道路网络模型 道路网络能为最短路径计算、地图匹配等许多算法提供基础数据，为将其转 换为计算机能够识别的信息和高效率地进行路径分析，本章首先将现实中的道路 网络实体抽象化为按节点和弧的关系构成的网络图。这就需要对原始道路图进行 预处理，通过详细采集试点市区的所有道路信息，本章建立了面向城市配送的道 路网络模型。 2 1 图论中的网络模型 图论【4 3 1 起源很早，远在十八世纪就出现了图论问题，如著名的哥尼斯堡 ( 1 【c 嘶g s b c i g ) 七桥问题就是当时很有名的图论问题。1 7 3 6 年，瑞士数学家列昂 啥德欧拉( 蛐a me l l l 盯) 发表了图论的首篇论文，解决了哥尼斯堡七桥问 题。由于欧拉的研究奠定了图论的基础，目前一般均公认欧拉为图论之父。 图论是研究由线连接的点集的理论点集中的点称为节点，连接某些点对的 线称为边一些由节点及边构成的图称为线圈。在线图中，节点的位置分布和边 的长短曲直都可以任意描画，这并不改变实际问题的性质，关心的是它有多少个 节点，在哪些节点间有边相连，以及整个线图具有的某些特性。 线图可以用来表示和研究一个系统的结构及它的性质。例如，若节点表示运 输站点，边表示站点间的路线，我们便可以通过相应的线图来研究道路网络中货 物的运输问题。 2 1 1 相关概念与定义 定义2 1 在图论中，一个图g 是指由非空有限集合联g ) 和坎g ) 中某些元素 的无序对的集合联g ) 构成的二元组( y ( g ) ，耳g ) ) 。坎g ) 称为图g 的顶点集，其 中的元素称为g 的顶点。觑g ) 称为g 的边集，其中的元素称为g 的边。有时， 也记为降h g ) ，房耳g ) 。 f 色 y l ，屹，) ( 2 - 1 ) 层= m ，叼 im nb y ( 2 2 ) ， 设g = ( n 毋是一个图，若p = i i 岣e ，则称顶点m 和顶点岣是边e 的起始 节点也称顶点m 和顶点屹是相邻的，p 与m 、岣是关联的。若旬、吃b 且 1 4 山东大学硕士学位论文 p l 和晚有公共的顶点，则称自与也是相邻的。 两个端点重合的边称为环如果有两条边的端点是同一对顶点，则称这两条 边为重边。既没有环也没有重边的图称为简单图。一个图的边仅在端点处相交，j 则称该图为平面图。 一个图的点数称为该图的阶图中与顶点 i j 相关联的边的数目( 相关联的环 算作两条边) 称为顶点v 的次( 也叫做度) ，记为撕) 称硬) 为偶数的顶点m 为偶点，称碳协为奇数的顶点为奇点，称d m ) = o 的顶点，i i 为孤立点可以得 出下面的定理。 定理2 1 设g 警( nd 是一个图，则有： d ( v ) = 搁 ( 2 - 3 ) m y 如果图g 的某些顶点和边可以排成非空的有序列辟k l 够ln 氏飞，其中m k g ) ( 0 i k ) ，岛联g ) ( 1 q k ) ，并且自= v i 1 m 则称矿为g 的一条途径。 称为矽的起点， 1 c 称为矿的终点，其余的顶点称为w 的内部顶点。有时将途径 简单的记为v l h ，但有时v o ，1 h 表示的不只是一条途径，只有在简单图中 v ov 1 氓才表示唯一的途径如果途径w 中的边互不相同，则称矿为g 的迹。 如果途径矿中的顶点互不相同，则称该形为g 的链。 如果图g 和图日满足h 印坎g ) ，目( 联g ) ，则称日是g 的子图，记， 为王，c g 。如果埏g ，且h 两= h g ) ，则称日为g 的支撑子图。 如果对于图g 中的任意两个顶点 i i 和崎，g 中都存在m 、 ：i ) 链，则该图g 为连通图。不是连通的图称为非连通图。 如果题= g ，且胃是连通图，则称日是g 的连通予图。如果在图g 中不存 在别的连通子图日使得z 廷，妊啊，则日称为g 的极大连通子图，又称为连 通分支。连通图有且只有一个连通分支，而非连通图存在不止一个连通分支。 定义2 2 在图论中，一个有向图d 是指由非空有限集合阳) 和k d ) 中某些 元素的有序对的集合彳( d ) 构成的二元组( k d ) ，4 呻弛) 称为有向图d 的顶 点集，其中的元素称为d 的顶点。4 ( d ) 称为d 的弧集，其中的元素称为d 的弧。 有时，也记为降印) ，4 利( d ) 。 p 刍 v l ，耽， ( 2 - 4 ) a i “ | i ，码，jm n 岣矿， ( 2 5 ) 山东大学硕士学位论文 爿( k ) 必 乃 1 0 圪 图2 l 有向图 有向图d = ( e 彳) ，如果彳( d ) 中的元素4 与y ( d ) 中的某两个元素构成的有 序对 i i ，岣) 相对应，记口= ，嵋 ，其中边的始点称为弧尾( - r a i l ) ，终点称为 弧头( h e a d ) ，即m 称为口的弧尾，叼称为口的弧头；4 称为 i i 的出弧，称为岣 的入弧。顶点 ，在d 中出弧的数目称为 ，的出度，记为矿( v ) ；顶点1 ，在d 中入 弧的数目称为v 的入度，记为扩( v ) 则有下面的定理： 定理2 2 设d = ( 阼彳) 是一个有向图，则有： d + ( v ) ；d - ( v ) = i 爿i ( 2 石) * rm 弧尾和弧头重合的弧称为环。若两条弧有相同的弧尾和弧头，则称这两条弧 为重弧。既没有环也没有重弧的有向图称为简单有向图。如果把有向图的每条弧 “，叼) 用边 j i 崎代替，得到的图称为d 的基础图。可以利用基础图的概念来描 述和定义有向图的许多概念，如有向图的连通性、链、途径等。 在有向图中常将有向链称为路，称有向圈称为回路如果在有向图中任意两 个顶点 i i 和均，d 中既存在m ，) 路，也存在心，v ) 路，则称d 为强连通。 定义2 3 给定有向图d n ) 后，如果对d 中的每条弧口赋一个实数m 和) ， 州4 ) 通常称为弧口的权。w 是上的一个实值函数，称为d 的权函数。赋权的有 向图d 称为网络或赋权有向图，记为d = ( n 彳，w ) 。有向图d 称为网络的基础 有向图，必要时可以给每条弧赋以多个权。同样，也可以给节点赋权，这样得到 的网络称为点权网络。相对于点权网络，给边赋权的网络就称为边权网络 同样可以考虑赋权的图赋以权w 的图g 称为无向网络或赋权图，记作 g 气ne ，w ) 。如果把无向网络g b ( ne ，w ) 中每条边萨 l 岣e 代之以一对弧， 这样得到一个相应的网络呵n 彳，w ) 。 定义2 4 给定一个有向图d = ( n 彳) ，c 是定义在爿上的非负函数，对一切 1 6 山东大学硕士学位论文 口彳，c 缸) 称为弧口的容量。若口气m ，岣) 4 ，则记c 0 ) = q 称网络d 呵n 一，c ) 为容量网络。在d 中指定两个顶点v i 和m ，v l 称为d 的发点，h 称为d 的 收点。 设，是容量网络d 的弧集一上的一个实函数，对一切口气i j ，岣) 彳，记如) = 响，如果函数产 ，叼) 彳 满足守恒条件： 乃一乃= o 对一切v i v l v l ，v t ( 2 - 7 ) “，v j ) i ( v l ) l 则称厂是d 上的一个流。此时，五称为，通过弧m ，坳上的流量，称 兀一厶 ( 2 - 8 ) “) i “，v j ) l 为，的流值，记为“，) 2 1 2 网络的表示 图和网络的表示方法有两种，种是用图形方法，另一种是矩阵方法。图形 方法是常用的表示方法，该方法形象直观，符合人眼的视觉感受，顶点和边的连 接关系清晰明了，对于简单的图或网络，有利于分析。 用图形表示的图难以用计算机来存储和管理。为了把图输入计算机中，图论 中常常使用矩阵来记录图。由于研究问题的出发点不同，图的矩阵表示也有多种 形式，最基本的矩阵有关联矩阵和邻接矩阵。 关联矩阵，设g n 习是一个无空环图，取 一 f 1 ，若顶点v ；与边e j 相关 2 1 0 ，否则 。 ( 2 9 ) 这样得到的i 川旧矩阵麒g ) = ( m 日) 就称为图g 的关联矩阵关联矩阵朋【g ) 完整地表达了图g 中顶点与边的关联关系 m ( g ) = 岛岛 lo 1l ol 00 关联矩阵旭g ) 具有下列性质： 1 7 h 吃b 心 岛r=1叫叫 气o o o 2 略l o o 1 气o o i l 山东大学硕士学位论文 每一列恰好有两个非零元素l ； 每一行的元素之和等于对应顶点的度； 将矩阵中的两行或两列互换，相当于在同一个图中将对应的顶点或边的标 号互换； 如果g 有 ，个连通分支g i ，伤g 0 ，w 2 那么，通过适当地排列g 的 顶点和边所对应的行和列，g 的关联矩阵可以写成块对角矩阵。 邻接矩阵，设g = ( n 点) 是一个无空环图，取铂等于g 中顶点砧和的之间 的边数，则i 川阶方阵彳( g ) = 0 日) 称为g 的邻接矩阵： 一( g ) = 巧巧吩 02l 2ol 1lo lol u l 难 同样，有向图也有关联矩阵和邻接矩阵。 有向图的关联矩阵，设d ；( 巧彳) 是非空无环有向图，定义 f 1 ，若顶点v i 为边a 的弧尾 m # = 一l ，若顶点v i 为边a j 的弧头 ( 2 一l o ) 【o ，否则 则l 明陋耀阵j | l 艇d ) = ( m i ) j 竞称为d 的关联矩阵。 有向图的关联矩阵也有相应的性质： 肘中每一列恰好有两个非零元素，一个是l ，另一个是一l ： 埘) 中每一行的l 的个数等于对应顶点的出度，一l 的个数等于对应顶 点的入度； 肘【d ) 中的两行或两列互换，相当于在同一个图中将对应的顶点或弧的标 号互换； d 的关联矩阵也可以写成块对角矩阵。 有一向图的邻接矩阵，设d = ( k 彳) 是一个非空无环有向图，取取鳓等于d 中顶点i i 为尾岣为头间的弧的个数，则i v i 阶方阵一( d ) = 幽) 称为d 的邻接矩阵。 2 1 3 图论中的网络模型的不足 在图论中研究的图和网络尽管在原型上是对现实世界中的网络，特别是对道 1 0 山东大学硕士学位论文 路网络的模拟和抽象，也是对现实网络的分析、研究和利用，但受限于技术手段， 图论中的网络在模型建立和分析利用上都存在严重的不足，随着对网络分析需求 的不断扩大和相关技术的飞速发展，其不足性越来越突出，己经成为限制网络分 析发展的主要障碍。其不足之处主要表现在以下几个方面： 1 、网络模型单一 图论中的网络主要被抽象为无向网络和有向网络，构成网络的网络元素只简 单的分成顶点和边由于网络模型过于简单，不能完全表达现实世界中各种网络 所具有的共同特性，同时也体现不出具体地理网络的个体属性。 2 、表示形式简单 图论中的图多采用图形和矩阵的方式来表示网络，如果网络本身非常小，构 成网络的顶点和边较少时，用该方法来表示网络简单明了、关系清晰。但地理网 络本身相当巨大，构成的地理网络元素也决非人力所能管理，这时图论所采用的 表示形式无法管理地理网络 3 、分析内容缺乏 一般在图论中研究的网络除了考虑关联关系外，通常还会再考虑1 - 2 种权值 或属性，比如距离、费用、损耗等。而在研究实际的地理网络时，通常需要考虑 多种权值或属性，原有网络模型无法提供有效的解决 4 、数据精度低 受数据获取技术的限制，在图论中研究的网络更多的趋向于定性的描述和粗 略的估计，数据来源和精度无法保证。 2 2g i s 中的拓扑关系和网络模型 地理信息系统( g g m i ch 触m a t i s y s t 锄，简称g i s ) 是一类获取、处 理、分析、表示并在不同系统、不同地点和不同用户之间传输空间数据的计算机 应用系统。地理信息系统处理、管理的对象是多种地理实体和地理现象数据及其 关系，包括空间定位数