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

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

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

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

4、个变异的问题,包括制定synchronizinig的问题的一个网络的信号。Branch-and-bound发展出对于解决算法求解整数线性pro-grams ordiniary序列的线性程序。一个10-signal动脉的例子和7-signal拟定网络例子。交通信号可以达到同步，如果司机能够保持这一部分设置的速度，这样一辆车就可以畅通无阻地从一个街道的尽头驶到另一条街。信号周期的一部分，可能就是被称为带宽为那个方向。对于较大型的带宽的同时性一般称为连续数列（progression）。交通工程师们长久以来建立起的（progressions）数列,尽管在交通量较大时似乎作用很小，但在交通量较小时它们似

5、乎是相当有效的。HELLY和bakerli的工作倾向于支持这个情形。（progression）的价值也可以通过给予司机速度指令而提高,而这VONSTEIN已经做好了。在前面的论文中，J. MVIORG和作者开发了一mviorgaannd算法求解接下来的对于主干道交通信号同步问题的运算两个问题，带宽在任何一个方向上都是不可分裂的。1。给定任意数量的信号,一种常见的信号周期的、绿色的给不同信号和红色次旅行时间,和特定的相邻信号,* 工作报告被支持的部分原因是由于美军军队研究办事处(达拉谟)在DA-31-214-ARO-D-209合同下,是MAC工程的一部分,麻省理工学院搜索程序由高等研究计画署,部

6、门在办公室的防线,海军研究实验室合同号。Nonr-4102(01)。同步交通信号生产同步信号带宽,每个方向都是平等的,尽可能大。2、通过增加某些特定的一个带宽调整信号同步，可行性的价值和保持其他带宽一样大是可能的。随后，R-奥利弗指出，作者认为两个信号问题1的版本可以设置为线性规划问题。我们在这里展开这成为一个相当普遍的最大带宽制定理念问题。在一般情况下，我们仍然有一个线性规划问题，但unfortu-nately它是混合整数类型。对于问题1和2中的新没有优势和制定提供了许多缺点。然而，线性规划的格式打开了解决更多的可能性涉及引进新的决策变量的一般问题和新的限制。举例来说，最大带宽为通常执行计算

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

8、工程由组成对于一个网络方案包括加上额外的限制的干道方案，只要这些干道连接起来，就能形成循环或周期。主干道问题定义：考虑一个双行道有n交通信号。街道上的方向可以被定义为进境和出境。这些信号被表示为带有下标的S1S2Sn,增加出境的方向。图1显示了在街上运行的时空图。加重的水平线表示当该信号为红色。锯齿线代表的汽车通过沿轨道方向舒街道畅通无阻。坡度变化对应于速度的变化。这个可能的畅通轨迹，设置在一个给定的方向，形成一个绿色带的水平宽度是该方向的带宽。虽然但一旦制定，绿色带在每个周期的出现一次，在贯穿整个图的平行带里。通常在每个周期的带宽是单一的，也就是说，是不是在一个周期内分成两个或多个间隔的分裂

9、。一个分裂的带宽可以，但是，发生了特殊的例子，其中已建成的最大总带宽是由两片在一个或两个方向。这种可能性在目前的措施下将被忽略。该数学规划将最大限度地将建造两个带宽，每个方向迈出的可能性，而不考虑其他部分可能存在一个加权总和。某些信号最终形成了带宽的限制，并将于所谓的关键信号。信号Sj被认为是一个重要的信号，如果一边的信号Sj是红色触及的一个方向的绿色带，另一边的红色涉及绿色带的其他方向。因此，在图1信号S1和Si是至关重要的，而其它则不这样。图1基本法的制定最大带宽（571）首先，我们设置问题1作为一个混合整数线性规划。这是除了简单的整数限制。该整数约束出现，因为这两个方向的绿色条纹必须承受

10、特殊的关系，每人每一个信号等。每一个绿色的带明显通过在任何特定时间的推移和绿色信号，因为绿色时报（或者，等价地，红灯时间）发生的周期，除了整数，创建一个整数约束每个信号（除了最后一个）。我们将开发一些一般性的约束，然后专门眼前的干道情况。图让Sh和Si是任何两个信号，使得Si遵循Sh的外约束的方向。参考图2让 =所研究路段的红灯时间（次）=出境（入境）带宽（次）=由Sh到Si沿出境方向的运行时间（由Si到Sh沿入境方向的运行时间）（次）=由在Sh处的红灯中心到在Si处的一个特定的红灯中心的时间。两个红灯被选择从而使得它们每一个都立即向相同的出境（入境）的绿色带。是正面的如果Si的红色中心位于S

11、h的中心的右侧（左侧）。wi(zCv)=从Si的红灯的右侧（左侧）到绿波带的时间（次） （1）需要指出的是，有大量的时间量的尺寸可以总是用一个周期可以划分为若干时间段来表达。由图2来读取身份：. （2）和的值具有非常重要的约束，它们的和必须是一个整数，但在其他方面不受限制。因此，上述两个约束可以被替换为：目前，我们已经按照需要在出境方向让Si跟随者Sh，但是这种限制可以通过正确的定义来消除。出于这种物理原因，我们希望保持中关系。何处，设置h=j，我们得到：同样的道理也适应于因此我们采取的公约，为沿出境方向从Sl到Sk的出行时间大小的负值。现在（2）及（3）有任意的Si和Sh以及：持有相应的表达

12、式：从图2，我们也看到现在还没有任何使用的特殊编码沿出境的方向。在以后的网络工作中它还是一般需要的，但我们再这可以简单定义符号：问题1：现在是代表了一个混合整数线性规划。约束条件（6）需要每个信号，约束（3）需要每个相邻（信号）对。尽管有许多其他类型的（信号）对，但只需考虑相邻对，因为约束3对于任何其他对都可以从约束3相邻对中获得线性组合。LP1已知 ，得到max b,，使其服从：Integer(整数)LP1有3n-1个约束，3n个未知数，不包括松弛或人工变量。增加决策变量接下来，我们让时间和速度是变量。每个将受到上限和下限的控制。此外，从一路段到下一个路段的速度的变化，将是有限的。最后，我们

13、取一个带宽使其是其他带宽的固定比例，而不是在每个方向都寻求相同的带宽。（然而，这只是一种可能被使用的制约关系。）使 k =和之间的比例常数T =信号周期（s）周期的上、下限 （s）z =信号频率（次/秒）=和间的距离（米）=与之间出境方向的速度（和之间进境方向的速度）（米/ 秒）=出境（入境）速度的上下限（米/秒）=在出境进境方向上下限速度的倒数的变化，l/hi (1/vi+1) -(l/vi) l/gi (meters/second,)我们是制约变化速度通过改变上、下的限制之间的速度倒数（reciprocal speed.）。尽管两者并不完全一样，但是在相互制约速度的变化还是一定满足基本内涵

14、的，这是一个有效地防止速度突然发生大的变化的手段。速度的倒数起作用的原因是它线性的出现在约束中，并且可以转化为。因此在扩大方案中，和都是决策变量，这些一旦已知，将决定其速度。在对带宽、距离、速度、以及速度倒数的变化等限制通过一些代数运算后，可以被加到LP1中得到一个更通用的混合整数线性规划。LP2已知得到使其服从：LP2包括11n-10个约束和5n个变量，不包括松弛或人工变量。对称问题某些对称性，如果它们存在，则可以用来减少LP2的大小。特别地，如果对速度的约束在各个方向上是相同的，而且在每个方向带宽都必须相等，那么线性程序的大小是削减约百分之四十。节省时间的方法也可以解决极大带宽的平等，然后

15、调整其他方案同步。参考文献3表明，一些特殊的资格条件包括，max(+)是一个可以被分为之间的方向不变。为设置一个具有任意可行性的带宽值而给出的规则，另一个最大价值对给定速度和距离的可能。该案件的对称线性规划是基于以下两个定理。定理1如果在每个相同方向上速度的限制和速度的变化是相同的，并且，如果LP2拥有任何最优解，随后LP2有一个最优解，其中证明：在每个相同方向上拥有相同的速度限制和速度变化，即。设为所有t中对LP2的一个最佳解决方案，定义我们断言用代替，代替，将会为LP2将产生一个新的最优解。由于T的变化不影响目标函数，唯一的问题是可行性。显然，（14）依然满足的。（15a）加上（15b）然

16、后除以2得出：因此(15a)和(15b)也是满足的。一个相似的论点证明（16a）（16b）也是满足的。这就是证明过程。定理2如果在每个方向的带宽都必须平等，如果LP2有任何最优解，然后LP2有一个最佳的解决方案，其中对于任何一个i都有。证明：给定任何最优解给LP2，用 代替， 代替，并定义：相同类型的参数用来证明定理1中（13a）和（13b）和（14）新方案的可行性。最优的即是目标函数是不变的。如果两个定理的条件得到满足，我们可以制定以下简化混合整数线性规划：LP3已知得到：使其满足：LP3有6n-5个制约因素和3n个变量，不包括松弛变量和人工变量。确定同步变量的线性规划确定的同步的信号。让=

17、Sh与Si之间的相对相位（偏移），即为从Sh的红灯中心到另一个路口的红灯中心得时间间隔。（次）一个关于的例子已在图2中给出。我们采用的公约数。一组将被称为信号的同步。为了能够给以及某些其他的量一个简单、明确的表达式，我们定义，对任意的x，因此例如由图2我们可以看出并且，使用（2a）（4a）（7），我们得出：在对称情况下的LP3，（2）指出，由（2）（3）得出：因此（24）（4c）（7）给出对整型变量的限制该整数变量m(h,i) 的价值相当有限，他可以呈现出而不会造成一个不可行的方案。如果大多数的不可行值可以提前排除，我们应该可以在下一节的算法保存计算。我们寻求整数和如下：由（3）由于以及有类似

18、的关系。因此然而，T和T通常是变量，可以遵循该问题的常数的有界范围。因此，在LP2中遵循LP2中的符号，我们得到：一个分支定界（BRANCH-AND-BOUND）算法各种求解的一般混合整数线性规划问题的算法已制定。（7、8、9）被报道出来的这些计算经验在某些情况下相当有限，而在其他情形下，不免有些让人失望。因此，一个专门的算法已经制定了最大的带宽问题，利用分支定界（BRANCH-AND-BOUND）方法。这些方法已在其他一些组合问题被证明是相当成功的。（5、6）总体描述该方法的基本思想为，打破所以可行的解决方案至越来越小的子集，计算每一种上(下)界对最佳解决方案的目标函数的约束。边界引导子集的

19、分割并最终确定一个最大化（最小化）的解决方案。当发现一个子集，其中包含一个单一的解决方案，其目标函数是大于（小于）或等于上（下）的所有其他子集的上（下）限，该解决方案是最优。解决方案的子集可以方便的表示为树的节点，作为树的分支分配过程，因而得名，“分支定界”。这个过程的衔接，可以保证通过一个分区程序的制定，在最坏的情况下，导致所有的解决方案最终一一枚举。这个过程的计算效率，但是，非常依赖于执行分区和计算范围的使用方法。迄今为止，成功的应用已经开发特色的手边某类特定的问题,培养良好的界限。一个对LP2(或LP3)branch-and-bound算法将会被描述。考虑一个R-信号问题（2rn），组成

20、的第一个R信号的n-信号问题。假设我们挑选LP2中的变量的具体整数值。LP2现在是一个普通的线性规划问题，并且可以在一个直截了当的方式解决，以最大限度地提高目标函数。现在，设置了N -信号解决方案，这方面的具体的整数值是对所有n信号解决方案集的子集。此外，对于R信号问题有最大的目标函数，对于N信号解决方案中的这些m值形成目标函数的一个上限，由于增加了更多的信号能够仅仅限制最大化的可能性。因此，我们有一个确定的解决方案的子集（通过指定的M -值），并放置在他们的目标函数式（普通线性规划求解）方法。该可进一步划分子集通过指定的m的更多的价值。流程图上一节的想法，现在更正式地表示。让X=一对的N-信

21、号的问题解决方案的子集，即所有的解决方案具有的一个特殊r -信号问题的m值。=定义为X的问题中的信号数=定义为X的r-信号问题的整数值=通过进一步解决分割得到的子集X集合X被划分为子集每一个被定义为不同的（r+1)-信号问题。任何一个（r+1)-信号问题，为Xj提供说法，将会拥有和X相同的的值，i最大到r-1：另外，一个的值。让=使用最大和最小的S的值区分Xa（X）=对X的解决方案的目标函数的一个上限，通过解决一个带有知道m值的r-信号问题的普通线性规划问题来获取。=迄今为止发现的最好的n信号问题函数的计算一个算法的流程图如图3所示。我们将跟踪这些盒子，这些完成之后，就对所提到的图4有作用，它

22、显示出已经完成的10个交叉口信号问题的树。在树的表示中，节点代表解决方案的子集，所以我们用X来同时指代子集和它们的节点。Box 1初始化三个数量：X的所有解集，r到1图4。10个信号主干道问题的树。节点上的标签是解决方案的带宽的上界的计算值（一个周期）。标签X表示没有可行的解决方案。节点内的数字是mi右边显示的值。和F3为零。专栏2初始化两个量是在X分支的节点的用来兴建干线：该指数计算的节点，设置为1和，其值将定义的节点，其较低的设置限制。方框3,在分支结构上设置一个节点，这个节点可能被确认为，设置为的当前值，【在图4中，的值被写为该周期内的每一个节点的值，药完全定义节点，我们还需要，但是它们

23、都可以追溯回树的全部解决方案来找到，并阅读过所有节点所遇到的。】接下来，LP2是为了解决由当前m值，m1定义的r+1信号问题。该目标函数的最大值成为的上限值，并被用来标记为节点。方框4测试是否一个n-信号的问题正在得到解决。如果是这样，框5测试，看是否产生更好的目标函数是比以前的最好的。如果是这样的话，框6取代了以前的最好与新的解决方案。框7测试，看看是否所有计划MR值已被用来创建新的节点。如果没有，框8 ，J和加1，并返回框3，成立一个新的节点。方框9，从分支中寻求一个新的节点，这些候选人是树的节点，除了那些没有分支的的树。这里没有必要考虑那些r=n的节点。在够资格的节点中，有最大的节点被选

24、出，成为一个新的X。r 的当前值由r（X）取代，的当前值由取代，（i=1r-1）。方框10测试，看其最大上限值是否大于目前为止最好的N-信号目标函数。如果是，那么就有可能找到一个更大的n-信号目标函数和计算，从一个新的X的分支返回到方框2。否则，计算结束，而目前最好的解决方案就是对原来的n-信号问题的混合整数优化。它可能有助于追踪在图4中的前几个节点。第一，这个节点的作用解决方案都已被列出。然后，由于，那么，以及，已被列出。这两者中的最大值为0.440，所以的节点被用作分支。除了它又来了两个节点：m2=O, a=0.282 and m2=1, a=O.381。接下来的一步就是从节点m2-=1,

25、 a =0.381继续分支。最后，整个树网就的一样被建立起来了，如图所示。请注意，十个信号问题被标记为“最佳”的节点的目标函数的值为0.282，这是大于或者等于其他终端节点的上限值的。例子10信号的问题被用来作为一个取自参考文献3的数值例子，它代表了在Cleveland的Euclid Avenue大街的延伸。距离和绿灯间隔？取自实际的使用情况。对时间、速度以及速度的变化的限制已经做出了非常随意的（让步？）该问题的常量，现简述如下。这些信号，与SI和工作出站出发，分别位于0，168，381，716， 929，1173，1371，1493，1706和1843米。对应的红灯时间是0.47，0.40，

26、0.40，0.47，0.48，0.42，0.40，0.40，0.40和0.42个周期。对周期的限制为T1=55s T2=75s。速度的上下限为ei= (30 mph, 48.3 km/hr),( 40 mph, 64.4 km/hr)。速度倒数的变化的限制为这相当于最大可能在速度变化在速度限制的下限约为2.2米/秒(4.9 mph, 7.9 km/hr)，而在速度限制的上限为米/秒(8.7 mph, 14.0 km/hr)。这个问题可以由LP2解决，或者由于我们选择相同的带宽而由LP3解决。这树通过“分支定界”算法在图4中发展。一共需要52个线性规划问题。每个方向的带宽是0.282个周期。街道

27、的距离-时间图如图5所示。最佳周期时间为75秒，带宽为21.2秒。在S1和S2之间开始并逐步发展，速度分别为17.9，17.9，17.1，14.2,13.4，14.9，13.4，15.6，17.9米/秒。这些阶段，为了增加指数，由i=1开始，分别为个周期。关键信号分别为S1, S3, S5, S8, 和 S9。这个结果可以与利用参考3的方法通过对不同恒定速度和时间探索得到的结果相比较。最好的结果为在65s时以15.2m/s的速度，带宽为0.235个周期时长。这实质上同步显示在参考3中。变速的灵活性可以允许在增加带宽的20%。讨论：对于在这里报道的数值实例，分支定界算法的步骤除了线性规划还有手动

28、。在一些线性编程代码，有可能控制限制。然后，整个n-信号问题可以载入，只有那些对应于当前r信号问题所使用的限制。的随着常数向量的变化而变化。通常情况下，可以在一个类似问题的基础上完成新的问题而节约时间。该算法的计算限制是相对为开发的。如果在一个相当不同的应用领域里德经验就是指导，那么线性规划的数将会很可能随着n成倍的增加。如果是这样，一个比较突出的上限的大小问题的计算有可能是可行的。我们认为，然而，这里的例子表明实际利益的大小是可以解决的。一个可通过求解2n线性规划获取的，看上去很好的解决方案，但未必是最佳的。这个过程就是简单地从那些当前X中创建值中最大值的节点向分支。在其他终端的节点扫描就被

29、省略了。r的值单调递增至n。图4中的例子，以这种方式获得的解决方案中的带宽为0.278。网络问题混合整数规划可扩展到网络。该网络方案包括个别街道的主干道方案，加上、”周期限制”将道路连接在一起。一个客观的函数可以由主干道的带宽形成。一个新的决策变量，红绿间隔，可以有效地引入某些信号。有些LP2中的决策变量将会在本节中得以发展的网络的制定中被删除。原因就是我们所预期的网络问题将比个别的主干道问题会更大，计算更加复杂。因此，似乎应该显现出一种途径，即这种计划可能会被简化。无论把干道作为一个整体还是由干道到干道，我们应该保持固定的速度在干道的一段距离，干道约束在一个网络问题中，干道将会被用于一个被需

30、要的进程的任意道路，例如：在这之上，我们定义一个带宽，并将它应用于数学程序中。正如早些时候，网络的信号被假定为指定的S1，S2，.S，但我们不能再假设与相邻的索引值信号相邻。然后考虑干道，并假设在极端情况下结束的信号是Si及Sj。我们指定一个方向，说由Si指向Sj作为出境方向，因此定义为arteryij.。（到底指什么？）关于artery ij 的量将会被确定为一个上标。因此，用一个简单的方法，由第二部分的简单定义推广到。此外，让=在artery ij出境方向上的速度（m/s）=在artery ij出境方向上速度的上下限（m/s）在artery上出境方向上的速度的倒数类似的符号在入境变量中叶也

31、被适当的运用。当定义一个量需要两个信号时，指定干线是多余的，将被忽略。例如，这些量将会被用作第二部分的定义。对于artery ij 的限制如下。把干道作为一个整体：对于在干道上的每一个信号：对于在干道上的每一对相邻信号，认为，信号Sk跟随着信号Sl的出境方向：目标函数在进展中，带宽决定了一个当保持规定速度就能够在街上畅通无阻的通行的platoon的最大长度（时间上）。因此，当一个进程系统是合适的，街道（或者街道上的方向）应该根据他们的流动分配带宽。两个设备在街道（方向）中分配带宽是可用的：目标函数和约束条件。理想的情况下，我们可能限制每个带宽要比一些指定的能够通过一个已知流量的带宽更大一些。不

32、幸的是，我们不能保证结果将是可行的。作为替代方案，我们可以选择一些重要的带宽，称之为，并最大限度的提高这一点，但是需要每一个带宽都要大于等于的指定的分数。这些分数将会依照相关的流量而被选择。这种限制是不足以得到系统的最大效益。有时主干道上的一个带宽将不会在与其他干道的带宽相冲突。了保证这种带宽最大化，每带宽必须包含在目标函数内。不太重要的带宽可以通过加权一些小的系数和大的系数。正式确定这些想法，让成为问题的带宽（为了方便起见这里重新索引），并让=分配给第i个带宽的权重；i=0，q。=保证第i个带宽的的分数。我们以网络的计划目标作为限制：要注意的选择以免让那个不重要的干道限制了。周期约束一个有新

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

34、络。信号出现在节点上。相邻信号间的街道长度成为弧或者边缘。弧有方向，通常在图中由一个箭头表示。为了我们的（研究）目的，将方向规定为街道上出境方向。一个边表示不考虑方向街段。一个边的序列形成一个封闭的循环被称之为一个周期。？ Sk处的节点被简单的记为k。从i到j的弧将会被记为（i,j）。提及相应的弧但是忽略它们自己的方向而得到边。无论是边缘还是弧的概念都被纳入概念：周期由边缘构成，但，在写下的函数分方程中，这是非常重要的为每一条道路都选择一个方向，并统一的使用这些方向。该限制为一个信号周期制定以下收益：假设我们追寻一个周期，发现一些干道。假设在干道交叉口的信号可以由节点代替，k1,k2,，kp中

35、在干道ipjp和i1j1的交叉口的k1，i1j和i2j2的交叉口的k2，等。周期将被C（k1,，kp）。让t=0成为沿着干道i1j1的在k1处的红灯中心的时间。然后，沿着干道i1j1的在k2处的红灯中心的时间为。同时也是沿着干道i2j2的在k2处的绿灯中心的时间。因此沿i2j2方向上的k2处红灯中心时间为：从这一时间开始，我们增加来寻找沿i2j2方向上在k3处的红灯中心。再加1/2我们就走出谷底并到达干道i3j3。将1/2假设为一个街道路口的红灯时间与相交路口的绿灯时间相一致，反之亦然。更复杂的安排是可能的并且可能需要更换一些其他部分的1/ 2。由周期出发，我们最终决定沿着干道i1j1发生在k

36、1处的红灯中心的时间。让=周期C的整数变量。然后，对周期的限制：对由以下由（2）（26）给出的程序其他变量的合适表达式，可能会对（4）（5）有一定的帮助。多周期引入多个约束。可能的周期数比所需要的限制数目大。限制的最小数可以发展通过在网络上进行如下追踪：选择一个起始节点。追踪构成每个贯穿起始节点的干道的弧（不论其方向）。然后，对于每一个目前能够追踪到的节点，描通过节点的干道的弧。现在，只要跟踪过程关闭一个周期，就形成了一个周期约束。继续这个过程，知道没有进一步的弧可以追溯。如果整个网络都被追溯了，工作就结束了。否则，网络分解为两个（或者更多）不连接的子网，其中一个刚刚被隔离。选择另一个节点并继

37、续。追踪过程因为它确定了哪些信号要承担严格的时间通过一系列干道运算，凭借信号的开端。只要信号是封闭的，刚性关系一定是由一个约束所兼容的。如果在感到的每个路口都有一个信号（即，没有立交桥），该系统的图形是平面。然后循环的限制数量与由干道封闭的不同区域一致。图6显示了一个平面图需要的两个循环限制。周期限制不一定是唯一的。在图6中，例如，我们可以运用周期对C（1,3,4,7）和C(7,4,5,6)或者和对C(1,3,4,7)和C(1,3,5,6)。代数地，这些中的任何对都可以从其他中获得。红灯时间限制一个由两个主干道的相交的交叉口对的信号可能是一个唯一的关键信号。然后，绿灯时间的转移可能会增加主干道

38、的带宽而减少另一方向的带宽。因此，在主干道交叉口的红灯时间可能有时会是一个有用的决策变量。变量将可能会收到限制。因为交通流的需求，每条街道上的红灯时间的倒数可能会受到限制。绝对红灯时间可能会被限制，最短允许行人过街，最长安抚司机。在这红色信号的时间是一个决策变量，让， =上限和下限控制在 (次)，=上限和下限控制在T (秒)则变量是受制于 (37a) (37b)制定一个网络问题的步骤 对于网络问题，一般的整数线性规划是有些麻烦,而非编写出程序，我们列出产生它的步骤。1、确定网络上的哪些街道将作为干道。2、成立了目标函数和相关的约束，（34）和（35）。3、设置时间限制：(1/T2) z (1/T1).（38）4、对于每一条干道，设置限制，（30） - （33），或者，如果在限制条件下优先考虑LP2或LP3的。5、建立应用了周期约束(36)和程序的