（计算机软件与理论专业论文）基于gis的混合业务车辆调度问题研究.pdf

摘要 混合业务车辆调度是指在物流配送中同时考虑集货业务，送货业务 和集送一体化业务的车辆路线规划问题。g i s ( g e o g r a p h i ci n f o r m a t i o n s y s t e m ) 技术能支持地理空间数据的获取、管理、操作、分析和显示， 以解决复杂的规划和管理问题。本文通过引入g i s 对道路网络的表达进行 了研究，构建了用于辅助车辆调度决策的辅助路网，建立了混合业务车 辆调度问题的数学模型，对该模型应用遗传算法进行求解。本文主要工 作与研究成果如下： 首先针对车辆优化调度模型中反复用到任意两配送点或配送点与配 送中心最短路径的要求，本文设计了一个辅助路网，用一个赋权有向完 全图来表示配送中心与配送点间的拓扑结构；针对有单双向限制和转向 限制的道路网络，本文提出了一种改进的增加网络限制集的表示方法， 对路网数据在g i s 的电子地图中的存储进行详细描述；对生成辅助路网的 最短路径算法进行了改进，提高了算法的执行效率。 其次对混合业务车辆调度的时间窗与混合业务的处理进行研究，在辅 助路网的基础上，建立了单配送中心、有时间窗、单车型的混合业务车 辆调度模型，用业务标识码解决了混合业务问题，用p d 对思想解决了集 送一体化业务问题，并对模型中参数定义、目标函数、约束条件进行详 细描述。 然后选择了遗传算法对该模型进行求解。分析了各类编码方式优缺 点，提出了带有服务顺序标识的配送点排列的编码方式，该编码方式便 于理解、解码，又具有较强的可扩展性的优点；采用优势自适应遗传算 法控制交叉率与变异率，防止了算法早熟收敛，提高了搜索精度；对不 满足约束条件的个体进行修改，使遗传算法在速度和性能上都得到提高； 还给出了算法的具体流程。 最后设计了一个基于g i s 的物流配送车辆调度系统原型，对主要功能 的设计进行详细描述。 关键词g i s ，混合业务车辆调度，辅助路网，遗传算法 a b s t r a c t h y b r i ds e r v i c ev e h i c l es c h e d u l i n gi s av e h i c l el i n ep l a n n i n gp r o b l e m t h a tw em a k eac o n s i d e r a t i o ns i m u l t a n e o u s l yp i c k u ps e r v i c e ，d e l i v e r ys e r v i c e a n dp i c k u p d e l i v e r ys e r v i c e g i st e c h n o l o g yc a np r o v i d eu sw i t hg e t t i n g ， m a n a g i n g ，o p e r a t i n g ，a n a l y z i n ga n dd i s p l a y i n go ft h eg e o g r a p h i cs p a c ed a t a t h i sp a p e rm a d es o m er e s e a r c ha b o u tu s i n gg ist od e s c r i b er o u t en e ta n d d e s i g n e da na s s i s t a n tr o u t en e t w o r ku s e dt oa s s i s tm a k i n gd e c i s i o no fv e h i c l e s c h e d u l i n g t h i sp a p e rm a d eam o d a lo fh y b r i ds e r v i c ev e h i c l es c h e d u l i n g p r o b l e m ，a n dt h e nu s e dg e n e t i ca l g o r i t h mt os o l u t et h i sm o d a l t h i sp a p e r m a i n l yd i dt h ef o l l o w i n gw o r ka n dr e s e a r c h e s ： f i r s t l y ，a i m i n ga tt h er e q u i r e m e n t sb e t w e e na n yd i s t r i b u t i o np o i n ta n d d i s t r i b u t i o nc e n t e r ，t h i sp a p e rd e s i g n e da na s s i s t a n tr o u t en e t w o r kw h e r ew e u s e dac o m p l e t ew e i g h t e dd i r e c t e dg r a p ht od e s c r i b e t o p o l o g ys t r u c t u r e b e t w e e nd i s t r i b u t i o nc e n t e ra n dd i s t r i b u t i o np o i n t s f o rt h er o u t en e t w o r k w i t hs i n g l ea n dd o u b l ew a yr e s t r i c ta n dt u mr e s t r i c t ，t h i sp a p e rp u tf o r w a r da d e s c r i p t i o nm e t h o do fu s i n gn e tr e s t r i c t s e ta n dd e s c r i b e dt h em e t h o do f s a v i n gt h er o u t en e to nt h ee l e c t r o n i cm a po fg i s a n df i n a l l yt h ep a p e rm a d e a ni m p r o v e m e n to i lt h em i n r o u t ea l g o r i t h m t h ei m p r o v e m e n tm a d et h e a l g o r i t h me f f i c i e n tt og e n e r a t et h ea s s i s t a n tr o u t en e t w o r k s e c o n d l y , t h i sp a p e rm a d er e s e a r c ho n t i m ew i n d o wa n dh y b r i ds e r v i c e b a s i n go nt h ea s s i s t a n tr o u t en e t w o r k ，t h i sp a p e rm a d eah y b r i ds e r v i c e v e h i c l er o u t i n gm o d e lw i t hs i n g l ed i s t r i b u t i o nc e n t r e ，s i n g l ev e h i c l et y p ea n d t i m ew i n d o w w eu s e ds e r v i c em a r kt os o l u t et h eh y b r i ds e r v i c ep r o b l e ma n d u s e dp dm e t h o dt os o l u t ep i c k u p - d e l i v e r ys e r v i c ep r o b l e m a m o n gt h i s m o d e l ，w ed e s c r i b ep a r t i c u l a r l yp a r a m e t e rd e f i n i t i o n ，o b j e c tf u n c t i o na n d r e s t r i c t i o nc o n d i t i o n s ，e t c t h i r d l y , t h ep a p e rc h o s eg e n e t i ca l g o r i t h mt os o l u t et h i sm o d e l t h i s p a p e ra n a l y z e dt h ea d v a n t a g ea n dd i s a d v a n t a g eo ft h ec u r r e n tc o d i n gm e t h o d a n dd e s i g n e dan e wc o d i n gm e t h o dw i t hu s i n gl o g oo ft h eo r d e rw i t ha d i s t r i b u t i o nc e n t r ea r r a n g e m e n t t h i sc o d i n gm e t h o di se a s yt ou n d e r s t a n d a n dd e c o d i n gw i t ht h ea d v a n t a g eo fs t r o n ge x p a n s i b i l i t y t h i sp a p e ru s e d a d a p t i v eg e n e t i ca l g o r i t h mt oc o n t r o lt h ec r o s s - - r a t ea n dm u t a t i o n r a t ei no r d e r t op r e v e n tc o n s t r i n g e n c ye a r l i n e s sa n di ti m p r o v e dt h es e a r c hp r e c i s i o n m e a n t i m ew em o d i f i e dt h ei n d i v i d u a l sw h i c hd i d n ts a t i s f yr e s t r i c ta n dt h i s m a d et h ea l g o r i t h mi m p r o v e dt h es p e e da n dc a p a b i l i t y a te n dt h i sp a p e r p r e s e n t e dt h ef l o w o f t h ea l g o r i t h m f i n a l l y , t h i sp a p e rd e s i g n e dap r o t o t y p es y s t e mo f v e h i c l es c h e d u l i n go f h y b r i ds e r v i c eb a s e do ng i s t h e nt h ep a p e rd e s c r i b e d t h er e a l i z a t i o no ft h e k e yf u n c t i o ni nd e t a i l k e yw o r d sg i s ，h y b r i ds e r v i c ev e h i c l es c h e d u l i n gp r o b l e m ，a s s i a t a n t r o u t en e t w o r k ，g e n e t i ca l g o r i t h m s 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：墨至应 日期：塑堕年月竺日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学 位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以 采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 作者硌丝虹导师签弹日期塑年上月竺日 硕+ 学位论文 第一章绪论 第一章绪论 1 1 课题背景 物流配送是现代流通业的一种经营方式。物流是指物品从供应地向接收地实体流 动的过程1 1 l 。在物品的流动过程中，根据实际需要，它包括运输、储存、装卸、包装、 流通加工、配送、信息处理等基本功能活动。配送指在经济合理区域范围内，根据 客户需求，对物品进行拣选、加工、包装、分割、组配等，并按时送达指定地点的 物流活动。物流与配送关系紧密，在具体活动中往往交结在一起，为此人们习常把 物流配送连在一起表述。 物流配送车辆调度是指物流配送企业为了提高配送车辆的利用率，降低物流成 本，提高服务水平，在满足客户要求的前提下，合理安排配送车辆从配送中心出发， 按最佳行驶路线依次完成配送任务，保证总成本最小。 客户的需求就是要在一定的时间内实现货物的移动，根据配送业务的性质，起终 点可以把它分成集货业务、送货业务、集送一体化业务。由于我国的物流配送企业 业务种类比较多，每个客户的需求量较少，对单个物流配送企业而言，他们的客户 需求往往是三种业务混合在一起的，需在车辆调度过程中将它们同时进行考虑。 地理信息系统【2 3 】( 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 ) 作为计算机科学、地理 学、测量学、地图学等多门学科综合的交叉学科，除了具有信息系统的各种功能外， 还能够进行相关的空间数据可视化操作，并在此基础上进行更为复杂的空自j 查洵与 分析等，g i s 技术的快速发展和广泛应用给物流企业的车辆调度提供了新的思路。 根据我国物流企业的混合业务特点，本文重点研究混合业务下物流配送企业的车 辆调度问题，同时借助g i s 技术辅助车辆调度处理和车辆调度系统的集成开发。 1 2 问题描述 1 配送中心。本文中的配送中心是一个广义的概念，指的是车辆的出发地，可 以是物流中心，仓库，车场等。许多大型的物流配送企业常常多个配送中心，多台 车辆，由调度中心统一调度，对这种企业来说他们的车辆调度是一个多配送中心的 车辆调度。 2 客户。客户是物流企业服务的对象，从不同的角度可以将客户划分为不同类 型，本文是从客户业务需求的角度研究车辆调度，按照需求不同，客户可分为集货 客户、送货客户和集送一体化客户。 3 集货业务。指按照集货客户的要求，将货物从某配送点运回配送中心，这个 硕士学位论文 第一章绪论 配送点称为集货点，如图1 1 所示。 4 配送点 配送中心 。配送点 + 货物转移方向 务示意图 将货物从配送中心送到某配送点，这个 配送中心 。配送点 货物转移方向 图1 - 2 送货业务示意图 5 集送一体化业务。指按照客户的要求，将货物从配送点玑装货，然后运到配 送点q 卸货，u j ，一为一个配送对，称为配送对前点，l 称为配送对后点。如图l 3 所示。集送一体化业务有特殊的配送要求：( 1 ) 该配送对必须由同一辆车进行服务； ( 2 ) 在配送过程中，车辆必须先经过坼，后经过q 。 o o 譬_ o + o 圈 配送中心 。配送点 + 货物转移方i j 图1 - 3 集送一体化业务示意图 混合业务的车辆调度指在同时考虑集货业务、送货业务和集送一体化业务的前提 下，合理安排车辆与配送路线，满足客户要求，使总成本最小。 1 3 研究现状 1 3 1 车辆调度问题研究 车辆调度问题( 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 ) 可以抽象为路线安排问题或者 车辆路径问题 4 】( v e h i c i er o u t i n gp r o b l e m ，v r p ) ，车辆路径问题可以看成是旅行商问 题( 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 ) 的延伸。1 9 世纪著名的数学家w i l l i a mh a m i l t o n 对t s p 问题描述为：假设有一个旅行商人要拜访n 个城市，他每个城市只能拜访一 2 图一 硕+ 学位论文 第一章绪论 次，而且最后要回到原来出发的城市，路径的选择目标是要求得的路径路程为所有 路径之中的最小值。t s p 问题是一个组合优化问题。该问题可以被证明具有n p c 计 算复杂性。因此任何能使该问题的求解得以简化的方法，都将受到高度的评价和 关注。v r p 问题将t s p 问题扩展为：用一个车队去服务一系列的客户，每个客户都 有不同的业务需求，每个车辆都有载重量限制，如何安排合适的行车路线，使得总 成本最小。 车辆调度问题几十年来一直是一个研究热点，尤其是近几年来随着物流在社会中 的地位越来越重要，很多专业如系统工程、交通工程、计算机、数理等的学者、研 究人员都在对此进行研究。但在以往的研究中，通常研究的是单纯的集货或送货、 同时考虑集货与送货或是只考虑集送一体化业务的车辆调度问题，对混合业务的车 辆调度问题研究得很少【5 1 。由于混合业务的复杂性，给建模和优化算法增加了新的困 难，下面就单纯集货或送货、同时考虑集货与送或只考虑集送一体化业务的车辆调 度问题研究现状作一概括分析。 1 单纯集货或送货业务的车辆调度问题研究 纯集、送货的车辆调度问题是最简单也是最常见的的一种类型，是经典的车辆路 线问题，也是研究其它业务类型的车辆调度的基础。国内外对此问题上的研究主要 是根据不同的酶提条件建立起模型，并选择合适的算法进行求解。 f e i y u el i l 6 】在他的博士论文中对不同条件下的送货业务车辆调度问题进行了研 究，针对不同的车辆数和业务数量建立了相应的模型，应用不同的优化方法进行了 求解。我国的骆义i7 】建立的模型情况如下：单一物流配送中心供货，处理的业务中只 有送货业务，并且货物足够多，不存在缺货现象；车型是单一的，并且所有配送车 辆的起始点都是物流配送中心；路网为完全网络，无方向性，在网络中也没有考虑 交通状况。他对时问窗的惩罚函数做了一定的改进，并且用遗传算法和启发式算法 相结合求解了模型。另外，卢安文【引、倪勤1 9 l 等人也做过相关研究。 2 集货业务、送货业务一起考虑的车辆调度问题研究 只考虑单纯集货或送货的物流配送有一个明显的缺点，在车辆回程或去程的过程 中车辆就为空载，于是利用回程车辆的空闲容量来降低成本、增加收入就成了人们 新的追求目标。这类问题最早由g o l d e n l 0 】等人提出，在他们的假设中允许有集货业 务需求的客户在送货业务需求的客户之前被访问，使用基于在收货客户的路线中插 入送货客户的方法来求解该问题；另# b c a s c o t j 等利用c l a r k e 和w d g h t 所提出的节约 法来构造有配送需求客户的初始路径，有集货需求客户则是使用修改后的g o l d e n 等 人的插入法，其思路是当剩余的配送量足够少时，才允许集货点插到配送点之前。 3 集送一体化业务车辆调度问题研究 集送体化业务的要求是将货物从一个配送点转移到另一个配送点，因此需将 它作特殊处理。对集送一体化业务处理方法大体上分为两种：西南交通大学的李军 教授把集送一体化业务看成一个连续的任务，它们是一个不可分割的整体，如果执 3 硕士学位论文 第一章绪论 行了集货，下一步必须为送货。尽管这样处理比较简单，并且也可以解决问题，但 是该方法在集送一体化业务中不能插入纯集货业务或送货业务，与实际状况不符。 另一种方法是将集送一体化业务分成两个独立的业务：集货业务( p i c k u p ) 和送货业 务( d e l i v e r y ) ，即一仑p d 对，在业务的完成过程中，只要保证集货业务和送货业 务由一辆车来完成，并且集货业务在送货业务之前完成即可。典型的例子有h a i b i n g l i l b 】等人提出的内置禁忌搜索的模拟退火算法( t a b u e m b e d d e ds i m u l a t e da n n e a l i n g a p p r o a c h ) 解决了一般的多车辆集送一体化的车辆调度问题。在局部搜索的时候， 该算法主要应用了三种机制：p - d 对移位操作、p d 对交换操作、p d 对重新排列。通 过这三种操作控s u p d 业务的两个客户总是由同一辆车进行服务，并且集货业务总是 在送货业务之前得到处理。 1 3 2 车辆调度优化算法研究 车辆调度问题是一个n p 难题，随着客户数量的增加，可选的配送路径方案数量 将以指数速度急剧增长，即出现组合爆炸现象【1 4 j 。求解物流配送车辆调度问题的方 法很多，究其实质，可以分为精确算法和启发式算法两大类。精确算法是指可求出 其最优解的算法，主要有：分枝定界法、割平面法、网络流算法、动态规划法等。 由于精确算法的计算量一般随问题规模的增大呈指数增长，在实际中其应用范围很 有限。为此，专家们把精力主要用在构造高质量的启发式算法上。， 常见的启发式算法有如下几种： 1 c 。ws a v i n g s 算、法1 1 5 j 该算法的基本原理是几何学中三角形的两边之和大于第三边。节约量 一 岛= 巴+ 岛一g ，i j ，f ，j = 1 ，2 ，刀。该算法首先将所有墨，按非增顺序排列，然 后从最大的爵开始，确定是否存在两条路径，其中一条从弧( 0 ，i ) 开始，而另一 条以弧( i ，o ) 结束，如果存在，则提供去掉弧( 0 ，i ) 、( i ，o ) ，引入弧( i ，i ) 合并这两条路径，重复上述过程直到没有路径可以合并。 2 s w e e p 算法1 1 6 1 该算法首先计算要访问的顾客位置的极坐标，并按极坐标角度大小排序，然后在 未分配到任何路径中的顾客中从角度最小的顾客开始，依次将顾客归并到相应的路 径中，直到车辆的能力约束满足为止，再重新选择新的车辆。重复上述过程，直到 一所有的顾客都分配完毕。最后利用t s p ( t r a v e ls a l e sp r o b l e m ) 的优化算法对各予路 径进行优化 3 遗传算法i j ( g e n e t i ca l g o r i t h m ，g a ) j l a w r e n c e 最先将g a 应用于v r p 并能有效的求解。在车辆数不事先固定情况下， 把聚类和排序有机地结合在一起，利用g a 与3 o p t 的混合算法对v r p 求解，可获得较 好的解，计算时问也可以接受。b a r r i em b a k e r 等采用邻域搜索与3 o p t 的混合算法求 4 硕士学位论文 第一章绪论 v r p 。计算结果表明g a 在计算时问和求解质量等方面并不劣于t s l l 8 】( t a b us e a r c h ) ， s a l j 州( s i m u l a t e da n n e a l i n g ，模拟退火) 。 4 禁忌搜索算法( t a b us e a r c h ，t s ) s t 在v r p 中应用广泛，许多研究者都倾向于选择该算法，主要原因是该算法设计 简单，计算效率较高，几乎所有类型的v r p 都有利用t s 求解的例子。 5 蚁群优化算法1 2 们( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 由于蚁群优化算法能有效地求解t s p ，将它应用于r v p 是一种自然地推广。b e m d b u l l n h e i m e r 2 1 】等修改了仇，设计新的信息素更新公式，并和2 o p t 混合求解v r p ，所 得的结果并不总是劣于t s ，l s m a i lt l l a b b i b 等通过设计r , 所得到的简单a c o ，不仅能 求解规模较大带时间窗v r p ，而且所求解优于以g a 、s a 等算法。当然a c o 在v r p 中的应用研究才刚刚起步，计算效果和计算效率还有待进一步改进。 1 3 3g i s 在车辆优化调度中的应用 g i s 是一门以计算机为基础的交叉性、边缘性的新学科，是管理和研究空问数据 的技术系统。它利用计算机建立地理数据库，将空间地理分钷状况及所具有的属性 进行数据存储，建立数据管理系统，方便快速地获得信息，同时具有各种分析和处 理功能。 从应用层面来讲，g i s 的应用就是对电子地图的使用。电子地图实质就是传统地 图的电子化2 2 彩1 。2 0 世纪6 0 年代，人们将计算机引入到地理信息管理领域，主要是 想借助计算机的数字化手段来提高工作的效率。但随着计算机技术的发展，地图的 数字化为人们生活所带来的便利远远超出了最初的期望，其动态、可编制的地理要 素内容和显示效果是传统的地图所无法比拟的，也为地理信息与其他信息的集成提 供了可能。因此电子地图系统可以说是g i s 系统的核心内容。 车辆优化调度中涉及到大量的空问地理信息，如车辆调度所涉及的各配送点的地 理位置及其相应的路径情况、配送点之问的距离最短路径等，这些都需要使用到电 子地图的查找和分析功能。而对车辆优化调度的结果进行直观的显示，则更需要使 用电子地图的编辑和输出功能。因此如何利用电子地图在车辆优化调度系统中是很 重要的一个组成部分。 1 4 本文的主要工作及结构安排 1 4 1 本文主要工作 1 辅助路网的构建。本文分析了物流配送中道路网络的特点，对有单双向限制 和转向限制的道路网络表示方法及存储进行了研究；对物流配送车辆调度优化模型 中经常要用到任意两配送点或配送点与配送中心最短路径的要求，本文设计了一个 5 硕+ 学位论文 第一章绪论 辅助路网，用一个赋权有向完全图来表示配送中心与配送点间的拓扑结构并对生成 该路网的最短路径算法进行了改进。 2 混合业务车辆调度问题建模。对混合业务车辆调度的时问窗与混合业务的处 理进行研究，采用了软时间窗处理时间窗问题，用业务标识码解决了混合业务问题， 用p d 对的思想解决集送一体化业务问题。然后在辅助路网的基础上，建立了单配送 中心、有时间窗、单车型的混合业务车辆调度的数学模型，并对模型中参数定义、 目标函数、约束条件等进行了详细描述。 3 车辆调度优化模型求解算法。本文在目前各类启发式优化方法中，选择了遗 传算法对该模型进行求解。通过研究各种自然数编码的优缺点，提出了带有服务顺 序标识的配送点排列编码方式：在交叉率与变异率的控制上，采用了文献【6 2 】的优势 遗传自适应算法，并对该算法进行了验证；对不符合约束条件的个体采用了修改策 略，使算法在速度和性能上都得到提高。 1 4 2 论文结构 第一章绪论。阐述课题背景、研究现状、本文的主要工作及意义和文章的组织 结构。 第二章辅助路网的构建。本章对道路网络的拓扑结构特点进行分析，使用了改 进的增加网络限制集的方法。对生成辅助路网的最短路径算法进行改进，并给出了 生成辅助路网的步骤。 第三章混合业务车辆调度问题的建模。本章首先对时间窗和混合业务的处理进 行研究，然后建立了单配送中心、有时间窗、单车型的混合业务车辆调度模型，详 细描述了模型中的参数定义、目标函数及约束条件。 第四章混合业务车辆调度问题的遗传算法求解。本章主要对遗传算法中编码的 设计、交叉率与变异率的确定和约束条件的实现进行了研究，给出了该遗传算法的 总体流程图。 第五章设计了一个基于g i s 物流配送车辆调度系统的原型系统。按照系统开发 背景、系统总体设计、主要功能实现的顺序进行详细描述。 第六章总结与进一步的工作。总结本文的研究内容和所做的工作，阐述进一步 的研究方向。 6 硕士学位论文 第二章辅助路网的构建 第二章辅助路网的构建 为了从基础道路网络( 以下简称路网) 中抽象出辅助路网以满足车辆优化调度的 数据要求，本章首先对路网的拓扑结构特点进行了分析，为其选择了合适的表达方 法和并对其在g i s q h 的存储进行了研究，然后分析了辅助路网的拓扑结构特点，并对 生成辅助路网的关键技术即最短路径算法进行了研究，最后给出了详细的生成步骤。 2 2 路网的表示及存储 在g i s 理论中，常将空间事物抽象成点、线、面等几何要素 2 6 - 2 8 1 。点、线建立拓 扑关系可以组成网络。网络在几何上由边连成，边的断点、交点是网络的节点。g i s 网络分析的理论基础是图论。现实中的道路网络和本章要构建的辅助路网都具有图 的特征，可以抽象为图对其进行存储，下面我们就详细的讨论图的相关理论。 2 2 1 图论基础 1 图和有向图 在图论中，有序- - - 元组g = y ( g ) ，e ( g ) ，畈j ) 称为一个图 其中： 矿( g ) 称为节点集； 。 e ( g ) 称为边集或弧集； 坝j 称为关联函数，是e ( g ) 到v ( g ) 的映射。 如果是e ( g ) 到v ( c ) 的无序对集合的映射，则g 称为一个无向图，e ( g ) 称为 边集。类似的，如果恢；是e ( g ) 到v ( g ) 的有序对集合的映射，则g 称为一个有向图， e ( g ) 称为弧集。 v ( g ) 中的元素称为节点，e c g ) 中的元素称为边或弧。y ( g ) 所含元素的个数即 节点个数称为图的阶，记为f v ( g ) l 或聆，e ( g ) 所含元素的个数称为g 的边数或弧数， 记为i 层( g ) i 或m 。 2 稀疏图和稠密图 对于无向图，边数m 最大允许值为妄”( 行一1 ) ，对于有向图，弧数m 的最大允许 z 值为n ( n 1 ) 。边数或弧数远远小于此值的图( 如m = o ( n ) 或m n l o g n ) 称为稀疏图， 反之称为稠密图( 如m = o ( n 2 ) ) 。 3 赋权图 图的边或弧可具有与之相关的量化信息，表示从一个节点到另个节点的距离、 费用等等，这些与图的边或弧相关的量化信息n q 做权，这种边或弧带权的图称为赋 7 硕十学位论文第二章辅助路网的构建 权图或赋权有向图，通常又称为网络。 一般地，将弧( 甜，v ) 上带的权记为w ( u ，v ) ，它也称为这条弧的长度。 4 路径和路径长度 有向图g = ( y ，e ) 的路径是一个非空的节点序列，即 p = v i ，v 2 ，) 其中v ，y ( 1 f 七) ，且( v f ，k 1 ) e ( 1 f j i ) 。此时路径p 的长度三p 定义为七一l 。 对于赋权有向图，路径p 的长度是其所经过的弧的长度之和，即 l p = w ( u ，i ，) ( h ，v ) p 若路径p 是从节点”到v 的所有路径中长度最短的一条，则称p 是从节点u 到1 ， 的最短路径，其长度记为l ( u ，v ) ，称为从节点u 到v 的最短距离。 2 2 2 路网的拓扑结构特点及表示方法 路网的经典表示方法是赋权图。用节点表示路网中的点状实体，用边或弧表示路 网中的路段，用边或弧的权值表示路段的长度。在实际道路网络中，交通管理部门 经常会采取一些交通管制措施，比如单向行驶、交叉口转向限制等，由此造成直观 上连通的路线，在实际交通行为中是不可达的。如图2 1 ，因为单向限制，使得从节 点l 到节点4 方向的路径是不通的，由于交叉口转向限制，使得3 j l 一2 与5 专l 专2 的转向是禁止的。 4 5 d i l 1 k 、 一 人 c 1 ，- a i 冰， b i 3 图2 - 1 交通限制信息示意图 2 对于单向限制，可以采用前面介绍的有向图的理论，用两条弧来表示双向通行的 路段，用一条弧表示单向通行的路段。交叉口转向限制则比较特殊，因为在数据库 中对各节点及弧段的存储并没有左右之分，因此交叉口转向限制并不能单纯的通过 有向图来解决，而应该采用其它方法。我国的戴文舟1 2 9 1 用过路口拓展法解决这个问 题，但该方法存在着增加大量虚拟节点的缺点；也有很多学者采用过对偶图 ! 去【3 帕l l 来解决交叉口转向限制，该方法的优点是不会增加网络中的节点，但它会完全改变 网络拓扑。我国的吴向华、蔡翔云1 3 2 l 使用了增加网络限制集的方法较好的解决了交 8 硕十学位论文第二章辅助路网的构建 叉口转向限制，他将路网这样表示： r w = ( r ，n ，k ) r = | x ，y n ，l ( x ，y ) ) n = i l ( n j ，) ，伟，伤r ，且惕，他存在公共结点) l r = m ，刀) 1 所，刀n ，上( 聊，以) ，且m 和府在公共结点) 其中肌代表整个路网，尺代表路段集合，其元素是有序对 ，谓词l ( x ，) ，) 表示由节点x 到节点y 存在一条有向通路，如图2 1 所示，若分别用x t ，矗表示节点i 、 节点2 ，则 就表示从节点1 到节点2 有一条有向道路a 。 代表网络两个路段的拓扑关系集合，有序对 表示连接路段啊到路段 的道路节点，谓词( 啊，n 2 ) 代表路段啊可通行到路段。如图2 1 ，有向路段d 可 通行到有向路段c ，则 代表从d 到c 的节点1 。 三。代表转向限制的集合，其元素是有序对 ，其中谓词( 肌，刀) 表示从有向 路段m 到有向路段r 不存在有向通路，即转向限制。如图2 一l ，若。存在 ， 则表示在交叉路口1 处禁止从有向路段b 行驶到有向路段a 。 这种方法的优点：没有改变路网的拓扑结构，也没有新建虚拟点或孤段，仅增加 了一个转向限制集来表示交叉口转向限制，能够充分的表示路网的拓扑结构。 这种方法的缺点在于： ( 1 ) 使用弧来表示路段，增加了路网数据量。在路网中，单向限制的路段一般 是很少的，双向路段的来回长度是相等的，使用有向图来表示路网，无疑增加了路 网数据量； ( 2 ) 进行最短路径分析时，传统的d i j k s t r a 算法是对节点进行搜索的，使用该方 法时，考虑下一个节点是很麻烦的。例如，当前结点是l ，考虑下一个搜索节点2 时， 首先要分析节点l 的前一个搜索节点，如果前一个搜索节点是3 ，根据b o 爿是转向 限制的，即 专 转向限制，因此节点2 不应该成为下一个搜索节点。 受该方法启示，本文也采用增加网络限制集的方法表示路网，并对这种方法进行 改进。使用图论中常用的符号，本文将路网表示为： g = ( e ，v ，厶) e = v ，甜，i ) 1 1 ，“v ，i = l ，2 v = h ，v 2 ，k i k = ( _ ，如，) i ，_ ：，气y 且三( ，) 较之文献【3 2 】中的表示方法作了如下改进： ( 1 ) 将路段用无向图中的边 表示。当i _ 1 时，表示该边对应的路段是单 向的，从v 到u 的方向，当i ：2 时，表示该边所对应的路段是双向的。因此该无向图中 边的数量大概是文献1 3 2 1 中有向图中弧的数量的一半，大大减少了数据量。 9 硕士学位论文 第二章辅助路网的构建 ( 2 ) 以节点转向限制代替路段转向限制。z ( 匕，v j , 虼) 表示匕专v 的转向是 禁止的。作最短路径分析时，首先保存当前节点的前一个访问节点，考虑下一个节 点时，只需从节点转向限制集查找就可以了。 2 2 3 路网数据存储 路网数据作为g i s 数据的一种，由道路实体的几何空问数据和非几何属性的属性 数据构成。空问数据表达了物体地理实体的几何定位特征，一般以坐标数据来表示， 如城市和道路交叉口在路网中的空间位置，路段的空间位置等；属性数据表达了地 理实体和几何位置无关的属性特征，如路段的编号、等级、里程、路段交通量等。 在g i s d ? ，空问数据和属性数据是分别存储蒯2 4 2 5 1 。两者之间通过一定的索引机 制联系起来。数掘索引机制是指空间对象与属性数据之间相互关联的方法。索引过 程是这样的： ( 1 ) 当从属性信息查询空间信息时，先要在属性数据文件中找到相应的数据库 记录，如记录号为n ，则可以在交叉索引文件中找到第n 个指针，该指针所指向的地 图对象就是与数据库记录相对应的空间对象。 ( 2 ) 当从空间信息查询属性信息时，如果己从地图上查到某一空间对象，可以 从空间数据文件中读出其空白j 信息和与之对应的数据库记录号，根据数据库记录号 就可以在属性数据文件中查到该地图对象的属性信息。 g i s 是以表( 数据库) 的形式来组织信息，表与地图之间通过地图图层建立密切 的联系，每个图层包含了整个地图的一个不同方面。本文使用的电子地图是已经设 计好了的，包含了多个图层，其中对车辆化化调度最为重要的是道路网络层。但这 个图层并没有完全表达路网的拓扑结构。为了使电子地图能够表达本文所述的路网， 需对它的属性表作一定的修改。首先为路段表增加了一个属性项，存储路段的单双 向限制信息，然后增加一个转向限制表，存储交叉口转向限制信息。这样就可以利 用原电子地图的数据很好的表达路网的拓扑结构。具体的属性表设计将在第五章的 系统设计中详细叙述。 2 3 辅助路网的生成 最短路径分析是车辆优化调度的基础，因为在进行车辆调度时，我们希望车辆在 访问邻近的两个配送点时，尽量走最短的路径，以节省成本。因此本文在用户录入 配送点与配送中心信息后，通过最短路径的分析，得到任意两个配送点或配送点与 配送中心的最短路径，抽象出一个只有配送点与配送中心拓扑关系的辅助路网。在 问题建模与模型求解过程中需要最短路径信息时，直接从辅助路网的距离矩阵提取 就可以了。 1 0 硕七学位论文第二章辅助路网的构建 生成辅助路网的具体步骤如下： ( 1 ) 在原路网上标记配送中心与配送点信息。如图2 - 2 ，原路网中共有8 个节点， 9 条路段，除了 是单向路段外，其余都是双向的；只有一个转向限制：8 斗4 3 。 在标记配送点与配送中心后，对原路网作如下更改：标记点在原路网的某条边上， 将该边拆分为两条边，如配送点a 将边 4 ，拆分为 ， 两条边；标记 点在原路网某个结点上，用该点代替原节点，如配送中心b ，代替原节点8 ，不在原 路网中上的标记点，与最近的一个节点相连，形成边，如配送点c 与6 相连形成一条 新的边。更新后的路网拓扑结构如图2 3 所示。 叶尸3 一6 7 一一一 8 二- 一一5 r - o 。3 一一二c ，6 7 7 - i 一一一一? ，一乏4 一下一，5 一 舻孑刃赋点 乡 硕七学位论文第二章辅助路网的构建 在生成辅助路网的过程中，第一步可以通过对电子地图的操作而实现，第二步的 最短路径的分析是最关键也是最难处理的，我们接下来重点讨论。 2 3 1d i j k s t r a 算法改进 d i j k s t r a 算法是由e w d i j k s t r a 于1 9 5 9 年提出的一个最短路径算法，也是目前公认 的求解最短路径问题的最经典算法。它可以给出从某个指定顶点到其他顶点的最短 路径，其时间复杂度为o ( n 2 ) ，n 代表顶点数。 d i j k s t r a 算法实现的主要是利用松弛技术1 3 3 l ，这种技术的实质是反复减小每个节 点实际路径权值的上限，直到该上限等于最短路径的权值为止。此算法首先把图中 的所有顶点分成两个集合，集合s 和集合t 。集合s 包含了以s t a r t p o i n t 为源点的己经确 定了最短路径的所有终点，它的初态只包含s t a r t p o i m ；集合t 包含了尚未确定最短路 径的顶点，它的初态是包含除源点s t a r t p o i n t # b 的路网中的所有顶点。在算法的执行 过程中，首先按各顶点与源点s t a r t p o i n t 问的最短路径长度递增的次序，来设置优先 级队列口，再通过优先级队列口的相应操作，逐个把t 集合中的顶点加入到s 集合中 去，并使得从s t a r t p o i n t 至t s 集合中各顶点的路径长度始终不大于从s t a r t p o i n t 至t j 集合t 中各顶点的路径长度，直到找到目标点e n d p o i n t 为止。 一般的d i j k s t r a 算法是采用线性数组来实现优先级队列，在文献 3 4 1 提出了使用堆 代替线性数组实现优先级队列来进行改进，取得了较好的效果。本文也采用这种方 法，并根据前文所述路网的拓扑结构特点作一定的改进。 w i l l i o m s 在1 9 6 4 年提出了堆排序方法，该方法引入了堆这种特定的数据结构。这 里二叉堆结构可以被视为一棵完全二叉树，而且其含义表明，完全二叉树中所有非 终端节点的值均不大于( 或不小于) 其左、右子节点的值。除了用于堆排序之外， 二叉堆最常见的应用是作为高效的优先级队列。该优先级队列是一种用来维护由一 组元素构成集合s 的数据结构，而且这一组元素中的每一个都有一个关键字k e y 。一 般作用于优先级队列上的二叉堆的相应操作有： h e a p i r y ( s ) 即首先将集合s 调整成二叉堆，并设定其根节点具有最小关键字： 然后浚操作从堆的根节点开始，通过对当前节点的左右子树关键字的比较，来调整 相应节点在堆中的f 确位置，即通常所谓的“筛选”过程，而且此操作为维持堆性 质的关键。 h e a p i n s e r t ( x ，s ) ：s u x 卜s ，即将元