交通信号的同步的整数线性规划翻译

1、交通信号的同步的整数线性规划论文的作者（们）:John D. C. Little资料来源:运筹学卷，第3期，第4号，第148（1966年），页。568-594由发布Http:/stable/168720 稳定的 URL:07/11/2009 21:33 访问:您使用JSTOR JSTOR档案显示出你的验收的使用条款及细则的限制，口J在Http:/page/info/about/policies/terms.jspo JSTOR 的使用条款及细则的限制 规定,在部分，除非你获得耒经许可，不可以下载整个一期的杂志上的文章或多个副本，你可以使用内容仅供你 个人档案JSTOR,非商业性的使用。请与我们

2、联系一我们将进一步使用关于任何的出版商的这项工作。出版商联系信息可以被获 得Http:/action/showpublisher?Publishercode=informSo每份副本的任何部位的JSTOR传输必须包含相同的版权声明，岀现在屏幕上或打印出來页 曲的传输。JSTOR是一个非营利性的服务，帮助学者、研究人员和学牛发现，使川，和建立一个广泛的 内容在一个信任的数字档案。我们使川信息技术和工具,以提高生产率和促进新形式的奖学 金。更多详情，请联系 HYPERLINK mailto:support support JSTOR。合作与JSTOR通知在数字化、保存和延长访问运筹学。交通信号的同

3、步的整数线性规划标John D. C. LittleMiassachusettisnstitute of technologyc,ambridge,Massachusetts 交通信号可以被synichroniized使一辆汽车,在一条主干道的开端动并按照预定的速度行驶, 到达另一端而不遇任何一个红灯。信号周期的一部分，这是可能是为所谓的带宽的那个方向。 利用混合整数线性程序是为了证明接下来的干道问题:给(1)任意数量的信号,(2)在每个信号 的红绿灯,(3)上部和下部限制信号周期,(4)上位机、下位机之间的限制acenit signials速度;(5) 限制在速度、找到改变普通信号周期、(2

4、)速度信号，并betweeni相对分阶段的信号，以 最大限度地总和的带宽为两个方向。儿个变异的问题，包括制定synchronizinig的问题的一 个网络的信号。Branch-and-bound发展出对丁解决算法求解整数线性pro-grams ordiniary 序列的线性程序。一个10-signal动脉的例子和7-signal拟定网络例子。交通信号可以达到同步，如果司机能够保持这一部分设置的速度，这 样-辆车就可以畅通无阻地从-个街道的尽头驶到另条街。信号周 期的一部分，可能就是被称为带宽为那个方向。对于较大型的带宽的 同时性一般称为连续数列(progression) 交通工程师们长久以来

5、建立起的(progressions)数列，尽管在交通量较大时似乎作用很小， 但在交通量较小时它们似乎是和当有效的。HELLY和bakerli的工作 倾向于支持这个情形。(progression)的价值也可以通过给予司机 速度指令而捉高，而这VONSTEIN己经做好了。在前面的论文屮，J. MVIORG和作者开发了一 mviorgaannd算法 求解接下来的对于主干道交通信号同步问题的运算两个问题，狀 在任何一个方向上都是不可分裂的。1o给定任意数量的信号，一种常见的信号周期的、绿色的给不同信号和红色次旅行时间,和特定的相邻信号，*工作报告被支持的部分原因是由于美军军队研究办事处(达拉谟)在DA

6、-31-214-ARO-D-209合同下，是MAC工程的一部分，麻省理匸学院搜索程序由高等研究计画署，部门在办公室的防线，海军研究实验室合同号。Nonr4102(01)。同步交通信号牛产同步佶号带宽，每个方向都是平等的，尽可能人。2、通过增加某些特定的一个带宽调整信号同步，可行性的价值和保持其他带宽一样大是可能的。随后，R-奥利弗指出，作者认为两个信号问题1的版本可以设置为线性规划问题。我们在这 里展开这成为一个相当普遍的最大带宽制定理念问题。在一般情况下，我们仍然有一个线性 规划问题，但unfortu-nately它是混合整数类型。对于问题1和2中的新没有优势和制定提 供了许多缺点。然而，线

7、性规划的格式打开了解决更多的可能性涉及引进新的决策变量的一 般问题和新的限制。举例来说，最大带宽为通常执行计算有一个令人不安的特点。在漫长的街道上的关键信号收 缩带宽对能会变得很远。然后一个小的沿街的设计速度的变化，在重新解决这个问题，导致 不同的同步和不同带宽。然而，司机并不准确的拥有自己的速度常数，事实上，众所周知， 往往会调整自己的速度信号。因此，这就形成了一个很好的协议感，让设计速度信号之间是 一个变量，至少在一定限度内。这很容易做到在线性规划。另一个可以明确地引入变量是信号周期。问题1,周期是一个常数，虽然它并不 太难用我们以前使用的方法來检查组织方式中的相当多的值。对连续变化的线

8、性规划的制定，似乎更可取。也许最有趣的发展是同步的的街道网络信号问题可以作为一个混合配制而成整 数线性规划。一个街道网络的工程曲组成对于一个网络方案包括加上额外的限制 的干道方案，只更这些干道连接起來，就能形成循环或周期。主干道问题定义：考虑一个双行道有n交通信号。街道上的方向可以被定义为进境和出境。这些信 号被表示为带有下标的S1S2Sn,增加出境的方向。图1显示了在街上运行的时空图。加匝的水平线表示当该信号为红色。锯齿线代表的汽车 通过沿轨道方向舒街道畅通无阻。坡度变化对应于速度的变化。这个町能的畅通轨迹，设置 在一个给定的方向，形成一个绿色带的水平宽度是该方向的带宽。虽然但一旦制定，绿

9、色带在每个周期的出现一次，在贯穿整个图的平行带里。通常在每个周期的带宽是单一的，也就是说，是不是在一个周期内分成两个或多 个间隔的分裂。一个分裂的带宽可以，但是，发牛:了特殊的例了，其中已建成的 最大总带宽是出两片在一个或两个方向。这种可能性在目前的措施下将被忽略。 该数学规划将最大限度地将建造两个带宽，每个方向迈出的可能性，而不考虑其 他部分可能存在一个加权总和。某些信号最终形成了带宽的限制，并将于所谓的关键信号。信号Sj被认为是一 个重耍的信号，如果一边的信号Sj是红色触及的一个方向的绿色带，另一边的 红色涉及绿色带的其他方向。因此，在图1信号S1和Si是至关重要的，而其 它则不这样。图1

10、OutboundInboundFig. 1. Space-time diagram showing out bound and inbound green bands.基本法的制定最大带宽（571）首先，我们设置问题1作为一个混合整数线性规划。这是除了简单的整数限制。 该整数约束出现，因为这两个方向的绿色条纹必须承受特殊的关系，每人每一个 信号等。每一个绿色的带明显通过在任何特定时间的推移和绿色信号，因为绿色 时报（或者，等价地，红灯时间）发生的周期，除了整数，创建一个整数约束每 个信号（除了最后一个）。我们将开发一些一般性的约束，然后专门眼前的干道 情况。DistanceTime(cycle

11、s)Fig. 2. Geometry of green bands. Notice that (h9 分)+3仇，i) must equal an integer.让Sh和Si是任何两个信号，使得Si遵循Sh的外约束的方向。参考图2 让A；二所研究路段的红灯时间（次）级初=出境（入境）带宽（次）心亦（亦）卜由Sh到Si沿出境方向的运行时间（由Si到Sh沿入境方向的运行时间）（次）0（/2,i）P（九洲二由在Sh处的红灯中心到在Si处的一个特定的红灯中心的时间。两个红灯被 选择从而使得它们每一个都立即向相同的出境（入境）的绿色带。0（/M）p仇洲是正面的 如果Si的红色屮心位于Sh的屮心的右侧（

12、左侧）。vv,.（ur）wi（zCv）=从Si的红灯的右侧（左侧）到绿波带的时间（次）(1)需要指出的是，有大量的时间量的尺寸可以总是用一个周期可以划分为若干时间 段来表达。由图2来读取身份：%乙 + 叫 +M，i)叱 一%耳=0(/2,0+ W力+（力丿）一叱一%乙=0（力显）.(2)0SM)和0(/M)的值具有非常莹要的约束，它们的和必须是一个整数，但在其他方面不受限制。因此，上述两个约束可以被替换为：(w/t+w) (Wi+Wt)+t(A, i)i) = m(h, i)(心一心)， m(hy i) = integer,目前，我们已经按照需要在出境方向让Si跟随者Sh,但是这种限制可以通过

13、正确的定义t(i. h) 丿来消除。出于这种物理原因，我们希望保持中关系。 TOC o 1-5 h z (人 j) = t(打分)+Z仏 j)；(4a) 何处，设置h=j,我们得到：l( h) = i(hf i)(5a)同样的道理也适应于取心因此我们采取的公约，(咫D妝息？)为沿岀境方向从S1到Sk的出行时间大小的负值。 现在(2)及(3)有任意的Si和Sh以及：(4b) m(hj) = m(hf(4c)eG h) = 一(人(5b)m(t, h) = m(h, i),(5c)持有相应的表达式：从图2,我们也看到奶+bWl r 亦(6a)Wi+blTi.(6b)现在还没有任何使用的特殊编码沿出

14、境的方向。在以后的网络工作中它还是般需要的，但我们再这可以简单定义符号：i+1),(7)x=t90,九 m.问题1：现在是代表了一个混合整数线性规划。约束条件(6)需耍每个信号，约束(3)需 要每个相邻(信号)对。尽管有许多其他类型的(信号)对，但只需考虑相邻对，因为约 束3对于任何其他对都可以从约束3相邻对屮获得线性组合。LP1,得到 max b,，(“1,严)(8a)(8b)使其服从：(t = 1, n1) (9)(W+1 + Wt+1) + =叫一(咒741),= integer,b, Wi, WiOInteger（整数）LP1有3n-1个约束，3n个未知数，不包括松弛或人工变量。接下来

15、，我们让时间和速度是变量。每个将受到上限和下限的控制。此外，从一 路段到下一个路段的速度的变化，将是有限的。最后，我们取一个带宽使其是其 他带宽的固定比例，而不是在每个方向都寻求相同的带宽。（然而，这只是一种 可能被使用的制约关系。）使k和乙Z间的比例常数T 二信号周期（s）T,T2 =周期的上、下限 T, T T2 （s）z二信号频率（次/秒）d（h，D= Sh和SJ可的距离（米）di - d（i ,i + 1）*（石）=S,与S/+之间出境方向的速度（Sj+I和之间进境方向的速度）（米/秒） 弘/丄玄,万卜出境（入境）速度的上下限（米/秒）/ 、%，%在出境进境方向上下限速度的倒数的变化，

16、1/hi (l/vi+l) -(l/vi) +6),使其服从:b = kb,(11)1/7总W1/几(奶+bWl叫(13a)(i = 1, , ?!)Wi+b(15b).(16a)(i= 1,，n2)(16b)(如加)z W (山/山+】)兴+1 JW (d/gjz, I(血/ 広)zg (此a+jN+i-冷 w (血/0“zjb, b, v)iy 帀.NO.LP2包括llmlO个约束和5n个变量，不包括松弛或人工变量。对称问题某些对称性，如果它们存在，则可以用來减少LP2的大小。特别地，如果对速度的约朿在 各个方向上是相同的，而且在每个方向带宽都必须相等，那么线性程序的大小是削 减约百分之四

17、十。节省时间的方法也可以解决极大带宽的平等，然后调整其他方案同步。参考文献3表明，一些特殊的资格条件包括，max（b + ）是一个可以被分为之间 的方向不变。为设置一个具有任意可行性的带宽值而给出的规则，另一个最大价 值对给定速度和距离的可能。该案件的对称线性规划是基于以下两个定理。定理1如果在每个相同方向上速度的限制和速度的变化是相同的，并月.，如果LP2拥 有任何最优解，随后LP2有一个最优解，其屮证明：在每个相同方向上拥有相同的速度限制和速度变化，即伏=%/尸九g尸九and hihi. 设& ?4为所有t中对LP2的一个最佳解决方案，定义常=*=仏+初）/2伍=1,，-1）我们断言用/代

18、替-代替将会为LP2将产生一个新的最优解。由于T的-变化不影响fl标函数，唯一的问题是可行性。显然（14）依然满足的。（15a） 加上（15b）然后除以2得出：因此（15a）和（15b）也是满足的。一个相似的论点证明（16a）（16b）也是满足的。 这就是证明过程。定理2如果在每个方向的带宽都必须平等，如果LP2有任何最优解，然后LP2有一个 最佳的解决方案，其中对于任何一个i都有=-o证明：给定任何最优解b “给LP2,用 叱代替叱，代替疋，并定义：w/ = w/ = 2+相同类型的参数用来证明定理1中（13a）和（13b）和（14）新方案的可行性。 最优的即是日标函数是不变的。如果两个定理

19、的条件得到满足，我们可以制定以下简化混合整数线性规划：LP3已知6 z, s, 皿 得到：max b9使其满足： TOC o 1-5 h z （1/八）3（1/口），（17）妙+bWl心（t = l, , n） （18）奶一伽+l+= % 7心一坯（心一心+1）,（i = 1, , n 1） （19） nii=integer,/（血ZA）z W ti垒（必/偽）2,J（20）（心/仏）進（血/必+1）衣+1亡（山/依）為（1=1,，仇一2） （21）6,奶全0LP3有6n5个制约因素和3n个变量，不包括松弛变量和人工变量。确定同步变量的线性规划确定的同步的信号。让&（/M）=Sh与Si之间的相

20、对相位（偏移），即为从Sh的红灯中心到另一个路口 的红灯屮心得时间间隔。（次）一个关于8（h,i）的例子己在图2中给；I1 o我们采用的公约数 owe（h,“ 5. Space-time diagram for symmetric 10-H)gnal problem. Maximal bandwidth is 0.282 cycles or 21.2 seconds. The signal period is 75 seconds.10信号的问题被用来作为个取鬥参考文献3的数值例子,它代表了在Cleveland的Euclid Avenue大街的延伸。距离和绿灯间隔？ ？取口实际的使用情况。对时

21、间、速度以及速度的 变化的限制已经做出了非常随意的(让步？)该问题的常量，现简述如下。这些信号，与SI和工作出站出发，分别位于0, 168, 381,716，929, 1173，1371, 1493，1706 和 1843 米。对应的红灯时间是 0.47, 0.40, 0.40,0.47, 0.48, 0.42, 0.40, 0.40, 0.40 和 0.42 个周期。对周期的限制为 T1=55s T2=75So速度的上下限为 ei= _(30 mph, 48.3 km/hr), _( 40 mph,云=13.4听犬=丁 = 17.9听64.4 km/hr)o速度倒数的变化的限制为斤光广严呵町

22、这相当于最大可能在速度变化在速度限制的下限约为22米/秒(4.9 mph, 7.9 km/hr)，而在速度限制的上限为3.9米/秒(8.7 mph, 14.0 km/hr)。这个问题可以由LP2解决，或者由于我们选择相同的带宽而由LP3解决。这树 通过“分支定界”算法在图4中发展。一共需要52个线性规划问题。每个方向 的带宽是0.282个周期。街道的距离时间图如图5所示。最佳周期时间为75秒, 带宽为21.2秒。在S1和S2之间开始并逐步发展，速度分别为17.9,17.9,17.1,14.2,13.4, 14.9，13.4, 15.6，17.9 米/秒。这些阶段，0(1丿)，为了增加指数,由i

23、=1开始,分别为0,0,0, %,% ,0,0,0,%个周期。关键信号分别为S1,S3, S5,S8,和S9o这个结果可以与利用参考3的方法通过对不同恒定速度和时间探索 得到的结果相比较。最好的结果为在65s时以15.2m/s的速度,带宽为0.235 个周期时长。这实质上同步显示在参考3中。变速的灵活性可以允许在增加带宽 的 20% o讨论：对于在这里报道的数值实例，分支定界算法的步骤除了线性规划还有手动。在一 些线性编程代码，有可能控制限制。然后，整个n信号问题可以载入，只有那些对应于当 前r信号问题所使用的限制。加,的随着常数向量的变化而变化。通常情况下，可以在一个 类似问题的基础上完成新

24、的问题而节约时间。该算法的计算限制是和対为开发的。如果在一个相当不同的应用领域里徳经验就是指导，那 么线性规划的数将会很可能随着n成借的增加。如果是这样，一个比较突出的上限的大小 问题的计算令可能是可行的。我们认为，然而，这甲的例子表明实际利益的人小是可以解决 的。个可通过求解2n线性规划获取的，看上去很好的解决方案，但未必是最佳的。这个过程 就是简单地从那些当询X中创建值中最人Q值的节点向分支。在其他终端的节点扫描就被 省略了。r的值单调递增至n。图4中的例子，以这种方式获得的解决方案中的带宽为0.278网络问题混合整数规划可扩展到网络。该网络方案包括个别街道的主T道方案，加上、”周期限制”

25、将 道路连接在一起。一个客观的函数可以由主干道的带宽形成。一个新的决策变量，红绿间隔, 可以有效地引入某些信号。有些LP2中的决策变量将会在本节中得以发展的网络的制定中 被删除。原因就是我们所预期的网络问题将比个别的I汁道问题会更大，计算更加复杂。因 此，似乎应该显现出-种途径，即这种计划可能会被简化。无论把丁道作为个整体还是rh 干道到干道，我们应该保持固定的速度在干道的一段距离，干道约束在一个网络问题屮，T道将会被用于一个被需要的进程的任意道路，例如：在这 之上，我们定义一个带宽，并将它应用于数学程序中。正如早些时候，网络的信号 被假定为指定的S1, S2, .S,但我们不能再假设与相邻的

26、索引值信号相邻。然后考虑干 道，并假设在极端情况下结束的信号是Si及Sjo我们指定一个方向，说山Si指向Sj作为 出境方向，因此定义为arteryij.o （到底指什么？）关T artery ij的量将会被确定为一个上标。因此，用一个简单的方法，由第二部分的简单定义推广到2卅&仁此外，让 vJ二在artery ij出境方向上的速度（m/s）e,J,f,J=在artery ij出境方向上速度的上下限（m/s）T =在artery上出境方向上的速度的倒数（少） 类似的符号在入境变量屮叶也被适当的运丿U。当定义一个量需要两个信号时，指定干线是多 余的，将被忽略。例如，这些量将会被用作第一部分的定义。

27、对于artery ij的限制如下。把T道作为一个整体:(30a)(30b)对于在干道上的每一个信号Sk:(31a)(31b)对于在干道上的每一对相邻信号，认为，信号Sk跟随着信号SI的出境方向:目标函数在进展中，带宽决定了一个当保持规定速度就能够在街上畅通无阻的通行的 platoon的最大长度（时间上）。因此，当一个进程系统是合适的，街道（或者街 道上的方向）应该根据他们的流动分配带宽。两个设备在街道（方向）屮分配带 宽是可用的：目标函数和约束条件。理想的情况下，我们可能限制每个带宽要比一些指定的能够通过一个已知流量的 带宽更大一些。不幸的是，我们不能保证结果将是可行的。作为替代方案，我们 可

28、以选择一些重要的带宽，称Z为胪，并最大限度的提高这一点，但是需耍每一个带宽都要大于等于胪的指定的分数。这些分数将会依照相关的流量而被选 择。这种限制是不足以得到系统的最大效益。有时主干道上的一个带宽将不会在与其他干道的带 宽相冲突。了保证这种带宽最人化，每带宽必须包含在II标函数内。不太求要的带宽可以通 过加权吐小的系数和大的系数仇。正式确定这些想法，让成为问题的带宽（为了方便起见这里重新索引），并让=分配给第i个带宽的权重；i=0,q。2/呆证第i个带宽的的分数。我们以网络的计划口标max a&+ aqbq.作为限制:V(1 = 1,，q) (35)耍注意U的选择以免让那个不重要的干道限制了

29、。周期约束一个有新的整数变量的新的约束时，必须采用多种干道相交，形成一个封闭的环, 或者像我们称呼它，一个周期。作为一个周期的例子，S1、S3、S4、S7出现 在图6里一个周期的干线的交叉口。新的约朿的根本原因在于一个对同吋性的物 理要求。假设我们在S1的红灯时间的屮心设置一个主时钟为0。如果我们将T 道13降低为S3,这里的红灯屮心时间将由13的进程所固定。作为一个结果， S3的红灯时间中心沿干道35的方向，也是曲主时钟所确定的。35的进程随后修 正S5红灯中心的时间。继续循环，我们最终返冋到确定S1红灯中心的时间。 这个时间一定是在0时段之后一段时间的整数倍。这一需求的代数声明构成了新 的

30、约束。图理论的术语可能被用來描述网络。信号出现在节点上。相邻信号间的街道长度成为弧或者 边缘。弧有方向，通常在图中由一个箭头表示。为了我们的（研究）廿的，将方向规定为街 道上出境方向。一个边表示不考虑方向街段。一个边的序列形成一个封闭的循环被称之为一 个周期。？ Sk处的节点被简单的记为k。从i到j的弧将会被记为（i,j）。提及相应的弧但 是忽略它们口己的方向而得到边。无论是边缘还是弧的概念都被纳入概念：周期由边缘构成，但，在写下的函数分方程中，这 是非常垂耍的为每一条道路都选择一个方向，并统一的使用这些方向。Fig. 6 A network of 7 signals. In this net

31、work, five arteries: 13, 35, 5(), 16, and 47, have been selected for consideration. Two cycles constraints are required. Arrows indicate direction chosen as outbound. Numbers on street segments are distances in meters The red-green split has been made a decision variable at 7.该限制为一个信号周期制定以下收益：假设我们追寻

32、一个周期，发现一些干道丿jp 假设在干道交叉口的信号可以由节点代替，k1,k2,，kp 111在干道ipjp和i1j1的交叉口的k1, i1j和i2j2的交叉口的k2,等。周期将被C（k1,kp）。让t=0成为沿着T道i1j1的在k1处的红灯中心的吋间。然后，沿着干道i1j1的在k2处的 红灯屮心的时间为t = 0仏,h）。同时也是沿着干道i2j2的在k2处的绿灯中心的时间。因此沿i2j2方向上的k2处红灯中心时间为:=0（饥上2）+%.*从这一时间开始，我们增加0（心人）來寻找沿方向上在k3处的红灯中心。再加1/2我 们就走出谷底并到达干道i3j3o将1/2假设为一个街道路口的红灯时间与相交

33、路口的绿灯时间相一致，反Z 亦然。更复杂的安排是可能的并H.可能需要更换一些其他部分的1/2。巾周期出发，我们最终决定沿着干道i1j1发牛在k1处的红灯中心的时间。让松,kp卜周期C的整数变量（，kjo然后，对周期的限制：C（fci, , fcp） =/（1,力2）+/（他,上3）+ kp）（36）+（/（爲,俎）+ 坯 p .对0（，J）由以下由（2）（26）给出的程序其他变量的合适表达式，可能会对（4）（5）有一定的帮助。多周期引入多个约束。可能的周期数比所需要的限制数目人。限制的最小数可以发展通过在 网络上进行如下追踪：选择-个起始节点。追踪构成每个贯穿起始节点的T道的弧（不论其 方向）

34、。然后，对于每一个H前能够追踪到的节点，描通过节点的干道的弧。现在，只要跟 踪过程关闭一个周期，就形成了一个周期约束。继续这个过程，知道没有进一步的弧可以追 溯。如杲整个网络都被追溯了，工作就结束了。否则，网络分解为两个（或者更多）不连接 的子网，其中一个刚刚被隔离。选择另一个节点并继续。追踪过程因为它确定了哪些信号要承担严格的时间通过一系列干道运算，凭借信号的开端。 只要信号是封闭的，刚性关系一定是由一个约束所兼容的。如果在感到的每个路口都有一个信号（即，没有立交桥），该系统的图形是平面。然后循环 的限制数量与山干道封闭的不同区域一致。图6显示了一个平而图需要的两个循环限制。周期限制不一定是

35、唯一的。在图6中，例如，我们可以运用周期对C（1,3,4,7）和C（7,4,5,6） 或者和对C（1,3,4,7）和C（1,3,5,6）。代数地，这些屮的任何对都可以从其他屮获得。红灯时间限制一个出两个主干道的相交的交叉口对的信号可能是一个唯一的关键信号。然后， 绿灯时间的转移可能会增加主干道的带宽而减少另一方向的带宽。因此，在主干 道交叉口的红灯时间可能有时会是一个有用的决策变量。变量将可能会收到限 制。因为交通流的需求，每条街道上的红灯时间的倒数可能会受到限制。绝对红 灯时间可能会被限制，最短允许行人过街，最长安抚司机。在这红色信号的时间 是一个决策变量，让E： , F?二上限和下限控制在

36、川（次） G： , H；=上限和下限控制在时T （秒）则变量卅是受制于E?十 F? (37a)Gf r/ Hl (37b)制定一个网络问题的步骤对于网络问题，一般的整数线性规划是有些麻烦，而非编写出程序，我们列出 产生它的步骤。1、确定网络上的哪些街道将作为干道。2、成立了日标函数和相关的约束，(34)和(35)o3、设置时间限制：(1/T2) z (1/T1)(38)4、对于每一条干道，设置F跚,(30) - (33),或者，如果在限制条件下优 先考虑LP2或LP3的。5、建立应用了周期约束(36)和程序的章节的“周期约束。6、为任何将要形成的红灯决策变量增加红灯时间限制。网络问题可以通过这

37、一节中“分支定界”的方法即带有一些修改的“阿部定界技 术”来解决。在这整数变量一次引入一个。在任何阶段，部分整数变量都被赋予 具体数值的并且为网络问题定义一个解决方案的子集服务。对于解决方案的子集 中忖标函数的上限，通过用整数变量的特定值求解一个普通的线性规划而被发 现。然而，在网络的问题中，即使是一个r 信号的问题也耍使用，那么完整的N 信号H标函数必须使用。否则，上界获得的不恰当。最后，每个出现在H标函数 屮带宽，在解决每个线性规划时必须有一个约束方程(31),否则，日标函数将 出现一个无限大值。因此，r 信号的问题通常会比R信号问题有更多的约朿。 事实上在每一个普通的线性规划屮，将被允许

38、使用所有原始问题的约朿(除涉及 整数尚未分配的具体值变量)。刚才提到了无界问题是例外的，然而，直到约(32)其中包含整型变量被添加，与一个信号相关的约束，才会被预期严重影 响到目标函数。因此，通过保持线性规划问题的规模增加限制信号，可预期节省 计算时间。然而，添加信号的顺序，将影响树的规模。总的來说，麻烦约束应该尽早采用。 例如对信号靠拢和短周期的约束要尽早采用。例图6显示了 7信号，已经在对称情况卜-解决的5干道的问题。干道是13,35，47, 56和16。所使用的冃标函数是屮+001(胃+屮+泸+沪)随着限制b35 N 0.5613, 性 0.5b13? bb6 N 0.5b1;617 全