（产业经济学专业论文）基于GIS的同城运输路线最优化研究.pdf

对外经济贸易大学硕i 。学位论文 摘要 物流是现代企业管理中的重要组成部分，经过半个多世纪来的发展演变已经 取得了很大的发展与进步，逐渐成为了现代企业的“第三利润来源”。鉴于物流 在企业商务活动中的重要地位，如何降低物流成本成为近年来国内讨论的热门话 题，但目前的研究现状和应用现状表示更多的研究主要倾向于车辆的调度，也就 是传统的车辆路径选择问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) ，但对于车辆上路 后如何行驶，走什么样的路线这方面研究甚少。目前的路线选择仍然是基于司机 经验的“盲目”选择，这大大增加了企业的运输和配送成本。同时由于客户对物 流响应程度要求的逐渐增强，时间这个因素也不容被忽视，那么如何将成本和时 间两个因素同时考虑到路线选择过程中去成为一直困扰着企业的一大难题。本研 究课题正是在这样的现实背景下展开的，通过分析研究，在应用g i s 技术的基础 上给出了一个有效的解决方案。 本课题研究的主要目的是在已确定起点和目的地的情况下，通过引入g i s ， 在充分考虑道路畅通情况的基础上，实现最优路线选择。为不同行业，以及同行 业内不同客户提供一种有针对性的路线选择方案，从而达到运输成本和响应速度 双坚固的效果。 本研究课题引入通过地理信息系统( g i s ) 相关技术，首先，在充分分析现 实中物流运输和配送成本主要来源的基础上，对物流运输和物流配送过程中的行 车路线选择进行详细的分析；其次，抽取出主要的影响因素，针对不同情况下的 运输进行分类建模，提出了一种针对性较强的路线选择方案。再次，对现有的路 线选择算法进行优化，提高算法的效率；最后，从系统分析和设计的角度出发， 对基于g i s 的路线选择系统给与实现。 关键词：g i s 路线选择路网模型 对外经济贸易大学颀i 一学位论文 a b s t r a c t l o g i s t i c si st h em o s ti m p o r t a n tp a r to ft h em o d e r ne n t e r p r i s em a n a g e m e n t i th a s b e c o m e “t h et h i r ds o u r c eo ft h ep r o f i t ”i nt h em o d e me n t e r p r i s em a n a g e m e n t t h e t o p i ca b o u th o wt o r e d u c et h ec o s to fl o g i s t i c si st h ep o pt o p i c sb e c a u s eo ft h e i m p o r t a n tp o s i t i o no ft h el o g i s t i c s b u tn o wt h em a i nr e s e a r c h e sa n da p p l i c a t i o n sa r e a b o u tt h ep r o b l e m so fv e h i c l es c h e d u l i n gw h i c ha r ec a l l e dv r p t r a d i t i o n a l l y ( v e h i c l e r o u t i n gp r o b l e m ) b u tt h ew a yw h i c ht h ed r i v e r sc h o o s ea r em o s t l yb a s e do nt h e d r i v e r s e x p e r i e n c e w h i c ha r en o tv e r ye x a c t ，i tm a k e st h et r a f f i cc o s ta r eh i 。曲m o s to f w h i c ha r en o tg e n u i n en e e d w i t ht h el o g i s t i c sr e s p o n s ew h i c ht h ec u s t o m e r sr e q u k e i n c r e a s i n g ，t i m ef a c t o rc a n tb ei g n o r e da n ym o r e s ot h eq u e s t i o na b o u th o w t ou s e t i m ea n dc o s tf a c t o r st os e l e c tt h eb e s tw a yb e c o m e sap u z z l et ot h ec o m p a n y t h i s r e s e a r c hs t a r t u p sa n dg o e sa l o n gi nt h i sc o n d i t i o n t h r o u g ht h ea n a l y z i n gt h er e s e a r c h g i v e sa l le f f i c i e n ts o l u t i o nw i t ht h eh e l po fg i st h e o r y t h ep u r p o s eo ft h i sr e s e a r c hi st os e l e c tt h eb e s tr o u t ew i t hi m p o r t i n gt h et h e o r y o fg 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 ) ，a n dc o n s i d e r i n gt h ee x p e d i t et r a f f i c c o m p l e x i o n ，w h e nt h es p r i n g b o a r da n dt h ee n d p o i n ta r cs u r e t h er e s e a r c hc o u l d p r o v i d ea b e s tr o u t ee s p e c i a l l yf o rt h ed i f f e r e n ti n d u s t r i e sa n dt h ed i f f e r e n tc u s t o m e r s ， a n ds a t i s f y i n gt w or e q u i r e si nl o g i s t i c sw h i c ha r er e d u c i n gt h ec o s ta n di n c r e a s i n gt h e r e s p o n s e i nt h i sr e s e a r c h ，f i s to fa l l ，a n a l y z et h ep r o c e s so fs e l e c t i n gw a y si nd e t a i la f t e r k n e wa l lo ft h ec o s ti nt h et r a f f i c s e c o n d l y , m o d e l i n gf o re v e r yc o n d i t i o n sa n dg i v e t h ee s p e c i a ls o l u t i o n st os a t i s f yt h ed i f f e r e n tn e e d sa f t e rd r a w i n go u tt h em a i nf a c t o r w h i c hi n f l u e n c et h et r a f f i cc o s t t h et h i r do n e ，o p t i m i z et h ea r i t h m e t i co fs e l e c t i n g w a y t oi n c r e a s et h ee f f i c i e n c y t h el a s t ，a n a l y z ea n dd e s i g nt h es y s t e mw h i c hi sc a l l e d t h eb e s tw a ys e l e c t i o ns y s t e mb a s e do i lg i s k e yw o r d ：g i s ，w a ys e l e c t i o n ，r o u t em o d e l 2 对外经济贸易大学硕十学位论文 第一章引言 1 1 物流运输的概念及作用 1 1 1 物流运输的概念 物流是通过运输、储存、装卸、包装、流通加工、配送、信息处理等基本物 流活动实现物品从供应地到接收地的实体流动过程。创造物品的空间效用和时间 效用是物流系统的两项最主要的功能，他们分别通过运输和储存来实现，因此运 输和存储被看成是物流系统的两大支柱。随着技术进步和物流管理水平的提高， 现代物流系统中通过储存创造时间效用的功能正在弱化，随着科技的进步看板式 拉动型的生产逐渐成为了现代工业生产的主流方向，而拉动式生产模式的核心就 在于减少储存时间，降低成本。在这种储存环节大大弱化的情况下，合理地组织 运输，降低运输成本实现准时制配送，逐渐成为了生产企业以及物流企业关注的 重点。 在这种大环境下，我们明确运输的含义及特点为我们后面进行合理优化提供 了可能。运输就是通过运输手段使货物在物流节结点之间流动。它是在不同地域 范围间，以改变“物”的空间位置为目的的活动，对“物”进行空间位移。它和 搬运的区别在于，运输是较大范围的活动，而搬运是在同地域之内的活动。它 解决了供给者与需求者之间场所分离的矛盾，创造了场所功效。在现代市场中， 运输具有扩大市场、稳定价格、促进社会分工、扩大流通范围等社会经济功能。 运输具有如下的基本特点： ( 1 ) 运输是在流通过程中完成的。运输表现为产品的生产过程在流通领域 中的继续，运输业不断为企业生产提供原料、材料、燃料和半成品， 以保证企业不问断地从事生产。 ( 2 ) 运输产品计量的特殊性。运输产品是以运输量和运输距离进行复合计 量的，也就是说在运输成本计算的过程中主要包含两部分费用，即运 输量引起的费用和距离引起的费用，对于此特点的认识不仅更清晰的 认识了运输过程，同时为下面确定本文研究的范围奠定了基础。 ( 3 ) 运输费用在预留成本中占有较大的比例。在整个物流费用中，运输费 用与其他环节的支出相比是比较高的。运输路程越远，运量越大，运 输费用也就越高，在整个物流费用中所占的比例也就越大。 对外终济贸易大举顾e 学位论文 由于物流运输目的是实现“物”的空间转移，并且明显区分于搬运的就是地 域的范围，故可见物流运输是远程的“物”的空问转移，因此物流运输的渠道就 有很多中，主要分为：铁路运输、公路运输、水路运输、航空运输、管道运输等， 而本文的主要目的是利用g i s 的有关理论和技术为同城运输的路线选择提供一 种优化方法，从而节约运输成本，故本文所考虑的运输工具主要是公路运输，即 汽车运输，它是物资运输的一种主要方式。 公路运输的特点是机动灵活，速度快、装卸方便、路网分布密。这些特点使 它成为了短途运输的主要手段，但是由于路网分布密集，目前的在路网选择上存 在着严重的经验主义，造成了很多资金外流，大大增加了物流费用。本文正是发 现了公路运输的这个弊端，致力于提出一种合理的解决方案，优化目前的公路运 输模式，从而降低成本，集体内容将在后面章节详细介绍。 1 1 2 物流运输的主要原则 物流商品的运输工作，要遵循“及时、安全、经济”的原则，做到加速商 品物流，降低商品流通费用，提高货运质量，多、快、好、省地完成商品运输任 务。 1 、及时 就是按照客户需要的时间把商品及时运往消费地，及时地把货物从产地运到 销地，尽量缩短货物在途时间。缩短流通时间的主要手段是改善交通，实现运输 现代化。本文正是利用g i s 的相关理论和技术改变传统的单纯从成本考虑的路线 选择，加入时间概念，实现软时间窗的最优路线选择。在这中理论下，时间是一 个主要的参数。 2 、准确 就是在货物运输过程中，切实防止各种差错事故，做至4 不错不乱，准确无误 地完成运输任务。由于商品品种繁多，规格不一，一件商品从工厂交货到达消费 者手中，中间要经过不少环节，稍有疏忽，就容易发生差错。发运商品不仅要件 数准确，规格也不能搞错。 3 、经济 就是以最经济的方法运输货物。降低运输成本。如选择最经济合理的运输路 线和调配方式，尽可能减少运输环节，缩短运输里程，为求花最少的费用，把商 品运到目的地。其中缩短里程降低成本是本文优化运输路线的又一个重要参数。 4 、安全 商品在运输中的安全，一是要注意运输、装卸过程中的震动和冲击等外力的 作用，防止商品的破损，二是要防止商品由物理、化学或生物学变化等自然原因 所引起的商品减量和商品变质。物流运输的这一原则要求对一些特殊的商品给予 2 对外经济贸易大学硕士学位论文 更高的时间响应，以便保证商品的原有属性和使用价值，这也是本文后面提出方 法的重要依据。 1 1 3 物流运输在物流中的重要作用 运输工作是整个物流工作中一个十分重要的环节，在整个物流过程中具有举 足轻重的特殊地位。以前人们在研究物流时，片面的地认为解决了运输问题便解 决了物流问题。显然这种看法是不全面的，但从另一个角度看，也表现了运输在 物流中的重要地位。运输将生产和消费所处的不同空间连接起来，实现了物品的 空间效应，为实现实物从生产到消费的移动起到了决定性的作用。在现代生产中， 由于生产的专门化、集中化，生产与消费被分割的状态越来越严重，被分割的距 离亦越来越大。从而，运输的地位也越来越高。 运输对于物流的意义主要体现在一下几个方面： 第一，便利和可靠的运输服务是有效组织输入和输出物流的关键。 在物资的实物转移中，运输的实现的关键。任何产品的生产与消费严格说来 都必然存在空间位置的差异，物资为完成生产的目的，满足消费者的愿望，都必 然要借助不同的运输工具和运输手段来解决。从而运输被看作实物转移的关键是 无可非议的。 第二，物资运输费用在物流成本中占有较大的比例 运输费用在物流费用中占有很大的比重。运输费用与运输量成正比，与运输 路程也成正比。运输路程越远、运量越大，运输费用也就越高，在整个物流费用 中所占的比例也越大。下面通过两组数据来说明运输费用在物流成本中的重要作 用：第一组数据，表1 1 是美国和加拿大公司2 0 0 1 年物流成本构成情况，从表 中可以看出运输成本超过了总成本的1 3 ；第二组数据，据统计o ，2 0 0 4 年，美 国物流成本总支出1 0 0 6 0 亿美元，其中运输成本为5 8 5 0 亿美元，占全部物流成 本的5 8 2 ，6 ，并占当年名义g d p 的5 9 。同时卡车运输4 8 1 0 亿美元，卡车运输 占全部运输成本指出的8 1 5 。 从上面的两组数据中我们可以看出，在各国运输成本不但在物流成本中占有 很大的比重，同时这个比重还有不断上升的趋势，而其中卡车运输又是物流运输 中的主要方式，如何降低物流成本尤其是公路运输方式下的物流成本对于物流有 着只管重要的作用。因此，组织合理运输，以最小的费用，较快的时间，及时、 准确、安全地将货物从其产地运到销地，是降低物流费用和提高经济效益的重要 途径之一。 第三，运输对社会产品的需求有其特殊地位 物资运输的且的是在时间上和数量上满足用户的需求。因此，运输的特殊地 o l 佐，美国物流发展概况【z 】，2 0 0 3 3 对外经济贸易人学硕士学位论文 位表现为：它在一定成都上决定着消费。有时，使用价值相同的商品，由于存在 地区差价，进行适当的运输，对产品有市场实现有利的销售具有举足轻重的作用。 表1 1美国、加拿大公司2 0 0 1 年物流成本构成情况 成本内容 美国公司( )加拿大公司( ) 客户服务订单清关88 仓储 2 52 5 运输 3 73 6 管理 98 库存搬运2 12 3 资料来源：中国航务周刊第4 2 7 期，第6 页 1 2 物流的业务流程及其细分 1 2 1 物流运输业务流程 运输业务非常复杂，分别现针对物流公司进行分析，基本整理归纳可得以下 的物流运输的基本流程，如图1 1 所示，分析发现物流公司从发送到货物到达这 一过程，有极大的优化的可能，因为大部分的物流公司仍然采取经验式的运输路 线选择方式，一旦通过合理的优化可以大大的降低物流成本。 4 对外经济贸易大学硕l 学位论文 1 2 2物流运输与配送 图1 i 物流运输业务模型 资料来源：本研究整理 在企业的物流活动中，物流运输和物流配送两个名词常常被混合使用，在以 前的研究中很多人忽视了这两种企业业务的区别，将其混为一谈，但实际上这两 种活动有一定的联系和共同点但同时也有很大的区别，本文的这部分就是对这两 类活动进行区分的同时，找出其共同点，进行统一的优化，从而实现降低物流成 本的目的。 从整体上看物流运输和配送是一个相互衔接的过程，1 9 9 1 年版的日本物流 手册的表述是：生产厂到配送中心之间的物品空间移动叫“运输”，从配送中 心到顾客之间的物品空间移动叫“配送”。当企业将货物大批量、长距离地从生 产工厂直接送达客户或配送中心称为运输；货物再从配送中心就近发送到地区内 对外经济熨钙大学硕士学位论文 各客户手中称为配送，关于二者的区别可以概括成以下几个方面，如表1 3 所示： 表1 2 企业物流运输和配送的区别 运输配送 远距离大量货物的移动短距离少许货物 据点间的移动企业送交客户 地区间货物的移动地区内部货物的移动 一次向一地单独运送一次向多处运送，每次只获得少量货物 资料来源：张建伟物流运输业务管理模板与岗位操作流程2 0 0 5p 1 1 从图中可见，配送是物流运输的延续，是为了进一步实现货物空间效应，来 满足客户的需求。通过公司配送的业务分析，本文把配送业务分为三个部分：配 送区域划分、配送决策、路线选择，如图1 4 所示，配送区域划分主要是对于那 些多配送中心的企业，根据某种方法以最优的方式将订单划分给不同的配送中 心，这个阶段的着眼范围主要是企业的所有配送中心；而作为配送的第二个阶段 就是以各配送中心为着眼点，根据不同客户的地理位置以及对响应时间的要求， 确定出配送顺序；而作为配送最后一个阶段的配送路线选择则是在配送中心以及 目的客户已知的基础上，实现点到点的运输。 曲 铺售部门8 客户 图1 2 配送业务流程 资料来源：本研究整理 通过对上面配送业务的分析，可以发现它与运输的共同点就在于车辆上路后 直到目的地的这部分业务方面，一个合理的路线选择能够帮助企业大大的降低运 输成本从而提高利润。由于公路运输方式是较为常见的配送方式，并且公路网络 的复杂性给运输的路线选择提供了多样性的选择，正是这种多样性就从客观上决 定了运输成本最低化的可能，本文正是发现了这个问题，在下面的各个章节中将 进一步讨论一种可行的路线选择方案，为企业物流运输和配送的路线选择提供可 执行方案，降低企业物流成本。由于考虑问题的复杂性，为了提出一个广泛使用 的方法，本文主要针对同城配送的公路网络，提供一种考虑时间、成本等参数的 最优路线选择方案。 1 3 地理信息系统与路线选择 6 对外经济贸易大学硕士学位论文 1 j 1地理信息系统概述 1 3 1 1信息系统的基本概念 g i s ( g e o g r a p h i c a li n f o r m a t i o ns y s t e m ，地理信息系统) 是在计算机硬、软件支 持下，对整个或部分地球表面与空间和地理分布有关的数据进行采集、储存、管理、 分析和表达的空间信息系统，它集计算机科学、地理学、信息科学等学科于一体的新 兴边缘科学，可作为应用于各领域的基础平台o 。这种集成是对信息的各种加工、处理 过程的应用、融合和交叉渗透，并且实现各种信息的数字化过程。地理信息系统与其 他信息系统的主要区别在于其存储和处理的信息是经过地理编码的，地理未知与该位 置有关的地物属性成为信息检索的重要部分。 在地理信息系统中，空间信息和属性信息是不可分割的整体，他们分别描述地理实 体的两面，以地理实体为主线组织起来。空间信息还包括了地理目标之间的空间关系 信息，使g i s 能够支持一般管理信息系统所不能支持的空间查询和空间分析，以便于 制定规划和决策。 1 3 1 2 地理信息系统的基本功能 地理信息系统的基本功能如下 ： 数据采集：检查与编辑。主要用于获取数据，保证地理信息系统数据库中的数 据在内容与空间上的完整性、数据值逻辑一致、无错等。 数据格式化、转换通常称为数据操作。 数据的存贮与组织。这是一个数据集成的过程，也是建立地理信息系统数据库 的关键步骤，涉及到空间数据和属性数据的组织。 查询、检索、统计、计算功能。查询、统计、计算是地理信息系统以及许多其 他自动化地理数据处理系统应具备的最基本分析功能。 空间分析是地理信息系统的核心功能，也是地理信息系统与其他计算机系统的 根本区别。模型分析意指在地理信息系统支持下，分析和解决问题的方法体现， 它是地理信息系统应用深化的标志。 显示。地理信息系统为用户提供了许多用于显示地理数据的工具，其表达形式 既可以是计算机屏幕显示，也可以是诸如报表、表格、地图等硬拷贝图件，尤 其要强调的是地理信息系统的地图输出功能，以供地理信息系统的使用者能够 设计和制作出具有高品质的地图。 。邬伦、刘瑜、张品等，地剧信息系统原理、方法和俺用。2 0 0 1 0 7 北京科学i f | 版社 。边馥苓，地理信息系统原理和方法，1 9 9 6 武汉，测绘小版社 7 对外经济贸易人学坝上学位论文 1 3 2地理信息系统在路线选择中的应用 通过前面的分析我们不难发现，不论是物流运输还是配送都存在着一个共同的方 面即路线选择。由于大多数的物流运输和几乎全部的物流配送都是基于公路网的汽车 运输，随着交通行业的不断发展，目前全球各个国家各个城市的公路网都不断的复杂， 遍布在各个角落，这给人们带来方便的同时，给我们的物流的路线选择带来了一个难 题，那就是选择什么样的路线才是最快的? 选择哪条路线才是成本最低的? 这两个问 题成为了不断旋绕在企业主面前的问题。 同样，根据前面我们对于g i s 的介绍以及对其特点的了解，我们不难发现利用g i s 的相关理论正可以解决这个问题，不仅可以提供一种可能的查询选择方法，同时还能 提供一种直观的解决方案，知道企业选择合理的路线，实现其提高物流相应度和降低 成本的目的。除此之外通过将g i s 技术融入到物流配送过程中，就可以更容易的处理 物流配送中货物的仓储、装卸、传递等多个环节，并对其中这几的如仓库位置的选择、 仓库的容量设置、合理装卸策略、运输车辆的调度和投递路线的选择等闯题进行有效 管理和决策分析，有助于物流配送企业有效地利用现有资源，降低消耗，提高效率。 目前随着电子商务、物流和g i s 本身的发展，g i s 技术将成为全程物流管理中不可缺少 的组成部分，并越来越多的公司将其化入自动物流的一部分，其运行模式如图1 4 所 示： 实物流 信息流 图1 3 自动物流模式 资料来源：本研究整理 对外经济贸易大学硕j 学位论文 在“第一届中国现代物流g i s ，g p s 应用研讨会”上，国内注明物流专家王之泰教 授指出：不管是企业自己搞物流，还是第三方、第四方物流，有一点是肯定的，就是 没有后台强大信息技术支撑下的高效物流过程，现代物流就是一句空话。g i s 技术在物 流领域中的应用，使现代物流管理正在跨入智能化管理的领域，实现物流信息化。物 流信息化的直接结果是信息流动的加快、信息流动的及时准求，而信息的迅速流动直 接关系到物流的工作流程的平衡。例如，能大大缩短配车计划编制时间、提高车辆的 利用率、减少闲置及等候时间、合理安排配送区域和路线等。 目前的g i s 物流分析软件主要集成了车辆路线模型，最短路径模型，网络物流模 型，分配集成模型和设施定位模型等。如a r c g i s 系列产品提供的物流解决方案对物流 中的许多重要决策问题，如配送中心的选址、货物组配方案、运输的最佳路径、最优 库存控制等方面，大都可以得到较好的解决。但是对于多约束条件下的车辆路线目前 仍没有具体的解决方法。o 。邱克，f i 销传播策略。2 0 0 2 0 7 北京；机械t 业；版社 9 对外经济贸易大学顺上学位论文 第二章路线选择现状及相关理论研究 2 1 路线选择现状 我国的物流市场是一块潜力巨大的利润源，根据国际货币基金组织的统计，1 9 9 9 年我过第三方物流的市场份额为4 6 1 8 亿元，预计2 0 1 0 年将达到11 9 7 2 亿元翰。我国许 多商品总成本中，物流费用已占到2 册左右，产品存储、运输支付的费用约占了生产成 本的3 0 到4 0 ，每年因包装造成的损失约1 5 0 亿元，因装卸、运输造成的损失约5 0 0 亿元，保管不善造成的损失在3 0 亿元上下，但目前，公路货运因缺乏合理的物流组织， 工商业企业自有运输工具的空驶率为4 0 9 6 ，仅此一项每年造成的损失就高达1 0 0 亿元。 目前在国内很多企业在物流管理方面纷纷实现了电子化信息化，很多e r p 软件都 包含了物流运输这一个主要部分。但经过相关的分析和分析我们发现这类的物流运输 更多的集中在了库存管理上，而对于车辆调度的相关管理确实微乎其微，对于行车路 线选择更是无人涉及，很多公司在货发出后采取的方针依然是司机说了算，凭经验进 行路线选择。这无疑是一个巨大的漏洞，从这个漏洞里漏出的不仅是资金还有企业的 信誉。 为了对这个问题进行深刻的研究，在研究本问题的同时对a 快餐企业进行了跟踪 研究，同时进行了数据分析，在此以该企业为例，说明目前大多数企业采取的路线选 择方法以及其存在的弊端。 首先，通过研究我们得到了a 企业的基本运行模式，如图2 1 所示： o 经济日报2 0 0 1 年6 仃2 6l l 第七版 1 0 对外经济贸易大学碳- 上学位论文 客尸 图2 1a 企业的业务流程 资料来源：本研究整理 从图中我们清晰的看到在两处运输过程中对于行车路新的选择都是依赖于司机的 经验，对于快餐业这种强调及时的企业来说无疑存在着很多隐患，经过相关调查得到 以下问题： 1 、由于北京的交通一向拥挤，在行车过程中难免出现堵车现象，大大影响了送 餐速度。在实际调查中我们发现，如遇到交通高峰期时，订餐后的等待时间 竞长达2 个小时之久，这大大影响了企业的信誉。 2 、司机的经验不足，使得在路线选择上不能选出最短路线，造成行车成本的大 量浪费。据统计单从运输成本上来讲，该企业的运输成本就站该企业营运成 本的4 0 9 6 左右，这么巨大的支出让我们不得不考虑其中巨大的浪费。 3 、公路状况的不确定性造成一定的不便。例如道路的维修或者临时的禁止通行 等，这些对于不能及时获取信息的司机来讲都是潜在的问题，一旦遇到这样 的问题很多情况下司机会选择绕路或者选择其他路线，这无疑增加了成本， 同时也延长了送货的响应时间。 通过以上的分析，我们不难发现这种仅凭经验的路线选择是大大不可取的。然而这 并不只是a 企业一个企业的问题，同时它也是目前国内大多数企业的共同问题，从中 我们发现在路线选择方面不仅存在这巨大的研究空间，同时也存在这很大的研究价值。 对外经济贸易大学硕二l 学位论文 2 2 理论现状 在运筹学、交通科学、以及地理信息系统中都有对车辆路线问题的研究。在地理 信息系统中，车辆路线问题属于网络分析中的内容。 2 2 1 网络分析 网络分析是地理信息系统中的核心内容之一，也是地理信息系统却别于其他计算 机辅助软件的关键所在。对地理网络( 如交通网络) 、城市基础设旌网络( 如各种电网、 电话线等) 进行地理分析和模型化，是地理信息系统中网络分析功能的主要目的。同 时，网络分析也是运筹学模型中的一个基本模型，它的根本目的是研究、筹划一项网 络工程如何安排，并使其运行效果最好，如一定资源的最佳分配，从异地到另一地的 运费最低等。其基本思想则在于人类活动总是趋于按一定目标选择达到最佳效果的空 间位置，这类问题社会经济活动中不胜枚举，因此在地理信息系统中此类问题的研究 具有重要意义。在本文中，我们对道理网络进行分析，网络分析是本文的重要研究内 容。 2 2 2 车辆路线分析 目前，物流是在国内还是在国外，对于车辆路线的分析，主要集中于最短路径分 析，最佳路径分析，而对于实践中需要的：带多种约束条件的车辆路线及行车时间表 的定制考虑的不多。多约束条件是指物流公司在制定行车路线的时候，需要考虑的若 干问题。例如：( 1 ) 公司的车辆数有限，并且每辆车的载重量是有限的。( 2 ) 司机的总驾 驶时间有一定的上限。3 ) 站点的特殊要求：只能在特定的时间内取货和送货。“) 每个 站点需要取一定数量的货，又要送一定数量的货物等。从中我们可以看出这些约束条 件主要集中在时间窗口上。因此，他设计到物流配送中非常重要的综合计划闯题。 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 在运筹学中也是组合优化领域 中著名的n p - 难题之一显示生活中除了许多运输生产组织问题都可以归结为v r p 问 题。 现实生活中，用户往往对车辆运输服务的时间区域有要求。如果这个时间区间的 要求是硬性的，则这类问题称之为带时间窗车辆路径问题( v e h i c l er o u t i n gp r o b l e m w i t ht i m ew i n d o w ，v r p t w ) 。今年国际上有不少有关该类问题的论文发表，国内也开 始有相关的研究成果报道。但如果用户对时间窗的要求允许有偏差，则这类问题称之 为带软时间窗车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hs o f tt i m ew i n d o w ， v r p s t w ) 。对于这类问题的研究，相对而言起步较晚，研究较少。在物流系统中的车辆 。李军，带时间窗的车辆路径安捧问题的一个启发算法系统t 程 1 2 对外经济贸易大学硕上学位论文 路线问题大都可以归为此类，因而至今还没有好的解决办法。 y r p s t w 问题是多目标问题，s a v e l s b e r g h 等人证明这类问题属于n p 一难题。因此 构造合适的启发式算法应该是比较好的途径。s e x t o n 和c h o i 是最早从事该方面研究工 作的学者之一，他们对带软时间窗的单车辆取送问题进行了探讨。目前，国内已有学 者开始研究用遗传算法来解决v r p 问题，但目前对v r p s t w 问题的研究还比较少。对于 物流系统中这种多约束条件下的车辆路线问题的分析更是少之又少。 2 3 本文研究内容及意义 目前对物流运输和配送中的路线选择多基于无时间窗或者是硬时间窗的路线选 择，而目前企业却发生了变化，再不是一种方法遍天下的情况了，而逐渐的呈现出两 种趋势： i 客户区别。随着经济的不断发展，人民生活水平的提高，很多高端客户在购买 过程中不仅看重商品的物美价廉，更看重的是订货的响应速度，甚至愿意为了 这种高相应速度付出一定的资金；而同样也存在着一些较低层次的客户更看重 商品的价格，在同种商品中选择价格较低的，并愿意为这种价格等待一段时间。 这样的客户差别使企业要在竞争中立于不败之地，就必须把更多的关注供应链 的响应速度，运输的响应速度。而这种速度很大程度上就体现在路线选择上。 2 企业区别。随着社会分工的细化，以及生产产品的种类不断增加，很多产品具 有了很大的时间效应，例如海鲜这种商品，海鲜是一种存放时间较短的产品， 尤其在特殊的季节，这就要求生产厂家要在较短的时间内将产品送到销售点， 无疑这种企业对物流的响应速度要求极高；而同时对于生产钢材的企业来说， 这种商品并不存在过期的问题，因此除了特殊情况以外，这种商品在运输过程 中就更看重成本。 从上面的分析我们不难发现时间因素是在路线选择过程中不得不考虑的一个重要 因素，同时针对不同客户不同企业进行区别式对待更是必不可少，那么软时间窗的车 辆路径问题就有很大的研究价值和实用空间。而目前的理论和现实情况并不乐观，图 2 2 用因果图的形式表示了目前存在的主要问题。 。邱克，背销传播策略。2 0 0 2 0 7 北京：机械丁业出版社 ”m s a v e l s b e r g h l o a ls e a r c hj nr o u f l n gp r o b j r n mw j c ht i m e 们m d o w $ o l m c r 1 9 8 5 a2 8 5 - 3 0 5 1 3 对外绎济贸易大学顾i 学位论文 ， 图2 2 企业车辆路线选择因果图 资料来源：本研究整理 本文中利用成熟的图的模型以及在地理信息系统中比较成熟的各点最短路径算 法，引入时间因子，并充分考虑到道路状况，运用运筹学中的节约思想，从而在一定 程度上解决了软时间窗的车辆路线选择问题。 对外经济贸易大学顾上学位论文 3 1 图论基础 第三章路网建模 在g i s 理论中，常将空间事物抽象成点、线、面等几何要素。点、线建立拓扑关 系可以组成网络。网络在几何上由边连成，边的断点、交点是网络的节点。地理信息 系统网络分析的理论基础是图论。同时，在现实中的道路网络信息同样具有图的特征， 可以抽象为图对其进行存储，这也正是物流运输配送过程中路线选择可以应用g i s 理 论的基础。下面我们就详细的讨论图的相关理论。 3 1 1图的基本概念 一个图g 是一个三元组，这个三元组包含一个定点集v ( g ) ，一个边集e ( g ) 和 一个关系，该关系使得每一条边和两个定点( 不一定是不同的点) 相关联，并将这两 个定点称为这条边的端点回。 如图3 1 所示，顶点集为v ( g ) = l ，2 ，3 ，4 。5 ，边集e g ) = e l ，e 2 ，e 3 ， e 4 ，e 5 ，e 6 ，e 7 。 7 图3 1 图的基本形式 资料来源：本研究整理 从上面的图的基本定义以及实例中，但我们不难发现这样的图存在这样一条边， 它的两个端点是相同的如e 1 ，这叫做圈：而同样存在着具有统一对端点的多条边如e 4 ， e 5 ，这叫做重边。 。d o u g l a s b w e s ti n t r o d u c t i o n t o g r a p h t h e o r y ( s e c o n d e d i t i o n ) 2 0 0 6 1 5 七压，v欠致 对外经济贸易大学硕j ：学位论文 一个简单图是不含圈和重边的图( 如图3 2 所示) ，我们用点的集合和边的集合来 确定一个简单图，边的集合被表示为一组无序点对的集合，我们用e = x u ( 或e = t l x ) 来 表示一条以u ，x 为端点的边e 。 图3 2 有向图和无向图 资料来源：本研究整理 因此对图g 的表示方法为： g = v ，e ； v = x ，y ，z ，u ，w ) ； e - ， ， ， ， ， ) ； 在图3 2 中边的两个定点是无序的，成为无向图，而在图和每条边分配一个方向 是很自然的，例如在现实生活中的单行道路等，这样的图成为有向图( 如图3 3 所示) 。 对有向图，有向边e 用与其相关联的顶点x ，l i 的有序对来表示，即e = ，x 表示 边e 的起点，u 为边e 的终点。因此图3 3 就可以表示为： g = v ，e v = x ，y ，z ，1 1 ) e = ( ， ， ， ， ) 应用中往往还需要对图中的边赋值，这个值称为权。它可以表示边的各种不同的 意义：如经过边的是一条道路，则权就可能是它的长度，也可能是它的通行成本或通 行时间等。设边e 的权是w l ，则e 可以表示为： e = ( e i ，w 。) ，( e ：，w ：) ，( e 。，w n ) 或者设 w ：( w l ，w 2 ，砜 则此时，图g 可以表示为一个三元组，g = v ，e ，w 3 1 2图的存储方法 从上面对图的基本概念的分析，我们了解到图的结构比较复杂，任意两个定点之 对外经济贸易大学硕1 学位论文 间都可能存在联系，同时在有向图中同样两个定点之问的边并不相同，因此在存储数 据时无法以数据元素在存储区中的物理位置表示元素之间的关系，即图没有顺序影响 的存储结构。但可以借助数组的数据类型表示元素之间的关系，那么最好的表示图的 方法就是邻接矩阵表示图的基本关系。 对于无向图来说： i f - 1 若( i ，j ) 是图g 的边一 a i ，j j = l0 若( i ，j ) 不是图g 的边 例如图3 3 ： 图3 3 无向图的表示方法 资料来源：本研究整理 对于有向图，邻接矩阵如下所示： 厂1 若 是图g 的边 a i ，j j = l 0 若 不是图g 的边 例如图3 4 ： v lv 2v 3 v 4 v 1 厂0 10 l 1 v 2 i oo1l i v 3 | l 000 l v 4 l 1olo j 图3 4 有向图的表示方法 资料来源：本研究整理 显然无向图的邻接矩阵是对称的，但有向图的邻接矩阵则不一定。用邻接矩阵法 来表示有n 个定点的图，需要存放n 个定点的信息和n 2 个弧的信息的存储量。若考虑 无向图的邻接矩阵的对称性，则可采用压缩存储的方法之存入矩阵的下三角( 或上三 角) 元素。 对于有向图有权值的邻接矩阵的表示方法为； 1 7 、i l i _ 、 订，0订，o 以，o l ， 订o l l 1 ，。l 订也以讨 对外经济贸易人学顾士学位论文 a i ，j = 例如图3 3 2 建立路网模型 w 。若顶点i 到顶点j 有邻接边，w i j 为该边上的权 一若顶点i 到顶点j 无邻接边 图3 5 资料来源：本研究整理 路网模型是进行最有路线计算的基础，首先明确一个指导思想：即本节研究的路网 模型的表达方法及存储结果是为车辆调度系统完成最有路线计算这一核心功能服务 的。充分分析路网模型的基本要素，从而给下面计算最优算法提供一种符合实际的权 值，能够从时间和成本两方面对路径给出综合评价，给出最优路线。考虑到路网的特 殊性以及对最优路线计算问题的特殊意义，适合于同城最优路线选择系统的网络模型 应满足一下要求： 1 、能够充分表达路网结构及路网连通性 2 、能够表达路段单向交通、交叉口转向限制及分时段交通管制等信息 3 、能够反应路网对货车通行限制等约束条件 4 、能够表达路网的收费站 5 、能够体现路网动态交通信息的变化以及历史交通畅通数据 6 、能够体现交叉口转向延误 7 、便于动态最优路线计算 3 2 1地理网络概念模型 按照几何形态，空间实体被抽象成点、线、面等目标，从本质上说，地理网络属 于线状目标，是在弧段基础上生成的。弧段的构建网络之前具有完整的地理意义，通 过结构化的组织生成目标意义的网络体系。由弧段构建网络的过程表现为分解和合并 两方面，弧段的一部分作为边，参与网络的生成，或者多条弧段合并成一条边参与网 络的生成。为此提出段与路径的概念，路径是地理网络中具有较完整地理意义的特征 1 8 厂1瓢 对外经济贸易大学颀二j 二学位论文 子类，它可以与各种事件直接关联，路径也是地理网络分析结果的存储和显示方式。 通过段的概念，路径与地理网络的基本存储单元弧段联系。这样，利用路径系统和动 态分段模型就可以更好地表达和分析现实世界的地理网络国。 构成一个地理网络的元素可以分为地理网络边、地理网络节点、站、中心、拐角 等，地理网络在总体上由线状目标及其附属的点状目标组成，每种目标又有自己的属 性。 地理网络边是现实世界中各种线路的抽象，是网络中资源流动的路线、街道、河 流、输电线、输水管等。网络边构成了网络模型的框架，它可以用各种线状特征( 弧 段、路径) 来表示，而不仅仅局限于弧段。网络边有图形信息和属性信息。 网络边和网络边之间的连接点就是网络节点，它位于网络边的两端。节点可以表 示道路的交叉口多条网络连通网络节点建立联系。由于网络边不仅仅是弧段，因而 网络的节点与弧段的节点可以一致，也可以不一致。 在地理网络作为一种复杂的地理目标，除具有一般网络的边、节点间的抽象的拓 扑关系意义之外，还具有空间定位上的地理意义和目标组合上的层次意义。与一般的 地理目标一样，地理网络中的现状设施和点状设施除具有空间位置外，还具有丰富的 地理属性，如道路的路面状况、通行能力、交叉口的通行能力等，这些都是进行地理 网络分析的重要因素，同时对于物流运输与配送过程中的路线选择也存在着密切的关 系，因此对这些方面的因素都会在下面进行详细的讨论。 本文正是通过考察网络元素的空间数据和属性数据，对网络的性能特征进行多方 面的分析计算，找到最合适的路径。给物流运输和配送过程提供一种导航的作用，从 而节约物流成本同时提高物流的响应速度。 3 2 2 路网模型的基本要素 在g i s 中，网络模型由多个要素类( f e a t u r ec l a s s ) 组成，因为要素具有几何形状 并且可以显示，所以这种网络称为几何网络( g e o m e t r i cn e t w o r k ) 。构成网络模型的基 本要素包括：节点要素、路段要素、转向要素、交通区要素和o d 要素五类，其中最 重要的两类：点要素节点和线要素弧段。下面分别介绍节点和弧段在路网模 型中代表的对象及形成规则。 1 、节点 在网络模型中点要素称为节点( n o d e ) ，节点是弧段的端点，可以表示交叉路口。 但在实际路网中，道路属性信息发生变化，而且该属性的变化直接影响到作为路线最 优化算法一句的路权“。如在某处道路宽度显著减少，使得通行能力有了显著变化，由 此直接影响到车辆的行程时间，在这种情况下，为了满足最优路线计算的需要，需要 9 e 家耀，字同信息系统原理，科学：f ；版社北京，2 0 0 1 ”张小国一f 庆，上云，万德钧。