（应用数学专业论文）时变最短路问题及其在时变最小费用流中的应用.pdf

摘要 网络优化研究的是网络上的优化问题。它在许多重要领域都有广泛的应用，例如， 交通，通信，计算机网络，能源系统等。大量文献中研究的网络优化问题都是静态 的，即流经过一条弧不需要花费任何时问，并且网络的参数，例如，流经过一条弧的 费用，弧的容量都是不随时间变化的。然而，现实生活中的网络本质上是时变的。在 这种网络上，流经过一条弧需要花费一定的时阎，网络的参数( 例如，弧和顶点容 量) 是随时间而变化的。 本文详细地研究了时变网络上的两个优化问题。一个是时变最短路问题，即在总的 传送时间小于给定的常数t 下，找出从源点到其他所有点的最短路。本文研究了该阿题 的三种不同情形。第一种情形，假设流在除了源点外的其他任何顶点都不能等待。第 二种情形，假设流在任何点都能无限制地等待。最后，考虑一般情形，假设流在每个 顶点的等待时间有一个上界。对每一种情形，给出它的原规划，并相应地写出其对偶 规划，提出最短路最优性条件。然后，根据最优性条件，设计出对偶算法，并分析其 算法复杂性。另一个是时变最小费用流问题，即在截止时间t 前，确定怎样从源点送给 定数量的流到收点以致总的费用最小。本文研究了该问题的二种情形。首先，考虑零 等待时间，即流在除了源点和收点外的其他任何顶点都不能等待。然后，考虑任意等 待时间，即流能在任何顶点无限制的等待。同样地，对每一种情形，给出它的原规划 和对偶规划，从线性规划的互不松弛定理推导出一些最优性条件。接下来，利用时变 最短路的对偶算法和最优性条件，设计出伪多项式时间算法，并分析了算法复杂性。 最后，本文用一些数值的例子阐述了算法的有效性。 关键词：最短路；对偶算法；时变网络；优化；最小费用流；剩余网络；对偶规划 a b s tr a c t ne 乞w o r ko p t i m i z a t i o nc o n 嬲螺a b o u to p t i l i z a t i o np r o b l e m so nn e t w o r k ，毗b m a y a r i s ei na 谢d ev a r i e 锣0 f 洫p o r t 础丑e l d s ，s u c h 鹪t r a n 印o r t a t i o n ，t e l e c ：l 心c a t i o n ， c o m p u 七e rn e t w o r l 【i n g ，e n e r g ys y s t e m s ，e t c m o s tn e t w d r ko p t i m i z a 土i o np r o b l e m st h a t h g v eb e e n8 t u d ：di nt h el i t e r a l t u r ea r es t a t i ci nn a t u 】呛h 叭垤i v e r ，n e t w o r ：k 8i nt h er e a l w d r da r et i n l e - v a r 订n gi n 豁n c e ，i i lw h i c ha n y 丑c 啊咖斌t a k eac e r t 咖锄o u n t0 ft i n l e t 0t r 嗍趾缸ca n dt h ep a 删啪t e r s ( s u c h 鹪跗ca n dn o d ec 印a d t i 馏) 0 ft h e 舶佃0 r k m a yc h a n g e0 v e rt i n l e i nt h i 8t b e s i s ，w ee x 龇i l i 球dt w op r o b k m so ft h et i m 争v 葛旺_ ) ，i n gn 咖r k o p t i n l i z a t i o n o n e p r c 而l e mi st h et i m 争、瑾盯y 妇gs h o r t 鹤tp a t hp r 0 1 ) ：i e mw h i c hi st o 矗n dn 炝出1 0 r t e 8 tp a t h ， i e ，t h ep a t h 丽t ht h el e 鹄tp 0 8 s i b l ec o s t ，矗o mt h e8 0 u r e en o d et oa ：l lo t h e rn o d 陷，s u b j e c t t ot h ec o 璐t r a i n tt h a tt h et o t a lt r a v e r s et i m ei sa 七m o s ts o m en u n l b e rt t h r e ev a 面a i l t s o f 乞h ep r o b l e m 钺e 麟锄血e di nd e t 碰i nt h e 丑r s to m ，w e 獬珊z e r o 础i n gt i m 铅， n a m e l 孔w a i t i n ga ta n yn o d ei 8s t r i c t b rp r o h i b i t e de x c e p tt h es o u r c en o i es i nt h es e c o n d 疵a n t ，w e 髑眦et h a tw a l i t i n ga 七an o d ew i t h o l l t 衄yr 鹤t r i c t i 0 咀i s 址k w e al a s t ，w e c o 璐i d e rt h eg e n e r a l lc a w h e r et h e r ei sa n o d e - d 印e n d e n tu p p e rb o u n d 0 nt h ew a i t i n g a te a c hn o d e i ne a c h 、，a d a n t ，w ef o m u k et h ep r o b l 锄鹪al i n e a rp r o 口a m m i n ga n d t h e ng i v ei t sd u a lv 凹s i o n a tn 屺8 锄et i n l e ，w ep r o p o s e 衄0 p t i d l a l i t yc o n d i t i o n 毗l d d e v e l o pa d u a l la l g 砸t h mt os o l v ee a c hv a i r i a n t t h e0 t h e rp r o b l e mi 8t h et i m e - v 甜姐n g 瑚i n i 皿【u mc o s t 丑o wp r o b l e mw 址c hi st od e t e r n l i n eh o wt os e n da 百、，e na 肛：d u n to f 丑0 w 舶mt h e8 0 l l r c en o d est ot h es i n kn o d epb e f 6 r eap r 争8 p e c i 丘e dd e a d l i n ets oa st o m i n i m i z et h et o t a l lc o s t t w o 洒跚1 t so ft h ep r o b l e m 剖陀e x 锄血e d ，o n ea 龉岫e st h a t w 越t i n ga 土a n yn o d ei ss t r i c t l yp r o h i b i t e de x c e p tt h es o u r o en o d e8a n dt h es i n kn o d e | p ，t h eo t h e r 鹪s 眦鹤t h a tw a i t i n ga tan o d ei sp 锄i t t e dw i t h o u t 锄yr 篑t r i c t i o n f 1 0 r t h e8 锄et o l 。e n ，i i le 旋h 、，萄匝粕t ，w ef b r m u l a t et h ep r o b l e m8 sau n e a rp r o 日踟n 瑚i 1 1 9 锄d t h e ng i v ei t sd u a l lv e 瑙i o n m e 嬲t i m e ，w ep r o p o s o m eo p t i m a l i t yc o n d i t i o 璐f b re 施h 、，丑l r i a n t m o r e ( ) v e r ，w ed e v e l o pt w o 聊d o p o 驷删a la l g o r i t h l n st o8 0 l v et h ep r o b l e n 玛 a n da 以甜y z et h e 锄p l e ) d t yo ft h ea l l g o r i t 妇 f i n a u y ，w eg i v e8 伽m 皿e r i c a l 懿锄p 1 鹤t oi u u s t r a t et h ea 丑9 0 r i t k 陷w l l i c h 讹 d e v e l o p e d k 删d s ：s h o r t 鹤tp a t h ，d u a la 1 9 0 d t h m ，t i l 争v a 耐n gn e 栅o r k ，0 p t i m i z a t i o n ，r e d l i o e d o o s t ，n l i n i m u mc o s t 丑o w ，d y n a m i cr 毯l i d u a ln e t w o r k n t 上 6 ( 蕾，j ，亡) l ( 主，j ，t ) c ( 主，j ，t ) ，( i ，歹，亡) ，( i ，亡) ( 1 ，亡) ( t ，j f ，牡) p ( s ，z ) 丁) q ( 戤) ( p ) m a i nn o t a t i o n s t h en e t o r k t h es e to f n o d 鹤 t h es e to f a r c s t h em m l b e r0 f 村 t h en u 加b e ro fn o d e s t h ep r 雕；p e c m e dd e a d l i n e t h e8 0 u r c en o d e t h es i n kn o d e t h ew 虹t i n gt i m ea tn o d ei t h eu p p e rb o u n d0 ft h ew a i t i n gt i m ea tn o d el t h et r a n s i tt i m e0 fa r c ( i ，歹) 硝t ht h ed 印a r t u r et 妇e 亡 t h ec 印a u c i t y0 f 甜c ( t ，j ) 丽t ht h ed 印a r t u r et i n l et t h ec t0 fa r c ( i ，j i ) w i t ht h ed 印a r t u r et i m e 亡 t h e 丑o wt r 踟1 s m i t t e d 山n gt h ea r c ( i ，歹) w i t ht h ed e p a r t u r et i m e t t h e 丑o ww a j t i n g8 tn o d ei 五- 0 mt i m e 孟t ot + 1 t h e 丑o ww h i c hw a i t sa tn o d et 五r o mt i m ett ot + 1w i t ht h e w a i t i n gt i m ek t h en 0 wt r 啦锄i t t e da l o n gt h ea r c ( ，j ) 而t ht h ed e p a r t u 阳 t i i i l et a n dt h ew a i t i n gt i m e 七a tn o d ei ad i r e c tp a t h 白o mst oz t h ed e p a r t u r et i 地o f t h e 丑0 wa tn o d e 戤 t h ea r r j v a it i i i 地0 ft h e 丑a wa tn o d e 靓 t h ec 印a c i t yo f p a t hp l v g y a m n t s p 毗 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者签名：日期： 论文使用授权声明 ， 沪毽。s 、1 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 名掣名咿眺础f a c k n o w l e d g e m e n t s f i 瑙t ，1w o u l dh k et o 唧r 嘲h e a r t 五e l tt h a n l c st o l ys u p e r v i s o r ，a s s o c i a t ep r o f b 8 s o r d a n s h a ，f o rh i sc o 璐t a n te n c o u r a 皂p m e n ta n di n s i 曲t f ms u p e i s i o nt k u g h o u tt h ee n t i r e p r o c e 蹈0 fm y 留a d u a t e8 t u d i 鹤i 玉i s9 1 1 i d a n c ei si 瑾嘲u a b l eb o t hi nt h i sr 髑e 村c hw 0 r ka n d i nm yg 朗e r 址a c “k 】咀i c8 d 、，a 田 c e m e m m e o v 髓，ia me s p e c i a ：n yt h 趾1 1 【= 缸lt 0h i 8g r e a t h e l pt om yu f e n e 】c t ，i 锄v e 巧f a t e h l lt om 柚yt e a 龟h e r si nt h ed 印a n m e n to fa p p h e dm a t h 争 m a t i c s ，s h a n g h a in o m a lu n i v e r s i t 弘w i t h o u tt h e i rc o 璐i s t e n t8 n di l l u m i l l a t i i l gi i l s t m c - t i o n ，ic a nn o tc o m p l e t em yg r a d u a t e ds t u d ys u c c e 鸽i v e l 弘i 锄g r e a t l yi n d e b t e dt ot h e p r o f 豳o r sa n dt e a c h e r sa tt h ed e p a r t m e n to fa p p h e dm a t h e m a t i c s ： p r o f 豳0 ry o n 乎 b m gs h i ，p r o 钕s o rd e 乞0 n gz h u ，p r o 溉8 0 rj i z h o uz h a n g ，p r o 妇s o rg u o r o n gw 缸g e ta 1 t h 锄kt ot h e i ri n s t m c t i v e9 1 1 i d 觚c e 雠dc o m p r e h e 璐i v ee d u c a t i o nd u r i n gn l yt h r e ey e a 璐 f a d u a t e d8 t u d 弘t h e r e8 r es t mm 锄yn a m 豁w i ub el 【e p ti nm ym 砌f o rt h e i r8 i n c e r e 矗i e n d 8 h i p 舭i dp 】懒i o n “h e l p f i o rs p a c el i m i t a t i o n ，h 娟嗍，ic a n 卫眦m e n t i o nt h 哪 址1 1w i s ht ot h a n km yb e l o v e d 铀血l y 五d rt h 由l o 、r i i l gc 0 璐i d e r a t i o 璐觚dg r e a tc o n - ：氤l e n c ei nm ea l lt h r o u 曲t h 镐ey e a 勰。 io w em ys i n c e r e 黟a t i t u d et om y 缸e n d s 姐d r o o m m a t w h og a v em et h e i rh e l pd u r i n gt l l r e ey e a r s0 f l yf a d u a t es t u d y f i n a n y it h 锄ka l lp r o f l 潞。瑙衄d 唧e r t sw h oc a 蛐r e 、托wm yt h 鹤i s 觚d o d l l t r i b u t et h e i r 、阻h la ：b l eo d 】豇l e 玎t s c h a p t e r 1 i n t r o d u c t i o n 1 1n e t w o r ko p t i m i z a t i o n n e t w o r ko p t i m i z a 七i o nc o n c e m sa b o u to p t i m i z a t i o np r o b l e n 玛o nn e 咖r k ，w h i c hm a ya r i s e i n8 诵d ev 龃i e t y0 fi i p o r t a n t 丘e l d 8 鲫c h 鹪t r a 璐p o r t a t i o n ，t e l 黝m 删c a t i o n ，c o m p u t 盯 n e t w 伽k i n g ，自啪c i 越p l 龇l n i n g ，l o g ：i s t i c sa n ds u p p l yc h a i nm 龃a g e m e n t ，e n e r g ys y s t e m s ， e t c m 0 8 tn e l l w o r ko p t 曲也a t i o np r o b l e 略t h a ：th a v eb e e i ls t u d i e di nt h e1 i t e r a t l l 】f e 踟孵 s t a t i ci nn a t u r e ，i nt h e8 伽l t h a tt h e y 蝴u m et h a 七i tt a k e 8 姗t i m et ot r 删啪e 锄ya r c i nan e t w o r k 龃dt h a ta ua t t r i b u t 鹪o ft h en e t w o r k ，f o re x 锄p l e ，t h ec o s tt os e n d 丑o w a ：1 0 n g 雠跚ca n dt h ec a p a c i t yo fa na r c ，踞ec o n s t 锄tw h i 6 hd on o tc ：h a n 田eo y e rt i i n e s t a t i cn e 拥r o r k0 p t 妇i z a t i o np r o b l e m sh a y eb e e ns t u d i e d t e n s i v e l yi nt h eh t e r a t u r e ： s ，f o r 嘲观p l e ，趾l u j a ，m a 弘础i 跹do r l i n ( 1 9 9 1 ，1 9 9 3 ) ，a d e l s o n v e l s l 【i ，d i n j c 髓d k 盯锄0 v ( 1 9 7 5 ) ，b 讹a r 跳，j 解凼锄ds h e r 址( 1 9 9 0 ) ，f 0 r d 趾dn l k e r 8 0 n ( 1 9 6 2 ) ，g u p t a ( 1 9 8 5 ) ，i r i ( 1 9 6 9 ) ，j e 璐e n 趾db 锄鹤( 1 9 8 0 ) ，l a w l e r ( 1 9 7 6 ) ，衄dm i n i e l c a ( 1 9 7 8 ) n e t w o r l 【si nt h er e a lw o r da r e ，h i 娟嗍，t i 睁、，乏岫gi n 瞪8 e n c e ，i nw h i d h 锄y 丑i 聊删t 址【eac e r t a i n 锄o 吐o ft i 坨t ot r a ：v e 瑙e 锄a r c 艄l dt h ep a r 缸l e t e 璐( s u d h 鹋 舭ca n dn o d ec a p a c i t i 鹤) o ft h en e t w o r km a yc h a n g eo v e rt i m e i ns u c hap r o b l e m ，h o w t 0p l 姐舭l dc o n t r o lt h et r 锄s m i j 陷i o no f 丑o wb e c o m 唧i m p o r t a n t ，s i n c ew a i t i n ga ta n o d e ，o rt r 洮g 乩d n gap 毗i c u l a ra r c 稍t hd i 珏h e n ts p e e d ，m a ya l 炯0 n et oc a t c ht h e b 髑tt i m i n g 山n gt h ep a t h ，a n dt h e r e f b r ea c h i e v eh i so v e r a no 协e c t i v e ，s u c ha sm i n i 瑚【u m a v e r a uc o s t0 ram i n i 姗l mt r a v e lt i m e 矗o mt h eo 埔g i nt 0t h ed 销t i n a t i o n t h e r e 盯e p l e n 锣0 fd e c i s i o nm 出n gp 咖b l e m si np r 碱i c et h a ts h o l l l db ef 0 珈n l l l a t e d 嬲o p t i m i z a t i o n m o d e l so nt i m 争v 奶r i n gn e t w 0 r l 【s ，a8 一鹤0 fm o d e l 8 ，p r o p i t i o 璐，舭l da l g 毗h 瑚，t h a t r e s e a r c h e r sh a v ed 倒r e l o p e di nt h i s 盯e ai nr e c e n ty e a 璐 1 2 1 2 t i m e - v a l r y i n gs h o r t e s tp a t hp r o b l e m sw i t hc o n s t r a 庄i l t s t i h es 舡此i cv i 埘o no ft h es h o r t e s tp a t hp r o b l e m 鹅跚l m et h a 七z e r ot i i n ei sr e q l l i r e dt 0 t r 删e r 雅yp a t hi nt h en e t w 0 r k ，w h 既ea ：i lp r o b k lp a 舳m e t e 硌射en o tc h 柚g e da ta ：u o 佗rt i l e i h j 8p r o b l e mi st h e 瑚【0 s 七f u n d 锄e n c a lo n ei nn e l 忍，0 r ko p t 洫i z a t i o n ，w l l i c hh a s b e e nw i d e l ys t u 出e di nt h el i t e r a t u r e a ne ) ( t e n s i o l no ft 1 1 es t a t i cn 】【0 d e li st h ep r o b l e mo f 丑n d i n gas h o r t e s tp a t hs u b j e c tt os o m ec o n s t r a i n t si n 、烈v i n gt r 趾s i tt i m 髑a ne x 锄p l e i s t h ep r o b l e mw h e r eat r a i 塔i tt i m ei sr e q u i r e dt ot r 踟，e r s ea n 铷汜，s u b j e c tt ot h e0 0 n s t r a i n t t h a tt h et o t a lt i m et ot r a v e r ap a t hc a n n o tb eg r e a t e rt h 锄a n yg i v e n 锄o u n tt t b j sc l a 鼹o fp r o b l e n 玛h 蠲b ns t u d i e db ya n 咖。( 1 9 7 8 ) ；h a 鹃觚( 1 9 9 2 ) ；j 0 k s c h ( 1 9 6 6 ) ； s k i s c i me t 址( 1 9 8 9 ) ；w i t z g a l le ta l ( 1 9 6 5 ，i e r se 乞a l ( 1 9 8 6 ) ，锄di sk n o w nt 0b e n p c o m p l e t e ；s a h 哪ae ta l ( 1 9 9 3 ) ；h 缸d l e re ta l ( 1 9 8 0 ) w b 丽uc o 璐i d e r ，i nt h i 8t h 豁i s ，t h et i m e _ v a r 妒n g 、伧璐i o n0 ft h ep r o b l e m ag e n e r a l 皿【0 d e lw m b e 羽k b 髑e d ，i nw h i 6 ht h et r a n s i tt i m ea n dt h ec 0 8 tt ot r 习e r s ea na r cv 翟旺y i n g o y e rt i m e ，w h i c hd 印e n du p o nt h ed e p o n l l 】呛t i m ea tt h eb e g i i l n i n gn o d eo ft h ea r c m o r e 。i v e r ，w a i t i n ga ta i l o i ei sa l l o w e d ，a taw a i t i n gc o s t t h ep r o b l e mi 8t o 丘n d 龃 o p t i m a lp a t ht ot r 蜀l v e l 舶mas 0 1 l r c en o d est oa n o t h e rn o d ez ，8 0t h a l tt h et o l t 砒c o s t o ft h ep a t hi sm i n i m i z e ds u b j e c tt ot h ec o n s t r a i n tt h a 七t h et o i t a lt r a v e lt i 功l eo ft h ep a t h i 8a tm 0 8 tt ，w h e r eti 8ag i 珊i n t e g e r i na d d i t i o nt ot h ed e t e r m i n a t i 阻0 fap a t h t oo 咖e c tt h et w on o d 鹤sa n dz ，t h ew a i t i n gt i n l 鹤a td un o d 圈a 1 0 n gt h ep a t hs h o u l d a ：b ob ed e c i s i o nv 缸i a ：b l 瞪t 0b ed e t e r m i n e d w bc a ：i lt h i 8t h e 统m e t ，口删饥g 娩口付古阳忱 ( t v s p ) p r o b k 姐 t h e7 s pm o d e lh 鹪m 锄ya p p n c a t i o 姗o n ee x 锄p l ei 8t h ed a t at r a n s m i 陷i o n p r o b l e m s u p p o s et h a tad a t ap a c 1 c e th a st ob es e n tb e t w e e nt w 0s p e c i 矗e dn o d e 8i na n e t w o r ka sc h e a p l y 鹪p o 鼹i b 沁w i t h i nat i m el i m i tt a st h et r 踟鸲i tt i m e 舭l dt h ec 0 8 t n e e d e dt o8 e n dt h ep a 肽e to n 觚a r cv 猢了o v e rd i 丘咖n tp e r i o l s ，t h e r ee 虹s t sa no p t i m a l d e p 剐吨l u et i m et ot r a v e 璐ea n 踟- c t b u s ，a no p t i m a l8 0 l u t i o nt ot h ep r o b l 锄s h o u l d n o to n l yp r o v i d et h eb 销tp a t hc 0 皿e c t i n gt h et w on o d 鹄，b u ta l s os p e c 匆t h eo p t i m a l d u r a t i o nf b rt l l ed a t ap a c ：k e 乞t o8 t a va te a c _ hn o d et ow a i tf b rt h eb e 8 td e p 锄吨u r et i m e a n o t h e r c 锄p l ei st h e 丘e i g h 七t r a n s p o r tp r o b l e m s u p p e 跚虹l e 行e i g mi st ob e8 e n t 缸i mas o u r c et os i i l ki nan e t w o r kb e f o r ea 捌l i n et b e t w e 铋t w on e i g l l b o r i n gc i t i e s ， 8 e 、他r a l 咖鹤0 f 丘e i g h t r v i c 髑a 托a 、枷l a b l e ，w m d h ，h l 阿y e r ，h 孙，e 出珏h e n to t s 龇l d t r 锄印0 r tt i m 鹤，d e p e n m 】略u p o nt h e8 e 鹄。璐a no p t i m a ls o l u t i o ns h o u l dt h _ u ss p e c 姆 t h er o u t e 鹪w e u 雒t h ew a i t i n gt i m 皓0 f t h e 在e i g h ta te 翻。hc i 锣s ot h a tt h eo v e r 8 nc 0 8 t i 8m i n i m u mw h i l et h e 缸i 罢灿缸t i v 陷a 七t h ed e s t i n a t i o nn ol a t e rt h 8 nt h ed e a db n et 3 x c a ie ta l 铡：蛐e dt h e 舌白7 l e - u 口r 撕n 9 曲d n 卵沈( s p ) p r o b l e mi nd e t a i l t h e yp l r 0 i p o s e d 咖龇n i cp r o 日踟m n i n ga l g o r i t h m st o8 0 l v et h ep r o b l e mu n d e rt h r e ed i f f e r e n tw a a t i n gt i m ec 0 璐t r a i n t si np s e u d o p 0 1 y n o m i a lt i m e 【2 】i nt h i st h 铝i s ，h o w e v 髓，w f w mf 0 】彻u l a t et v s pp r o b l e mb o t hi n 砸m a la n di nd u a ll i n e 舡p r o 蓼锄珊血g 五d r m 8 ， 衄dp r o p 0 8 eo p t i n l a l i 锣c o n d i t i o n sf b rt h ep r o b l e mu n d e rt h r 优w a l i t 通gt i m ec 0 璐t r 出t s r 鹤p e c t i v e l y w bf u r t h e rd e v e l o pd u a la l g o r i t h 塔t os o l v et h 锄w bn o t i c et h a tt h e 小 9 0 r i t h 够p r o p o s e di n 【2 】c 蛆s o l 、，ep r o b l e l n s 丽t hp 戚t i v et r a n s i tt i m eo n l y h 佣r e v 既， o u r 反嚏o r i t h h 玛c a nt r e a 七t h ep r 6 b l 锄w i t hn e g a t i v et r a n s i tt i l e t h i si san e w 啊d r k a n di th 糙w i d e l ya p p h 昭t i o n sb o t hi np r a c t i c ea n di nt h e o r y o n ec a n 珏n dt h a tt h e a l g o r i t h mf b rs h o r 乞e s tp a t hp r o b l e i ni 8o f t e ne m p l i d y e d 够as u b r o u t i n ef b rs o l 咖g0 t h e r n e t w 0 r ko p t i m i z _ a t i o np r o b l e m s ，s u c h 弱t h em 画剁【mn o wp r o b l e ma n dt h em i n i 功u m c 0 毗丑o wp r o b l e m m o r e o v e r ，t h eo p t i l a l i 妙c o n d i t i o n sf o rt h ep r o b l e m sa l s oa c ta n i m p o r t a n tr o l ei nd e v e l o p i n ga 1 9 0 r i t h i 璐a n dt h e yc 觚i l p r a v et h ec o m p u t a t i d nt i i n ei n m a n y8 i t u a t i 0 璐【1 1 1 3 t i m e v a 瞳y i n gm i n i m u mc o s 七n o wp r o b l e m sw i t h c o n s t r a i n t s t h em i 饿m 伽7 暑c d s t 月d t ，p r d 6 把mh a sb ne 赋e n s i v e l ys t u d i e di nt h el i t e r a t l l 】旧( s ，e g ， a h u j ae ta 1 ( 1 9 9 3 ) ) t h ep r o b l e mi st od e t e r n l i n eh 0 wa 百v e n 锄。眦t0 fa o ws h o u l d b e8 t 丘0 n lt h e8 0 u r c et o8 i n ka 七m i n i h l mc o s t ，8 u b j e c tt ot h ec a - p a c i t yh i n i t s0 nt h e a f c 8o ft h en e t w o r k t a 碰t i o n 吞u y ，t h 遗p r o b l 锄i sc o i l s i d e r 够as t a l t i co n e ，w h e r ei ti 8 a s s u m e dt h a 七an a wt a 玉嘟z e r ot i m et ot r 孙，e r s ea n y 锄汜，a n da l la t t r i b u t e 8o ft h en e l m n o r k ， m c l u d i n gt h ec o s tt os 姐d 丑a wo n 缸眦，衄dt h ec a p a c i t y0 f a n 盯c ，a r et i l n ei i r 哪i a n t i i lm 锄yp r a c t i c 甜s i t u a t i o 瑚，h i 娟嗍，t h e 8 s s u m p t i o n sa r en ol o n g 凹v a l i d c l e a r l y a 1 0 r er e a l i s t i cn l o d e li st ota ：k ei n t oa c c o u n tt h et i m en e e d e dt ot r a v e r s ea na r c w e 丽l la d d r e s 8 ，i nt h et h 铅i s ，t h e 抚m e 惭佗口嘲n 溉t mo d s t 肋伽t 卿肿6 - j e 仇t h ed r o b l e mi st od e t e r m i n eh o wt os e n dag i v e n 衄l o u n to f 丑o i w 丘o mt h es o l l j e n o d est ot h es i n kn o d epb e f b r eap r e s p e c i 丘e dd e a dl i 玎et8 0a st om i n i n 】【i z et h et o t a l c o s t t h i sr e q u i r 鹤u st od e t e n i l i n et h eb e 8 tr o l u t e st os e n dt h ef 1 0 1 w 丘蚴3t op8 n dt h e b 鹤t8 c h e d l l l 笛t o 趵n dt h ea o wm o n gt h e r o u t 鹤s i n c et h et r 锄i tt i m e ，t h ec 嘴t ，衄d c 印晒t yo na n 舭c 舢et i m e 唧n g ，i tm a yb en e c 鹤s 触yt ow a i ta 七t h es t 毗i n gn o d e0 f 盯cf 醣t h eb 馏td e p 砒u r et i z n e t h e r e f b r e ，i na d d i t i o nt ot h er o u t 鹤t o n dt h e 丑o w ， w a i t i n gt i m e 8a 土a un o d e sa 1 0 n ge a d hr 0 吡t ew ma l l s ob ed e c i s i o n 、，a r i a b l ei n0 u rm o i i e l x c a ie ta lp r o p o s e dd y n 眦i cp r o 口a m 畸n ga 1 9 0 r i t h i 璐t os o l v et h ep r o b l e l 璐u n d e rt h r 衄b r e n tw a i t i n gt i m ec o 璐t r a i n t si np u d o p o l y l l o m i a lt i n l ea n dp r o 哦 dt h ep r o b l e m sa r e 4 m 锄m p l e t e 【3 j i nt h i 8t h 髑i s ，w ec 0 璐i d e rt w o 、雕i 柚t s0 ft h et v m c fp r0 _ b l e l nw i t hz e r 沪w 蚯t i n g t i m 髑a n d 龃b i t r a 叮谳t i n gt 缸e sr e 8 p e c t i v e l y i ne a c h 、，a r i a n t ，w e 丽u 五d n 姗l a t e 即，m c f p r o b l