（管理科学与工程专业论文）交通网络工作站选址模型研究.pdf

华中科技大学硕士学位论文 摘要 f 在交通产业蓬勃发展的今天，研究网络工作站选址的重要性越来越突出。它为 交通部门分析、预测和设计监控车辆流量提供了基本信息，促使交通部门用最少的 资源获得最大效益，有效的利用服务设备。网络用户流量信息对网络管理者研究制 定合理的扩张计划、优化调度和合理的使用网络资源方面有非常重要的价值。这些 信息的准确可靠程度通常取决于工作站设置的个数和工作站的选址。因此，我们必 须对网络工作站选址进行研究，给决策者提供有价值的信息分析，以便更好的利用 、 资金，促进我国城市交通网络的建设和发展。7 本文的第一部分讲述了网络选址的意义和国外研究发展的现状、网络选址的研 究方向和复杂性及网络选址的分类。 本文的第二部分是对网络选址的常见模型和算法的详细介绍。列举了覆盖问题、 中值问题及中介问题等各种常见模型及其应用背景，指出选址点位于边或者位于节 点上，其算法也相应的有所改变。 最后，本文针对交通网络工作站选址的优化模型研究，给出最优交通网络选址 o d 阵估计的精确度范围，及工作站选址标准。将工作站选址在顶点和工作站选址 在边上统一起来研究形成了一个线性整数规划模型，提出列生成算法求其最优解。 本文还研究了用户流线路是随机的，且工作站选址在网络边上的选址模型，在己知 用户流通过线路的概率分布条件下，形成一个线性混合整数规划问题，并提出贪婪 算法求解。 关航选彩作站算法氨鳓给， 关键词：选址l t 工作站算法荭( 国q 澎。， 华中科技大学硕士学位论文 a b s t r a c t t h e i m p o r t a n c eo fs t u d y i n gt h en e t w o r k w o r k s t a t i o ni sm o r eo b v i o u st h a nb e f o r ea s t h et r a f f i ci n d u s t r yh a sd e v e l o p e dq u i c k l y i tp r o v i d e st h eb a s i ci n f o r m a t i o nt oa n a l y z e ，t o f o r e c a s ta n dt od e s i g nt h ei n s p e c t i o no ft h et r a f 矗cf l o w i ti m p e l st h et r a f f i cd e p a r t m e n tt o u s et h el e a s tr e s o u r c et o a c q u i r et h em o s tb e n e f i t t h ec u s t o m e rf l o wi n f o r m a t i o n i s i m p o r t a n tt on e t w o r km a n a g et od e s i g nt h er e a s o n a b l eo u t s p r e a d i n gp l a n ，t oa s s i g nt h e f l o wa n dt ou s et h en e tr e s o u r c e ，b u tt h ep r e c i s i o na n de f f i c i e n c yi sb a s e do nt h en u m b e r a n dt h e p o s i t i o no f t h e w o r k s t a t i o n s ow em u s t s t u d y t h en e t w o r kw o r k s t a t i o nl o c a t i o nt o a f f o r dt h ev a l u a b l ea n a l y s i sa n dt ou t i l i z et h ec a p i t a lt op r o m o t et h ed e v e l o p m e n to ft h e t r a f f i ci n d u s t r ya n dt h ec i t yt r a f f i cp r o g r a m m i n go f o u rc o u n t r y a tf i r s tp a r t ，t h ep a p e rn a r r a t e st h es i g n i f i c a n c ea n dt h ed e v e l o p m e n to ft h ef o r e i g n n e t w o r kl o c a t i o nr e s e a r c h ，t h ec o n s e n to fr e s e a r c h ，t h ec o m p l e x i t ya n dc l a s s i f i c a t i o no f n e t w o r kl o c a t i o n a tt h es e c o n dp a r t ，t h ep a p e ri n t r o d u c e st h ec o m m o nm o d e l sa n dt h ea l g o r i t h m s p a r t i c u l a r l y i t e n u m e r a t e st h ea p p l i c a t i o n so ft h eb a c k g r o u n da n dt h em o d e l so ft h e c o v e r i n gp r o b l e m ，p - c e n t e rp r o b l e ma n dp - m e d i a np r o b l e m i ta l s op o i n t so u tt h a t t h e d i f f e r e n c eo ft h ea p p l i e da l g o r i t h mw h e nl o c a t i o n sl i eo nt h el i n k so ra tt h ep o i n t so f t h e n e t w o r k a tl a s t ，t h ep a p e r e x p l a i n st h es t u d y o no p t i m a ls e l e c t i o no f w o r k s t a t i o n si nn e t w o r k s i ti n d i c a t e st h ep r e c i s i o nr a n g eo ft h ee s t i m a t i o no ft h eo dp a i r sa b o u tt h eo p t i m a l l o c a t i o ni nt r a f f i cn e t w o r ka n db r i n g sf o r w a r dt h ec r i t e r i o no fl o c a t i o nr u l e s i ts o l v e st h e l o c a t i o np r o b l e mo nt h ep o i n t so ro nt h el i n k si nt h el i n e a rm o d e la n dp u t sf o r w a r dl o w f o r m a t i o na i g o r i t h r nt of i n dt h eo p t i m a ls o l u t i o n i ta l s os o l v e st h el o c a t i o np r o b l e mt h a t t h ec u s t o m e rf l o wt r i p sa r es t o c h a s t i ca n dl o c a t i o n sa r eo nt h el i n k s o nt h ec o n d i t i o no f g i v e nc u s t o m e rf l o w sc i r c u i t r yp r o b a b i l i t y , i t f o r m sam i x i n gi n t e g r a la n du s e st h e h e u r i s t i ca l g o r i t h mt os o l v et h ep r o b l e m k e y w o r d s ：l o c a t i o n w o r k s t a t i o n a l g o r i t h m 华中科技大学硕士学位论文 1 网络选址状况 在全球交通和通讯蓬勃发展的今天，研究网络工作站的重要性越来越明显。它 为交通部门分析、预测和设计监控车辆流量提供了基本信息，促使交通部门用最少 的资源获得最大效益，有效的利用服务设备。因此，我们必须对网络服务站选址进 行研究，给决策者提供有价值的分析，以便于更好的利用资金，促进我国城市规划 的建设。 1 1 网络工作站选址的简介 1 1 1网络工作站选址的起源 选址问题( l o c a t i o np r o b l e m ) 源于工厂、医院、商店等服务工作站的建造，选择 合适的位置为其实际应用背景。通常其基本提法为：在给定平面有n 个点 p i ( x i ，y o ( i = l ，2 ，n ) ，现要找某个选址点p ( x ，”，使得m a x i x x 。卜j y - y | ) 最小。这就是选 址模型中的极小极大( m i n m a x ) h i 题或绝对距离( r e c t i l i n e a rd i s t a n c e ) 问题。f r a n c i s 等人早在六十年代就讨论了这种问题，并给出了一些有益的结果，其后相继出现了一 些较直观的几何求解法，并开始探讨其它目标类型的选址问题，如欧氏距离、范数距离 以及用形式的目标函数等。至七、八十年代，有人开始研究选址点p 必须位于某个 凸区域内( 包括边界) 的带约束问题，以及网络的边或节点上有权重值的问题。在近几 年，有关文献还研究了选址点p 限于在给定的任意形状区域之外( 包括边界) 的情况，以 及同时带有二个目标函数的多目标选址模型。 1 1 2 网络工作站选址的发展 h o d g s o n j 、b e r m a n 0 等人首次研究了用户流线路是确定的条件下，以网络服 务站为背景的网络工作站选址问题，在给定工作站数目且工作站选址位于网络的顶 点的条件下，如何设置这些工作站，使得通过工作站的用户流量总和达到最大，他 们建立了此类问题的数学模型，并给出求解算法。 华中科技大学硕士学位论文 随后，b e r m a n 、r i c h a r d & x u 研究以公路检查站为背景的用户流线路在随机条 件下，网络工作站的选址问题，与其它模型不同之处在于给出了每个用户流从一个顶 点流向相邻顶点的概率。对此问题应用了m a r k o w 决策过程。他们建立了一个混合 整数规划模型，提出用贪婪启发式算法求解。 b i a n c o l 等研究用户流线路不确定时，且工作站位于网络顶点的条件下的选址 问题。由于用户流线路是不确定的，每个用户流从起点经任意可能线路到达终点， 因此只有当每一线路上都有工作站，才能确保该用户流通过工作站。因此目标函数 是如何设置尽可能少的工作站才能确保所有的用户流至少通过工作站一次? 或者在 给定工作站数目的条件下如何选址，使得可能未通过工作站的用户流最少? 他们提 出了一个两阶段迭代程序求解此类问题。 y a n gh 等对交通网络工作站选址问题提出了o d 覆盖、边独立、截流量最大 等四条选址标准，并研究了选址点位于网络顶点时一般情形，形成一个整数线性 规划模型，并用启发式贪婪算法求解。 l a m 和l o 、l a m 和l i m 讨论另一类工作站选址模型，他们假设工作站选址设在 网络的边或弧上，并提出一些启发式程序来论证在那些边或弧上设置工作站。y a n g h 等研究了用户流线路不确定但工作站选址在边上的选址问题，他们建立了此问题的 一个非线性整数优化模型，并提出求近似最优解的启发式遗传算法。随后，y a n g h 和y a n gc 对用户流线路不确定的两种选址问题( 工作站选址在顶点和工作站选址在 边上) 统一起来研究形成了一个线性整数规划模型，并提出了求其最优解的列生成 算法。该模型简单，计算效果大大提高。 本文还研究了用户流线路在随机的条件下，工作站选址设在网络边上的选址模 型。在己知用户流通过线路的概率分布条件下，形成一个线性混合整数规划问题， 并提出贪婪算法求解。 1 2 网络工作站选址的意义 工作站选址问题涉及生活中的各个领域，影响着居民的生活、企业的效益及国 家的发展。站在政府立场而言，选址的好坏直接关系到国民经济的发展和社会稳定 2 华中科技大学硕士学位论文 的因素。例如核电站，通讯交换站，高速公路的突发事件处理所，消防站及医院等， 不合理的选址将导致更多的成本费用，效益的降低及更高的死亡率。对于企业，生 产线的布局，物料配送中心的选址，厂房与职工宿舍的合理布局将直接影响着生产 成本的高低。不合理的安排降低了效益，减少竞争实力。在交通产业蓬勃发展的今 天，研究网络工作站选址的重要性更为明显。它为分析和预测和设计监控车辆流量 提供了基本信息，促使交通部门用最少的资源获得最大效益，更有效的利用设备。 网络用户流的信息对其管理者研究制定合理的网络扩张计划、优化调度和合理的使 用网络资源方面有非常重要的价值。这些信息的准确可靠程度通常取决于工作站设 置的个数和工作站的选址。因此，我们必须对网络服务站选址进行研究，给决策者 提供有价值的分析，以便于更好的利用资金，促进我国城市交通规划的建设及信息 产业的发展。 1 3 网络工作站选址复杂性 1 3 1 网络工作站选址的研究方向 选址问题研究的方向主要为三个方面： ( 1 ) 不断的修正和改进模型，使模型更简洁易懂更有效的反映现实问题的本质； ( 2 ) 提出有效的算法，并对已有算法的最优性探讨，对所求解与最优解的偏差 进行有效估计： ( 3 ) 对算法复杂性的讨论。 1 3 2 网络选址问题的复杂性 在实际研究中，对算法有效性及其复杂程度的关注侧重于解决问题所耗费的时 间。通常是把算法用计算机语言编程，计算执行时间的长短。综合考虑问题和算法 的复杂性和用此算法解决该问题所需的计算时间的长短等因素，建立了复杂性理论。 通常复杂性理论考虑以下几方面 ( 1 ) 模型能清晰的表达所需解决问题的有效程度； ( 2 ) 用该算法所能解决的问题的范围及不能解决的范围： 华中科技大学硕士学位论文 ( 3 ) 估计解决问题所需要的时间。 1 3 3 复杂性理论研究 对于复杂性理论的研究方向主要集中在对算法的最差性能( t h e w o r s t c a s e ) 的探 讨，在此不做过详细的介绍。m a r kd a s k i n 曾在其著作中，站在另一个角度对复杂性 理论进行研究：他指出算法最差性能讨论的缺陷，提出某些算法在线性规划问题具 有强大优势。 显然，当所需解决的选址问题的节点个数增加、对成本的限制及对边的流量的 限制往往会加大问题的复杂程度。下面可以用一个表来说明问题的容量随着函数的 变量的增加而其算法的有效性随之降低，而最差性能却随之增加。 1 3 4 p 及n p ( 及n p - h a r d & n p - c o m p l e t e ) 的分类 如果f ( n ) 是n 的多项式函数，则该算法是多项式时间算法，例如上图中的n ， r 1 2 ， n 3 。与之相对应的n l o g ( n ) 。n 3l o g ( n ) ，2 “，e “，则被认为是指数时间算法， 其函数f i n ) 是n 的非多项式函数。p 问题即指决策问题可用多项式算法解决，而n p ( n o n d e t e r m i n i s t i c p o l y n o m i a l ) 指所有的入选方案需要在一定的条件下才能满足多 项式时间算法。显然p c _ n p 。n p 问题能否用多项式时间算法来解决的关键在于两种 分类是否等价，很明显，它们不是等价的。因此我们提出对n p 问题求其满意解。 c o o k 对满意度定义为：当分类p = n p ，问题能用多项式时间解决。他指出问题是 n p c o m p l e t e 时，如果某些问题能通过多项式时间算法解决，那所有的问题都能迎刃 而解，但这往往不可能实现，因此选址问题没有统一的算法。 多项式时间算法通常比指数时间算法有效。并且随着容量的增加显然系统的耗 4 华中科技大学硕士学位论文 费的时间递增的速度要远低于指数算法。一般而言，许多选址问题是不存在多项式 时间算法，虽然这种提法目前并没有可靠的论据来说明。然而，我们希望能够找到 多项式时间算法来解决某些问题。对于某些问题( 此类问题常指n p c o m p l e t e ) 能够 用该算法解决，则对其它同类问题必然也能解决。在现有的研究中，g a r e y & f o h n s o n ( 1 9 7 9 ) 年的著作对复杂性理论进行初步探讨，后来b e r k e l e y , h o m e r & k a n a m o r i ( 1 9 9 3 ) 对复杂性理论进行了更为深入的研究。 由于选址问题很多都是n p 问题，由于交通网络的节点及其边的数目成千上万， 线路的流量具有不确定性，因此计算量繁重，计算过程很复杂，很难找出有效的算 法来解决所有的问题。大部分算法都只能近似估计求其最优解。 1 4 工作站选址的分类 1 4 1 选址分类 选址问题的分类有许多种，站在不同的角度，选址分类的标准也互不相同。下 面列举在研究中常见的选址分类标准。 ( 1 ) 按选址的供求和需求点的分布类型：平面选址、网络选址、离散型选址； ( 2 ) 按对选址的模型的描述的方式不同分为树型、图表型； ( 3 ) 按工作站的个数作为分类标准：工作站的个数可能是外生的已知条件，也 可能是由模型生成的解决方案。并且根据给定工作站的个数的多少，可分为单个工 作站选址和多个工作站选址问题： ( 4 ) 按选址变量输入的性质对时间依赖程度分为确定型或是随机型选址问题： ( 5 ) 按同一模型中工作站类型的个数：在某些问题的研讨中所有的工作站的标 准是相同的，而某些问题中在不同地点对设施的标准也相应的标准不同； ( 6 ) 站在站在不同的投资者的角度，工作站的选址的国有化性质为标准。投资 者不同，其追求的目标也有所不同。私人企业更注重私人的利益大小而不顾环境的 隐含成本，而政府还会权衡更多人的公众利益和未来成本； ( 7 ) 需求是否有弹性作为选址标准：某些选址问题的需求量往往取决于给定的 华中科技大学硕士学位论文 环境，要考虑工作站的类型及系统的规模。而对另一些问题需求而不论成本的多少， 必须强行满足； ( 8 ) 按工作站的是否有容量限制作为分类标准： ( 9 ) 按照系统的决策目标的层次分为单目标模型及多目标选址模型。 1 4 2 有关选址位置讨论 在本文中讨论的选址问题只限于网络和离散型，而非平面和连续型的选址问题。 在网络选址中，需求点、工作站之间的距离往往被假定为网络中节点之间的边上。 很多时候，我们假定需求就在节点处，尽管有些网络选址问题允许需求可以发生在 边上的任意位置。令人感兴趣的一个关键问题是：在何时只在节点上的选址是最优 解。它的出现将有利于算法方案的改进。在离散型选址模型还涉及到节点之间的任 意距离，因此，尽管网络结构是虚拟的，但通过不断对节点间距离的迭代，生成更 简洁的离散型选址问题。通常，离散型选址问题能形成混合整数规划问题。多数的 网络和离散型选址问题能形成线性规划模型，其中某些变量的约束是整数约束，能 形成了混合型线性整数规划问题。 6 华中科技大学硕士学位论文 2 网络工作站选址的典型模型及常用算法思想介绍 2 1 选址问题的关键 选址问题涉及到许多因素的综合考虑，需要权衡各种利弊关系，并在此基础上 求出满意解。通常选址模型在给决策者决策时提供参考性的意见时，包括了多重相 互矛盾的目标。一般而言，简洁的模型要比繁杂的模型要好，尽可能用最少的变量 简洁的反映现实问题的本质。通过建模，在尽可能满足现实约束条件的前提下，权 衡各目标之间的利益冲突。但无论哪一类工作站选址问题都是要考虑以下几方面的 因素： a 需要多少个工作站： b 在何处建立每个工作站； c 每个工作站的成本规模； d 选址点如何满足需求的流量分配。 2 2 简介常见的工作站选址模型 2 2 1 两类经典工作站选址模型 网络工作站的选址涉及生活中方方面面，由于决策目标的不同，则在相同背景 下对模型的要求也有所不同。根据工作站的性质，工作站选址主要可以分为两大类： 有害物质站选址问题和服务站问题。后者根据决策要求的变化，具体又可细划分为 覆盖问题、中值问题p 一中心( p c e n t e r ) 问题。p 一中值( p m e d i a n ) 问题。在下一节 我们用救护车这个模型简单的说明三者之间的关系。 2 2 2 救护车选址模型及有害物质选址问题 当目标问题为满足所有的需求点到最近的救护车的响应时间不大于给定的时间 内x 的条件下，使得所需的救护车的数目最少。这是一个很典型的覆盖问题模型。 7 华中科技大学硕士学位论文 x 是系统要求的响应时间标准。如果最近的救护车到达的时间不大于x 分钟，则认 为该点被覆盖。 该模型引发的相关的问题是：解决方案很可能超过了社区能支付的最大费用。 由此，如何用更少的服务站重新分配工作站的选址，使得在不超过成本预算的前提 下，满足覆盖标准的需求点的数目最大化，即尽可能减少没有被覆盖的需求点的个 数。换而言之，增加一辆救护车的边际成本将不能超过所增加的边际效益。因此决 策目标为：在给定的工作站数目的条件下，使得系统中满足覆盖标准的需求点的个 数最大化。这是覆盖问题中的最大覆盖问题。 当系统的标准对于某些点过于苛刻或者成本过高，站在效益与成本的立场来考 虑，我们需要根据需求点的环境进行调整响应时间或者覆盖距离。因此，在给定p 个数目的条件下，使得最大的需求点和最近的救护车的响应时间最小。该模型被称 之为p 中心( p c e n t e r ) 问题。 由于覆盖问题和中心问题基于对系统的最坏行为的考虑上建立模型。在实际 生活中，通常决策者是在最小最大响应时间和最小平均响应时间之间权衡，使之 综合价值最大化。因此，它的目标问题是：在给定p 个工作站的条件下，使得需 求点和救护车的平均响应时间最小化。该模型被称为p 中值( p m e d i a n ) 问题。 有害物质选址是一类特殊的环境冲突选址问题。社区需要建立这些公共设施为 全社会服务，但它们的存在或多或少会对周围的环境产生一定的不良影响。选址必 须满足一系列的目标要求：垃圾生产点的运输成本最小化，同时运输过程中暴露在 公众社区的程度最小。最小平均( 总) 路程又导致了p 中值问题。但由于许多垃圾 生产点与市区距离不远，废物处理站对环境会有一定的污染，此时我们希望能够让 它们尽可能远离人群。因此在工作站数目给定的条件下，选址应在居民住所与最近 的处理点最大化的位置。很显然，此目标与p m e d i a n 的目标相矛盾。因此，建模的 目的要尽可能权衡不同目标的利益，解决相互之间的利益冲突，用最少的成本取得 最大的效益。 有害物质选址问题一般涉及以下考虑：第一、效率或成本。即处理成本及总运输 成本；第二、风险，即由于有害物品及运送有害物品的车辆会给处理场所及沿途附近 华中科技大学硕士学位论文 环境带来潜在的危害，因而象城镇这样的人口密集地均不希望靠近处理站及所经路 线：第三，风险公平性，填埋场选址的风险可能只强加在一部分人头上而使其它相关群 体没有或只有很少风险。 在下面的几节中我们针对上述常见的选址问题作详细的介绍。 2 3 覆盖问题( c o v e r i n gp r o b l e m ) 2 3 1 最小费用覆盖模型 简单而言，覆盖即指服务区工作站的选址问题。其方案的好坏往往取决于居民 区和被分配到相应的工作站的距离的远近。如果顾客所选择最近的服务点不超过给 定的标准值，则认为该工作站满足选址要求，此居民区被覆盖。反之居民区没有被 覆盖。当所有的需求点至少被一个服务区所被覆盖时，如何使得花费的成本最少， 即建立最少的工作站来满足所有的覆盖。对此问题可用以下为模型来描述： f l ，选址岗能覆盖需求点i 8 r i o ，选址岗不能覆盖需求点i 、，f 1 ，如果在，处选址 1 1 0 ，如果不在，处选址 则m i n i m i z e f j x j ( 1 ) a i j x j 一 l vi( 2 ) x j = 0 ，l v j ( 3 ) 目标函数( 1 ) 使得建立所选择的工作站点的成本最小化 约束条件( 2 ) 是任意一个节点i ( 需求点) 至少能被其中某个服务区所覆盖， 不等式左边给出的是需求点在i 处被覆盖的次数。此约束条件还可写为： x j l vi ，( 3 、) 我们仍可将问题近一步简单化，如果所有设施的费用是相同的，即对于所有的 可选址点j ，费用f j 都相等，我们可令其为l ，或者我们只需简单的找到所需要设施 9 华中科技大学硕士学位论文 的个数，则目标函数可简化为： m i n i m i z e x j ， ( 4 ) 在此覆盖问题中，集n i ( 类似还有系数d i j ) 通常定义为需求点i 与入选址点j 的距离。我们定义为d 。覆盖半径，因此，当幽s d 。，a i j = l ，或者等价于n i = j l z j vi( 1 ) p x j ( 2 ) x j 卸，l ； v j ( 3 ) z i 卸，1 ；vi ( 4 ) 2 3 3 算法研讨 2 3 2 1 列( 行) 消减法 在覆盖选址问题中，限制选址点的位置增加了系统的费用，它比在任意点选址 所需的工作站费用更多。下面列举一个简单的例子。 a8b 1 0 华中科技大学硕士学位论文 如果我们限制覆盖距离是5 ，即d 。= 5 ，并且选址点只能在节点a 、b 两点上， 显然，需要两个选址点。但是如果选址点可以设在网络的任意位置，则只需一个选 址点位于a 、b 的中点就可以将两点同时覆盖。在c h u r c h m e a d o w s ( 1 9 7 9 ) 所指 出，如果选址点可以设在边上时，当网络交点( n e t w o r k i n t e r s e c t i o n p o i m ，指选在边上 的选址点的距离至少满足有一个节点与覆盖距离相等) 在增加时，其需求点的个数 的增加并不导致所需求的工作站的数目的增加。入选点的增加即意味着的原问题中 列向量的增加。因此可用列( 行) 消减法来减少原问题的规模的大小，节省计算时 间。 假定工作站的成本是相同的。如果存在两列i 和j ，对于所有的需求点i ，满足8 0 辄，且至少存在a i i 1 节点b 被覆盖x a + x b +x d 1 节点c 被覆盖x c + x e +x f 1 节点d 被覆盖x a + x b +x d + x e 1 节点e 被覆盖x c + x d + x e l 节点f 被覆盖x c +x f 1 运用行列消减法，原模型可简化如下： m i n i m i z e x c + x d + x e s u b j e c tt o 华中科技大学硕士学位论文 节点a 被覆盖x d l 节点b 被覆盖x d 1 节点c 被覆盖x c + x e i 节点d 被覆盖x d + x e 1 节点e 被覆盖x c + x d + x e l 节点f 被覆盖x c +x e l 如果a i j = l ，则只有一个工作站覆盖节点i ，在此前提下，可采用行消减法。 不妨令在选址点j + ，即a i j = 1 ，即x j = 1 ，我们可以消除出现的x j 的所有行。否则可用次 行消减法。存在两行m 和n ，对于所有的入选点j ，满足a m j q ，至少存在a m j 1 h i z i + + k ( a i j x j + 一z i + ) h i z i + 其中，( x j ，z i ) 为原覆盖问题的最优解。第二个不等式显然是成立的，因为 拉格郎日因子丸是非负数，且a i jx j 一z i 满足约束条件时，也是非负数，该不 等式提供了原问题的上界。 ( ) 对于固定的九，原问题被分解成为分别含变量xi ，z i 的两个问题。对于 z i ，可令z i = j 1 ，如果h - a i o 1 0 ，觑一2 , - = 0 对于( ) 的第二个代数式，我们可认为x j 的系数是在j 处选址覆盖i 点的k 华中科技大学硕士学位论文 需求。只需找到p 个选址点，求从i 点发出的h 需求后的最大覆盖量，令x j = l ， 剩下的全为0 。上述求解不一定满足约束条件，但可以求出函数的下界。 由前面两步可知，原问题的上下界都已知，根据确界定理，不断修正拉格郎日 园子，不断迭代，使得上下界不断逼近。 如果在给定的迭代次数已满足或者上下界近似或者相等时算法停止。 通常拉格郎日算法用于对最坏偏差估计，或者与贪婪式算法结合，在给定的有 效偏差内求其近似最优解。 2 4 中心问题( c e n t e r p r o b l e m ) 2 4 1 简介 在最小费用覆盖问题中，由于资金预算与成本之间的矛盾，由此引发了最大覆 盖选址模型。在本节中，我们从另一角度去克服此缺陷。在工作站数目为p 时( 在 此，p 不一定是定值，可能是变量) ，如何使得被覆盖的需求点的最大距离最小化， 它又称之为最小最大模型。 在中心问题中，如果选址可以在网络中的任意位置，则称之绝对中心问题 ( a b s o l u t ec e n t e r p r o b l e m ) ；如果选址只能位于节点处，则称之为顶点选址问题( v e r t e x c e n t e r p r o b l e m ) 。显然，两者在同一背景下的模型的求解算法是不同的。 对于固定费用p 个工作站选址问题，网络有n 个节点时，中心问题是多项式时 间算法。只需每次计算。( ；) = 。c ，种组合。 对于常见的中心问题，如果费用p 不是固定的，则p c e n t e r 问题是n p c o m p l e t e 一般要计算凳班- 引z n ， 2 4 2 顶点中心问题建模 输入：d i j = 从需求点i 到工作站j 的距离 h 严在i 点的需求量 华中科技大学硕士学位论文 p = 选址点的个数 决策变量：玛= l ，翟簇址 y “= 在i 处被在j 处的工作站服务的份额 w = 在需求点与最近的工作站之间的最大距离 由此，我们形成p 顶点中心模型 m i n m i z ew s u b j e c t t o ：y i j = 1 vi x j - p x j y w d i j y n ， x j = o ，1 y u 0 如果还需考虑距离的权重 w h i d u y i j vi ，j vi 、j vi ， 只需将( 4 ) 转换为下列式子： vf( 4 + ) 2 4 3 顶点中心算法探讨 在此节，我们将解决不含权重的p c e n t e r 问题。假定所有的距离取整数( 此约 束并不是很严格，因为总可以通过某种方式将其近似取整) ，搜索覆盖范围内能覆盖 所有的节点的最小距离为目标，称之为二元搜索。 其步骤基本如下： 步骤1 ：令d e “是一个相当大的数，不妨令d 。h _ ( n 一1 ) m a xi ，j ( d i j ) 其d c “ 中为覆盖距离的上界，而d c l = 0 ，其为覆盖距离的下界。显然，网络中两个节点最多 存在( n - - 1 ) 条边，而m a x i ，i d 日) 是边的最大距离，d c “显然满足要求。 步骤2 ：令d 。= 【( d 。“+ d 。h ) 1 2 。 步骤3 ：求在覆盖距离为d 。时，所需的工作站最小覆盖数目。不妨令其为p + ( d 。) 1 6 i i q q “ 华中科技大学硕士学位论文 步骤4 ：如果p ( d 。) p 则令d c u = d 。，反之，则令d 。l = d c + l 。 步骤5 ：如果d e h d 。，返回步骤2 否则，停止。d 。“则是在p - c e n t e r 问题的覆 盖问题所需的最优覆盖距离，即为最优目标值。 对于有权重的顶点p - c e n t e r 问题，我们只需对此步骤作小小的修正。首先设上 界初值，及已知需求点权重，则d 。“= ( n - 1 ) m a x i ，j ( 如) m a x i ( h i ) 】。，在此 只需满足d i ih i d 。，则节点j 能覆盖节点i 。 范例：p = 2 1 0 迭代 i 2 3 4 5 6 o o 0 6 9 1 0 8 5 4 2 l o l o 1 0 1 0 d 。p ( d 。) 4 21 2 1l 52 86 94 终止 由上述解法可知原问题用2 个工作站覆盖所有的需求点的覆盖半径为1 0 ，选址 位置位于节点a 、e 。其中选址的位置在求最小时覆盖可得出。 2 4 4 树形绝对p c e n t e r 问题 在一般图中，绝对p c e n t e r 问题是n p c o m p l e t e ，通常解法过于复杂晦涩。在此 我们只简单的介绍用树形图解决对于一级和二级绝对c e n t e r 问题。 2 4 4 1 无权重的绝对中心选址问题 对于一级无权重值中心问题，其算法如下： 步骤1 ：在树上任意选择初始点，并找出其顶点距离最远的位置。令该点为e t 。 步骤2 ：找到距离e l 最远的顶点令其为e 2 。 华中科技大学硕士学位论文 步骤3 ：则无权树的级中心问题最优解为e l 到e 2 路的中点。( 注，此法还可以 用在顶点问题上，即距离中点最近的点上) 二级中心问题则在一级的基础上分解成两个一级问题再求解即可。如果选址点 在某条边上，则去该边；如果选址点正好位于某个顶点位置，则去掉连接从e i 到e 2 的连接该点的某条边。 2 4 4 2 含权重的绝对中心选址问题 考虑任意两点巧，如果中心问题x 位于两点之间的莱边上。要覆盖这两点，则 必须满足方程：h i d ( i ，x ) = h j d ( i j ) - - d ( i ，x ) 】 可得d ( i ，x ) = h j d 0 vi vi ，j 、j vi ，j ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) 对于中值问题，h a k i m i ( 1 9 6 5 ) 给出了p m e d i a n 问题最优解位于节点处的证 明。不妨设某个工作站位于网络的某条边( i j ) 距离i 为a 的某点上( o h 2 ，将工作站从最优选址位置( 假设的) 移动到点a 处，设在目标方程中工作站变换后距离变化的比值为6 倍，则我们至少可以减少目 标函数值6 ( 2 ha - - h ) 1 0 。 该算法的思想是不断找可以被吸收的需求点，吸收该点的需求，再将该点去掉， 直到某个节点的需求超过总需求的一半即可。( 所谓吸收点为树形图中的树梢位置处 1 9 华中科技大学硕士学位论文 的节点。) 用树形法求得该问题最优如下所示： hc = 7he 1 4 hb = 1 5 hb = 1 5h c = 1 9 he = 1 4 _ _ b7c1 0e h b = 1 5 b 7c h c = 3 3 2 5 2 2 改进松弛算法的探讨 p - m e d i a n 问题通常是n p - c o m p l e t e 问题，其常见算法有三类：近视算法( m y o p i c a l g o r i t h m ) ，交换启发式算法( e x c h a n g e h e u r i s t i c ) 近点搜索算法( n e i g h b o r h o o d s e a r c h a l g o r i t h m ) ，其中近视算法与贪婪式算法在最大覆盖应用时的思想比较接近，通过构 造来找到比较好的解决方案。而后者与郎格拉日算法类似，通过对计算过程的不断 改进，不断逼近最优解，从而生成近似解，故又可称其为改进松弛算法。由于贪婪 算法或者近视算法中往往只考虑眼前的最大利益而不顾以后的整体效益。因此用改 进算法往往能更快的更有效的逼近最优解。 给出相应的o d ( o r i g i n d e s t i n a t i o n ) 矩阵，首先求出对应的选址点。将分配给 同一个工作站的需求点组成的集合称之为工作站的邻点集( n e i g h b o r h o o ds e t ) 。需求 点分配给距离最近的工作站，将网络分成不同的区域，对于每个区域，是1 - m e d i a m 选址问题，通过此算法，原问题的解有了进一步的改进。 但它仍存在一定的局限，最主要表现在于当它重新分配选址点时，只考虑局部 影响，忽略对整体的效益。因此，我们进一步用交换算法克服这一缺陷。 2 5 2 3 交换算法 交换算法( e x c h a n ga l g o r i t h m ) 的思想是对已选址的p 个工作站位置，找出 要转换的节点，构造某种方法找出某个最优的可替代的节点，进入下一步选址点 的替换。如果都检查过，则停止，反之继续。 对于p m e d i a n 问题，拉格郎日松弛法亦可用。由于最大覆盖问题时已对其算法 做了详细介绍。在此不再介绍。 华中科技大学硕士学位论文 3 交通网工作站选址 3 1交通网络工作站研究目的 网络用户流的信息对网络管理者研究制定合理的扩张计划、优化调度和合理的 使用网络资源方面有非常重要的价值。而这些信息是否准确可靠，通常取决于工作 站设置的个数和工作站的选址。欲使收集的总用户流量达到一定的要求，网络管理 者如何设置尽可能少的工作站? 或在给定工作站个数的条件下，如何合理的设置工 作站，使得收集的总用户流量尽可能达到最大? 这类问题自然成为国内外学者研究 的重要课题。 3 2 最优交通网工作站选址的o d 矩阵估计 在对交通网络工作站的选址研究中，存在大量对o d ( o r 3 【百n d e s t i n a t i o n ) 矩阵 的估计的方法应用。通常对于o d 矩阵的估计精确度取决于输入的数据、工作站的 数目及网络中选址位置。在此节，提出在给定的交通网络，如何决定工作站的数目 及选址的位置。并提出交通工作站选址标准，拟采用贪婪算法解决一些实际问题。 3 2 1 最大可能性偏差( t h em a x i m u m p o s s i b l er e l a t i v ee r r o r ) ( m p r e ) 由于在实际生活中，我们无法对估计的的o d 矩阵与真实的偏差进行度量。因 此只能用m p r e 描绘估计0 一d 矩阵的可依赖程度。定义网络g ( n ，a ) ，n 为节点集， a 为边集。假设a 是被检查到的流量所对应的边集显然a c a ，其对应个数分别为 n ，严。w 为0 一d 对的集合，m 为o - d 对个数。r 为网络的路集，对于每个w e w ， 其真实或者估计的路线的流量分剐用c w 和o t 表示，在边a ( a a + ) 测得流量为v a ， p 。表示通过w 中的边a 是否被工作站所检查的值。则满足： p 。t w + = p 。w t 。飞， a a + w e 甲蚝甲 2 1 华中科技大学硕士学位论文 即p a w ( t w * - - t w ) - 0 ，a a + w e w 令6w - ( t w * - - t 。) t w ) ，则显然6w 一1 ，因此，我们得到 p a w t 。5 w = 0 a e a + 吨矿 定义g ( 6 ) = ( 6 。2 m ) 1 陀 w e w 对于估计值，我们总是希望与真实值的偏差尽可能小，则精确度越大。显然，g ( 6 ) 越小，则估计的精确度越高。因此，最大可能性偏差m p r e 模型可定义为： m p r e ( 6 ) = i l a xg ( 6 ) s u b j e c t t o ：p a w t 。6 w = 0 ，a e a 眦矿 3 2 2 交通网工作站选址标准 3 2 2 1 选址原则 由于交通网工作站选址原则可从m p r e 模型中衍生而得，我们希望尽可能增加 系统的确定性，并减少对0 d 矩阵估计的误差。因此只需将上述模型最小化。 但对于上述模型存在一个问题，如果p 。= o ，对于所有的a a + ，显然6 。的系 数p a w t 。恒为零。因此变量6 。没有约束，故m p r e ( 6 ) 将无界。这种结果将导 致o d 对中不需要任何选址点。为避免类似现象，则定义 o d 覆盖原则( c o v e r i n g r u l e ) 交通检查站选址必须位于能检查任意0 d 对的路线上。 对于上述模型，我们找到至少有一个p i 。0 ，则定义 6 w - p a w t w 6