（交通运输规划与管理专业论文）基于电子地图的车辆优化调度及管理的研究.pdf

摘螫 摘要 智能交通系统是改善城市交通运输状况的重要手段，对其丌展研究具有重要 的实际意义。 本文的中心内容是：组建了一个基于电子地图大型车队优化凋度及管理系 统，并用动态规划算法实现了车辆的智能调度。具体工作包括以卜儿点： ( 1 ) 设计了车辆调度系统总体框架及各子系统结构模块。 ( 2 ) 结合电子地图设计和制作过程中所使用的软、硬件，并根据电子地图所 具有的图层以及相应的图层属性，成功地设计和制作了一幅用于车辆优化调度 的交通电子地图。 ( 3 ) 建立一个大型车队信息数据库。对车辆信息进行存储、索引、查询处理 和事务管理。 ( 4 ) 用d i j k s t r a 算法实现了城市中两点间最短路径搜索，在此基础k 实现 了基于电子地图的大型车队优化调度及管理的系统软件。 最后对城市交通流诱导系统存在的问题和发展前景进行了分析和展望。 ：t 题词：智能交通系统，电子地图，优化调度，d i j k s t r a 算法 两北 _ ：业人学坝卜论文 a b s t r a c t i n t e l l i g e n t f r a f f i es y s t e mi st h ei m p o r t a n tm e t h o dt h a li m p e v e st h e u r b a nt r a f f i cs i t u a t i o n t h es t u d yt oi n t e l l i g e n tt r a f f i ( ：s y s t e r nh a s s i g n i f i c a n c eo fp r a c t i c e t h i s p a p e ri s t oe s t a b l i s ha s y s t e mb a s e do n e 1e ( 1 t f o n i c m a p f o r m o t o r c a d e o p t i m 【z e dd i s p a t c h i n g a n dd y n a m i cp r o g r a m m i l t ga i g o t il h mis u s e dt or e a l i z ev e h i c l ed i s p a t c h i n g t h em a i nw o r ki n c i u d e s ： ( 1 ) t h ef r a m e w o r ko fam o t o r c a d e o p t i m i z e d d i s p a t c h i n gs y s t e mi s d e s i g n e d ，a n ds t r u c t u r e so fe a c hs u b s y s t e ma r eg i v e n ( 2 ) ak i n do ft h ed e s i g nm e t h o do fd i g i t a lr o a dm a pw it ht l a f f i ci s p r o p o s e d m o r e o v e r a t r a f f i cd i g i t a lr o a dm a pw i t hv e h i c l ea s s i g n a t i o n e x p e r i m e n t i s d e s i g n e db yt h i sm e t h o ds u c c e s s f u l l y ( 3 ) ad a t a b a s eo fv e h i c l em a n a g e m e n ti n f o r m a t i o nisb u i tt o c e c o r d i n d e x ，a n dq u e r yt h ev e h i c l ei n f o r m a t i o n ( 4 ) a ne f f i c i e n ta p p r o a c ho ft h es h o r t e s tp a t ha l g o z i t b mw h i c hisb a s e d o nd i j k s t r aa l g o r i t h mi sr e a l i z e d am o t o r c a d e o p t i m i z e d d i s p a t c h i n g s o f t w a r eisr e a liz e d f i n a l l y ，f u t u r ea p p l i c a t i o n s o ft h eu r b a nt r a f f i cf l o w g u i d a n c e s y s t e ma r ed i s c u s s e d k e yw o r d s ：i n t e l l i g e n tt r a f f i cs y s t e m ，e l e c t r o n i cm a p m o t o r c a d e o p t i m i z e d ，d i j k s t r aa l g o r i t h m ； i l 第一章绪论 衍币绪论 1 1 引言 2 0 世纪六七十年代，世界各国经济发展进入了高速增长期，汽车数量急剧 增加，导致已有的道路难以满足经济发展的需要，从而产生系列的问题就是 交通问题。最近的一项研究表明，仅美国的主要城市每年由于交通捌挤而造成 的浪费就超过4 7 5 亿美元，每年因交通拥挤浪费了多达1 4 3 5 亿l 的燃料和2 7 亿工作小时。在国土狭小的日本，人口密度比较大，每天昼夜行驶的汽车有7 0 0 0 万辆，每年交通事故死伤人数达1 0 0 余万人，汽车交通的大量需求，在各地区 均造成了交通拥挤，每年仅时间损失就达5 3 亿小时，经济损失达1 2 兆闩元， 给社会和经济带来沉重的负担；如此的交通状况导致沿路环境恶化、能源消耗 增加等严重问题。另据介绍，日本交通事故的死亡人数从1 9 8 8 年以后连续8 年 每年达到1 万人以上。我国道路交通死亡人数每年达1 0 万人左右，直接经济损 失近2 0 亿。所有交通问题的现状说明：现代的交通运输已经对人类生命、财产、 和生存环境构成威胁【l 】。 交通运输系统是构成社会基础结构的一个核心要素，它是一个动态系统，是 社会经济发展的通道和载体，它决定着社会经济的运行状态。建立智能运输系 统( i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ，简称i t s ) 是交通运输系统实现现代化的 一项重要举措，i t s 能够促进社会经济环境的进一步优化，是世界经济发展的必 然要求a 智能运输系统利用信息技术、通信技术、电子控制技术和系统集成技术等现 代科学技术，在道路、车辆和驾驶员( 乘客) 之间建立起智能的联系。借助系 统的智能，车辆可以在道路上安全、自由地行驶，靠智能化手段将车辆运行状 态调整到最佳，保障人、车、路的和谐统一，在极大地提高运输效事的同时， 充分保障交通安全、改善环境质量、提高能源利用率【2 】。 由于智能交通系统可以使汽车与道路的功能智能化，所以目前它匙围际公认 的解决城市以及公路交通拥挤、改善行车安全、提高运行效率、减少空气污染 两北1 _ _ k 人学顺卜论文 销章绪论 等的最佳途径，也是全世界交通运输领域研究的前沿课题。 i t s 的作用包括以下几个方面： ( l ) 提高公路交通的安全性 ( 2 ) 降低能源消耗，减少汽车运输对环境的影响 ( 3 ) 提高公路网络的通行能力。 ( 4 ) 提高汽车运输生产力和经济效益，并对社会经济发展的各方面都将产生 积极的影响。 ( 5 ) 通过系统的研究、开发和普及，创造出新的市场。 在过去，城市规模小，城市公路交通状况简单，车辆少，整个交通状况处于 闲置状念。现今，随着城市的规模趋向于大规模，超大规模发展。城市交通就 逐渐变得庞大复杂。对于很多行业( 例如：运输公司、公交公司、出租车公司、 l i o 报警、1 1 9 火警以及医疗救护系统等) 已经面临着一个很重要问题：“怎样 在庞大复杂的城市交通网，以及繁忙的路面交通状况中寻找_ - 条合理的路径以 满足需要”这样一个问题在交通网络中属于最短路径求解问题。对于最短路径 求解目前主要是运用线性规划等理论及方法，如d i j k s t r a ( 迪克斯特拉) 算法。 d i j k s t r a 算法是一种基于图论的最短路径算法，所以这种算法需要有一个地理网 络数据库。电子地图是一种以地图数据库为基础，以数字形式存贮于计算机外 存贮器上，并能在电子屏幕上实时显示的可视地图它不仅能作为一种地理网 络数据库，而且能直观地把交通地理信息表示出来。因此，把电子地图与最短 路径求解结合起来是一种很理想的方法。 动态交通诱导系统是智能运输系统的一种重要服务子系统，本文中基于电子 地图车队优化调度及管理系统就是属于动态交通诱导系统。下面将介绍国内外 动态交通诱导系统的发展情况。 1 2 国内外动态交通诱导系统的发展情况 动态交通诱导系统的研究最早开始于2 0 世纪7 0 年代中期的 = _ 本首先进行 了基于f r 射频通信的车载动态诱导系统的开发试验，并得到了可以减少1 3 行程时间的结论，但是由于受当时技术、经济等因素的限制该研究项目没有继 续下去。在2 0 世纪8 0 年代又相继进行了道路车辆通信系统 l 弧( 、s ) 和高级车 - - 常绪论 辆交通信息与通信系统( a m t i c ) 的研究，在2 0 世纪1 9 9 0 年开始的v i c s ( v e h i c l e i n f o r m a t i o na n d c o m m u m c a i i o n s y s t e m ) 项目则是世界上第一个金困统一的车辆 信息与通信系统1 1 1 。 欧洲的德国和英国分别在2 0 世纪8 0 年代末期开发除了用于示范的撼r 红外 信标进行通信的动态路径诱导系统，即l i s b 系统和a u t o g u i d e 系统，而这 都是利用历史数据进行诱导的，即如2 0 世纪9 0 年代，德国西门子公司基于l i s b 丌发的a l l s c o u t 系统( 在欧洲称为e u r o s c o u t ) 具有一定的网际影响， 它是基于红外信标通信方式的中心决定是的路径诱导系统。基于a j 。 ! r 1 二( ：协议 的交通数据频道广播以或即将在英国、德国、意大利等1 1 个欧洲困家丌通，它 能够向用户提供交通事故、拥挤、道路施工等信息，其商用路径诱导系统 c r m i n a t 、d y n a g u i d e 等不但可以显示( 提示) 交通信息，也可以实现分布 式的动态路径诱导【孙。 p a t h f i n d e r 是美国第一个i v h s 研究项目，它提供的信息为道路拥挤程度信 息，以文字形式显示于电子地图上或以语音方式提示驾驶员。1 9 9 1 年7 月到1 9 9 6 年1 2 月间，美国在i l l i n o i s 的c h i c a g o 进行了a d v a n c e ( a d v a n c e d d r i v e ra n d v e h i c l ea d v i s o r y n a v i g a t i o nc o n c e p t ) 项目的研究，这也是一种分布式的路径诱 导系统。 目前美国投入使用的m a y d a y 系统可以向自动用户报告车辆位置，用户在 必要时可以获得紧急帮助。该系统的扩充功能包括：出行者信息、路径帮助和 诱导等服务。 我国的一些大城市，包括北京、上海、南京、沈阳、长春等大城市都建立了 交通诱导广播系统。道路上的交通信息由车辆检测设备和摄像机镜头自动采集 并持续不断地送到交通指挥中心，经计算机处理后的结果自动传送到交通广播 电台的监视终端和打印机上，在由播音员每个一定时间或随时予以播出。这是 动态交通诱导的初级形式，其诱导效果是很有限的，而车载分布式诱导系统或 单车自主式诱导系统还未见报导【5 1 。 1 3 g i s 与g p s 技术及其在车辆调度系统中的应用状况 地理信息系统( g j s ) 综合了数据库、计算机图形学、地理学、儿何学等技 第j ；= 绪论 术，以地理空间数据为基础，采用地理模型和分析方法，适时提供多种空削和 动态的地理信息，从而为存放和管理定位导航信息提供服务。刚此在车辆导航 定位和监控调度管理中，g i s 充当着信息系统的角色。他集城市地理信息系统 和被管理目标主体信息于一体，不但能够借助电子地图迅速准确地为车辆驾驶 员和系统管理员提供各种信息的查询，灵活方便地为车辆在道路网的任意两节 点问选择最佳行驶路线，并且能够通过监控中心与管理车辆之间的双向通信， 对车辆实行跟踪和调度管理【舶。g p s 全称为g l o b a lp o s i t i o n i n gs y s t e m ，意为全 球定位系统，其实质上是卫星定位系统，即通过卫星系统来进行授时、定位和 测速6 】 8 】。g i s 与g p s 配合，能够实时为车辆驾驶员提供导航信息，为调度管 理人员提供交通路况信息，从而有效地实现车辆的定位导航和调度管理。具体 地况，g i s 与g p s 技术相结合，能够实现的功能包括： ( 1 ) 电子地图显示功能 包括电子地图的全屏显示、放大缩小、漫游、旋转、动态标记和分层届示等。 ( 2 ) 标注当前车位 通过车载设备实时接收g p s 定位数据，并将地理坐标转化为屏幕坐标，通过 软件对误差进行修正，或通过传感器和地图数据计算车辆位置，对车辆所在位 置进行修正后在地图上标出当前车位，从而实现对车辆位置的实时跟踪。 ( 3 ) 地理信息分类索引 通过输入属性信息，利用图层操作和分类信息提示，实现用户的信息查询； 另外借助地图数据库内的各类索引，如设施索引、地址索引、电话号码索引等， 为设定目的地实现索引查询地图功能。 ( 4 ) 最佳路径选择 用户根据自己的需求，可在电子地图上设定行车路线，还可以同时设定多条 行车路线，借助辅助路线决策、最短距离、最短路径、单行线和禁左等功能由 导航软件来确定其最佳路径，并建立路线库，供驾驶员选择。 ( 5 ) 行车路线导航 在电子地图上显示所设计和选择的路线，同时显示车辆运行方向与运行路 径。汽车运行线路可以记录保存，以便事后回放。在运行路线导航中，同时显 4 两北丁业火学硕【：论文 销带绪论 示车辆所在位置的经度和纬度，以及到达目的地的剩余距离等。 在我固电子地图在智能交通系统中的应用已有成功的范例，特别是fc 1 _ 子导航 地图，如李曙光等人设计制作的西安市大雁塔地区交通电子地图，已成功地应用 于课题“g p s 技术在车辆导航系统中的应用研究”：北京市公芡交通总公司g p s 车辆监控系统中的电子地图：杨兆升等人设计制作的城市交通流诱导系统中的 电子交通地图。这些都说明了交通电子地图的日趋成熟，但也存在着很多需要努 力的地方。现在的交通电子地图功能相对简单，只能达到导航的功能，还有很多 问题需要解决，例如最佳路线和最短路线的选择算法己实现，但运用起来还未如 意1 。 1 4 论文的主要工作和章节安排 本论文研究的主要目标是将电子地图运用于一个大型运输车队的优化调度 并制作一个集车辆管理、人事管理、财务管理，以及基于电子地图的车队优化 调度软件。主要工作包括：电子地图的制作；地理信息数据库的) 1 发；车队优 化调度系统方案设计；电子地图的二次开发；d i j k s t r a 算法在车辆调度系统中的 应用研究；大型运输车队管理数据库的开发。具体内容如下： ( 1 ) 车队优化调度系统方案设计：车辆调度系统的原理及结构：硬件组成、 软件组成；通讯控制，语音控制等。 ( 2 ) 电子地图的制作：m a p l n f op r o f e s s i o n a l5 0 2 是一个制作电子地图的 软件。它有绘图、图层制作、地理信息设置、道路生成器、数据库的查询等许 多功能。通过熟悉和掌握这些功能，制作出一张能满足车辆优化调度的电子地 图。 ( 3 ) 地理信息数据库的开发：利用m a p l n f op r o f e s s i o n a l5 0 2 软件添加大 量丰富生动的文字和多媒体资料。地理信息不但要包括最短路径搜索所需的信 息，而且还要把地图丰富多彩地显示出来。 ( 4 ) 电子地图的二次开发：应用m a p i n f o 公司提供的m a p x 控件把电子地图 嵌入自己的应用程序中，这样就能方便的使自己的应用程序操作和使用电子地 图及信息。通过m a p x 可以分析和可视化企业数据、创建与编辑地图特征以及地 图化的显示结果。 两北t 、业大学坝卜论史 私章绪论 ( 5 ) d i j k s t r a 算法在车辆调度系统中的应用研究：将经典d i j k s t r a 饽法应用于 车队优化调度，对网络数据进行优化组织，并结合快速搜索技术，实现高效的 最短路径搜索。 ( 6 ) 大型运输车队的管理数据库的开发：选用m i c r o s o f ta c c e s s 作为数据库 开发平台，建立一个大型车队管理信息关系数据库模型。对车辆信息进行存储、 索引、查询处理和事务管理。大型车队管理信息应包括：车队的车辆管理、人 事管理、财务管理等。 论文章节安排： 第一章绪论。简要阐明研究主题、背景和意义，明确研究重点和主要工 作内容，安排论文章节。 第二章算法设计与分析的理论基础。结合车辆优化调度将现有的优化算法 进行比较。 第三章车辆调度系统的设计方案。阐述了调度系统的总体框架及各个子系 统。 第四章电子地图的设计。阐述电子地图制作的方法，包括地图的矢量化、 地图数据信息采集、软硬件环境等。 第五章软件设计。阐述系统软件设计。 第一章算：法政u ，钳惭帆胖硷举啦 第二章算法设计与分析的理论基础 2 1 引言 快速电子计算机的出现是本世纪的一件大事，因为它改变了我们这个世界 的面貌。快速电子计算机贵在神速，也就是它的运算速度快。一台作1 ( ) 9 秒运 算的计算机的效率超过l o 亿人同时工作。它可以作中期的天气预报，可以控制 庞大的化工厂生产过程，以至于还可以驾驭现代战争，从这个意义e 束说它确 实是近乎神奇的。计算机虽然神通广大，但是它并非什么事情都能做，有的事 情理论上它根本作不了。比如拿最简单例子，2 6 个英文字母全排列。它的排列 数为： 2 61 4 x 1 0 2 6 以每年3 6 5 天计算，共有3 6 5 x 2 4 x 3 6 0 0 = 3 1 5 3 6 x1 0 7 秒必每秒能完成1 0 7 个 排列超高速电子计算机来做这项工作，需要 4 x 1 0 2 6 ( 3 1 5 3 6 x1 0 1 4 ) 1 2 1 0 2 年 即使计算机运行速度随着技术的提高，恐怕也还是不能实现的。因计算机的速 度再提高也有它的极限。 有人说“计算机科学是- - f - j 研究算法的科学”。不论这个说法是否全面，算 法无疑是计算机科学的重要组成部分。他近来发展及其迅速，瞬是异彩纷呈并 不为过。“算法与算法复杂性分析”已是计算机专业本科生，特别是研究生的 门必须掌握的内容。与算法有关的还有一个大家熟悉的公式”】： 程序= 算法+ 数据结构 这说明算法的研究不单是数学问题，还和数据结构密切相关。这个观点在这里 必须突出地强调，必须强调的还有一点，那就是“实践”，只有通过动手实践才 能掌握算法的实质。 评价算法的效率是要对它所需要的时阆和存贮空间单元进彳亍估计，前者为 时间复杂性分析，后者为空间复杂性分析。 l 儿i 北t 业人学倾论义 第二章算法改汁。- j r 析的理论崔础 2 2 动态规划 2 2 1 最短路径问题 3 】【4 【1 2 】【1 3 l 数学规划是研究最优化的一类数学问题，包含有线性规划，非线性上见划等 内容。和动态规划有什么关系昵? 动态规划实际上是研究一类最优化问题的算 法，应用范围十分广。下面通过若干实例，介绍如何将一个最优化问题通过动 态规划来求解的基本原理。 如图2 1 ，从a o 点要铺设一条管道到a 6 点，中间必须经过5 个中i d j 站，第 一站可以在a l ，b 1 两地中任选一个，类似地，第二、三、四、五站可供选择的 地点分别是： a 2 ，b 2 ，c 2 ，d 2 ， a 3 ，b 3 ，c 3 ，fa 4 ，b 4 ，c 4 ，fa 5 b 5 ) 。 连接两地间管道的距离( 或造价) 用连线上的数字表示，要求选一条从a o 到a 6 的铺管线路，使总距离最短( 或总造价最小) 。 图2 1 4k 、4 一 3 。 b j 我们首先想到使用穷举法。在第一段，有两种路径选择：a o a ，、a ob l 。在 第二段，若选a o a l ，第二短路径由三种选择：a ia 2 、a lb 2 、a lc 2 ；若选a 0b j ， 也有三种选择：b lb 2 、b lc 2 、b l6 2 。所以两段共有6 种选择。依次类推， 从a o 到a 6 共有2x3 2 2x2xl = 48 种不同的路径。可通过48x 5 = 240 次加法，47 次比较，即通过各种可能方案的穷举，最后可求出从 第二二_ 串= 弊融垃汁，目i 佝删除皋i 土 a o 到a 6 的最短路径是： a o - a 1 b 2 i a 3 - 毋4 p 5一一p 6 相应的晟短距离是l8 。 但我们注意到最短路径有这样一个特性，即如果最短路径的笫k 站通过p 。，则这。最短路径在由pk 出发到达终点的那一部分路径，对于始点为i ) k 到终 点的所有可能路径来说，必定也是距离最短的。这一特性很容易证明。根据最 短路径这一特性，启发我们计算是从最后一段开始，从后向前逐步递推的方法， 求出各点到a 6 的最短路径，最后求得从a o 到a 6 的最短路径。步骤如下：k = 6 时 设f ( a s ) 表示由a 5 到a 6 的最短距离，f ( b 5 ) 表示由b 5 到a 6 的最短距离，显 然有： f 【a 5 ) 2 4 ，f ( a s ) = 3 k = 5 时 f ( a 4 ) 2m i n d ( a 4 ，a s ) + f ( a 5 ) ，d ( a 4 ，b s ) + f ( b s ) 2 m i n 型，5 + 3 ) = 7 这里括号里的底线表示最小值所取的项。即f ( a ，) 取的是 以专彳5 斗4 6 ，而不是4 啼b 5 以。以后同此，不再畿明。 f ( b 4 ) 。m i n d ( b 4 ，a 5 ) + f ( a s ) ，d ( b 4 ，b s ) + f ( b 5 ) 2 m i n 5 + 4 ，逊 = 5 f ( c 4 ) 2r a i n d ( c 4 ，a s ) + f ( a s ) ，d ( c 4 ，b 5 ) + f ( b 5 ) ) 2 r a i n 6 + 4 ，亘卫 = 9 k = 4 刚 f ( a 3 ) 。m i n d ( a 3 ，a 4 ) + f f a 4 ) ，d ( a 4 ，b 4 ) + f ( b 4 ) ) 2 r a i n 2 + 7 ，搂) = 7 f ( b 3 ) 2 m i n d ( b 3 ，1 3 4 ) ) + f ( b 4 ) ，d ( b 3 ，c 4 ) + f f c 4 ) 2 m i n 世，2 + 9 ) = 6 f ( c 3 ) 2m i n d ( c 3 ，b 4 ) + f ( b 4 ) ，d ( c 3 ，c 4 ) + f ( c 4 ) 】 。m i n 班，3 + 9 = 8 两r 业人学坝f 论义 第二章算泣改计i ，舒析的州论艟6 i f j k = 3 时 f ( a 2 ) = m i n d ( a 2 ，a 3 ) + f ( a 3 ) ，d ( a 2 ，b 3 ) + f i b 3 ) ： 2 m i n 业，8 + 6 ) 2 1 3 f ( b 2 ) = m i n d ( b 2 ，a 3 ) ) 十f ( a 3 ) ，d ( a 2 ，b 3 ) + f ( b 3 ) j 2 r a i n 瑚，5 + 6 2 1 0 f ( c 2 ) = m i n d ( c 2 ，b 3 ) + f ( b 3 ) ，d ( c 2 ，c 3 ) + f ( c 3 ) = m i n 班，3 + 8 = 9 f ( d 2 ) = m i n d ( d 2 ，b 3 ) + f ( b 3 ) ，d ( d 2 ，c 3 ) + f f c 3 ) 2 m i n 8 + 6 ，生盟 = 1 2 k = 2 时 f ( a 1 ) = m i n d ( a t ，a 2 ) + f ( a 2 ) ，d ( a i ，b 2 ) + f ( b 2 ) ， 2 m i n 1 + 1 3 ，三地，6 + 9 ) = 1 3 f ( bz ) = m i n d ( b t ，b 2 ) ) + f ( b 2 ) ，d ( b i ，c 2 ) + f ( c 2 ) 2 m i n 8 + 1 0 ，7 + 9 ，6 + 1 2 = 1 6 k = 1 时 r a o ) 5m i n d ( a o ，a i ) + f ( a d ，d ( a o ，b 1 ) + f f b i ) 。r a i n ( 主业，3 + 1 6 l = 1 8 d ( b l ，d 2 ) f f d 2 ) 上述计算结果可表示如图2 2 ，其中( 秒表示从a 5 出发到终点的最短路 径长度为4 即a 5 - a 6 ，余此类推。 共要用1 5 次比较运算和2 8 次加法运算就可得到从a o 到a 6 的最短距离， 而且在这过程中，还得到其它各点到a 6 的最短距离。 一般地，若我们考虑如图2 3 所示从始点o ( o ，0 ) 到终点e ( m n ) 的最 短路径( 也称格路) 问题。若用穷举法，则需 ( m + n - 1 ) c ( 珂慨班姓掣 西- 1 l y - - 业人学硕i 论文 第二章算法址汁j 分析的埋论基础 j j5 f 二垃l 7 1 8 图2 2 次加法及尘! _ ；掣一1 次比较运算。组合数c ( n + m ，n ) 为从o 点到e 点的路径 n ! m ! 数，这是考虑到图2 3 的每一格路m 个x ，1 1 个y 的任一排列4 对应。比如排 列掣皑，对应于从o 点先沿x 方向走m 块，后沿y 方向走n 块到e 点a m 7 | n 个 相当于由m 个y ，n 个x 构成的长度为m + n 的符号串数目，即从1 3 1 n 个格子中 任选1 2 1 个格子作为x 、其余为y 的方案数。 但用后种方法只需2 m n + m + n 次加法及m 1 次比较就够了。不难知道图2 3 由虚线包围的矩形域内的点要做2 次比较，2 次加法，在这以外的点只需1 次加 法，无需做比较。 当m = 1 1 时，穷举法需进行( 2 一一1 ) ( 2 玎) ! “门! ) 2 次加法，( 2 胛) ! ( 凡! ) 2 1 次比 较。后种方法只要作2 ( n 2 + n ) 次加法，n 2 次比较。由公式 n ! * 压磊( 兰) ” 8 可知穷举法的运算量是n 的指数函数，后一种算法则只是丌2 量绒。 两北l 业大学硕r 论文第二章箅浊垃h 分l j 二的理论基础 ( 0 ，0 ) 2 3 优先策略 2 3 1 优先策略概述 图2 3 1 n ) 优先策略顾名思义是“择优录取”，在某些方面的应用是非常成功的，也是 我们设计计算法时经常使用的一种策略。国外也叫做g r e e d ym e t h o d ，意即见到 好的就抓住不放。 2 3 2 最短树的库鲁斯卡尔( k r u s k a l ) 算法【3 】【4 】 设图g = ( 矿，e ) 是一简单连通图，m = h ，吲= m ，每条边p ，都给以权， 假定是边p ，的长度( 也可以是其他) ，i = 17 2 ，州。求图g 的总长度最短树。这 就是最短树问题。 晟短树的( k r u s k a l ) 算法的基本思想是：首先将赋权图g 的边按权的递增 顺序排列，不失一般性设为 qe 2 ， 其中w k + i 。然后再不构成回路的条件下，择优取进权最小的边。 求图2 4 所示的赋权图的最优树，数字表示该边的长度。把权按权的递增顺 序排列。 晒北r r 、【k 人学坝i 。论史第二章臂范i 1 1 汁一舒晰的璀论堆础 a e i 冬一= 、。 吃三，爹 。e 9， 、- 、： 、必 一 d e 1 2 g h 图2 4 p ? = 1 ，e 譬1 = l ，3 = 2 ，e ：= 2 ，5 = 2 ，e ；6 = 3 - 舔= 3 ，e 粤= 3 ，”- - 4 ，胡! = 4 ，硪= 4 ，2 = 5 ， e = 6 ，p = 6 ，p p = 7 ，”= 7 ，”= 8 。 ：右j 2 t a 括号里的数是排列的序号。按( k r u s k a l ) 算法的基本思想得到图2 4 的最短树t ( 图2 5 ) a ? 1 中每条边括号里的数为进入r 的序粤，丁的权是1 6 。 下面给出求最短树的( k r u s k a l ) 算法，为方便起见不妨设q 就是边的长度： ( 1 ) 对属于e 的边进行排序得 p i 已2 s 口m ( 2 ) 初始化操作：w 卜0 ，t + _ o ，后卜0 ，卜0 。 a ( 1 ) ( 4 ) ( 2 ) 一 f ( 7 )一( 8 ) 一 ( 9 ) 。 图2 5 加北下业人学顺i + 论义 第二章算法l ：2 7j 分析的理论壮础 ( 3 ) 若忙n l ，则转( 6 ) 。否则转( 4 ) 。 ( 4 ) 若t u 吼) 构成一个回路，则作【k k + 1 】，并转( 4 ) 。 ( 5 ) 7 t 卜t u e ) ，_ + ，f + _ t + l ，k 卜k + l ，转( 3 ) 。 ( 6 ) 输出t ，0 9 ，停止。 算法中r 中边就是最短树的树枝的，珊给出最短树的权。 ( k r u s k a l ) 算法首先要求对图g 的边进行排序，以后我们将看到排序的时 间复杂性为o ( m l 0 9 2 m ) 。 2 3 3 求最短树的普林( p r i m ) 算法【4 l ( k r u s k a l ) 算法采取在不构造回路的条件下，优先选择长度最短的边作为 最短树的边。下面介绍的普林( p r i m ) 算法采用另外一种优选策略。 已知图g = ( 矿，e ) ，v = “，v 2 ，心) ，d = ( 吃) 是图g 的距离矩阵，若 ( v ，v ，) 售e ，则令如= 0 0 ，并假定巩= c 0 。 普林( p r i m ) 算法的基本思想是：从某一顶点( 设为v ，) 开始，令，求v 、s 中点与s 中点距离最短的点，即从矩阵d 的第一行元素中找到最小元素，设为 d ，则令s 卜s u 蚋) ，继续求矿s c a - 与s 中点距离最短的点，设为u ，令 s _ s u 唯) ，继续以上步骤，直到押个顶点用n - 1 条边连接起来为止。还是以 图2 4 为例( 假定从a 点出发) 来进行说明。 图2 6 给出了利用普林( p r i m ) 算法对图2 4 求最短树的过程。 下面给出求最短树的普林( p r i m ) 算法。 ( 1 ) 初始化操作：t 4 - - g ，g ( 1 ) 七- - 1 ，i 从2 到胛作【p ( f ) 1 ，吁( f ) 卜z ，】 k + - 1 。 ( 2 ) 若”则作【r 输出，结束】。 否则【m i n _ ： ，从2 到 作 听北下业人学坝论文 第二章算法i 5 汁i 分晰的埋硷摧拙 一一 中 【若0 g ( f ) p ( v k ) + w k j ，则招l7 r ( v j ) 修改 为p ( v k ) + w k j ，把九( v j ) 修改为k 。 丌v 1 ) = 懈m i n r ( 。) 4 7 孤北 业人学f i ! j 卜论文 如果丁( ) 十m ，则把v j l 的标号变为p 标号j d ( ) = 丁( 0 1 ) ，令 墨+ 1 - s i + 1u n ，k _ 五，i = i + l ，转，否则终止，这时列每 个v c i s i ， d ( v s ，v ) = p ( v ) ，而对每一个v 芒s i ，d ( 珞，v ) = r ( v ) 。 经典d i j k s t r a 算法的流程图如图5 3 。 5 。5 2d i j k s t r a 算法在优化调度中的高效实现 从以上介绍可以看出，在按标记法实现d i j k s t r a 算法的过程中，核心步骤就 是从未标i 己的点中选择一个权值最小的弧段。这是一个循环比较的过程，如果 不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中。那么要 选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下， 这无疑是一个制约计算速度的瓶颈。要解决这个问题，最有效的做法就是将这 些要扫描的点按其所在边的权值进行顺序排列，这样每循环次即可取到符合 条件的点，可大大提高算法的执行效率。另外，g i s 中的数据( 如道路、管网、 线路等) 要进行最短路径的计算，就必须首先将其按结点和边的关系抽象为图 的结构，这在g s 中称为构建网络的拓扑关系( 由于这罩的、千算与面无关，所 以拓扑关系中只记录了线与结点的关系而无线与面的关系，是不完备的拓扑关 系) 。如果用个矩阵来表示这个网络，不但所需空间巨大，而效率会很低。 下面主要就如何用一个简洁高效的结构表示网的拓扑关系以及快速搜索技术的 实现进行讨论口引。 网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示。一般 而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表 和十字镪表表示，其优缺点的比较见表5 i 。 螽韭e 4 e 火学颤，| 浅盅 一一1 。 一一一一一。t 一一一1 名称实现方法；优 点 ；缺 点 邻接豫降二维数组 邻接收链袁 | l i = = = 2 1 1 = = 雠! = = = = = = = = ：= = = ： 时间复杂度 o ( u 。r n + 吣 o ( n i m l 谶 o ( n 4 m 、 衰童l 存储结梅比较图 h 盼，对于算法中快速搜索技术的实现，生要有桶结构法、队列法以及堆 栈实现法。t q q 、d k a 以及d k d 在这方面是魄被典型的代表。【q q 虽然是 基于图增眭孽论的，倪是快速搜索技术同样是篡算法实现的关键，它用两个 f i f 0 的队列实现了个双端队列结构来支持搜索过程。 d k a 和d k d 是慕躅鲤委5 4 陵示鸵辆皱翰来支持这个运算，其算法的命 名也来源予此。在d k a 算法中，薷i 个椭内装膏权值藩在 b “i 1 ) 瓶酗 内的可供扫描的点，菇中b 是视网络中边的权越分布情况蔚窀的个篱数。每 一个插翔歇尉来维护，这样每个点宥霹艟被多次扫播，但最多次数石会超过b 次。最坏情况下，d k a 的时闻复杂攫将会是0 ( m 辜b + l l ( b 1 c b ) ) ，其中，c 为 图中边的最大权值。d k d 将点按权值的范围太小分装在两个绒剐的确内，赢绂 剥匏橱保存权值较大的点，捆应的投焦鞍小的点都藏崔抵缓涮的捕幽，每次绉 描都只针对低级月桶中的点。当然随着点的插入和删除。两个嘶i 的s 是需要 动态调犍的。在d k a 算法中，给镎个桶一定的薄圈以及d k i ) 中f g j m 双桶，在 讯h 乒软件改汁 一定程度上都是以空间换时间的做法，需要改进。 图5 4 车辆优化调度系统提出的d i j k s t r a 算法实现： f 网络拓扑关系的建立 上面介绍的各种图的存储结构考虑了图在理论上的各种特征，如有向、无向、 带权、出度、入度等。而g i s 中的网络一般为各种道路、管网、管线等，这些 网络在具有图理论中的基本特征的同时，更具有自己在实际中的一些特点。首 _ 先，在g i s 中大多数网络都是有向带权图，如道路有单双向问题，电流、水流 都有方向( 如果是无向图也可归为有向图的特例) ，且不同的方向可能有不同的 权值。更重要的一点是根据最短路径算法的特性可以知道，顶点的出度是个 重要指标，但是其入度在算法里则不必考虑。综合以上4 种存储结构的优缺点， 我采用了两个数组来存储网络图，一个用来存储和弧段相关的数据( n e t a r c l i s t ) ，另一个则存储和顶点相关的数据( n e t n o d ei n d e x ) 。n e t _ a r cl a s t 用一个 数组维护并且以以弧段起点的点号来顺序排列，同起点的弧段可以任意排序。 这个数组类似于邻接矩阵的压缩存储方式，其内容则具有邻接多重表的特点， 即一条边以两顶点表示。n e t n o d ei n d e x 则相当于一个记录了顶点出度的索引 表，通过它可以很容易地得到此顶点的出度以及与它相