（管理科学与工程专业论文）基于开源WebGIS的物流配送路径选择.pdf

西南交通大学硕士研究生学位论文 第1 i 页 摘要 物流是现代企业管理中的重要组成部分，素有企业的“第三利润来源 之称。 在物流系统当中，运输、配送处于核心地位，是物流配送优化的关键所在。作为 物体在时间和空间上的位移，物流配送对地理空间具有较大的依赖性，也必然涉 及到多方面的地理因素。将g i s 应用于物流配送系统中，可大大加强对物流过程 的全面控制和管理，减少物流运输成本，提高企业的收益。传统g i s 软件和数据 库软件的价格非常昂贵，而开源软件由于其免费性和安全性，可以减少物流系统 的开发费用。 本文参考了国内外的g i s 在物流配送中的应用研究现状、开源g i s 软件的发 展现状，以及国内外对物流配送路径选择问题的研究现状，在此基础上提出了基 于开源w c b g i s 的物流配送路径选择解决方案，并以成都市的路网数据进行了实 证研究，证明了开源w e b g i s 应用到物流配送系统路径规划中的可行性。 本研究重在搭建开源w e b g i s 平台及其在物流配送路径选择方面的应用，着 重介绍了g i s 软件的国内外发展状况，引入了g e o s e r v e r 、o p e n l a y e r s 、p o s t g r e s q l 、 p o s t g i s 、t o m c a t 和e c l i p s e 等一系列开源软件，构建了由开源地图服务器、开源 w e b 服务器和开源空间数据库服务器组成的三层架构w e b g i s 平台，实现了基于 电子地图和开源软件的物流配送最短路径选择。此外，由于传统的路径规划问题 多是有固定的配送点，但在现实中，物流配送常常具有客户规模不确定的特点， 本研究在考虑该问题和经典的求解算法的局限性的基础上引入了遗传算法，经过 实验得到了较优的遗传算法种群和代数，并与经典的精确求解算法进行了对比， 实现了根据配送点规模的算法动态切换。 关键词：物流配送：w e b g i s ；开源软件；g e o s e r v e r ；o p e n l a y e r s ；p o s t g i s ：j s p 西南交通大学硕士研究生学位论文 第li l 页 _ _ _ 詈詈量皇量量曼皇置鲁_ _ _ 寡詈皇量量巴鼍置鼍! 皇暑皇! ! 詈皇詈暑詈量_ 量置皇曼詈詈曼皇皇岂曼皇詈量置皇置量皇_ e 曼曼曼鲁e 皇掣i l l 皇! 皇篁曼曼皇鼍詈舅 a bs t r a c t l o g i s t i c si s a ni m p o r t a n tp a r to fm o d e r ne n t e r p r i s em a n a g e m e n t ，w h i c hi s c o n s i d e r e da s “t h et h i r dl o c a l i t yo fp r o f i t ”o fm o d e r ne n t e r p r i s e s t r a n s p o r t a t i o na n d d i s t r i b u t i o n w h i c ha c t sa st h eh e a r to fal o g i s t i c ss y s t e m ，i st h em o s ti m p o r t a n t b o t t l e n e c ko fl o g i s t i c sd i s t r i b u t i o no p t i m i z a t i o n t h en a t u r eo fl o g i s t i c sd i s t r i b u t i o n i st h e s p a c e t i m eb a s e dd i s p l a c e m e n t o fo b j e c t s 。w h i c hh a sd e t e r m i n e dt h e d e p e n d e n c eo fl o g i s t i c sd i s t r i b u t i o no ng e o g r a p h i c a ls p a c ea n dg e o g r a p h yf a c t o r s f o rt h a tr e a s o n ，t h ea p p l i c a t i o no fg i st e c h n o l o g yi nl o g i s t i c sd i s t r i b u t i o nw i l lb r i n g a b o u tg r e a ti m p r o v e m e n t si nt h eo v e r a l lc o n t r o la n dm a n a g e m e n to fl o g i s t i c s d i s t r i b u t i o na sw e l la sr e d u c t i o ni nl o g i s t i c st r a n s p o r t a t i o nc o s t sa n da c h i e v e e f f i c i e n ta n dh i g h q u a l i t yd i s t r i b u t i o ns e r v i c e s ，a n df i n a l l yi n c r e a s et h ee n t e r p r i s e s b e n e f i t t r a d i t i o n a lg i sa n dd a t a b a s es o f t w a r ei s v e r ye x p e n s i v e w h i l et h e o p e n s o u r c es o f t w a r ei sc o m p l e t e l yf r e eo fc h a r g e t h a n k st oi t se x c e l l e n ts e c u r i t y a n dz e r oc o s t s ，t h ea p p l i c a t i o no fo p e n s o u r c es o f t w a r ec a nr e d u c et h ed e v e l o p m e n t c o s t so fl o g i s t i c sm a n a g e m e n ts y s t e ms i g n i f i c a n t l y b a s e do nt h er e f e r e n c eo ft h es i t u a t i o no fs t u d i e sa b o u tt h ea p p l i c a t i o no fg i s t e c h n o l o g yi nl o g i s t i c sa n dr o u t ep l a n n i n gi nd i s t r i b u t i o nb o t ha th o m ea n da b r o a d ， a sw e l la st h ed e v e l o p m e n ts i t u a t i o no fo p e n s o u r c e dg i ss o f t w a r e ，t h i st h e s i s c o m e su pw i t har e s o l u t i o no fr o u t ep l a n n i n gi nd i s t r i b u t i o nb a s e do no p e n - s o u r c e d w e b g i s t h i st h e s i sa l s oc a r r i e so u te m p i r i c a ls t u d ya n dp r o v e dt h ef e a s i b i l i t yo f t h ea p p l i c a t i o no fo p e n s o u r c e d ，e b g i si nr o u t ep l a n n i n gi nd i s t r i b u t i o ns y s t e m w i t ht h er o a dn e t w o r kd a t ao fc i t yc h e n g d u t h i st h e s i sc o n c e n t r a t e so nt h ec o n s t r u c t i o na n di m p l e m e n to fo p e n - s o u r c e d w e b g i sp l a t f o r i l la n dt h ea p p l i c a t i o no ft h i sp l a t f o r mi nl o g i s t i c sd i s t r i b u t i o nr o u t e p l a n n i n g t h et h e s i sg i v e sa no v e r v i e wo ft h ed e v e l o p m e n ts i t u a t i o no f gi ss o f t w a r e b o t ha th o m ea n da b r o a d b yi n t r o d u c i n gas e r i e so fo p e n s o u r c e ds o f t w a r es u c ha s g e o s e r v e r , o p e n l a y e r s ，p o s t g r e s q l ，p o s t g i s ，t o m c a ta n de c l i p s e ，t h i st h e s i ss e t s u pat h r e e t i e r e dw e b g i sp l a t f o r l t lw h i c hi sc o m p o s e do fo p e n s o u r c e dm a ps e r v e r ， w e bs e r v e ra n ds p a t i a ld a t a b a s es e r v e ra n dc o m e su pw i t has o l u t i o no fl o g i s t i c s d i s t r i b u t i o nr o u t ep l a n n i n gb a s e do ne l e c t r o n i cm a pa n do p e n - s o u r c es o f t w a r e b e s i d e s t r a d i t i o n a lr o u t ep l a n n i n gu s u a l l yf o c u so nf i x e dd e m a n dp o i n t s ，b u ti n r e a l i t y , t h es c a l eo fc u s t o m e r si s o f t e n f l u c t u a n t t a k i n gt h i sp r o b l e ma n dt h e l i m i t a t i o no fc l a s s i ca l g o r i t h o mi n t oc o n s i d e r a t i o n ，t h et h e s i st a k e sa d v a n t a g eo f g e n e t i ca l g o r i t h ma n de d u c e sp r o p e rc o n t r o l sp a r a m e t e r ss u c h a sp o p u l a t i o na n d g e n e r a t i o n sb ye x p e r i m e n t sa sw e l la sc o m p a r i s o n sw i t hc l a s s i ce x a c ta l g o r i t h m ，a n d f i n a l l yp r o v i d e sas o l u t i o nt h a tc a ns w i t c ht h es o l v i n ga l g o r i t h o ma c c o r d i n gt ot h e s c a l eo fd e m a n dp o i n t s k e yw o r d s ：l o g i s t i c s d i s t r i b u t i o n ，w e b g i s ，o p e n - s o u r c es o f t w a r e ，g e o s e r v e r , o p e n l a y e r s ，p o s t g i s ，j s p 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密z 使用本授权书。 ( 请在以上方框内打“v ”) 学位论文作者签名：动矧 刁顿 日期： t , o o 。埽 指导挪签名：己峭屯 醐一“7 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： 1 、引入开源软件，并在此基础上实现了开源g i s 与开源w e b 平台的集成，搭建 了基于纯开源软件的w 曲g i s 平台，并将其应用到物流系统路径规划中，实现了基于 b s 模式的开源w 曲g i s 与路径优化的集成； 2 、运用开源w e b 服务器和j s p 技术，兼顾效率和可行性，在遗传算法和f l o y d 算 法的基础上实现了基于城市路网的多点配送最短路径选择，实现了根据配送点的规模 自动切换算法；在d i j k s t r a 算法基础上考虑了单点配送、和带一定限制条件的单点配送 等几种情况； 3 、通过地图服务器的w f s 服务，实现了根据路径计算结果动态构造空间查询， 并对服务器返回的数据进行解析，以此为基础在页面地图上进行最短路径标记。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰 写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。 本人完全了解违反上述声明所引起的一切法律责任将由本人承担。 学位论文作者签名：枞移牙饭 日期：聊，谚 西南交通大学硕士研究生学位论文第1 页 1 1 研究背景 第1 章绪论 物流是现代企业运营中的重要组成部分，经过半个多世纪的演变，己经有了很大的 发展与进步，由于物流对企业利润的巨大贡献，使其成为了现代企业的“第三利润来源”。 从上世纪8 0 年代起，随着经济全球化进程的不断推进、科技水平的快速提高以及社会 分工的细化，世界上一些发达国家开始对物流的实施和管理中的各个环节进行整合，物 流活动开始成为一个信息化、系统化的过程。上世纪9 0 年代后，欧美发达国家开始出 现各种专门的物流服务企业，物流产业逐渐形成，并成为这些国家服务业中的重要领域 【l 】 o 由于发展时间较短，我国的物流业尤其是物流管理目前还比较落后【2 】。由于物流对 企业的运营具有重要的作用，如何降低物流成本已成为近年来各个领域专家学者关注的 热点，不少企业也致力于通过物流管理来减少企业在物流这一块的成本，从而提高企业 的整体竞争力 3 】。 在整个物流活动过程当中，运输、配送是最重要的一环，是物流配送优化的关键所 在【4 j 。由于物流本身就是物资在时间和空间上的运输和移动，因此它必然要依赖于地理 空间信息，而g i s ( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，地理信息系统) 技术正是为地理空 间信息的分析和管理而生的，因此，运用g i s 技术来协助物流配送管理，不仅可以对 物流配送活动的全过程进行优化和改进【3 】，还可以减少物流运输成本，提高企业的收益。 但是，g i s 软件和数据库软件( 如o r a e l e ) 的费用是非常昂贵的，而开源软件由于其免 费性和安全性，更能减少企业对物流系统的开发费用。 1 2 国内外研究现状分析 1 2 1 国内外地理信息系统研究现状分析 地理信息系统( g i s ) 是一种以空间数据库为基础的决策支持系统，它具有其他信 息系统所没有的空间信息输入、存贮、查询、维护和输出等功能 5 1 。g i s 系统将现实世 界抽象为一系列的地理空间要素 6 1 ，并通过计算机建立空间数据库，对各种地理空间要 西南交通大学硕士研究生学位论文 第2 页 素的空间位置及其属性数据进行处理，并加以存储和分析，再通过地图将地理要素的各 种数据表现出来。现在，g i s 技术已经广泛应用于许多商业领域，并且仍在不断发展。 由于g i s 可以提供友好的图形用户界面，还具有强大的空间分析功能，并且用户只需 通过鼠标就可以对地理要素及其属性信息进行查询、分析以及处型7 1 ，因此g i s 技术几 乎可以用在所有与空间分布相关的领域中。 g i s 最早萌芽于北判引，它的真正繁荣是从8 0 年代开始的。由于8 0 年代后出现了 性能较高而且价格适中的新一代计算机，因此g i s 的广泛使用从此具备了硬件基础， 而g i s 的普及又反过来刺激了其理论和技术的发展和完善，开始在土地规划【9 】、自然灾 害预测和评估 1 01 1 1 、野生动植物生境分析【1 21 3 1 和森林管理【1 4 1 等问题的解决中扮演重要角 色。近些年来，g i s 的使用范围逐渐扩展到犯罪制图与犯罪预测分析【l5 1 、救急与应急规 划【1 6 1 以及交通规划 1 刀等领域。同时，以g i s 技术为关键技术基础的数字化城市【1 8 1 建设 也开始兴起，并引起了各个国家和地区政府的极大兴趣，此外，g i s 在网络分析、企业 选址问题以及路径规划等领域的应用也成了人们的研究热点。随着 n t c r n c t 和w e b g i s 技术的发展，一些网站开始提供网上电子地图浏览服务( 比如意大利的群众保护部门就 在2 0 0 4 年在专门的网站上发布了一张公开而透明的地震灾害地图【1 6 】) 。在g i s 软件的 研发方面，西方国家也取得了很大的成就，研制出了一批优秀的地理信息系统软件，如 a r c l n f o 、a r e v i e w 、a r c c a d 、m a p l n f o 、m a p g u i d e 、g e o m e d i a 等等。 g i s 的研究和开发在我国起步较晚，到上世纪7 0 年代末我国才开始展开g i s 的启蒙 研究。到8 0 年代后，我国开始大力发展g i s 技术，在其理论、规范的研究及软件开发等 多个方面都取得了很大的进展。9 0 年代后，我国研制出了自己的g i s 商业软件，其中比 较有代表性的有g e o s t a r 、s u p e r m a pg i s 、m a p g i s 等。1 9 9 4 年4 月，中国地理信息系统 协会( c a g i s ) 成立，该协会致力于开展g i s 的学术和管理交流活动，加强了国内c b g i s 组织的联系及国际g i s 技术的交流合作，我国g i s 领域的技术和研发能力开始跻身于世 界先进行列，g i s 的应用也得到了极大的推广和普及【l9 1 。 1 2 2 开源gis 软件发展现状分析 地理空间开源基金会( 简称o s g e o ，o p e l ls o u r c eg e o s p a t i a lf o u n d a t i o n ) 是一个国 际非营利性组织，其使命是支持开源g i s 软件的开发、推广和普及。o s g e o 基金会所 支持的项目有很多，其中一些( 如m a p s e r v e r , g r a s s 等) 在开源地理信息软件领域已 成为主流。到目前为止，该基金会已经发展了多个重要的g e o s p a t i a l 软件项目，其产品 覆盖了从桌面端软件到服务器端软件的多个方面，还包括了大量的空间数据中间件【2 0 】。 1 2 2 1 开源g is 桌面端软件 所谓桌面端g i s 软件，是指以电子地图为基础，重在其他信息的分析、统计并将 西南交通大学硕士研究生学位论文 第3 页 处理结果在电子地图上表达出来的面向个人用户的桌面地理信息系统。o s g e o 的g i s 桌面软件包括g r a s s ( g e o g r a p h i cr e s o u r c e sa n a l y s i ss u p p o r ts y s t e m ) 、q g i s ( q u a n t u m g i s ) 等目前极负盛名的项引2 0 1 。 g r a s s 是一个大型g i s 系统，其功能包括空间数据管理与分析、图像处理、地图 制作、空间建模等等。目前g r a s s 已经在全球的学术和商业领域中得到了广泛使用， 许多政府机构和环境顾问公司也在使用g r a s s 。 q g i s 也是个用户友好的跨平台开源地理信息系统，利用q g i s 可以对不同格式和 投影系统的矢量数据和栅格数据进行查看和叠加，而不需要转换为某种内部格式或通用 格式，可以创建、编辑和导出空间数据，还可以通过插件进行空间分析等等。此外，由 于q g i s 拥有良好的可扩展性，用户还可以通过各种插件来使q g i s 更好地满足自己的 要求。 除了上述的两种开源桌面g i s ，还有一个重要的开源g i s 桌面端软件u d i g ( u s e r - f r i e n d l yd e s k t o pi n t e r n c tg i s ) 。u d i g 开源项目是一个基于e c l i p s er c p 2 q 的胖客 户端开源桌面应用程序架构，其目标是提供一个完全基于j a v a 的桌面g i s 数据存取、 编辑和浏览解决方案。u d i g 致力于为g i s 用户提供友好的界面以及用户熟悉的制图环 境，可在w i n d o w s 、m a co s x 及l i n u x 平台上运行。 1 2 2 2gis 开源服务器端 m a p g u i d eo p e n s o u r c e 是一个基于w e b 的平台，用户可通过该平台进行w e b 地图 应用程序及地理空间w e b 服务的开发和部署。m a p g u i d e 包含了一个x m l 数据库，并 可支持大多数的空间数据文件格式。m a p g u i d e 可部署在l i n u x 和w i n d o w s 系统上，并 可支持a p a c h e 和i i s 服务器，而且为应用程序的开发提供了可扩展的p h p 、n e t 、j a v a 以及j a v a s c r i p t 接口。 g e o s e r v e r 是一个遵循o g c 开放标准的基于j a v a 的开源g i s 服务器，它支持w f s 、 w m s 和w c s 服务，支持所有遵循开放标准的主流空间数据源。通过g e o s e r v e r ，用户 既可以利用w m s 服务将数据作为图像来发布，也可以通过w f s 服务直接发布实际的 数据【2 2 1 。 1 2 3 国内外物流配送路径选择研究现状分析 国外对物流配送车辆路径优化和车辆优化调度问题作了大量的研究，一般可以分为 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 、车辆路径问题( v e c h i c l er o u t i n g p r o b l e m s ，v r p ) 和车辆调度问题( v e h i c l es c h e d u l i n gp r o b l e m ，v s p ) 【2 3 1 。 t s p 问题是一个著名的n p 难题【2 3 】，大规模的t s p 问题求解起来非常困难。t s p 西南交通大学硕士研究生学位论文 第4 页 问题一般描述为：给定n 个城市，一个旅行商人需从起点出发，访问每个城市一次且 仅一次并最终回到起点，寻找使该旅行商按照上述要求所行的路程最短的城市序列。 与t s p 问题类似，v r p 问题可以描述为：一配送车辆需到若干个给定的地点进行 货物配送，已知每两个地点之间的距离，要求找出一条路径，使配送车辆访问每个地点 一次且仅一次，并最终返回起点，而且所走的路径长度最短【2 3 1 。d a n t z i g 和r a m s e r 在 1 9 5 9 年首次提出了冲问题【2 4 2 5 ，之后该问题很快引起了诸多领域的专家和决策者的 极大兴趣【l 】。目前国内外对v r p 问题的解决方法可以分为下面几类： ( 1 ) 精确算法。精确算法是指可求出其最优解的算法，常用于车辆调度的局部优 化问题【4 1 。精确算法主要有分枝定界法( b r a n c ha n db o u n d a p p r o a c h 2 6 2 刀) 、网络流算法 ( n e t w o r kf l o w a p p r o a c h 【z 驯) 、标号法( l a b e l i n g a l g o r i t h m ) 、割平面法( c u t t i n g p l a n e s a p p r o a c h 2 9 ) 、动态规划法( d y n a m i cp r o g r a m m i n ga p p r o a c h t 3 0 】) 等。l a p o r t e 和n o b e r t 提出了多种分枝定界法【3 l j ：h a d j i c o n s t a n t i n o u 和c h r i s t o f i d e s 等人先用q p a t h s 和k s h o r t e s t p a t h s 法求得解的上下界，在此基础上再用树状搜索法求解肿问题的最优路径【3 2 1 ， c h r i s t o f i d e s 还提出了一种用树状搜索来求解最短路径的精确算法 3 3 】；f i s h e r 等人在拉格 朗日松弛法的基础上运用k 树状算法，解决了多达1 0 0 个客户规模的带时间窗和负载 限制的冲问题1 3 4 j ；j b r a m e l 和d s i m c h i l e v i 提出先用列生成法得出一个可行解集， 再用割平面法或分枝定界法进行优化来解决v r p 问题，该方法能不保证所得出的最终 解就是最优整数解，但一定是非常接近最优解的【”】。随着车辆运输调度系统的复杂化 和调度的目标数目的增加，v r p 问题的求解运算复杂度会呈指数级增长，使得对最优 解的求解越来越困难，甚至不可能，因此精确算法的使用范围比较有限。 ( 2 ) 启发式方法。它是指人们根据经验规则来发现问题的满意解的方法。用启发 式方法求解问题时往往注重求得满意解而非最优解。在上世纪6 0 年代，c l a r k e 和w r i g h t t 3 6 】 提出了节约算法，该算法是目前公认的最具代表性的启发式方法。此外，国内外对启发 式方法这一领域的研究还有很多，如分支交换探索法，该方法由s “n 和 b w k e n l i i l 曲a i l 【37 】于1 9 7 1 年提出，是一种针对对称t s p 问题的可高效生成最优解和次优 解的启发式算法；g i l b e r tl a p o r t e 等人提出运用整数规划和分支定界法求解非对称车辆 路径问题【3 驯；g i l l e t 和m i l l e r 提出用扫描法解决中大规模的带有车辆负载和距离约束的车 辆派遣问题，该方法可将需求点分为若干组，每组求出一条经济的车辆路径，若每条路 径所经过的需求点数量相对恒定，则该算法花费的时间将随总需求点数量的变化呈线性 增长【3 9 】；l a p o r t e 提出了一种先求得初步解集再进行改良的禁忌搜索算、法【删；i h o s m a n 用模拟退火算法加禁忌搜索法求解v r p 问题，并在禁忌搜索算法中采用了特殊的数据结 构，将计算时间降低了5 0 以上f 4 l 】；o l l ib r i i y s y 提出用一种新的变邻域搜索法来求解带 时间窗的车辆路径问趔4 2 l 。西南交大的李军教授在节约算法的基础上进行了修正，并 西南交通大学硕士研究生学位论文 第5 页 提出用修正后的节约算法来解决有时间窗的车辆路线安排问题1 4 引。 ( 3 ) 人工智能方法。主要有模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m ) 、蚁群 算法( a n t s a l g o r i t h m ) 、粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ) 、遗传算法( g e n e t i c a l g o r i t h m ) 等，这些方法为规模庞大的多目标车辆调度优化问题的求解提供了新的途 径。浙江大学的蔡延光m 】等人提出用模拟退火算法来求解n ( n 1 ) 台车辆的多重运 输调度问题，证明了模拟退火算法在该问题上的实用意义：张潜【4 5 等人提出将聚类分 析与改进遗传算法相结合，来求解多目标车辆路径问题；党国英 4 6 】等人提出利用蚁群 算法和模糊理论来解决有时间窗的车辆路径问题；李宁【4 7 等人构建了带时间窗的车辆 路径优化问题的粒子表达方法，证明了粒子群算法是求解v r p 问题的一个有效办法。 1 3 为何选用开源软件 g i s 软件虽然具有强大的功能，但其价格也相当昂贵，下面是国内外一些具有代表 性的g i s 软件的报价嗣： 表1 1g i s 软件报价 系统名称报价 m a p c a d 桌面版￥4 8 0 0 m a p c a d 测图版 ￥6 8 0 0 m a p c a d 工程版￥9 8 0 0 嗄a p g i s单机版 ￥1 9 8 0 0 工程版 网络版￥1 8 0 0 0 0 m a p g i s i m s￥8 0 0 0 0 a r c i n f o 1 ￥1 8 0 0 0 0 a r c e d i t o r ￥9 9 9 0 0 a r c v i e 、n c o n ￥4 9 9 0 0 a r c s d e ￥1 5 5 0 0 0 a r c i m s9 0 ￥1 6 7 0 0 0 a r c g i ss e r v e rv 9 0 ￥5 0 0 0 0 0 m a p i n f op r o f e s s i o n a l8 5 ￥2 4 8 1 7 m a p i n f om a p b a s i c ￥1 3 1 9 7 m 印1 1 1 f od i s c o v e r y1c p u ￥8 3 0 0 0 m a p i n f om a p xm o b i l e1 0 0 0 用户授权￥3 ，10 0 ，0 0 0 m a p i n f om a p x5 0s d k ￥2 4 9 0 0 可见，g i s 软件的价格非常昂贵，而数据库软件如o r a c l e 价格也不菲，o r a c l e 9 i 市 西南交通大学硕士研究生学位论文 第6 页 场价格为9 8 0 0 0 元，o r a c l e l 0 g 则高达3 8 0 0 0 0 元，就算是s q ls e r v e r ，2 0 0 5 标准版的 也要4 9 0 0 0 元( 仅限服务一颗c p u ) 。另外，在服务器软件方面，m m 的w e b s p h e r e 网 络部署版要价2 9 3 ，9 9 7 6 0 元，而开源软件因为费用低廉，可以大大节省系统开发的费用。 1 3 本研究的内容及意义 本文在研究国内外g i s 软件和相关开源软件的发展状况，以及物流配送路径选择方 面的研究概况的基础上，利用开放源代码的g i s 软件、数据库及开发工具，搭建了开源 的w e b g i s 平台，实现了基于开源w e b g i s 的物流配送路径选择解决方案。由于开源软件 完全免费，而且稳定性和安全性也非常可靠，因此在实际应用中能够为企业节省大量经 费，具有一定的实际价值。 西南交通大学硕士研究生学位论文 第7 页 第2 章物流配送路径优化求解算法选取 对大多数企业来讲，运输通常是物流成本中最大的单项成本【4 9 1 。对于物流中心的 车辆调度来讲，需要考虑如何为配好货物的车辆制定运送线路，以便货物能以最小的运 输成本依次送到各个客户手中，因此，物流配送路径优化就成为物流系统优化中关键的 一环。如何对运输路径进行合理规划以降低运输成本，对物流企业具有重大的意义。运 用现代数学方法及计算机技术来求解目标函数，可以更为高效地进行车辆调度方案优 化，达到最大限度地节约配送成本的目标，从而实现物流企业效益的最大化。 2 1 图论 要进行车辆路径规划，就必然涉及到道路网络，而网络在数学和计算机领域中被抽 象为图，在各种车辆路径规划问题中，道路网络和计算所需的数据都是以图的形式来表 现和存储的，因此，图论是进行车辆路径规划的基础。 图论( g r a p ht h e o r y ) 是数学的一个分支，它以图为研究对象。在最早的时候，图 论主要用于研究一些游戏或纯理论问题，近年来，由于计算机的应用，引起了图论的飞 跃发展，使其在各种学术和技术领域都得到了广泛应用啪3 。 图论中的图由点及点与点之间的连接线段所构成，图中的点可以用来表示某个事 物，两点之间的连线则可以表示两个事物之间所具有的某种关系【5 。图中顶点的个数 称为图的阶，一个顶点到自身的回路称为环；若图中的顶点没有任何边与之相连，则称 该点为孤立点；若图中某对顶点之间的边数大于一，这些具有相同端点的边就称为多重 边。若两个顶点之间至少存在一条边，则称这两个顶点为相邻顶点，同理，如果两条边 至少有一个共同的顶点，则称这两条边为相邻边。 既没有环也没有多重边的图称为简单图。如果一个图中的边都没有标明指向，这样 的图就称为无向副5 0 】。如果一个图中的各条边都指明了方向，比如说，规定某条边只 能从点i 到点j ，而不允许从点j 到点i ，这样的图就叫做有向图。本研究所采用的路网 模型就是简单无向图。 2 2 图中任意点对之间的最短路径问题 最短路径问题在许多方面都有着重要的作用，现代社会的交通运输、网络通讯等等 都离不开它。因此，对最短路径问题的研究具有重要的价值。在现实生活中，最短路径 西南交通大学硕士研究生学位论文 第8 页 除了指一般地理意义上的距离最短，还可以扩展为其他的问题，如时间最短、费用最小 等。研究最短路径问题时，完全可以将其抽象为图论意义下的网络图最短路径问题，这 样，可以大大方便计算机的数据存储和求解计算。考虑赋权图g ，设g 中包含一个项点 集v ，v 中有n 个顶点，要求从图中点v 。到点v t 之间的最短路径，则该问题可用下面 模型来描述： m i n z = 岛乃( v 且f ：，) ( v i ，v je v 且f 甸) ( v s ，v j e v 且s 匀) ( v j ，v t e v 且_ ，f ) 最短路径不经过v j 最短路径经过v j ( 2 1 ) ( 2 2 ) ( 2 3 ) ( v i ，v j v ，i j ：s ，f 且f 句) ( 2 - 4 ) ro 最短路径不经过边( v i ，v j ) 鼽舻 l 1 最短路径经过边( v i ，v j ) ，是一个0 1 变量，目标函数中厶，代表从v i 到v j 的边的长度，在其他类型的最优 路径计算中，厶，也可以是从v i 到v j 的边的权。 由于本研究所选取的图是城市路网图，因此式( 2 1 ) 表示两点间一定存在一条最 短路径。式( 2 2 ) 表示最短路径一定是从起点v 。出发，式( 2 3 ) 表示最短路径一定到 达终点v t ；式( 2 - 4 ) 表示地图中的点( 除起点、终点外) 要么不在最短路径上，若在， 则最短路径必定从某点到达该点并由该点走向其他点( 城市道路一般为双向，故只需对 与该点相连的道路求和) ，该式确保了最短路径的连贯性。 关于最短路径问题，目前所公认的最经典的求解方法，是1 9 5 9 年由e w d i j k s t r a 提出的双标号法，也就是d i j k s t r a 算法【5 烈。d i j k s t r a 算法适用于所有边的权值均为非负 的情况下，属于前面提到的精确算法的范畴。它可以计算出图中任意两点间的最短路线， 、 b k 驴 匹、乳、乳 阢， 西南交通大学硕士研究生学位论文 第9 页 时间复杂度小于o ( n 3 ) ，其中n 为顶点个数。 d i j k s t r a 算法的原理如下： 首先，给图中每个点i 都赋一对标号( d i ，p i ) ，其中d i 是起始点s 到点i 的最短路 径的长度；p i 则是i 点在s 到i 的最短路径中的前点。初始时，将源点s 的d 。值设为o ， 同时将其他点的d 值设为无穷大，表示从源点s 到这些顶点的最短路径还有待计算，标 记起源点s ，记p s = s ，将其他所有点设为未标记的。初始化之后，d i j k s t r a 算法的计算步 骤如下： ( 1 ) 计算图g 中从所有己标记的点k 到与其直接相连的未标记的点i 的距离，并 将d i 设置为m i n d i ，”k 】，其中，k 是从点k 到i 的边的长度。 ( 2 ) 从所有未标记的点中，选取d i 最小的点，假设这个点是j ，则将点j 选为最短 路径中的一个点，并标记点i 。 ( 3 ) 将点k 设为点j 在最短路径上的前一点，即将p i 设为k 。 ( 4 ) 检查是否终点t 己标记，若是则算法结束，否则，记k = j ，转到( 1 ) 继续执 行5 3 1 。 算法维护两个顶点集r e d 和b l u e 。已求出最短路的点放在r e d 中，其它点放在b l u e 中。集合r e d 开始时仅含点s ，其它点全在b l u e 中，随着求最短路迭代计算的进行，每一 步都从b l u e 中删去一个顶点，并将其加入到r e d 中，当终点t 也被纳入r e d 中时，迭代结 束 5 0 1 。当算法结束时，d i 中存储的便是从源点s 到点i 的最短路径长度，而根据每个点的p 值即可推出最短路径的走向。 2 3 图中所有点对间的最短路径问题 解决这个问题的最经典的方法是f l o y d 算法。其基本思想是：对有n 个顶点的图g ， 首先将其抽象为邻接矩阵l o = ( k ) ，其元素值l i i 为顶点v i 到v j 的直达边长( 即从v i 到 v j 的弧长) ，若v i 与v j 不相邻，则令1 0 = m ( m 为足够大的正数) 。此外，如果计算时不 允许顶点到其自身存在回路的话，则将d i i 设为一个足够大的正数，否则将d i i 设为o 。 同时，构造中间点矩阵v o = ( v i i ) ，该矩阵用来表示各点在最短路径上的前点编号， 并将v o 中的各元素v i i 全置为i 。 接下来将l i i 与( 1 i l + l l i ) 相比较，若l i j l i l + 1 1 j ，则说明以v l 作为v i 到v j ( i ，j - - 2 ，3 ， n ) 的中间点所形成的路径的长度要比从v i 直接到v j 的路径长度短，因此在下一步的邻 接矩阵中将元素l i j 替换为l i l “1 i 取代，并将v o 中的v i j 换为1 。反之则不修改k 和v 0 的相应元素的值。按照这样的方法考察并修改完k 和v o 的所有元素后，就得到下一步 的邻接矩阵l l 和中间点矩阵v l ，然后开始下一步迭代，即比较l l 中的1 0 与l i 2 + 1 2 j ( i j 2 ) ，若l i j l i 2 + 1 2 j ，则将l z 中的相应元素值换成l i 2 + 1 2 j ，并修改中间点矩阵的相应元素， 西南交通大学硕士研究生学位论文 第1o 页 将v 1 中的v i i 改成2 ，以得出下一步的邻接矩阵l 2 和中间点矩阵v 2 ；否则，不修改l 2 和v 2 中相应元素的值。同样，考察并修改完v 1 和l l 中的所有元素后，得矩阵v 2 和 l 2 ，再进入下一步的考察和修改，即考察1 0 与( 1 i 3 + 1 3 j ) ( i j 3 ) 的大小，如此进行，直 至考虑完所有n 个顶点，得到最终的邻接矩阵k 和中间点矩阵v n 。这时由于已考虑了 全部顶点作为中间点的可能性，故k 就是图g 中所有点对之间的最短路长矩阵，其元 素l “就是v i 到v i 的最短路径长度，而v n 则是和最短路径相对应的中间点矩阵。 接下来就可以利用v n 推导出图中各个点对间的最短路径了。其具体步骤如下： ( 1 ) 首先找出w ，若v i j = i ，则v i 到v 的最短路径就是v i v i ； ( 2 ) 若v i j i ，设v i j - k ，则找到