（控制科学与工程专业论文）随机运输网络优化模型及其算法研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 军事运输网络中的运输路径、流量等优化问题直接影响到运输梯队的机动性、 后勤效率以及对作战部队的保障水平，在军事运输决策中具有重要理论意义和实 用价值。 以往军事运输网络优化问题的研究主要是集中于静态信息、确定性领域，而 在实际运输过程中，涉及大量不确定性信息，传统的模型难以描述军事随机运输 网络优化问题；而且，随着网络规模的不断扩大，军事随机运输网络优化问题求 解变得十分困难。因此，有必要进一步研究军事运输网络的随机特性及其优化问 题，并为网络优化问题求解构造出更有效的模型与算法。本文以某军事运输优化 辅助决策项目为研究背景，针对随机运输网络优化问题，给出了相应的频域优化 模型及算法，其主要研究内容及成果如下： 第一，问题研究综述。在对大量相关文献进行总结提炼的基础上，回顾了国内 外对运输网络优化问题的研究成果，分析了构成该问题的各个子问题及其要素， 并指出传统模型及算法在解决随机运输网络优化问题中的局限性。 第二，随机运输网络频域模型及其期望优化求解。考虑到偶发的交通事故等因 素导致运输时间的不确定，将路段通行时间、流量、可靠性等指标都视为随机变 量，建立了随机运输网络的频域生成图模型，有效地描述运输网络中各种复杂的 概率信息，并给出了时域频域概率函数之间的转换关系及其若干性质，提出了基 于广义割集的期望优化算法。通过算例分析验证了所给出的模型及其优化算法的 有效性。 第三，随机运输网络优化频域建模及算法。针对期望优化求解方法丢失随机信 息问题，提出采用频域优化模型的概率分布求解方法。在求解随机最优路径方面， 其问题分两种情形：一种以成功概率为优化目标，搜索约束条件下完成运输任务 最大概率的路径；另一种以运输时间为优化目标，搜索在规定概率置信度下完成 运输任务所花费时间最少的路径。在求解随机最大流最小流方面，将其问题转化 为求解频域模型下最小双向割( s ，s ) 。；。的集合s 中所有结点的流量之和，即结点流 量频域函数之乘积。在求解随机运输网络可靠性方面，通过频域下路段可靠度函 数的定义，给出了随机运输网络可靠度的频域模型及算法。算例的分析结果表明， 与期望优化方法相比，频域生成图的概率分布求解方法充分应用了各种信息，并 可以曲线图形直观地进行优化分析，具有良好表征特性。 第四，多目标多约束的随机运输网络优化建模及算法。针对军事运输网络的随 机、时变特性，讨论了运输时间、运输损耗和运输流量之间的函数关系，基于随 第i 页 国防科学技术大学研究生院博士学位论文 机运输网络的频域生成图，以时间、损耗、流量为优化目标，建立了多目标多约 束的频域加权效用模型，并给出相应的频域优化算法。通过算例对所构建的模型 及算法进行了有效性验证。 第五，大规模随机运输网络优化建模及算法。根据路径在层次网络中层次属性 值具有分段单调的特性，建立了大规模运输网络频域生成图的层次模型，并采用 分层结构给出了一种有效的频域层次优化算法，使问题空间状态数从指数形式变 为线性的搜索。通过算例分析和算法性能测试，说明了模型及算法的可行性与有 效性。 第六，随机运输网络优化模型及算法的应用研究。给出了在军事运输优化辅助 决策项目中的案例研究，以及在w e b g i s 系统中的应用研究。 主题词：随机运输网络频域网络优化最优路径最大流- 最小流运输网 络可靠性模型与算法 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t t h eo p t i m i z a t i o np r o b l e m so fr o u t e sa n df l o wr a t e si nt h em i l i t a r yt r a n s p o r t a t i o n n e t w o r kw o u l dh a v eg r e a ti n f l u e n c e so i lt h ef l e x i b i l i t yo ft h et r a n s p o r t a t i o nm o t o r c a d e ， t h ee f f i c i e n c yo fl o g i s t i c s 邵w e l la st h eq u a l i t yo fs e r v i c et ot h ef i o n t l i n et r o o p s s t o c h a s t i ct r a n s p o r t a t i o nn e t w o r ko p t i m i z a t i o ni so fg r e a tv a l u eb o t ht h e o r e t i c a l l ya n d p r a c t i c a l l yi nt h em i l i t a r yt r a n s p o r t a t i o nd e c i s i o n - m a k i n g p r e v i o u sr e s e a r c h e so i lt h em i l i t a r yt r a n s p o r t a t i o nn e t w o r ko p t i m i z a t i o nf o c u so i l s t a t i ca n dd e f i n i t ei n f o r m a t i o n h o w e v e r , al a r g en u m b e ro fi n d e t e r m i n a t ea n d s t o c h a s t i ci n f o r m a t i o ne x i s t si n a c t u a lt r a n s p o r t a t i o nn e t w o r ka c c o m p a n i e db ye v e r i n c r e a s i n gs c a l ea n ds t r u c t u r a lc o m p l e x i t y t r a d i t i o n a lm o d e l sa n da l g o r i t h m ss h o w g r e a tl i m i t a t i o n si ns o l v i n gt h ep r o b l e m , s oi ti sn e c e s s a r yt od of t l r t h e rr e s e a r c hi no r d e r t oc o n s t r u c tm o 他e f f e c t i v em o d e l sa n d a l g o r i t h m s b a s e do nam i l i t a r y t r a n s p o r t a t i o n - a i d e dd e c i s i o n - m a k i n gp r o j e c t , t h i st h e s i ss t u d i e st h eo p t i m i z a t i o nm o d e l s a n da l g o r i t h m so fs t o c h a s t i ct r a n s p o r t a t i o nn e t w o r k 1 1 h em a i nc o n t e n t sa n df r u i t so ft h i s t h e s i sa r eo u t l i n e da sf o l l o w s ： f i r s t l y , b a s e do ns u m m a r i z i n gag r e a ta m o u n to fr e l a t i v er e f e r e n c e s ，w er e v i e wt h e d o m e s t i ca n df 1 0 r e i 舯r e s e a r c ha c h i e v e m e n to nt h et r a n s p o r t a t i o nn e t w o r ko p t i m i z a t i o n , a n a l y z et h ec o m p o n e n t sa n ds u b s i d i a r i e so ft h ep r o b l e m , a n dp o i n to u tt h es h o r t c o m i n g s o ft h et r a d i t i o n a lm o d e l sa n da l g o r i t h m si ns o l v i n go p t i m i z a t i o n si nt h es t o c h a s t i c t r a n s p o r t a t i o nn e t w o r k s e c o n d l y ，f r e q u e n c y - d o m a i nm o d e lo fs t o c h a s t i ct r a n s p o r t a t i o nn e t w o r ka n di t s e x p e c t e dm e t h o d sa r es t u d i e d c o n s i d e r i n gt h er a n d o m n e s sr e s u l t i n gf r o mo c c a s i o n a l a c c i d e n t sa n do t h e rf a c t o r s ，w et r e a tt h et r a v e lt i m eo fr o u t e s ，f l o wr a t e sa n dr e l i a b i l i t y a sr a n d o mv a r i a b l e s t h e nw eg e n e r a t eo u rf r e q u e n c y - d o m a i ns p a n n i n gg r a p hm o d e lo f t h es t o c h a s t i ct r a n s p o r t a t i o nn e t w o r kf r o mt h es t a t i s t i c sa n dp r o b a b i l i t yt h e o r ya n dt h e c l a s s i cn e t w o r km o d e l s ，w h i c hn o to n l yd e s c r i b ea l lk i n d so fs t o c h a s t i ci n f o r m a t i o ni n t h et r a n s p o r t a t i o nn e t w o r ks u c c e s s f u l l y , b u ta l s op r o v i d et h et r a n s f o r m a t i o nb e t w e e n t i m e - d o m a i na n df r e q u e n c y - d o m a i np r o b a b i l i t yf u n c t i o n s b ya n a l y z i n gt h er e s u l to ft h e n u m e r i c a le x a m p l e , w ev e r i f yt h ef r e q u e n c y - d o m a i nm o d e l sa n da l g o r i t h m sa n db e l i e v e i ni t sf a s ta n dh i g h l ye f f i c i e n ta b i l i t yt oa n a l y z et h ee x p e c t e do p t i m i z a t i o no ft h eo p t i m a l r o u t e s ，m a x f l o wa n dr a i n f l o w ，r e l i a b i l i t yp r o b l e m sb a s e d0 ng e n e r a l i z e dc u t s e t a l g o r i t h m t h i r d l y ，f r e q u e n c y - d o m a i n m o d e lo fs t o c h a s t i c t r a n s p o r t a t i o n n e t w o r k o p t i m i z a t i o na n di t sa l g o r i t h mw i t hs o m ec o n s t r a i n e dc o n d i t i o n sa r es t u d i e d a l t h o u g h t h ee x p e c t e do p t i m i z a t i o ni se a s yt oi m p l e m e n t ，i tf a i l st oc o n s i d e rs o m es t o c h a s t i c i n f o r m a t i o na n ds o m e t i m e st h ea n a l y s i sd i f f e r sf r o mw h a ti ts h o u l db ei nr e a l i t y t h u s w ep r e f e rt oc o m p r e h e n s i v e l yo p t i m i z et h en e t w o r kw i t hp r o b a b i l i t yd i s t r i b u t i o nm e t h o d 第i i i 页 国防科学技术大学研究生院博士学位论文 t w os c e n a r i o sa r ec o n s i d e r e d ：o n es e t st h es u c c e s sp r o b a b i l i t y 舔t h eo b j e c t i v ea n dt r i e s t of i n do u tt h er o u t e 、i lt h e 戚n l 啪p r o b a b i l i t ys u b j e c tt ot i m ec o n s t r a i n t ；t h eo t h e r a i m sa tt h et r a v e lt i m ea n ds e a r c ht h el e a s tt r a v e lt i m er o u t ew i t h i nf i x e de r e d i t a b l e p r o b a b i l i t yr e g i o n b e s i d e s ，t of i n dt h es t o c h a s t i cm a x - f l o wa n dm i n - f l o w ，t h i st h e s i s g i v e ss o m ed e f i n i t i o n sa n dt h e o r e m si no r d e rt oc o n v e r tt h ep r o b l e m si n t of i n d i n gt h e s l i mo ft h ef l o wr a t e so fa l lt h en o d e si nt h em i n i m u mb i d i r e c t i o n a lc u t - s e t ( s ，s ) 曲，i e t h ep r o d u c to fn o d e s f u n c t i o n si nt h ef r e q u e n c yd o m a i n i na n a l y z i n gt h er e l i a b i l i t yo f t h es t o c h a s t i ct r a n s p o r t a t i o nn e t w o r k , w ep r o p o s eaf r e q u e n c y d o m a i nr e l i a b i l i t ym o d e l a n da l g o r i t h m n ep e r f o r m a n c eo ff r e q u e n c y - d o m a i n o p t i m i z a t i o n m o d e la n d a l g o r i t h m sa r ev e r i f i e db ya n a l y z i n gt h er e s u l t so fn u m e r i c a le x a m p l e s f o u r t h l y ，s t o c h a s t i ct r a n s p o r t a t i o nn e t w o r ko p t i m i z a t i o nm o d e la n di t sa l g o r i t h m w i t h m u l t i p l eo b j e c t i v e sa n dm u l t i p l ec o n s t r a i n t sa r es t u d i e d w i mr e s p e c tt ot h e s t o c h a s t i ca n dt i m e d e p e n d e n tc h a r a c t e r i s t i co fm i l i t a r yt r a n s p o r t a t i o nn e t w o r k , w e d i s c u s st h ef u n c t i o n a lr e l a t i o n s h i po ft h et r a v e lt i m e ，w a s t a g ea n df l o wr a t e t h e nw e p r o p o s et h em u l t i - - o b j e c t i v em u l t i - c o n s t r a i n tf r e q u e n c y - d o m a i nw e i g h t e du t i l i t ym o d e l s a n da l g o r i t h m sb a s e do nf r e q u e n c y - d o m a i ns p a n n i n gg r a p hm o d e l t h ep e r f o r m a n c eo f t h em o d e l sa n da l g o r i t h m sa r ev e r i f i e db ya n a l y z i n gt h er e s u l to fan u m 丽c a le x a m p l e f i f t h l y ，o p t i m i z a t i o n m o d e la n di t s a l g o r i t h m f o r l a r g e s c a l e s t o c h a s t i c t r a n s p o r t a t i o nn e t w o r ka r es t u d i e d b e c a m et h en e t w o r k l e v e la t t r i b u t ev a l u e sh a v e s u b p r o p e r t i e s o fm o n o t o n o u s ，ah i e r a r c h i c a ln e t w o r km o d e lb a s e do n f r e q u e n c y d o m a i ns p a n n i n gg r a p hi sp r e s e n t e d t 1 1 eh i e r a r c h i c a ls t r u c t u r ec o u l dr e s u l t i nav e r ye f f e c t i v ef r e q u e n c y - d o m a i nl a y e r i n gs e a r c ha l g o r i t h mt or e d u c et h es p a c e c o m p l e x i t y t h es t a t es p a c ei s d e c r e a s e df r o me x p o n e n t i a lt ol i n e a rs e a r c h t h e c o m p u t a t i o n a lr e s u l t so fn u m e r i c a le x a m p l ea n da l g o r i t h mp e r f o r m a n c ee x p e r i m e n t v e r i f yt h ef e a s i b i l i t ya n de f f e c t i v e n e s so fm o d e l sa n da l g o r i t h m s f i n a l l y ，t h ep r o p o s e df r e q u e n c y - d o m a i no p t i m i z a t i o nm o d e l sa n da l g o r i t h m sa r e a p p l i e dt oam i l i t a r yt r a n s p o r t a t i o n a i d e dd e c i s i o n - m a k i n gp r o j e c t o t h e ra p p l i c a t i o n so f p a t ho p t i m i z a t i o nb a s e d o nt h ew e b g i sa r ea l s os t u d i e d k e yw o r d s ：s t o c h a s t i ct r a n s p o r t a t i o nn e t w o r k ；f r e q u e n c y - d o m a i nn e t w o r k o p t i m i z a t i o n ；o p t i m a lm u t e s ；m a x i m u mf l o w sa n dm i n i m u mf l o w s ；r e l i a b i l i t yo f t r a n s p o r t a t i o nn e t w o r k ；m o d e l sa n da l g o r i t h m s 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表1 1 运输网络优化问题分类3 表1 2 网络流算法时间复杂度进展l o 表1 3 运输网络可靠性主要定义的特征比较1 2 表1 4 运输网络优化问题与遗传算法概念的对应关系1 9 表2 1 常用时域概率函数与频域概率函数转换表4 0 表2 2 运输网络中各路段的期望参数。4 6 表3 1 随机最优路径的分析计算结果5 7 表3 2 给定置信度的流量分析结果。6 5 表3 3 规定流量的发生概率计算结果6 6 表3 4 图3 1 1 中频域可靠度函数的数值设定6 9 表4 1 各路段运输时间的概率密度函数及与损耗、流量间的函数关系7 8 表4 2 约束时间、损耗、流量的多目标分析计算结果8 2 表4 3 约束发生概率的多目标分析计算结果8 3 表5 1 运输时间约束下最大成功概率的路径优化分析结果9 8 表5 2 成功概率约束下最短运输时间的路径优化分析结果9 8 表6 1 保障任务预测清单1 1 0 表6 2 战区内物资储备决策清单l l1 表6 3 运输网络路段连通情况表1l2 表6 4 补给决策清单1 1 2 表6 5 运输决策清单1 1 4 表6 6 运输网络统计状态及各路段旅行时间的概率分布函数l1 7 表6 7 约束运输时间的最优路径计算结果。1 1 9 表6 8 约束成功概率的最优路径计算结果1 1 9 表6 9 基于g o o g l em a p s 的随机路径优化的计算结果。1 2 0 第页 国防科学技术大学研究生院博士学位论文 图目录 图1 1 运输网络优化方法的研究进展1 3 图1 2 研究思路、主要研究内容及对应章节示意图2 5 图2 1 时域的随机运输网络模型2 7 图2 2 一个加权运输网络2 8 图2 3 时变运输网络中传统算法的局限2 8 图2 4 概率随机运输网络中传统算法的局限2 9 图2 5 新问题下传统算法的不适用2 9 图2 6 随机运输网络的频域生成图3 0 图2 7f s g 模型的串联结构31 图2 8f s g 模型的并联结构3 3 图2 9f s g 模型的环形结构3 4 图2 1 0f s g 模型的备选结构3 5 图2 1 lf s g 模型的桥形结构3 6 图2 1 2 一有向随机运输网络的频域生成图4 5 图2 1 3 广义割集求最优路径4 7 图3 1 硬时间窗结构。5 l 图3 2 时域下两条路段的通行状态。5 l 图3 3 随机运输路径优化的频域生成图5 2 图3 4 各路径的通行概率分布图5 5 图3 5 随机运输网络的最优路径。5 5 图3 6 一有向随机运输嘲络的频域生成图模型5 5 图3 7 图3 6 所示运输网络中各路径通行概率分布图的比较分析5 7 图3 8 随机运输列络流量的频域生成图。5 9 图3 9 一有向随机运输网络流量的频域生成图模型。6 3 图3 1 0 随机运输网络中不同割面的流通能力分析。6 5 图3 1l 一有向运输网络可靠度的频域生成图模型6 7 图3 1 2 图3 1 l 所示运输网络系统的可靠度k ( f ) 曲线7 0 图4 1 多目标多约束的随机最优路径分布图7 7 图4 2 一有向随机运输网络的频域生成图模型7 7 图4 3 随机运输网络中单目标路径优化的概率分布8 0 图4 4 不同权重下约束时间、损耗、流量的多目标最优路径分布图。8 l 第v 页 国防科学技术大学研究生院博士学位论文 图4 5 不同权重下约束发生概率的多目标最优路径分布图8 2 图5 1 广义层次化的大规模频域生成图。8 8 图5 2 频域生成图的层次网络模型8 9 图5 3 大规模随机运输网络的最优路径9 4 图5 4 大规模运输网络的广义层次f s g 模型示例9 6 图5 5 图5 4 所示运输网络中各路径通行概率分布图的比较分析9 7 图5 6 频域层次优化算法与其他算法的性能比较1 0 0 图6 1 军事运输优化辅助决策系统的基本组成1 0 2 图6 2 军事储备决策信息流程图1 0 4 图6 3 军事筹措决策信息流程图1 0 5 图6 4 军事补给决策信息流程图1 0 6 图6 5 军事运输决策信息流程图1 0 7 图6 6 军事储备决策界面1 1 0 图6 7 军事筹措决策界面l1 l 图6 8 军事补给决策界面1 1 3 图6 9 军事运输决策界面1 1 3 图6 1 0 随机时间路径优化的概率分布曲线比较1 1 5 图6 11 基于w e b g i s 的随机运输网络优化信息流程图11 6 图6 1 2 基于w e b g i s 的随机运输网络图1 1 7 图6 1 3 基于g o o g l em a p s 的随机路径优化的搜索结果1 2 0 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目： 学位论文作者签名：盘兰日期： 口j 年 学位论文版权使用授权书 4 月7 日 f 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 国防科学技术大学研究生院博士学位论文 第一章绪论 本文以军事运输网络为背景，研究随机运输网络优化问题。军事运输是运用 各种交通运输工具，在空间的各类交通线上，实现军队人员和装备物资在空间上 的位移，以保障军事意图得以顺利进行的活动【i - 3 】。其网络定义为一定空间范围内 由几种军事运输方式的线路和军事枢纽等固定技术装备组成的综合体【4 5 】。军事随 机运输网络中结点和弧的权值具有时间不确定性、参数多样性和信息随机性。其 背景起因于现代战争的突发性急剧增强，运输保障物资的补给空前加快，运输网 络规模不断扩大并呈现出高度复杂和瞬息万变的形势。这些对军事运输网络的随 机适应能力、快速运输能力、安全抗毁能力提出了更高的需求。随着智能交通、 计算机网络、通信、全球定位系统( g p s ) 、地理信息系统( g i s ) 、人工智能等 众多系统的广泛应用和现代网络理论及技术的进一步发展，随机运输网络涌现出 一些新特性睁引，导致出现传统优化模型及算法难以解决的新问题。本文正是针对 这些优化问题，在现有研究成果的基础上从理论方法及应用方面开展研究工作的。 1 1 研究背景与意义 随机运输网络优化问题是军事物流决策优化的主要研究问题之一，其最优路 径、最大流、最小流、网络可靠性问题为运输网络优化的关键技术问题【9 , 1 0 。从海 湾战争、科索沃战争和伊拉克战争中物资运输和供给的角度看，它们无一不是规 模庞大、物资高度繁杂和高效流动的跨国军事物流运输的战争，其运输网络、运 输任务和运输环境都呈现出明显的随机性，军事物资运输补给已成为影响作战进 程的重要环节。从冷兵器时代到高精尖武器时代，与其相伴的军事运输网络也由 通行人、役畜的道路以及天然水道所组成的运输网络发展到复杂的“陆海空一三 维一体的运输网络。面对世界新军事变革大潮，许多国家竞相加快了军事运输转 型步伐和保障模式的革新。将先进的信息技术、通信技术、电子控制技术、传感 器技术以及优化决策技术等有效地综合运用于整个军事运输体系，从而建立大范 围、全方位的高效准确的交通运输综合管理系统。其目的是以最少的运输资源提 供最优的配送支援，以最低的运输成本构建最佳的运输网络，以最短的运输时间 实现最大的配送效益，极大地提高运输效率、运输保障安全性和资源利用率。 军事运输网络是国家交通运输网络的一个重要组成部分，任何交通设施和技 术的发展都将影响军事运输的组织与实施。k i n g ，j e f f e r y 1 1 1 3 】等人研究发现，运输 车辆平均多行驶6 的不必要距离，6 的时间和1 2 的距离则被浪费。这表明运 输网络的利用效率还不高，若对军事运输网络加以控制和管理，平时军事运输现 第1 页 国防科学技术大学研究生院博士学位论文 有的运输能力将有较大提升空问，战时军事运输也将具有较高的可靠性。2 0 世纪 8 0 年代末，以美国为先导的发达国家提出了“配送式后勤 ，但因技术水平有限， 一直受配送信息不明、运输网络不畅、运输手段滞后等问题所困。而后1 9 9 1 年美 国国会制定的智能交通系统( i t s ) 发展战略规划中指出：i t s 的主要目标是应用 先进的技术和现代算法方法学来提高运输效率。1 9 9 6 年美军首次提出了主动配送 模式，并将其界定为“信息、后勤和运输技术的融合 在( 2 0 1 0 年联合构想 中，美军又首次把“配送保障 作为与“主宰机动、精确打击、全维防护 相并 列的四大作战原则之一【2 i o 】，并强调了军民运输网络的紧密结合。而这些都是建立 在完善的运输网络基础之上。因此，研究随机运输网络优化问题，对运输梯队的 最优路线选择和实施科学的运输管理，以提高运输效率、网络使用率和降低运输 损耗具有重要的理论意义和实用价值。 在传统的运输网络模型中，一般假设网络中的所有信息( 弧的权值、状态) 是确定的，而且这些信息与时间相关甚少。同时，军事运输制定配送方案中，对 运输路径的选择主要是靠经验评估，一般从时间、损耗、危险性等方面做定性和 静态网络的优化分析。然而，这些简化假设使得许多应用领域的分析结果与实际 结果并不相符，没有很好地反映出随机运输的特性。现实运输嘲络中存在着大量 的不确定性，例如，运输出勤时机的随机、交通堵塞和敌袭导致路段运输时间的 变化，以及优化决策者的主观偏好，等等。特别在现代战争的作战进程空前加快， 各类不确定信息的量化难度越来越大，运输规模不断扩大的情况下，使得确定性 运输网络的优化方法失去了实际意义，决策者往往更加关心的是在最短时限内完 成运输任务的可能性，即完成运输的成功概率。因此，传统的网络优化方法难以 适用于随机运输网络优化问题的求解，需要进一步研究与之相应的模型及算法来 解决随机运输网络优化中出现的新问题。 1 2 相关领域及国内外研究现状 1 2 1 国内外运输网络优化问题的研究现状 运输网络优化问题最初属于图论的研究范卧悼1 6 1 。1 7 3 6 年e u l e r 提出了著名的 哥尼斯堡七桥问题，标志着运输网络理论研究的开始。早期图论主要涉及一些利 用简单的规则网络来研究运输网络优化问题，如最小树问题、邮递员问题等。近 几十年来，国内外对运输网络优化问题的研究给予了越来越多的关注，根据其研 究的目标内容与数学模型，可分为最优路径、最大流、最小流、网络可靠性以及 车辆路径问题( 姆) 等；根据参数的属性和时间约束条件，分为静态和动态运 输网络优化问题；按照信息和网络环境的确定性与非确定性，分为确定、随机和 第2 页 国防科学技术大学研究生院博士学位论文 模糊运输网络优化问题；根据优化目标的维数，分为单目标和多目标运输网络优 化问题：按照网络规模的大小，分为中小规模和大规模运输网络优化问题；在研 究的计算路线和算法上，分为精确算法和近似算法。各大类之间的相互组合产生 了各种各样的运输网络优化问题，表1 1 给出了运输网络优化问题的分类。 表1 1 运输网络优化问题分类 分类标准问题类型 最优路径问题 数学模型最大流、最小流问题 网络可靠性问题 静态运输网络优化 时间变化 动态运输网络优化 确定运输网络优化 网络信息随机运输网络优化 模糊运输网络优化 单目标运输网络优化 优化r 标数f 1 多目标运输网络优化 中小规模运输网络优化 网络规模 大规模运输网络优化 带约束限制的运输网络优化 约束限制条件 不带约束限制的运输网络优化 运输网络优化问题可描述为：由结点( 运输枢纽、仓库、城市、港口、兵站 等) 、无向边和有向弧( 运输线路、铁路、公路、航空线路等) 组成的运输网络 中，根据供求关系，合理有效地计划、管理和控制运输梯队的运输路线和运输时 间，从而在给定的约束条件下完成运输任务，并使之产生最大的效益，即目标函 数最优化。 其优化问题的构成要素主要包括：运输网络、约束条件和优化目标。 ( 1 ) 运输网络。由结点和边、弧组成。边、弧的属性包括方向、权值和约束 等。其中，权值可用运输时间、距离、流量、损耗或费用等表示，可以是不随时 间变化的常量，即静态运输网络：也可以是随时间变化的变量，即动态运输网络。 ( 2 ) 约束条件。运输网络优化问题应满足的规定条件，如运输网络中路段流 量限制、必经结点、必经路段、运输途中损耗量限制、路段安全性约束、运输任 第3 页 国防科学技术大学研究生院博士学位论文 务完成时间的要求等。对于运输网络权值间的关系，可以具有相关性或满足三角 不等式，也可以不加任何限制。 ( 3 ) 优化目标。可以是单目标或多目标。常用的优化目标有，运输距离最短、 运输时间最少、运输综合费用最小、运输损耗最小、运力利用最合理、运输可靠 性最高、完成运输任务概率最大，等等。 下面综述运输网络优化中三个基本问题的研究现状，即最优路径问题、最大 流、最小流问题、网络可靠性问题的基本理论、模型特点以及发展现状。 1 2 1 1 最优路径闯题的研究 最优路径问题是运输网络优化关键问题之一，许多其他运输网络优化问题都 能够转化成该问题进行求解，包括经典最短路径问题、随机最优路径问题以及多 种不同的变形问题。 ( 1 ) 经典最短路径问题 经典最短路径问题【1 7 d 9 1 ，即网络中的结点和弧的权值为常量时，寻找静态网 络中两结点之间的最短路。设g = ( 矿，e ，矿) 是一个连通网络，y 为结点集合，e 为 弧集合，w 为权集，g 中弧( v f ，1 ，) e 的权一般为非负实数( w ，= ，表示结 点v i 与y ，之间无弧) ，起点和终点v o v 是网络g 中的任意两个结点。寻找一 条从v d 到的路径p ，使其为所有从到v d 的路径p 中路长w ( p ) 最短的路径， 故两点间最短路径模型表示为 w ( p ) - m 。i n 嘞 ( 1 1 ) 蚱，v j ) e e 这类问题模型与算法的研究已有相当的历史，从1 9 5 8 年美国数学家动态规划 的鼻祖r b e l l m a n 就开始研究这一问题【1 4 1 ，紧接着1 9 5 9 年荷兰著名的计算机科学 家e w d i j k s t r a 提出了具有深远影响的最短路径算法d i j k s t r a 算、法【1 7 1 。继d i j k s t r a 开创性的工作以后，研究人员提出了大量求解最短路径的方法，其理论不断发展， 产生了大量模型与算法【9 , 1 8 - 2 1 】。c h e r k a s s k y ，g o l d b e r g 和r a d z i k 2 2 1 在1 9 9 6 年对已有 的1 7 个最短路径算法进行了理论分析和试验评价，它们与d i j k s t r a 算法的不同之 处是对当前点的后续邻接结点的探测方面做了改进，提高了算法的效率。谭国真 【2 3 】、柳业玲【2 4 】等按照不同算法类型分析和评价了2 0 多个最短路径算法，并将其分 为标号设置方法、标号修改方法、动态规划方法、基于线性代数方法、启发式和 双向启发式算法、基于流体神经网络的算法。这些算法都属于静态确定性算法， 即处理固定运输网络拓扑和固定的权值。在现实生活中，最短路径问题的提法很 多，单目标最短路径问题( s d s