（电工理论与新技术专业论文）公路路政管理信息决策系统的研究与开发.pdf

a b s t r a c t f o l l o w i n gt h ei m p r o v e m e n to ft h ew h o l es o c i a li n f o r m a t i o n , b a s e dd e g r e ed a yb yd a y , a l lw a d e sa n dp r o f e s s i o n so fo u l c o u n t r yh a v ea l lr a i s e dt h et i d eo fi n f o r m a t i o n c o n s t r u c t i o n h lu n d e r t a k i n go ft h er o a d ，t h ec o r eo ft h ei n f o r m a t i o n - b a s e dp r o j e c ti n t h er o a dm a n a g e m e n ti st or e a l i z ei n f o r m a t i o nr e s o u r c e s h a r i n g t h r o u g hd e v e l o p i n g ， p o p u l a r i z i n ga l l k i n d so fr o a d so fb u s i n e s ss o r w a r e ，r e a l i z et h ee l e c t r o n i z a f i o n ， s t a n d a r d i z a t i o n ，a n ds c i e n t i f i cp r o c e s si nt h er o a dm a n a g e m e n t a tp r e s e n t ，t h er o a dm a n a g e m e n ti n f o r m a t i o ns y s t e m sw h i c ho u rc o u n t r yh a sa l r e a d y s e tu p ，m o s t l yl a y p a r t i c u l a rs t r e s so ng a t h e r i n g ，i n q u i r ya n dc o u n t i n gd a t ai nt h er o a d m a n a g e m e n ta n do f f e rs t a t ed a t at ot h eh i g h w a ye t c a n dal o to fp o l i c y - m a k i n g p r o b l e m s s t i l l r e l y o nt h ea d m i n i s t r a t i o nm e a n so rt h ee x p e r i e n c et o s o l v e ， s y s t e m a t i cr e s o u r c e sh a v en o tg o tv e r ye f f e c t i v eu s e s o ，i nt h er o a dm a n a g e m e n t ， h o wl e tl i m i t e dr e s o u r c eg i v ef u l lp l a yt ou t i l i z a t i o nb e n e f i tn e e d ss c i e n t i f i cp l a n n i n g a n dd e s i g n o nt h eb a s i so ff u l l ys u r v e ya n da n a l y s e s ，s e v e r a lr o a dm a n a g e m e n ts u b j e c t sw i t h o b v i o u so p t i m i z a t i o nn a t u r eh a v eb e e nc o n f i r m e di n c l u d i n gt h ee s t a b l i s h m e n to ft h e a d m i n i s t r a t i v es t a t i o n so ft h eh i g h w a y , s e t t i n gu pt h ep a t r o lr o u t e si nt h eh i g h w a y n e t w o r k ，t h es h o r t e s tp a t ho ft h e v e h i c l e sw h i c he x c e e dt h el i m i te t c m a t h e m a t i c s m o d e l sa r es e tu pi nt e r m so fg r a p ht h e o r ya n dt h es u i t a b l eo p t i m i z a t i o na l g o r i t h m s a r es o u g h tt os o l v et h ep r o b l e m s f u r t h e r m o r e ，b e c a u s eo ft h ec o m p l e x i t ya n dv a r i e t y o ft h ep r a c t i c a lp r o b l e m s ，m a n yg r a p ht h e o r yo p t i m i z ea l g o r i t h mc a nn o ta p p l y d i r e c t l y s o ，t h ep a p e rh a sc a r r i e do nad e e pd i s c u s s i o nt os e v e r a lr e l e v a n tp r o b l e mi n g r a p ht h e o r ya tf i r s t t h e n ，t h ec o r r e s p o n d i n gn e wa l g o r i t h ma c c o r d i n gt ot h ec o n c r e t e p r o b l e ma r ed e v e l o p e do nt h eb a s i so ft h ek n o w na l g o r i t h m a f t e rt h a t ，c o m b i n i n g g r a p ht h e o r yw i t ht h er e a l i t y , t h ep a p e rs e t su pt h ee f f e c t i v ei n f o r m a t i o nd e c i s i o n s y s t e mo fr o a dm a n a g e m e n t t h i ss y s t e m w h i c hd e p e n do nt h es t a n d a r dc + + l a n g u a g ea n dt h es e c o n d a r yd e v e l o p m e n tf u n c t i o no fm a p g i s ，h a so f f e r e da s c i e n t i f i cr e f e r e n c eb a s i sf o rd e c i s i o no fr o a dm a n a g e m e n t a tl a s t ，t h ep a p e rp r o v e s t h a tt h es y s t e mi sf e a s i b l ea n ds c i e n t i f i cb yc o m p u t e rs i m u l a t i o na n dt h e o r e t i c a l d e d u c t i o n t h es e t t i n g u po ft h es y s t e mi sa i le f f e c t i v ea t t e m p tt o a p p l y t h eg r a p ht h e o r yt ot h e n r a c t i c a lm a n a g e m e n ts u b j e c t sa n de x p l o r eaf e a s i b l et e c h n o l o g i c a lr o u t e i ns o l v i n g m a n yp r a c t i c a lo p t i m i s t i cs u b j e c t s f u r t h e r m o r e ，t h i ss y s t e m ，w h i c h r i c h e st h ee x i s t e d f r a m e o f t h er o a dm a n a g e m e n ti n f o r m a t i o ns y s t e m ，i m p r o v e st h es c i e n t i f i cl e v e lo f t h e d e c i s i o no f t h er o a dm a n a g e m e n t ，h a sv e r yg o o dp r o j e c tu s i n ga n dt e c l m o l o g i c a lv a l u e t op o p u l a r i z e i tw i l lp l a yag o o dr o l ei np r o m o t i n gt h ei n f o r m a t i o n a la n ds c i e n t i f i c d e g r e eo f r o a dm a n a g e m e n t k e yw o r d s ：r o a dm a n a g e m e n t ，g r a p ht h e o r y , s h o r t e s tp a t hp r o b l e m ， c o n s t r a i n e d p c e n t e r p r o b l e m ，g a ( g e n e t i c a l g o r i t h m ) ，i n f o r m a t i o nd e c i s i o ns y s t e m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人己经发表 或撰写过的研究成果，也不包含为获得墨洼盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签辄私铺签字魄川年，月p 日 学位论文版权使用授权书 本学位论文作者完全了解基洼盘堂有关保留、使用学位论文的规定。 特授权墨盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 彳花诵 、j i导师签名：嬲雨荆 签字日期：砌年1 月弦日 签字日期： 琦厂m 月h 日 天津大学硕士学位论文第一章绪论 1 1 公路路政管理概况 第一章绪论 公路的建设、养护、管理是公路部门的三大主要任务。其中，路政管理作为 公路管理的重要组成部分，是公路外部行政管理的集中体现。路政管理具有广泛 性、法制性、复杂性等特点，是维护路产路权，保护公路完好畅通，改善交通环 境的基础和保证【2 1 。 在路政管理规定中明确指出，路政管理是指县级以上人民政府交通主管 部门或者其设嚣的公路管理机构，为维护公路管理者、经营者、使用者的合法权 益，根据公路法及其他有关法律、法规和规章的规定，实施保护公路、公路 用地及公路附属设施的行政管理 3 】a 公路管理机构的具体路政管理职责如下： ( 一) 宣传、贯彻执行公路管理的法律、法规和规章； ( 二) 保护路产： ( 三) 实施路政巡查； ( 四) 管理公路两侧建筑控制区； ( 五) 维持公路养护作业现场秩序： ( 六) 参与公路工程交工、竣工验收： ( 七) 依法查处各种违反路政管理法律、法规、规章的案件； ( 八) 法律、法规规定的其他职责。 其主要内容框图如图1 1 所示 “。 1 2 公路管理信息系统的建立 随着国民经济的发展及信息化水平的提高，我国公路管理正面临新的挑战。 一方面，目前公路建设、养护管理等大部分还处于手工操作水平，或只有分散、 第1 页 天津大学硕士学位论文第一章绪论 1 1 公路路政管理概况 第一章绪论 公路的建设、养护、管理是公路部门的三大主要任务。其中，路政管理作为 公路管理的重要组成部分，是公路外部行政管理的集中体现。路政管理具有广泛 性、法制性、复杂性等特点，是维护路产路权，保护公路完好畅通，改菩交通环 境的基础和保证1 1 l 【2 】。 在路政管理规定中明确指出，路政管理是指县级以上人民政府交通主管 部门或者其设置的公路管理机构，为维护公路管理者、经营者、使用者的合法权 益，根据公路法及其他有关法律、法规和规章的规定，实施保护公路、公路 用地及公路附属设施的行政管理【”。 公路管理机构的具体路政管理职责如下： ( 一) 宣传、贯彻执行公路管理的法律、法规和规章； ( 二) 保护路产； ( 三) 实施路政巡查： ( 四) 管理公路两侧建筑控制区： ( 五) 维持公路养护作业现场秩序： ( 六) 参与公路工程交工、竣工验收： ( 七) 依法查处各种违反路政管理法律、法规、规章的案件； ( 八) 法律、法规规定的其他职责。 其主要内容框图如图1 1 所示1 4 j 。 1 2 公路管理信息系统的建立 随着国民经济的发展及信息化水平的提高，我国公路管理f 面临新的挑战。 一方面，目前公路建设、养护管理等大部分还处于手工操作水平，或只有分散、 一方面，目前公路建设、养护管理等大部分还处于手工操作水平，或只有分散、 第1 页 天津大学硕士学位论文 第一覃绪论 局部的、不完全的自动化水平，在交通量日益增加，道路、桥梁、隧道等交通设 施建设翻修频繁，道路路线变更不断，新的资料不断出现的条件下，这给公路建 设、养护及管理决策支持带来了极大困难。同时，因公路管理时间与空间跨越较 大，历史资料残缺不全，更加大了公路管理与决策的难度。另一方面，随着计算 机技术( 如实时数据库、数据仓库) 、通信技术，g p s 及g i s 技术等的发展，又为 建立日常业务操作及决策支持等管理信息系统提供了可能性。在国外，公路管理 信息化已达到相当高的水平，并得到了较好的应用啡”。建立和完善公路管理信 息系统是国际公路管理发展的趋势，对提高公路管理现代化、信息化和科学化水 平具有重要意义【5 ”。 公路法等法律法规及规章制度 路政管理队伍( 机构、人员) 路政外业管理 堕堕銮堡查丝l 厢前i 葡 童声 啊暖莉网li 匝纠 率l 电击 匮圃l 回际葫 匝圈ll 陌薪 行政复议行 i 结寰 倒1 - 1 路政管理主要职责图 公路管理信息系统的目标为：建立公路路况、路线、道路基础设施数据的采 集、存储、显示与处理的统一框架结构和协同工作环境；建立公路路况、路线、 道路基础设施数据库；开发实现日常业务操作处理的应用软件：与相关系统进行 综合集成，建立公路管理数据仓库，进而开发出公路管理决策支持等上层应用软 件；实现与社会相关系统的综合信息发布与收集【9 。 系统主要由如下模块组成：1 ) 数据采集及处理模块。由于公路路况总是随时 间不断变化，路线的空间范围变化很大、该系统利用车载g p s 对大部分路况数 据实现自动采集：同时一些数据没法自动采集，通过人工采集及输入。2 ) 数据库 第2 页 耋一 天津大学硕士学位论文 第一章绪论 模块。把基站g p 5 接收到的数据及人工采集的数据通过计算机分析处理存储于 数据库，主要有路面、桥梁、隧道等数据库，各个库都有包含经处理过数据的数 据表。3 ) 日常业务处理模块。利用g i s 数字化地图实现路网、路况信息的桌面地 图显示及日常公路管理业务处理，包括路面养护与管理、桥梁养护与管理等于模 块。4 ) 数据仓库模块。公路管理数据仓库是一个面向公路管理进行联机分析处理 及决策支持的面向主题的、集成的、不可更新的、随时间不断变化的数据环境， 是一个以主题为数据组织方式的数据库。5 ) 联机分析处理与决策支持模块。支持 公路管理中、长期建设、养护、规划、管理的支持软件。主要为中、高层领导者 提供决策咨询服务。6 ) 综合信息发布模块。主要提供与社会其他系统的接口，进 行综合信息发布，并接收社会其他系统的数据【9 】。 整个系统的结构图如图1 2 所示。 t 数据收集模块 数据库模块数据仓库模块 l 车载g p s 、数据| _ _ _ l 自动测量设备l 数 惯性测量l 据 v 加 工 ! 1 人工测量 图1 2 公路管理信息系统结构图 1 3 与图论相关的基本概念 图论是组合数学的一个分支，关于图的研究起始于e u l e r 对于r o n i g s b e r g 桥 的研究。在近代，图的理论已渗透到电理论、分子理论、计算机科学、管理科学 和运筹学等多个学科，使这些领域的研究取得了巨大的突破。图论在广泛应用的 同时，其自身也正以空前的速度发展着。目前，图论已成为多个学科的公共数学 第3 页 天津大学硕士学位论文 第一章绪论 基础。在本节中，首先说明图论中的几个基本概念和定义，之后简单介绍算法及 其复杂性的相关知识，最后引入n p 、n p c 和n p h a r d 等概念。 1 3 1 图的基本概念 图( g r a p h ) 就是节点集合矿和节点的有序偶集合a 。a 的元素称为弧，即 连接各个节点的矢线。图用( v ，a ) 表示。当对弧的方向( d i r e c t i o n ) 不作规定 时，该无向弧就称为边( e d g e ) 。未规定弧的方向的图称为无向图( “n d i r e c t e d g r a p h ) ，用( v ，e ) 表示。在本文中，当末对方向作明确说明时，均用边e 和 无向图( v ，e ) 表示。 考虑任一节点序列x ，屯，z 。z 。，。弧日，a 2 ，a 。的任序列称为链 ( c h a i n ) ，若弧口，的两个端点是x ，和x ，f - 1 , 2 ，n 。因此，日，= ( x ，z ) 或 a ，= ( z ，工，) a 节点x j 称为链的始点( i n i t i a lv e r t e x ) 。节点x 成为链的终点 ( t e r m i n a lv e r t e x ) ，链从其始点延伸至其终点。链的长度( 1 e n g t h ) 等于这条链中 弧的数目。 若a ，= ( x ，x 。) ，i = j ，2 ：n ，则这样的链就是路( p a t h ) 。路的长度、始点 和终点都可以与链一样定义。如一条链的始点和终点为同一点，这样的链就是圈 ( c y c l e ) 。如一条路的始点和终点为同点，这样的路就是回路( c i r c u i t ) 。圈或 回路的长度定义为这条相应的链的长度。 在一条链、路、圈或回路中，如果不存在和两条以上( 不包括两条) 的互相 关联的节点时，这样的链、路、圈或回路成为简单链( s i m p l ec h a i n ) 、简单路( s i m p l e p a t h ) 、简单圈( s i m p l ec y c l e ) 或简单回路( s i m p l ec i r c u i t ) 。 1 3 2 算法及其复杂性 图论可以分为代数的和最优化的两个方面，在本文中所讨论的几个图论问题 均属于最优化方面的问题。所谓最优化就是对于给定的目标函数和约束条件，使 目标函数在约束条件下达到最小值或最大值。 定义1 - 1 设f 是一个集合，c 是定义在f 上的一个实函数，则m i n c ( f ) f 或 ，f 箱4 砸 天津大学硕士学位论文 第一章绪论 m a x c ( f ) ) 就是一个最优化问题，其中c 是目标函数，f = ，| f 满足约束条件) 。 ，f 一个要求解决的具体的最优化问题就称为一个实例，当给定了集合f 和函数 c 时，我们就认为给出了一个实例。因此，最优化问题其实就是某些具有共同性 质的实例的集合。 最优化图论的中心问题是寻求优化算法，因而又可称为算法图论。所谓算法 ( a l g o r i t h m ) ，就是在研究某一种类型的图或网络在实际应用中的最优化问题时， 为求出这些问题的最优数值解而给出的过程。一般地说，算法就是一组可行的、 确定的、有穷的规则。 衡量一个算法的效果，最广泛采用的标准是看这个算法解决问题所花费时间 的多少。为了制定一个统一的标准，人们通常从以下两个方面消除与算法无关的 因素所产生的干扰。首先，假定执行算法的计算机只能进行最基本的运算，而且 执行每一个基本运算都花费一个单位时间。这样，算法执行时间就可以用算法需 要执行的基本运算的次数来代替。其次，要消除实例带来的影响，我们引入规模 的概念。一般来说，为了把一个实例送到计算机中去，总要把与该实例有关的各 种信息变成二进制代码。描述实例的二进制代码的位数，就称为这个实例的规模。 在网络最优化中，采用网络的节点数和弧数作为实例的规模。 同样规模的实例，用同一个算法来计算，须执行的基本运算的次数往往也会 有很大的差别。因此，通常的办法是设法估计出该算法对规模为n 的实例需要执 行的基本运算次数的一个上界，( n ) ，也就是考虑最坏的情况。函数厂( 月) 称为 该算法的复杂性，用来刻划这个算法的效果。 在算法复杂性的研究中，感兴趣的是复杂性函数的增长速度，而复杂性的增 长速度只有在实例的规模很大时才能反映出来。当实例的规模足够大时，算法的 复杂性函数中增长速度较慢的项终将被增长速度很快的项超过。因此，对复杂性 的增长速度起决定作用的是增长速度最快的项。据此，人们引入下面的记号。 定义1 - 2 设i ( h ) 和正( h ) 是定义在正整数集上的两个正实值函数，如 果存在一个常数c 0 ，使得当n 足够大时有 ( 月) c 五( ”) ，则记_ ( ”) = o 坼( ) ) 。 第5 页 天津大学硕士学位论文 第一章绪论 若一个算法的复杂性厂( n ) 是问题规模h 的多项式函数，则称这个算法是有 效的或有多项式界的。有时也简单的说这个算法是好算法或多项式算法。我们把 不是有效的算法成为无效算法。无效算法的一类典型代表是指数算法，即复杂性 厂( 行) 是n 的指数函数的算法。因为对于任意给定的正数a 和a l ，当”足够大 时，h 。 a ”。所以，当实例的规模n 增大时，任意一个多项式算法终将变得比 任何指数算法更有效。这就是把多项式算法称为有效算法的原因之- - ”】。 1 3 3 尸与p 完全理论 寻找一个问题的多项式算法是不容易的。旅行商( 丁5 p ) 问题、背包问题等 很多问题到目前为止都还没有找到多项式算法。是这些问题本质上就不存在多项 式算法，还是由于我们研究的不透彻? 如果能够根据问题的难度对问题进行分 类，将会更好的描述和解决组合优化问题。 但是，对问题进行分类和判定一个问题属于哪一类，这两件工作都十分的困 难。目前绝大多数算法理论讨论都在一种“图灵机”的理想数学模型上进行，“图 灵机”是为纪念英国科学家图灵而得名，因为他最早提出了这个模型。图灵机是 对目前使用的实际计算机的一个很好的简化和抽象。凡是能用图灵机描述的在多 项式时间内运行的算法，都可以在实际计算机上用多项式时间运行。因此，凡是 在图灵机上有多项式算法的组合最优化问题就被称为p 问题。 定义1 3 对于给定的一个优化问题，若其存在多项式算法，则称给定的优 化问题是多项式时间可解问题，或简称多项式问题，所有多项式问题集记为p ( p o l y n o m i a l ) 。 之后，科学家们又引入了非确定性图灵机的概念( 与此对应，图灵机有时又 叫做确定性图灵机) 。非确定性图灵机是一种假象的具有猜测功能的计算机数学 模型，至今没有造出有相应功能的计算机来。如果一个问题，能在非确定性图灵 机上找到一个多项式算法，我们就称这个问题属于 垆问题类。在图灵机上有多 项式算法的问题，在非确定性图灵机上也一定有多项式算法，因此p 问题类是 n p 问题的一个子类。为了更好的解释n p 的概念，我们引入判定问题的概念。 定义1 4如果一个问题的每一个实例只有“是”或“否”两种答案，则称 第6 页 天津大学硕士学位论文第一章绪论 这个问题为判定问题( d e c i s i o n p r o b l e m ) 。 由定义1 1 ( 假设使c ( f ) 达到最小) ，对于最优化问题的一个实例，我们可以 提出相应的一个判定问题的实例：给定一个实数l ，问是否存在厂f ，使得 一个组合最优化问题，当然比它相应的判定性问题要困难。如果一个最优化 问题实例的最优解为 ，当c ( 厶) l 时它相应的判定性问题的答案是“y e s ”， 当c ( f o b 三时答案是“n o ”。给定了个组合最优化问题，我们任意选取它的一 个实例，并确定好它对应的判定性问题中的常数l 。如果任给判定性问题的一个 答案为“y e s ”的解f 能在多项式时间内验证这一点，那么就称这个组合最优化 问题属于n p 类。这里所谓的验证要做三件事：验证，f ；计算c ( f ) ；证明 c ( 厂) a 如果没有这样的路，则露= o 。由露的定义得知，d ；表 示从i 到，的最短路的长度，其中无中间节点，亦即，钟表示从i 到，的最短边 的长度( 如果有这样的边的话) 。对所有的节点f i 令钟= 0 。令d 表示从i 到j 的最短路的长度。 令d 表示一个n x n 矩阵，它的( f ，) 元素是d ：7 。如果我们已知图e e 每 条边的长度，则可以确定矩阵d “。我们最终希望确定最短路长度的矩阵d “。 f l o y d 最短路算法从d o 开始，由d o 计算d7 。然后，f l o y d 最短路算法再由d 7 计算d 3 。将这个过程重复进行下去，直至由d “求得d “为止。 这些计算的基本思路如下。设我们己知： ( a ) 从节点f 到节点研的最短路，其中只允许前m 一1 个节点即节点1 ，2 ， 胁一1 作为中间节点。 ( b ) 从节点m 到节点的最短路，其中只允许前m 一1 个节点即节点1 ，2 ， 胁一l 作为中间节点。 ( c ) 从节点f 到节点，的最短路，其中只允许前m 一1 个节点即节点1 ，2 ， t n 一1 作为中间节点。因为不存在有负长度的回路，所以( d ) 项与( e ) 项中给 出的两条路中较短的一条一定就是从f 到_ ，的最短路，其中只容许前m 个节点即 节点1 ，2 ，m 作为中间节点。( d ) 项与( e ) 项的两条路为：( d ) ( a ) 项和 ( b ) 项中两条路的并；( e ) ( c ) 项的路。因此，d , 7 = 肌f n d 二“+ d 。m ，- i ，d ；。) 。 从上式中可以看出，只需要矩阵d “。的各个元素，就算出矩阵d ”的各个元 素，且无须参看基本图就可以进行计算。f l o y d 最短路算法同时适用于有向图和 无向图。下面是f l o y d 最短路算法的详细步骤。 第一步：将图中个节点编为1 ，2 ，。确定矩阵d 。，其中( f ，) 元素 第1 2 页 天津大学硕士学位论文 第二章路的算法 等于从节点i 到节点_ ，的最短边( 弧) 的长度( 如果有最短边( 弧) 的话) 。如果 没有这样的边( 弧) ，则令刃= 0 对于i ，令刃= 0 。 第二步：对m = 1 ，2 ，依次由d ”的元素确定d “的元素，应用下 列递归公式：蝣= m i n d , ：- + d 孑1 ，d o ) 每当确定一个元素时，就记下它所表示的路。在算法终止时，矩阵d “的( f ， f ) 元素就表示从节点i 到节点，的最短路的长度。 2 3 约束最短路问题 d i j k s t r a 算法、n 耐算法作为计算最短路径的经典算法已得到了广泛的应用。 但是这两种算法是为解决单约束条件问题而设计的。在实际中，如生产流水线管 理、交通线路的调度、i n t e m e t 中的q o s ( q u a l i t yo f s e r v i c e ) 路由等应用场合下， 我们会面临很多需要考虑多约束条件的路径( m u l t i c o n s t r a i n e d p a t h s ，简称m 口) 选择问题。例如，进行生产流水线管理时，在选择一条加工路线的时候，不仅要 考虑该路线总的加工时间、各个工序的最大负荷，还要考虑这条路线的优质品率。 这些多约束条件往往不能简单地合成为一个约束利用经典算法来解决。因此，需 要对m c p 问题进行深入的研究以适应实际工程应用的需求。 文献 1 9 1 把约束条件对应的权函数分成了三类：单性权函数、加性权函数和 乘性权函数。权函数的性质决定了路径的总权值与组成该路径各边( 或点) 分权 值的关系。单性权函数指的是，对于某一路径其总权值等于组成该路径各边( 或 点) 分权值中的最大值或最小值。生产流水线管理中工序的最大负荷是一个单性 权函数，因为整个流水线的最大负荷是由组成该流水线各工序最大负荷中的最小 值决定的。加性权函数指的是，对于某一路径，其总权值是由组成该路径各边( 或 点) 的分权值相加而成。在进行网络规划时跳数是一个典型的加性权函数。乘性 权函数指的是，对于某一路径，其总权值是由组成该路径各边( 或点) 的分权值 相乘而成。生产流水线管理中工序的优质品率就是一个乘性权函数。 一般地，m c p 问题分成两种类型：至多有一个约束条件对应的权函数是加 性权函数或乘性权函数的问题称为i 类问题。这类问题比较简单，较容易求解， 第1 3 页 天津大学硕士学位论文 第二章路的算法 可以通过改进的d o k s t r a 算法、f o r d 算法直接求解；类问题则含有多个对应权 函数为加性权函数或乘性权函数的约束条件。它属于n p 完全问题，求解比较困 难，目前解决该类问题的通常思路是构造启发式算法，即通过简化问题求取近似 解。对于i i 类问题的讨论可参考文献【l ”。 本节给出i 类问题的解决算法通用步骤和流程图，作为相关章节的理论准备。 在赋权图g = ( ne ，l ) 中寻找一条最短路，始点和终点分别为v 。及v ，。 其约束条件对应的权函数集合为w ( v 。，v ，) 。在具体算法中，我们把单性权函 数再分成两种：一种是静态的，即在整个算法过程中每条边( 或点) 所对应的分 权值是固定不变的，如路政管理中每条路段及桥梁对车辆的载荷限制。处理这一 类约束的基本思路是在应用改进的d o k s t r a 算法之前先把网络图中不满足约束条 件的边( 或点) 去掉。另一种是动态的，即在整个算法过程中每条边( 或点) 所对应的分权值是不断变化的，如在进行多媒体通信的时候每条链路的残留带宽 率就是动态单性权函数。这一类约束条件同加性权函数或乘性权函数类似，在应 用改进的d o k s t r a 算法的具体过程中，每次确定一个新的着色点之前都需要重新 计算每条边( 或点) 的分权值。图2 1 给出了i 类约束最短路问题的算法流程图。 图2 - 1 】类问题算法流程图 第1 4 页 天津大学硕士学位论文 第三章受限少中心问题 3 1 基本概念 第三章受限厂中心问题 首先介绍一下选址问题的有关概念。 所谓选址问题，是在指定的范围内，根据所要求的某些指标，选择最满意的 场址。连通图的选址问题是网络理论中重要的内容之一。选址问题通常分为两大 类：第一类是平面内的选址问题；第二类是网络图上的选址问题。前者的场址可 以是平面内的任何一点；后者的场址只能在给定的网络中选择。 在选址问题中，目标函数为“使最大距离达到最小”的一类问题，称为中心 问题。中心问题通常是指网络图上的选址而言。在连通图的选址问题中，取网络 上的一个节点，使得该节点在所有节点中与离它本身最远节点的距离为最小值， 则称该节点为该网络图的中心【2 ”。 p 一中心问题是一类非常重要的选址问题，其定义如下。 定义3 1g = ( 矿，目是一个连通简单图，设v v 为任意节点，s 为v 的非 空子集。定义v 到s 的距离为v 到s 中最近的节点的距离，记作d ( v ，回。 d ( v ，$ 2m i n d ( v ，“) ( 3 1 ) 广中心问题就是从v 中选取p 个节点的集合s + ，使得 m a x ，d ( v s ) = m i nm a x d ( v ，$ ( 3 - 2 ) ，e r k i s l - pr e r 实际问题中往往对中心点的选择要作一定的限制，即只有一部分点有权利 被选为中心；而且，并不是网络上的所有点都应该得到服务，仅使某些特。定的点 能得到服务就可以了。我们称这一类服务点和需求点为整个网络节点的一部分的 p 一中心问题为( 服务和需求受到限制的) 受限p 一中心问题【2 6 】。 定义3 2 设g = ( v ，日是一个连通简单图，且，d 为y 的非空子集，其中 的节点分别称为需求点、服务点，或分别简称为尺点、d 点。又设p s l d l 为自 第1 5 负 天津大学硕士学位论文第三章受限p - 中心问题 然数。所谓受限p - 中心就是从d 中选取p 个节点的集合s ”，使得 m a x d ( r ，n2 唰m i h n ：pm a x d ( r e r r ，固 ( 3 _ 3 ) r e r s c d i s l = p 。 由定义2 可看出，受限p 一中心是p - 中心的拓广。当r = d = 矿时，受限p 一中 心就是p 中心。注意到，在受限p 中心问题中，矿中的某些节点可同时是尺点 和d 点，某些节点可以既不是月点也不是d 点。这些特性使得受限p 中心比p 中心具有更普遍的实际意义【2 7 。 3 1 2 研究现状 ，一中心问题只是对于特殊的图，如树、区间图、串并联图等才能得到其多 项式的时间算法，即使在二分平面网络上p 一中心问题也属于p _ 完全问题【2 引。 网络图中的受限p 中心问题，由于其需求点和服务点在，一中心问题的基 础上又增加了一些约束条件，亦属于属于典型的p 完全类组合优化问题。在第 一章中曾介绍过，由于p 完全问题本身所固有的计算复杂性，求其精确解的计 算量往往随问题规模呈指数型增长，以致于使用任何高速计算机都需耗费大量的 时间，甚至根本无法实现【1 5 】。在这里，我们引入启发式算法的概念。启发式算法 ( h e u r i s t i ca l g o r i t h m ) 是相对于最优算法提出的。一个问题的最优算法求得该问 题每个实例的最优解。而启发式算法是这样一种技术，它在可接受的计算费用内 去寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下， 无法阐述所得解同最优解的近似程度刚。启发式算法具有不稳定性和对实际问题 的依赖性，某些算法求出的解有时连局部最优解都不是，更不用说是全局最优解 了。因此，多年以来人们一直试图设计各种启发式算法求受限口一中- 心问题近 似解，以保证在具有可接受的时间复杂度的前提下，其解尽可能的接近最优解。 1 9 7 1 年。c h r i s t o f i d e s 等人通过引入穿透距离的概念，将问题转化为网络的 最小覆盖问题来解决。但最小覆盖的算法仍然十分繁锁，问题的困难程度没有得 到明显的改善 1 9 。之后，有人曾用多目标决策方法建立多种新问题的数学模型， 并用f i b o n a c c i 法求解，计算过程仍较为繁冗【29 1 。1 9 9 1 年，文献 2 8 1 将问题转化 为o 一1 整数规划，采用隐枚举法求解，但同其它整数规划算法一样，该算法也 不是有效性算法，即计算时间随输入节点数的增加而呈指数式增加，因而需要对 第1 6 页 天津大学硕士学位论文 第三章受限俨中心问题 节点采取一定的主观判断，以减少各中心的选择范围。 之后，人们开始将目光转向利用智能优化算法进行求解。智能优化算法是八 十年代初兴起的一类启发式算法。这些算法主要包括禁忌搜索( t a b us e a r c h ) ， 模拟退火( s i m u l a t e d a n n e a l i n g ) ，遗传算法( g e n e t i ca l g o r i t h m s ) 、人工神经网 络( n e u r a ln e t w o r k s ) 以及新兴的蚂蚁算法( a n ta l g o r i t h m s ) 口”。这些智能优化 算法主要用于解决大量的实际应用问题，近几年来在理论和实际应用方面都得到 了很大的发展，成为解决n p 完全类组合优化问题最主要的手段之一。但是由于 其实现的技术问题较为复杂，具有多样性和不确定性，对实际问题有很大的依赖 性，很多参数需要人为因素干涉，目前太多数研究都将其应用到一些特殊的受限 p 一中心问题中f 3 2 】p 3 】 3 4 1 ，或利用一些较智能优化算法更为直观的方法，如并行迭 代算法】等解决受限p 一中心问题，但计算过程仍较为复杂，且无法保证结果的 质量。为此，本文提出采用遗传算法来解决受限p 一中心问题。之所以这样选择， 主要考虑遗传算法所拥有的全局搜索能力、内在的并行性和自适应性，用于实现 上述问题是比较合适的。 3 3 遗传算法 智能科学的发展，出现了一个新的特征和趋势，这就是生命科学与工程科学 相互交叉、相互渗透、互相促进。遗传算法的产生就是这种交叉和渗透的产物。 它的诞生，极大的推动了工程科学的发展，而工程科学的发展，又促进了遗传算 法的研究。 遗传算法( g e n e t i ca l g o r i t h m 简称为g a ) 是模拟生物在自然环境中的遗传 和进化而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的 h o l l a n d 教授于t 9 7 5 年提出的，起源于6 0 年代对自然和人工自适应系统的研究。 遗传算法中，将n 维决策向量x = x l ，x 2 ，x n 】1 用n 个记号x i ( i = 1 ， 2 ，n ) 所组成的符号串x 来表示：x = x 1 x 2 - x n 刍x = 【x l ，x 2 ，x 。 t ， 把每一个x i 看做一个遗传基因，它的所有可能取值称为等位基因，这样，x 就 可看做是由n 个遗传基因所组成的一个染色体。一般情况下，染色体的长度n 是 固定的，但对一些问题n 也可以是变化的。根据不同的情况，这里的等位基因可 第l7 页 天律大学硕士学位论文 第三章受限p - 中心问题 以是一组整数，也可以是某范围内的实数值，或者是纯粹的一个记号。最简单 的等位基因是由0 和1 这两个整数组成的，相应的染色体就可表示为一个二进制 符号串。这种编码所形成的排列形式x 是个体的基因型，与它对应的x 值是个 体的表现型。通常个体的表现型和其基因型是一一对应的，但有时也允许基因型 和表现型是多对一的关系。染色体x 也称为个体x ，对于每一个个体x ，要按 照一定的规则确定出其适应度。个体的适应度与其对应的个体表现型x 的目标 函数值相关联，x 越接近于目标函数的最优点，其适应度越大；反之，其适应度 越小。 遗传算法中，决策变量x 组成了问题的解空间。对问题最优解的搜索是通过 对染色体x 的搜索过程来进行的，从而由所有的染色体x 就组成了问题的搜索 空间。 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由多个 个体组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法 的运算过程也是一个反复迭代过程，它首先产生一组初始解，一组解称为一个群 体( p o p u l a t i o n ) ，在每次迭代过程中都保留一组候选解，计算群体中每个解的目 标函数值( 称为适应值，f i t n e s sv a l u e ) ，按其解的适应值大小进行排序，并按某 种指标从中选出一些解，利用一些遗传算子( g e n e t i co p e r a t o r s ) 如交叉 ( c r o s s o v e r ) 和变异( m u t a t i o n ) 等对其运算，产生新一代的一组候选解，重复 此过程，直到满足某种收敛指标为止【3 8 】。 遗传算法的基本步骤： 编码：由于遗传算法不能直接处理解空间的解数据，因此在进行搜索之前必 须进行编码，将变量编码成一个定长的字符串( 设为z ) ，这些串的不同组合便构 成了不同的解 3 9 。 产生初始群体：随机产生m 个初始字符串，每个字符串称为一个个体，m 个 个体构成一个群体，遗传算法以这m 个字符串作为初始点开始迭代。m 值越大， 即初始群体中个体的数目越大，群体就越具备多样性，算法陷入局部解的机会就 越小。但规模太大，会增加计算量，并影响算法的效能。一般，若个体长度为l i 第18 页 天津大学硕士学位论文第三章受限p - 中心问题 则可取出使群体规模为：m = 2 “2 。但是，在实际应用中，初始群体的规模往往 在几十到几百之间。 计算适应值：适应值函数表明个体对环境的适应能力的强弱，不同的问题， 适应值函数的定义方式也不同。对函数优化问题，一般取目标函数作为适应值。 选择：一个群体中同时有n 个个体存在，这些个体哪个保留用以繁殖后代， 哪个被淘汰，是根据它们对环境的适应能力决定的，适应性强的有更多的机会保 留下来。这一思想是通过选择过程体现的