（运筹学与控制论专业论文）需求和容量不确定的多阶段网络流问题.pdf

摘要y 9 5 3 69 9 摘要 本文研究需求和容量不确定的多阶段网络流问题( m u l t i s t a g e n e t w o r kf l o w p r o b l e m w i t h u n c e r t a i n d e m a n da n d a r c c a p a c i t i e s ) 。在网络中，每个结点被赋予一个启 用时刻，以该结点为起点的弧在该时刻起可被使用。模型中结点需求和弧容量在相应 弧被启用前都是随机变量，且满足已知的离散分布。我们用情景来描述需求和容量的 不确定性，用情景集划分所得的情景束建构非预期性约束，该约束保证了两个情景不 能被区分时所作的决策是一致的。此外针对需求随机性，在每个结点上允许商品短缺 过量供应，但分别给予相应的惩罚。 本文用基于复合路径分解的拉格朗日分解算法求解模型，把容量约束松弛后得到 复合路径分解法的主问题和子问题。子问题的求解用到了多情景下的寻找最短路方 法；利用改进的次梯度算法求解主问题。文章最后给出一个计算实验。 关键词：多阶段网络流，需求和容量不确定，情景束，复合路径分解，拉格朗日松弛 分类号：0 2 2 a b s t r a c i a b s t r a c t w ec o n s i d e ram u l t i s t a g en e t w o r kf l o wp r o b l e mw h e r et h en o d ed e m a n d sa n da r c c a p a c i t i e sa r er a n d o mv a r i a b l e s i ni t sd i r e c t e dg r a p h ，e a c hn o d ei sa s s o c i a t e dw i t hs o m e t i m ea n da r ci sa v a i l a b l eu n t i li t ss t a r tn o d ei sb e i n gu s e d n o d ed e m a n d sa n da r cc a p a c i t i e s a f ea s s u m e dt ob cs t o c h a s t i cw h i c hm e e tad i s c r e t ed i s t r i b u t i o na n dw i l lb ek n o w nu n t i lt h e c o r r e s p o n d i n ga r ci sa v a i l a b l e w ed e s c r i b et h er a n d o m n e s su s i n gs c e n a r i o sa n di n t r o d u c e s c e n a r i ob u n d l e st om o d e lt h eu n a n t i c i p a t i v i t yc o n s t r a i n t s m o r e o v e li ft h en o d ed e m a n di s n o te n t i r e l ym e t ( u n d e r s t o c k i n g o v e r s t o c k i n 曲，ap u n i s h m e n tc o s tw i l lb ei n c l u d e d w eu s el a g r a n g i a nr e l a x a t i o nw h i c hi sb a s e do nas c h e m en a m e dc o m p a t h d e c o m p o s i t i o nt od u a l i z et h ec a p a c i t yc o n s t r a i n t s c o m p a t hs u b p r o b l e mi ss o l v e db ya d y n a m i cp r o g r a m m i n ga l g o r i t h md e r i v e df r o mf i n d i n gas h o r t e s tp a t hi na na c y c l i cg r a p h c o m p a t hm a s t e rp r o b l e mi sc a l c u l a t e db ya ni m p r o v e ds u b g r a d i e n tm e t h o d a tt h ee n d ，a c o m p u t a t i o n a lr e s u l ti sp r e s e n t e d k e yw o r d s ：m u l t i s t a g en e t w o r kf l o w , u n c e r t a i nd e m a n da n dc a p a c i t i e s ，s c e n a r i ob u n d l e ， l a g r a n g i a nr e l a x a t i o n ，c o m p a t hd e c o m p o s i t i o n 引言 引言 动态网络( d y n a m i cn e t w o r k ) 又名时间一空问网络。在该网络中，每个结点代 表一特定地点，并被赋予一个启用时刻，以该结点为起点的弧在该时刻起可被使 用。与动态网络关联的有向图称为动态网络图。动态网络具有广泛的应用背景。 早期被用于最小化满足进度表的油轮数目( d a n t z i g 和f u l k e r s o n ，1 9 5 4 1 ，之后由 l o r d 和f u l k e r s o n ( 1 9 6 2 ，i 9 1 于上世纪6 0 年代正式提出动态网络模型。动态 网络是描述动态车队管理问题的一种重要方法。w h i t e 和b o m b e r a u l t ( 1 9 6 9 ) 、 w h i t e ( 1 9 7 2 ) ；f t j 用确定动态网络明确表述了有轨车管理问题，并对换乘问题提出 了一个归纳算法。m a g n a n t i 和s i m p s o n ( 1 9 7 8 ) 回顾了一系列适用于车队管理的动 态网络模型，着重研究了用于解决多商品流问题的分解算法。关于动态网络的应 用，a r o n s o n l l j ( 1 9 8 9 1 对其作了进一步全面的研究。 早期关于动态网络的研究都集中在确定网络上。很多实际问题由于在决策过 程中会受到如结点需求、弧容量、弧上运输成本等不确定因素的影响，而被建模 成随机动态网络流模型。例如，有轨电车分布问题( j o r d a n 和t u r n q u i s t ，1 9 8 3 ) 、 货车装载时序安排问题( p o w e l l 等，1 9 8 8 ) 、投资规划问题( m u l v e y 和v l a d i m i r o u l 2 ， 1 9 8 9 ) 、空中交通管理模型( r i c h e t t a 和o d o n i i 矧，1 9 9 4 ；v r a n a s f 3 0 】等，1 9 9 4 a 和1 9 9 4 b ； g l o c l m e t 【”1 ，1 9 9 6 ) 、库存模型等。g l o c k n e r 和n e m h a u s e r 9 1 ( 2 0 0 0 ) 把弧容量不确 定的动态网络建模成多阶段随机规划问题，之后又把它推广到多商品流问题。 当多阶段随机规划的随机变量无限维时，求解难度很大。解决这种问题时， 我们通常用一个有限维的近似来代替它。即使随机变量都是有限维的，由于情景 数很大，问题通常也很难求解。虽然决策者想尽量避免不确定的发生，但计算方 法的局限性使得融入不确定因素的模型求解起来更为困难。对多阶段随机规划的 求解，目前已有两种方案：一种是时间分解法，如l - s h a p e d 方法( k a l l 和w a l l a c e i 玎】， 1 9 9 4 ；v a ns l y k e 和w e t s ”j ，1 9 6 9 ) 等；另一种是约束分解法，这种方法可以用 l a g r a n g i a n 分解或d a n t z i g - w o l f e 分解加以实现。 之前对多阶段随机网络流问题的文献都只涉及一个随机量。对于结点需求和 弧容量都不确定的网络流问题到目前为止还尚未有过研究，且具有一定的实际利 用价值。我们假定弧未被启用前，与该弧关联的结点需求和弧容量都是未知的， 这一不确定性增加了决策的复杂性。本文把它建构成多阶段随机规划模型，并在 目标函数中新增短缺持有成本，以便短缺需求量或多余的供给量尽可能达到最 小。用情景来描述量的随机性，引进非预期性约束来阐明相邻情景问弧流量的关 系。本文所用的求解方法是基于复合路径分解算法上拉格朗日松弛。该算法最终 引言 能够找出原始问题的近似最优解与近似目标函数值。 本文结构安排如下：第一章介绍了动态网络流问题及其背景，重点指出其与 一般的网络流问题的异同，以及目前的研究现状；第二章定义了几个函数，引进 了情景束，建立了结点需求和弧容量都不确定的多阶段网络流模型。对模型可能 的几种求解方案进行复杂性分析；第三章介绍算法中将使用的定理和推论，然后 提出建立在复合路径算法之上的拉格朗日松弛，并给出算法的具体步骤和对应框 图；第四章设计计算实验；最后一章是对全文的总结。 第1 章动态网络流问题及其背景 第1 章动态网络流问题及其背景 对于有向图g = ，4 ) ，如果v 中的每个结点f 都与某时亥q t ( i ) 关联，且对a 中 的每条弧( f ，j ) 都满足t ( ocr ( ，) ，则称g ；( y ，a ) 是动态网络图。动态网络也被称 为时间一空间网络，因为在特定时刻，每个结点代表一特定地点。如果网络流模 型对应的有向图是动态的，就称该网络流模型是动态网络流模型。对可行的动态 网络流来说，从结点i 到结点j 的传送时间为f ( ，) 一f ( f ) ，相应的区间【f ( f ) ，f ( 捌称 为该网络流在弧o ，) 上的传送时期。我们可以从多阶段存货问题构造出一个动 态网络流模型的简单例子，结点表示再订购日，弧表示在途库存，该例子在 g o l v e r i “o 等( 1 9 9 2 ，第4 章) 有详细论述。 一般的有容量或无容量限制的网络流问题主要解决商品如何以最小代价( 包 括设计费用( 网络设计问题) 、运输费用等) 从供应点集合配送到需求点集合。以 多商品流的运输任务为例，我们的目标就是在给定的一个含有n 个结点m 条弧的 有向图g = ，爿) 中，选出一些弧构成一个子网络，用于完成将第k 种商品( 后k ) 从供应点，耻) 运送至需求点d ( 七) 的k f 个运输任务。若涉及到选弧，目标函数中 还应添d i ：i * n 应的固定设计费用，问题的目标是使得所有产生的费用达到最小。 1 1 无容量限制网络流问题 无容量限制网络流问题( u n c a p a c i t a t e dn e t w o r kf l o wp r o b l e m ) 是最基础的一 种网络流问题，下面章节研究的多阶段随机动态网络流问题就是在它的基础上提 出来的。在这个网络流问题中，每一条弧可用于运送任意多种商品。 记( f e a ，k k ) 表示第k 种商品在弧f 上的流量，e ? ( f e a ，k e k ) 表示第k 种商品在弧f 上的单位运输成本，衅o e v ，k k ) 为第i 个结点对商品k 的需求 量。那么一般的无容量限制网络流问题( u n f p ) 可用以下数学模型来描述： m i n c 钟 忍詹 s t 何。= b 。，k e k( 1 1 ) ，0 ，e a ，k e k( 1 2 ) 模型中( 1 1 ) 为流量守恒约束，( i 2 ) 为流量非负约束。实际上， k ) 的取 值可从第t 种商品从供应点j ) 到需求点o ) 的相应于运输费用c ；的最短路算 法得到，该思想在后面章节中被得到推广。 第1 章动态网络流问题及其背景 1 2 有容量限制网络流问题 在有容量限制的网络流问题( c a p a c i t a t c dn e t w o r kf l o wp r o b l e m ) 中，每条弧z 都会给定一个容量限制“，要求该弧上各种商品流量和不超过“，。( c n f p ) 可用 下面的数学模型来描述： 晌荟荟。所觑息。 s 1 埘= b ，k e k 荟 f ( 5 ：，5 ，) ，则有 f o 】，s 3 ) = f ( 5 2 ，s 3 ) 。 证明：因为 k 12 掣2 = 妒，“f s l = “j 2 = “j 3 ，v ，爿。( ，) ， 又因为在时刻1 + r 0 ：，s ，) 必然存在弧f ，使得“；1 ；“；：一“尹( 否则与f ( s ：，屯) 的 定义矛盾) ，所以 r ( s l ，s 3 ) = m a x t ：“ = “j 2 ，t ( 1 ) s t = f 0 2 ，s 3 ) _ _ 定义3 1 ：称源汇路g 和q 对情景5 ，s 一致，如果到时刻f ( s ，5 ) 为止，路口 和q7 中的弧是相同的，即 q n 爿咖，) = g f l a ，( ，一) 。 定义3 2 9 1 ：称q = 佃1 ，9 2 ，q ) 是对应于情景集s 一 1 ，2 ，w 的一条复合 路径( c o m p a t h ) ，如果a 中的任n n 汇n q 和口对情景f ，都是一致的。 现在我们来研究表2 2 中分组法3 得到的子问题可行域 i盯+ 点 + 3 一e y 一5 = 矗，v s s p ( s ) = ，= ( ，y + ，y 一) ： 5 一，f ”1 = o ，v l 一，s s ， l，5 ，y ”，y o ，v s 5 其中n 是对应于单源、单汇、动态、连通有向图g ：( v ，a ) 的关联矩阵，因为g 是动态的，所以g 是无圈，p ( s 1 有界。 定义爿( q ) 是与复合路径q 关联的弧一情景对集合，它是爿s 的一个子集。 定义 s u p p ( y ) = 矗：y f 吣 第3 章模型求解 为向量y r “的支撑( r o c k a f e l l 盯，1 9 8 4 ，4 8 ) 。接下来的引理3 1 说明的是对分 组法3 子问题可行域中的任何可行流，= ( ，y + ，y 一) p ) ，都存在一条复合路 径包含在，= ( ，y + ，y 一) 的支撑中。 引理3 1 ：如果，p ) ，则必然存一条复合路径q ；幻1 ，q 2 ，q ”) 满足 4 ( q ) s u p p ( ，) 。 该引理的证明是采用对情景归纳的方法得出的。归纳过程中先寻找多情景下 的可行路径集，然后证明这些路径的一致性。证明过程中函数f 的三个命题发挥 了很大的作用。引理的证明过程也是构造复合路径的过程。在接下来算法寻找 ( m 2 ) 可行解的过程中就用到了该思想。 接下来给出的定理3 4 是对有界多面体极点的另一种描述，以可行流的支撑 为判断标准，完全不同于定理3 1 和定理3 2 。 定理3 4 。1 ：给定一个非空有界多面体p = ，：彬= b ，0 , b o 以及p 的 子集f = ，1 ，2 ，。) ，如果对任意的，p ，都存在，e 1 2 ， ，使得 s u p p ( f 1 s u p p ( f ) ， 则称c o n y ( f ) = p 。 定理3 4 是采用反证法得出的。由定理可以看出，如在有界多面体中能找到 某子集，使得该子集任意元素的支撑都包含在该多面体任意可行元的支撑中，则 该子集的凸包即为原多面体。 若把上述定理中有界多面体p 换成本文研究的多情景下的子问题可行域 p ( s ) ，把子集，= ，1 ，2 ， 换成f = ，1 ，2 ， ，则结论仍然成立。 若能找到这样的子集f ，则户中的元素，1 ，2 ，都是p ( s ) 的极点。 接下来的问题就是怎样才能找出p f s ) 的极点呢? 下面的定理3 5 和定理3 6 将给出答案。 定理3 5 。1 ：q ) = q l ，q ：，q ， 为对应于单源单汇、动态连通图g = ，a ) 和情景集s 的所有复合路径构成的集合，f + = 丘，丘，e 是对应于q ) 的源 汇流集合，则有n v ( 户+ ) ：尸岱1 。 上述定理是结合引理3 1 和定理3 4 得出的。该定理给出了多情景动态网络 流问题可行域的凸包表示。那么构成凸包的这些源汇流究竟是不是多情景下可行 域p ) 的极点呢? 下面提出的定理将会解决我们的疑问。 对于多情景下多面体的极点，我们还有以下两个重要的命题。 命题3 4 ：如果，”是多面体 p 1 = ，= ( f ，y ”，y 1 ) ：n ，+ 点y “一点y “= b 1 ，i = 1 , 2 ，k 第3 章模型求解 的极点，那么，一( ，“，“) 是 p = ( ，i ，) ：n 1 f 1 + e y “一e y = b 1 ，n f + 毋“一毋一= b k 的一个极点。 由命题3 4 可知：当多情景下几个独立的子问题整合成一个大问题时，子问 题极点整合后所得的向量即为整合后问题的极点。我们可以用该命题从情景子问 题的极点整合得到总问题的极点。 命题3 5 ：如果，是多面体 p 1 = ，= ( ，y + ，y 一) ：n 1 f + 正) ，+ 一e y 一= bz 的极点且2 ，+ + 巧”一点歹= b 2 ，那么，+ 是 p 皇 ，墨( ，y + ，y 一) ：n 1 f + 最y + 一点y 一= 6 1 ，2 ，+ e y + 一互y 一= 6 2 的极点。 由命题3 5 可知：在可行域中添加新约束后如果极点仍然可行，那么该极点 也是新可行域的极点。我们利用该结论在求解过程添加非预期性约束，从而验证 了原来的极点任是新问题的极点。 定理3 6 。3 ：若q 是对应于单源单汇、动态连通图g = ( v ，a ) 和情景集5 的一 条复合路径。f = ，1 。，”) 是对应于q 的源汇流，那么f 是p ( s ) 的极点。 上述定理可由命题3 4 和命题3 5 联合导出。由此我们已经知道，构成p 岱) 凸包表示的那些源汇流f 正是我们要找的极点。定理3 5 和定理3 6 是对单情景 下多面体极点描述( 定理3 2 和定理3 3 ) 的推广。 因为对应于复合路径的任意网络流都是p 岱) 的极点，若能找到问题的复合 路径，就能找出相应该路径的源汇流，也就找到了p ( s ) 的极点。 推论3 1 。1 ：若q ( s ) = q 。，q 2 ，q ，) 为对应于单源单汇、动态连通图 g = ，爿) 和情景集s 的所有复合路径构成的集合。令，= e ，f 2 ，f ， 为对应 于复合路径集q p ) 的源汇路经流，那么f + 就是多面体p ( s ) 的所有极点集。 3 2 复合路径分解算法 在对多阶段随机规划模型( m 2 ) 的求解过程中，我们采用2 2 3 节的分组方 法3 ，把容量限制约束拉格朗日松弛。含短缺量过剩量的流量守恒约束、非预期 性约束和流量非负约束被放在子问题中。主问题是一个对偶变量非正条件下的拉 格朗日对偶问题。原始问题被分解为主问题和子问题之后，子问题采用推广的多 情景下寻找最短路径算法，主问题求解采用改进后的次梯度算法。初始对偶解也 可以根据容量约束的边界代价由原始启发式算法得到。 第3 章模型求解 我们称这种求解方法为建立在复合路径分解算法( c o m p a t hd e c o m p o s i t i o n ) 上的拉格朗日松弛( l a g r a n g i a n r e l a x a t i o n ) 。它完全不同于一般随机线性规划的渐 进回避法，把非预期性约束对偶化。与p o w e l l 和c h e u n g 2 2 】提出的算法的主要不 同点在于：时间段分解算法假定在各个时间段随机变量间是相互独立的。相比之 下，我们的模型采用情景集来描述，对各时间段下的随机量p ，, ) 也没有任何独 立性限制。 我们先对原始问题( m 2 ) 按照上述算法进行分解：记玎。为情景s s 下与容量 限制约束( 2 4 ) 关联的对偶变量，则玎是m w 维的非正向量。 记工 ) 为容量限制约束松弛后得到的拉格朗日对偶函数，整理后表示为如 下的( m 3 ) ： 工 ) 2 荟“5 “5 + m m 薹( p s c - - 石s ) ，。+ 荟p ，( 缈”+ 方1 ) s 2 n f3 + e y + 3 一e y 一3 = b s ，v s ，f 5 一，f ”1 = 0 ，v f 4 ，v s ：t ( 1 ) r 0 ，s + 1 ) fs ，y “，y 0 ，v 5 于是求解多阶段随机规划模型( m 2 ) 可以转化为求解如下的拉格朗日对偶问 题( m 4 ) 。( m 4 ) 的近似最优解可以为( m 2 ) 提供一个较好的下界。我们称之为复合 路径分解法的主问题f m a s t e rp r o b l e m ) ： ( m 4 ) ：m a x l o ) 。 “j u 由( m 3 ) 可知，为了得出( m 4 ) 的目标函数l 加) ，我们必须先求出下述优化问 题的目标函数值： m i n 善( p s c _ y rs ) ，。+ 罢p ，( 掣”+ 妒3 ) s 1 n f6 + e y + 5 一e y 3 ；b s ，y s 五一，”1 = o , v i 爿，v s ：f ( f ) s r ( s ，s + 1 ) ，5 ，y ”，y 0 ，y s 我们对上述模型进行整理，可得下述问题，记为( m 5 ) ，称之为复合路径分解算 法的子问题( s u b p r o b l e m ) 。 ( m 5 ) ：m i n ( 几“y c s p ，p ；d ) ( ，5 ，) ，”，y 一5 ) _ s j ( ，e ，一e x f5 ，y ”，y 1 ) _ 6 5 ，讥 1 9 第3 章模型求解 一，5 + 1 = o , v i e a ，v s ：f u ) s f 0 ，j + 1 ) ( ，5 ，y “，y “) o , v s 其中( 厂5 ，y ”，) ，“) 为向量( ，y ”，y “) 的转置。 以下我们将分节描述各问题的求解方法。 3 3 模型子问题求解 针对复合路径分解算法的子问题( m 5 ) ，我们考虑一种能在线性时间内求解子 问题的动态规划算法，该算法思想来自于单情景下无圈图中寻找最短路的算法 ( s h o r t e s tp a t h a l g o r i t h m ) 。 最短路问题是一类很重要的问题，在很多实际问题，如运输网络、通讯网络、 最优控制以及复杂问题的子问题中都会遇到，我们可以把它定义成网络流问题。 但是最短路问题的实际求解方法却不依赖于网络流模型，而是围绕着一系列与动 态规划密切相关的最优性条件。 如果以f 代表从结点i 到汇n 的最短距离，f 表示以f 为起点的弧的另一端 点，c 。代表弧( f ，f ) 的代价，则有如下的最短路问题最优性条件： = m i n 删j ) h + ， 。 很多最短路算法都通过递归该最优性条件来确定，i 。在无圈图中，如果把结 点按照a h u j a 等( 1 9 9 3 ，第4 章) 或者l a w l e r b 8 1 ( 1 9 7 6 ，第3 4 节) 描述的方法进行 拓扑排列，上述递归就可以在0 伽) 内完成。这个拓扑排列保证了计算正时， 。， 分别已经代表了从结点k + 1 ，n 到汇n 的最短距离。在本节中，我们 将把该思想延伸到多情景下的最优复合路径问题中，先给出了最优复合路径的最 优性条件，然后通过对结点拓扑排列给出有效求解递归的方法。 我们不把递归定义在整个情景集s 上，而是定义在情景束d s ，上。记 ，( f ，d ) 为在情景束d e s 。、下从结点f 到汇n 的最优复合路径代价。如果从结点f 到汇n 的路径不存在，则对所有的情景束d s 。、，我们定义，( f ，d ) = 。因为d 中的情景在时刻t ( f ) 不可区分，所以情景束d 下仅包含唯一一条从结点i 出发的 弧。根据以上定义以及最短路问题的最优性条件思想，我们可以得到如下的多情 景下的最优性条件递归式m ，： f ( i ，d ) = m i n 御 写+ 孓f ( j ，d 7 ) ) ， ( 3 1 ) a 蜀 d 瓴” 这里的瑶= p ；c 。一s ，边界条件为f ( n ，d ) = 0 ，对所有的d e s m l 。由2 1 4 中 关于情景束的定义可知，d 。、是由情景束d 在时刻f ( f ) 经再次划分得到的。在情 第3 章模型求解 景集s 下从结点1 到汇n 的最优复合路径代价为f ( 1 ，s ) ，该值即为( m 5 ) 中从源1 到汇n 的最优单位费用。另外由瓦的定义可知，( m 5 ) 的代价系数与对偶变量玎有 关，每取定一个玎值，子问题的源汇最优单位费用就会随之改变。 我们对结点进行排序使得对所有的 i 都有t ( j ) = t q ) ，这个排序保证了a 中所有的弧z = ( f ，f ) 都有 f 。在计算之前，我们先得确定一个丌值，这个可从 主问题的求解中得到。由于，o ，d ) = 0 ，于是对所有的d e s 。n ，利用递归式 ( 3 1 ) 我们先来计算最优值，伽一1 d ) ，然后对所有的d e s 。a ，计算 ，0 2 ，d ) ，如此一直递归下去，直到计算出，( 1 ，s ) ，那么子问题的目标函数 值就确定了。当算法到达弧f = ( i ，j ) 的起点f 时，该弧被扫描一次。对每个情景束 d s 。、，每条从结点f 出发的弧又且仅有一次被扫描，因此该算法能在o 伽w ) 时 间内找到最优复合路径。该算法的运行时间与输入数据的长度( 图g = ，4 ) ， 需求和容量情景集) 成多项式的关系。 对于该算法的运行时间我们还得出了两个重要的结论：一是对于某些输入数 据，运行时间等同于最坏案例。譬如，考虑一个只包含一条从源1 到汇，l 的路径 的简单图，所有情景在时刻f ) 都是不可区分的，则最优复合路径算法相当于解 决w 个独立的无圈最短路问题，每个问题花费的时间为硎，这里口为常数。二 是考虑到扫描输入数据( 需求和容量情景) 所花的时间至少是m w 的倍数，因此 最优复合路径算法可能是求解该问题的最好方法。 还有两种随机最短路算法与该复合路径算法有关。c r o u c h e r ( 1 9 7 8 ) 讨论了包 含随机可用弧的问题，他使用的算法是建立在不包含r e c o u r s e 的动态规划上，当 一条弧不可用时，他的策略是从其它所有可用弧中随机地选择一条新弧。 p o l y c h r o n o p o u l o s 和t s i t s i k l i s ( 1 9 9 6 ) r 研究的针对w 个情景下的随机最短路问题的 算法是建立在包含r e c o u r s e 的随机规划上，然而问题对应的图可以包含圈，意味 着递归过程中每个结点将有2 ”个情景束。 3 4 模型主问题求解 基于复合路径分解算法的拉格朗日松弛主问题( m 4 ) 的目标函数三伍) 是一个 分段线性凹函数，我们采用次梯度方法来求解( l e m a r e c h a l1 9 8 9 ，s h o r1 9 8 5 ) 。在 实际求解过程中，次梯度方法的收敛速度取决于三个因素：每次迭代过程中搜索 方向的选取、步长选取规则以及初始对偶解的优劣。 在本节中，我们将详细介绍如何来选取较优的搜索方向，把对偶可行解处的 极次梯度的凸组合来作为我们求解过程中所用到的次梯度。步长和初始对偶解均 来自贪婪启发式算法( g r e e d yh e u r i s t i c ) ，它在弧容量允许的范围内通过最大可能 笺! 耋堡型查坚 一一 的分配商品流量来构造原始问题( m 2 ) 初始可行解。我们在步长的选取中利用了 h e l d 【l 卅等( 1 9 7 4 ) 提出的启发式对偶目标函数值，这样得到的步长是几何收敛的a 我们通过改变弧容量来重新计算原始问题的初始可行解，从初始启发式算法的边 界价值中得到初始对偶解。这些技巧使得复合路径分解算法的运行速度有了很大 的提高。 3 4 1 初始启发式算法 由引理3 1 可知，原始问题( m 2 ) f i o j 任一可行流，都可以被用来寻找复合路 径。反之，我们可以通过在复合路径上分配流量来构造( m 2 ) 的可行解。该初始启 发式算法在弧容量允许的范围内往复合路径上尽可能多的增加现有弧上流量来 构建问题的可行解。 该算法的详细步骤如下： 步骤l ：初始化： 令 5 _ 0 ，y ? 5 - 0 ，y i 5 ：；0 ，对所有的5 s ，f 矿，4 ； 代价向量f - ( p ，c ，p 。c ) ； 单位缺货成本向量a ； 单位过剩成本向量d ； 商品运输的总源一汇流v ； 原始问题( m 2 ) 的初始目标函数值z 置0 。 步骤2 ：如果vs0 ，转到步骤4 ；否则转到步骤3 。 步骤3 ：在v ，0 条件下进行迭代。 在容量允许的情况下不断增加复合路径c 上弧的流量。 6 为每次迭代过程中允许的流量最大增量： 令62 m i n v ，f f r a ，h i n u ；一册) ， 对所有的( f ，s ) c ，令，f = ，f 5 + 6 ； 如果“i = 。，则令互= m ； 令z = z + ( c 1 ，v = v 一6 。转到步骤2 。 步骤4 ：如果，。) b5 ，则y = ，5 6 5 ；否则y ”= b 5 一，5 a z ：z + n y + + 咖一即为添加短缺过剩成本后的( m 2 ) 的目标函数值。此时 的流量( ，y + ，y 一) 即为原始问题( m 2 ) 的一个可行解，z 为相应的目标函 数值。 步骤1 赋初始流量( ，y + ，y 一) 为0 ，步骤3 对代价系数进行重新赋值保证了 下一次迭代中该路径将不可用，c ( c ) 代表复合路径c 的代价。由迭代过程可知， 第3 章模型求解 如果弧容量”和商品源一汇总流量v 都是整数，那么通过上述迭代产生的，也是整 数可行流。通过每一步对弧流量的增加，最后迭代结束时要么所有弧流量达到饱 和，要么v 变为0 ，因此最多迭代o ( m 次我们就可以找到一条可行的复合路径。 对于原始问题( m 2 ) ，初始启发式算法总能找到可行流。该可行流对应的原始 问题( m 的目标函数值给最优目标函数值的寻找提供了一个上界。在子问题中利 用最短路算法每得到一条复合路径，我们总是会利用初始启发式算法寻找新的可 行解，从而得到一个新的目标函数值。我们把它与上一次找到的值作比较，保留 较小的值。如此进行，这样找到的上界将与最优目标函数值越来越接近。为了确 定原始问题是不是真的不可行，可以参见接下来3 4 3 中提到的对偶问题的无界 性。 初始运行启发式算法时我们令代价向量f 等于期望代价p ，c ，p w c ”) 。一 旦获取了更多的对偶信息，我们可以选取一个新的代价向量孑利用初始启发式算 法来重新获得原始问题( m 2 ) 新初始可行解。由g l o c k n e r 和n e m h a u s e r 【1 w ( 2 0 0 1 ) 可知，我们也可用( p ，c y g - 1 ，p 。，c z ”) 代替原来的代价向量( 这里石5 是情景s 下与容量约束关联的对偶变量，此时的代价向量与复合路径分解法子问题( m s ) 的相同) 。如果我们用在0 ，c ，p 。c ) 与p ，c 一硝1 ，p 。c 一玎”) 之间线性搜索得到 的向量来作为我们迭代时的代价向量，利用初始启发式算法所得的可行解会更接 近最优解。我们可以用在( p 。c 一万1 ，p 。c 一”) 附近进行线性搜索得到的向量来 代替原来迭代过程中的代价向量f 。 3 4 2 初始对偶解 在对主问题( m 4 ) 的求解过程中，我们采用的是次梯度算法，因此首要任务就 是要找到一个初始对偶可行解。由于对偶变量的可行域是伽：zso ，于是对所 有的f e a ，s e s ，我们可以用靠；= 0 或者石j e 作为初始值进行迭代，通过迭 代求出主问题的近似最优解和目标函数值。但是这种选取方法有时会由于偏离最 优对偶解太远，而使得收敛速度很慢。这时我们就可以利用前一节中的初始启发 式算法的边界值来产生一个初始对偶可行解。该想法来自于b e g s i m a s 和 t s i t s i k l i s ( 1 9 9 7 ，第4 章1 的最优对偶变量作为边界代价的理论，为了能有效的得 出边界值，我们先对边界价值理论进行回顾，然后对启发式算法迭代过程中弧的 增量进行修正。 在最优性理论中，对偶变量”；代表容量约束 3sh i 的边界代价，因此我们 可以通过在启发式算法中确定弧容量约束的边界代价来获得对偶变量 石川e a ，s s ) 的初始值。因为弧流量和容量都是整数，我们可以对弧容量摄动 一个单位来确定边界代价。令f = ( 矶c ，p 。c ) 为启发式算法中的初始代价向量， 第3 章模型求解 z 为对应的原始问题( m 2 ) 的可行解，z j 是弧容量u 。s 一u 。s 一1 代替后对应的( m 2 ) 的 n - g 行n ，则z z ；就是由启发式算法得到的对应于容量约束 s h j 的边界代 价。令 i = m i n ( o ，z z 甜， 则通过以上方法得到的石就是一个初始对偶可行解，并且优于直接令z j 一0 或者 玎? ；一e 。我们称该方法为“再计算法”，因为对每条弧的单位容量摄动，我们都 得用启发式算法重新计算一次，总共花费0 沏2 w 2 ) 步来计算初始启发式值， 0 m 3 w 3 ) 步重新计算来确定初始对偶可行解。 我们可以用以下两个方法来加快算法的运行速度。其一，我们可以避免计算 严格容量约束5c “? 对应的边界代价。因为由互补松弛性可知，有 兀；t f ? 一u ；、= 0 ， 所以? ；0 。其二，在z j 计算过程中，初始的弧流量增量与计算z 时是相同的， 我们可以通过合理的初始化减少重复计算。 此外，我们还可以近似计算边界代价来加快算法的运行速度。不同于3 4 1 节中每次迭代时弧流量的增量都是整数个单位，我们现在对3 4 1 节中的启发式 算法进行修正，每次迭代弧流量只增加一个单位。对于原始问题( m ，假定启发 式算法按照这样的复合路径顺序c ( 1 ) ，c ( 2 ) ，c 来增加弧流量，且沿着复合路径 c 。进行流量增加时，在情景s 下弧z 上的流量达到饱和，这意昧着在该情景下 复合路径c f ) ，c ( m 埘，c ( 。) 对应的弧f 上的流量必须为0 ，因此“；被h j - 1 替换 后所得的摄动问题按c ( 1 ) ，c ( ，一，) ，c 。) i ，c ( ) 顺序增加弧流量是可行的。在这 个部分解的基础上，我们可以找到某条可行的路径c 继续增加弧流量来获得摄 动问题可行解。原始解和摄动后所得解的不同点在于对边界代价的估价。由前面 的求解过程可知，两个解只有在路径c 。和c 处不同，因此两个目标函数值相 差- c ( c ) 一c ( c ) 。该近似值激发以下延迟再计算法。 为t n 用延迟再计算法来确定初始对偶值万? ，我们把用初始启发式算法求 解原始问题( m 2 ) 得到的解，作为起点。列一张表，用以记录摄动问题中在情景5 下破坏弧f 上容量约束的路径c 。将初始解，在c 上的流量减小一个单位来 代替弧容量摄动，然后在情景s 下重新寻找一条新的路径c 使弧，重新达到饱和。 令 靠i = m i n ，c ( c ) 一c ( c ) ， 则初始对偶值已得到。通过在同一张表中存储初始解和初始复合路径，主要步骤 是计算新的最优复合路径c ，这将花费时间o ( m w ) 。这意味着延迟再计算将在 时间0 沏2 w 2 ) 内计算所有初始对偶值。 2 4 第3 章模型求解 一般来说，再计算法往往比延迟再计算得出更好的初始对偶解。然而，在对 偶优化策略进行中这个差值并不是很重要。 3 4 3 对偶优化 拉格朗日对偶问题( m 4 ) 的目标函数三伽) 是连续分段线性凹的，因此我们可 以利用非光滑最优化求解技巧来求解拉格朗日对偶问题( m 4 ) 。由于标准的非光 滑最优化问题中目标函数是凸的，因此我们令f 何) 一工缸) ，( m 4 ) 就等价于如下 问题( m 6 ) ： ( m 6 ) 1 瓣枷) 。u ( ，y + ，_ ) ，一) 加) = a r g m i “( 一玎5 ，p s a , p ，d ) ( ，5 ，y ”，y “) s j ( ，e ，- e ) ( f5 ，y ”，y ”) = b5 ，v s 。一五”1 = 0 ，v z 彳，v s ：f ( f ) s f o ，s + 1 ) ( ，5 ，y ”，y 。) 0 ，v s 为与拉格朗日对偶变量“关联的子问题( m 5 ) 的最优解。记z 缸) 的次梯度为g 函) 则有 g 何) = 一“+ ，伽) 。 我们可以把占 ) 看作是子问题最优解破坏容量约束的数量，因此f 协) 的次微分 可以写成 甜缸) 一 叫+ ，d ) ：，如) ( ，y + ，y 一) p ) ) 。 在非光滑最优化的迭代中，每一步我们都会对拉格朗同对偶变量z 进行更 新： 口= + 耐。 ( 3 2 ) 这里口代表步长，d 代表搜索方向。我们首先来描述一下如何选取步长，如何产 生搜索方向；然后我们给出方法来保证按照( 3 2 ) 得到的对偶因子万7 是可行的， 即3 t s0 ；最后我们再来讨论一下对偶不可行性以及对偶无界性。 i ) 搜索方向d 的产生： 我们最容易想到也是最简单的搜索方向是负次梯度方向d = “一，协) ，这种 用于求解非光滑最优性问题的方法被称为次梯度方法，该方法在g l o c k e r 和 n e m h a u s e r ( 2 0 0 1 ) 、b e r t s i m a s 和t s i t s i k l i s ( 1 9 9 7 ，第5 章) 都有描述。但是一般按 第3 章模型求解 照这个方向搜索速度都很慢，原因可能是搜索方向在几个次梯度问循环。为了减 少这种情况的发生，不少学者又对该方向进行改进，如：d i l a t i o n 方法利用偏差 矩阵来投射次梯度，b u n d l e 方法利用最优化子问题，采用先前产生的有限个负 次梯度的凸组合来产生搜索方向。然而，对于产生我们的多维搜索方向，利用 d i l a t i o n 方法或者b u n d l e 方法都会花费很多的搜索时间。 我们这里的搜索方向是采用之前迭代产生的负次梯度方向的凸组合。考虑 ，0 ) 的一些次梯度的集合g = 9 1 ，g ) 0 1 印) ，假定o 硭o l 印) ，否则的话玎就 是( m 6 ) 的一个最优解。考虑搜索方向 拉i 丽l l g l l 2 1 。 ( 3 。) 孓川p 0 2 j 厶卿怕| | 这个搜索方向基本上和用b u n d l e 方法产生的方向相似，然而( 3 3 ) 会运行的更好 一些，因为它结合了b u n d l e 方法的特性与d i l a t i o n 方法的简洁性。 定义3 3 ；假定f ：r “一r 是一个凸函数，s 是一个很小的常数，如果存在 某向量g 满足 f ) f ( x ) + g o x + ) 一， 则称g 是函数f 在z + 处的s 一次梯度。 在具体实施过程中，我们采用了f ( 玎) 的一系列p 一次梯度集g 。记乳、为对应 于函数，o ( f ) ) 的次梯度，这里的f 一次梯度是从之前迭代的次梯度g ( ，) ，g ( ：) ，g ( 。) 中找到的。从次梯度的定义( b e r t s i m a s 和t s i t s i k l i s ( 1 9 9 7 ，第1 1 章) ) 可知对所有的 as 0 ，有如下不等式成立： z ( a ) 苫g ( o ( 一盯( i ) ) + f 如( n ) a ( 3 4 ) 如果存在某，使得 ，何) 一，缸( f ) ) + g u ) 瓴i ) 一石) ， ( 3 5 ) 则由( 3 4 ) 和( 3 5 ) 可知， z ( a ) 2 9 6 ) ( a j r ) + f ) 一。 ( 3 6 ) 出定义3 3 和( 3 6 ) 可知，占m 是， ) 在石处的- 次梯度。因此我们可以通过( 3 5 ) 式从之前迭代得到的次梯度g ( 1 ) ，g ( 2 ) ，g ( 。) 中找出f 0 ) 的e 一次梯度集g 。 i i ) 步长a 的选取： 关于步长的选取，b e r t s i m a s 和t s i t s i k l i s ( 1 9 9 7 ，第1 1 章) 做过相应的研究。假 定o ，为在第t 次迭代时对应的步长，则有 一 笙! 芏竖型查坚一 _ - _ _ _ _ h _ _ _ _ _ _ _ _ _