急！急！急！数学建模的两个题，有重分奖励！！！！
交叉路口的交通管理和控制问题
我国城市道路一般交叉口的交通灯只分成两个时段，通行规则是：绿灯亮时，准许车辆通行（可直行和左转弯，但转弯车让直行车先行）：红灯亮时，禁止车辆通行；在不防碍绿灯放行车辆行驶的情况下，准许向右转弯。
实际情况是：在车流量较小的情况下，这种交通能力较大：但在车流量较大的情况下，转弯车辆妨碍直行车辆通行，使道路交叉口通行能力降低。
（1）建立数学建模，描述交叉口通行能力与车流量的关系。选定一个城市车流量较大的交叉口，采集数据，检验你的模型。
（2）设计交叉路口的分车道，并把交通灯只分成多个时段，让转弯车辆和直行车辆互不影响。建立数学建模，描述这类样的交叉路口通行能力与车流量的关系。
（3）比较这两种交叉口设计的车辆通行能力。
道路交叉路口一般可以用交通灯控制或设置环岛，交通灯控制的交叉路口的通行规则是：绿灯亮时，准许车辆通行（可直行和左转弯。右转弯时，要转弯车辆让直行车先行）：红灯亮时，禁止车辆通行：在不妨碍绿灯放行车辆行使的情况下，准许向右转弯。设置环岛的交叉口通行规则是：入环岛的车辆不妨碍已在环岛上行驶的车辆。
（4）建立车辆通过交通控制交叉路口的时间与车流量的数学关系。
（5）建立车辆通过环岛交叉路口的时间与车流量的数学关系
（6）选定一交通灯控制交叉口与一环岛交叉路口，采集数据，检验你的模型
（7）比较车辆通过两种交叉路口时间，提出在何种情况下，道路的交叉口应设计为交通灯控制；在何种情况下，道路的交叉口应设置为环岛。
通过将车流量的增大或减小转化为路长权重的变化。将交通流量的动态问题转化为静态问题，用解决最短路问题的Dijkstra 方法，给出交通流量实时最优控制的可行性模型及其有效算法。
关键词：交通流, 实时最优控制, 道路加权, Dijkstra 方法
随着国民经济的持续、高速发展，各种机动车尤其是私家车拥有量急剧增加带来了交通运输业的空前繁荣。但是，大多数城市的交通已从过去的局部拥挤演变成为当今的大范围全面紧张，如我国的一个大城市，当处于早晚交通高峰时，交叉路口处的阻车长度长达1000多米，有的阻车车队从一个交叉路口延伸到另一个交叉路口，这时一辆车为通过一个交叉路口，往往需要半个小时以上，还不如步行快，这给城市交通带来了难以承受的负荷。拥挤不仅带来时间的浪费，还导致公交系统运行的无规则性，如公交汽车不能按时到站等，使人们对自己的旅行时间无法估计，耽误工作和计划等。这种紧张状况日趋严重，已成为大城市突出的社会问题之一，也成为国民经济进一步发展的“瓶颈”问题。因此，必须面对现实，解决城市的交通拥挤，堵塞问题。
那么城市交通拥挤、堵塞原因何在呢？分析如下：
（一）、现行交通信号控制方法中交通信号与交通流量不适应。目前，各城市交叉路口使用最为广泛的是单点定周期控制方式。这种控制方式存在的问题有以下几个方面：
1. 对交通流的随机变化无适应能力。由于是定周期方法，因此一旦周期时间和绿信比选定之后，一般就不再经常改动。而交通网络中车流、人流的变化是随机的、经常的，各个周期中交叉路口同一方向上通过的流量可能差异很大。不同的流量对绿灯时间有着不同的要求。所以此种控制方式给出的信号常常不能与客观实际车流的随机变化相适应。我们常常遇到这样的情况：有车辆等待通过的方向信号是红灯，而与此同时无车辆方向的信号却是绿灯，白白浪费了现有路口通行能力。为了克服这一缺点，人们考虑运用概率、统计的方法，在收集了大量交通数据的基础上，对周期时间和绿信比进行离线优化选择，使选出的周期时间和绿信比在概率意义下的合理性有很大提高。但是，这又带来了下面的问题。
2. 需要经常调节控制规律。首先是因为城市土地结构变化很快而带来的车流量变化很快。以往的数据很快便失去了实用价值。因此优化方案不在最优甚至不合理，需要重新进行数据收集，最优方案选择等工作。这一点对发展中城市更为明显。其次是同一路口 、同一方面在每星期中各天的流量是不同的，每天中高峰、平峰、低峰时交通也是不一样的，这些都要求按预先算好的时刻表、日期表调换周期时间和绿信比，局限性很大。并且交通流量的随机性越大，其缺点与明显。
3. 没有考虑各交叉路口的联系。“单点”即指各路口各自进行控制，不管邻近路口的信号灯翻转规律如何。这种各个路口互不配合、互不协调的控制方式人为地给交通流的流动设置了许多阻力。
（二）、信息流通条件极差，无法对乘客和车辆进行诱导和管理。这个问题在交通网络运行畅通的情况下并不明显，但当交通堵塞、交通事故等紧急事件发生时就显得非常突出。然而这些紧急事件却常有发生。每当这时，公共汽车调度站无法知道路上的情况，从而无法对公共汽车的线路、发车频次作恰当调整；其他车辆的司机也得不到信息无法选择较为畅通的线路；在公共汽车站等车的乘客也无法做出决策，是继续等车或是换乘其他车次或是步行等。实际上在许多情况下，只要进行恰当的诱导，道路的拥挤状况就会大大缓解或保证畅通。例如：1984年洛杉矶奥运会期间，由于采用了大量的动态路标显示板，诱导车辆选择恰当的路线，因而，尽管车辆较平时增多很多，但网络中交通流的运行状况却比平时还好。
（三）、停车场的能力不够，位置也不当。这是多年延续下来的旧病，只修路不修停车场。比如，成都火车站东西二环路，那里的批发市场很多，但是，无合理的停车场，大多数司机将车直接停放在街道上，这样严重影响了道路的通行能力。应该将停车场向专门化，地下化发展，在宾馆，商场，机关大楼，居民大楼的地下设置社会化的停车场是解决城市交通拥挤，堵塞的一条行之有效的办法。
交通运输是一个复杂的大系统，这个系统必须在严格科学的制度下运行，它不是一个自适应系统，任何违反规章制度的行为都可能导致大系统的局部、甚至“整体”的瘫痪。
交通拥挤和堵塞对策从总体上可分为三大类：
（1） 加强道路建设，以提高交通网络的交通容量；
（2） 加强交通运用与管理以充分发挥现有道路设施的作用，使得交通网络的使用效率最大；
（3） 全面实施交通需求管理以使交通需求在时间、空间上均匀化，交通结构合理化。由于交通基础设施建设工期长，耗资大，在当前资金有限的条件下，解决特定的城市交通问题时，必须事先进行对策的效果分析。
如前所述，要想比较有效的解决城市的交通拥挤，堵塞问题不能单纯的只依靠增加道路面积和长度，而要不断的完善路网系统，调整路网结构和加强交通管理的现代化，以及对单个车辆的控制及引导。首先就交通流量的静态情形是一种理想状态，既假设在一个城市街区内车流速度一定，对单个车辆的控制及引导进行研究分析，给出调控标准。
交通道路网的拓扑性质可以用图论的基本原理来分析。图由“弧”和“顶点”两部分组成，交通道路网的拓扑模型可以抽象认为是由节点（交叉路口）以及弧（道路）组成的有向图。边的方向就是车流的方向。由于道路和交叉路口都有很多属性，这样就可以把始发地和目的地之间的区域交通网抽象成了多属性赋权有向图。
假设：
1. 所有道路一样宽；
2. 每一条道路都不需停车等待；
3. 车流速度恒定；
4. 道路长已知。
5. 从 点到 点所用时间仅与路长有关。
不考虑意外事故对交通的影响。车子所在地设为 点，目的地设为 点。于是车子所要走的路线就可以用P来表述。
： , 两点间距离
v：车流速度
t：从始发地 到目的地 的时间
：P中所有弧长之和
表示道路状况的权重
表示车流速度改变而赋给道路的权重
表示
模型建立
由于假设车速恒定，由 可知，要求从始发地 到目的地 用时最短就可以转化为求道路最短。此时问题可以用以下数学模型描述:
（ * ）
我们将城市道路网描述为一赋权有向图D=(V,U)对每一条有向边 ∈U都存在一l 与这对应，其表示道路两结点间的距离，称之为有向边 的权。
＝
模型的求解
在赋权有向图中，我们选定某个起点 ，终点 .采用迪克特拉（E.W.Dijkstra）算法。Dijkstra方法的基本思想是从 出发，逐步地向外探寻最短路。执行过程中，与每一个点对应，记录下一个数（称为这个点的标号），它或者表示从 到该点的最短路的权（称为P标号）、或者是从 到该点的最短路的权的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p-1步，就可以求出从 到各点的最短路。
对静态的交通加权最短路问题进行了数学建模，但是实际状态中，还有许多因素影响交通运行时间，譬如道路宽度不尽相同，会使车辆流率不同（车流量的大小用车流率表示，车流率是道路上某点单位时间内到达或离开的车辆数，简称流率）；时段高峰期，会造成某一路段在某一时段交通拥挤甚至阻塞，从而使得车流速度降低等，也就是只从静态考虑了实际问题。这一些个因素没有考虑进去，按照理想模型来分析，会导致估计结果粗糙从而失真，不能有效地对单个车辆进行引导控制。于是我们在前面假设的基础上再进行模型的修改：当流量处于动态变化时，把道路宽度，交通阻塞等因素考虑进去。这样一来定点路段上的车行最短时间的问题上比静态情形复杂很多，我们采用因素转化法，将多因素变量转化为单因素变量来建立优化模型。
首先我们可以利用自动的交通检测装置来测量交通网络中各个不同部分的交通流状态，再通过一些电讯设备将这些检测到的信息送到控制中心或电台等，这样就可以知道某一时刻的各个路段的交通状况，从而为我们对司机的行车进行引导提供了信息。
由于加入了影响因素，车流速度随着高峰期拥堵而在一个时间段有所改变。由 知，求用时最短的方案必然有所改变。但是我们可以将车速改变转化为路长改变，即对道路加权改为随时间变化的函数，如速度增大则道路权为正小数，速度减小则把权设为正整数，使得要求用时最短仍能转变成求道路最短。
刚才考虑了车流速度改变的情况，现在来看看交通状况改变，譬如发生交通意外而使道路瘫痪不能行车，或是时段高峰期使得交通拥挤等。这时我们仍可以在一个时间段对道路加权来使问题转变成静态模型，即求道路最短模型。道路的权重可以通过经验给出。当道路不能畅通无阻时，我们设其权重为大于1的正整数，反之设为1。
仍同初始交通加权最短路问题一样，可将始发地和目的地之间的区域交通网抽象成多属性赋权有向图。
由自动的交通检测装置反馈来的数据信息，我们可以给一条道路赋予一定的权重，根据情况程度决定具体权重。
当道路因各种原因使得车流速度受到影响时，我们可以把权重 取值范围设定为〔1，∞），其中 =∞ 表示道路严重阻塞，车辆不能通行； =1 表示车流速度不受影响，可以自由行驶。车流速度改变后，我们可以把权重 的取值范围设定为（0，∞），当 时，表示车流速度增大； 时，表示车流速度减小； =1时，则表示与初始速度相比没有改变。
由以上所述，我们可以把模型建立为
（ ** ）
虽然每一时刻道路状况，车流速度不尽相同，但是经过转换，形成以上模型，就只是参数变化而已，如此一来仍然可以用初始最短路问题的模型求解，这样就大大简化了问题。
在下述Dijkstra方法具体求解步骤中，用P,T分别表示某个点的P标号、T标号， 表示第i步时，具P标号点的集合。为了在求出从 到各点的距离的同时，也求出从 到各点的最短路，给每个点 以一个 值，算法终止时，如果 ，表示在从 到 的最短路上， 的前一个点是 ；如果 ，则表示D中不含从 到 的路； 表示 = 。其中M表示无穷大的数。
模型检验与实用性研究
前面给出了一般性的优化模型，现在我们举个例子对模型进行计算。
如图所示，这是一个单行线交通网，车辆以速度v行驶，每弧旁的数字表示两点间相对距离。现在某出租车要从 出发，通过这个交通网到 去，求所用时间最短的路线。
图5-1
由 可知，若速度等因素没有改变时，根据模型（ * ），用Dijkstra算法直接求解，得从 到 的最短路是 。
假设，此时速度或道路状况改变，则根据模型（ ** ）我们可以得：
不妨设此时车已开向 ，并且车速变为2v（ =0.5）， 到 的路上由于上班高峰期造成了阻塞( =5)， 到 的道路由于不是主干道车流较之前减少畅通率提高 ( =0.6)，其他道路状况没有改变( =1)。此时根据模型（ ** ）：
可求得从 到 用时间最短路线为
实用性研究
优化后的模型，对于实际交通流量控制有着较好的导控作用。在运用此模型时，可通过三个设备获取数据，实现可行性。第一个是车辆设备，二是路边设备，三是控制中心。
车辆设备包括：
⑴ 接收由驾驶员输入数据的操作键盘；
⑵ 从路旁通讯设备接收数据和向该设备发送数据的收发部件；
⑶ 能提供从路旁通讯设备接收到的数据的现实控制板；
⑷ 接收来自路边或中心广播设备传送来的信息的接口。
路边设备包括：
⑴ 记录从中心处理设备传来的数据的路边通讯设备，以及通过嵌入路面的环形线圈和车辆天线与单个车辆进行双向通讯。
⑵ 直接用电缆线来连接中心控制与路边广播设备，再进行车辆通讯。⑶ 自动的交通检测装置，可测量车辆速度以及检测道路状况。
这样，司机把一个他所希望的终点站代码输入到安装在车内的键盘，一旦车辆接近确定的地点时，车上的微型计算机通过车辆天线和一个嵌入路面的回路线圈向路边微机设备传送存贮的代码数据，此微机再将代码数据反馈回控制中心，控制中心利用本文优化模型及给出的算法进行求解，得出合理的行驶路线，经由路边设备反馈给车上的微型计算机，司机通过显示器可以获取最短路线。
由于交通不是单个车辆的，而是众多车辆参与在内的运行，因此交通状况时刻可能改变，这将影响单个车辆行驶路线的改变。本文的导控考虑到此种情况，将导控分时间段进行：
表5-1
低谷期
5:00-
7:30 高峰期
7:30-
9:00 中间期
9:00-
12:00 高峰期
12:00-
13:00 中间期
13:00-
17:30- 高峰期
17:30-
19:00 低谷期
19:00-
23:00
在低谷期内的反馈周期为30分钟，中间期为15分钟，而高峰期则为5分钟一次，因为高峰期道路状况改变快，因此反馈给司机的数据间隔也不能太长。这样就使得本文的模型更具可行性。
关键词：交通流, 实时最优控制, 道路加权, Dijkstra 方法
随着国民经济的持续、高速发展，各种机动车尤其是私家车拥有量急剧增加带来了交通运输业的空前繁荣。但是，大多数城市的交通已从过去的局部拥挤演变成为当今的大范围全面紧张，如我国的一个大城市，当处于早晚交通高峰时，交叉路口处的阻车长度长达1000多米，有的阻车车队从一个交叉路口延伸到另一个交叉路口，这时一辆车为通过一个交叉路口，往往需要半个小时以上，还不如步行快，这给城市交通带来了难以承受的负荷。拥挤不仅带来时间的浪费，还导致公交系统运行的无规则性，如公交汽车不能按时到站等，使人们对自己的旅行时间无法估计，耽误工作和计划等。这种紧张状况日趋严重，已成为大城市突出的社会问题之一，也成为国民经济进一步发展的“瓶颈”问题。因此，必须面对现实，解决城市的交通拥挤，堵塞问题。
那么城市交通拥挤、堵塞原因何在呢？分析如下：
（一）、现行交通信号控制方法中交通信号与交通流量不适应。目前，各城市交叉路口使用最为广泛的是单点定周期控制方式。这种控制方式存在的问题有以下几个方面：
1. 对交通流的随机变化无适应能力。由于是定周期方法，因此一旦周期时间和绿信比选定之后，一般就不再经常改动。而交通网络中车流、人流的变化是随机的、经常的，各个周期中交叉路口同一方向上通过的流量可能差异很大。不同的流量对绿灯时间有着不同的要求。所以此种控制方式给出的信号常常不能与客观实际车流的随机变化相适应。我们常常遇到这样的情况：有车辆等待通过的方向信号是红灯，而与此同时无车辆方向的信号却是绿灯，白白浪费了现有路口通行能力。为了克服这一缺点，人们考虑运用概率、统计的方法，在收集了大量交通数据的基础上，对周期时间和绿信比进行离线优化选择，使选出的周期时间和绿信比在概率意义下的合理性有很大提高。但是，这又带来了下面的问题。
2. 需要经常调节控制规律。首先是因为城市土地结构变化很快而带来的车流量变化很快。以往的数据很快便失去了实用价值。因此优化方案不在最优甚至不合理，需要重新进行数据收集，最优方案选择等工作。这一点对发展中城市更为明显。其次是同一路口 、同一方面在每星期中各天的流量是不同的，每天中高峰、平峰、低峰时交通也是不一样的，这些都要求按预先算好的时刻表、日期表调换周期时间和绿信比，局限性很大。并且交通流量的随机性越大，其缺点与明显。
3. 没有考虑各交叉路口的联系。“单点”即指各路口各自进行控制，不管邻近路口的信号灯翻转规律如何。这种各个路口互不配合、互不协调的控制方式人为地给交通流的流动设置了许多阻力。
（二）、信息流通条件极差，无法对乘客和车辆进行诱导和管理。这个问题在交通网络运行畅通的情况下并不明显，但当交通堵塞、交通事故等紧急事件发生时就显得非常突出。然而这些紧急事件却常有发生。每当这时，公共汽车调度站无法知道路上的情况，从而无法对公共汽车的线路、发车频次作恰当调整；其他车辆的司机也得不到信息无法选择较为畅通的线路；在公共汽车站等车的乘客也无法做出决策，是继续等车或是换乘其他车次或是步行等。实际上在许多情况下，只要进行恰当的诱导，道路的拥挤状况就会大大缓解或保证畅通。例如：1984年洛杉矶奥运会期间，由于采用了大量的动态路标显示板，诱导车辆选择恰当的路线，因而，尽管车辆较平时增多很多，但网络中交通流的运行状况却比平时还好。
（三）、停车场的能力不够，位置也不当。这是多年延续下来的旧病，只修路不修停车场。比如，成都火车站东西二环路，那里的批发市场很多，但是，无合理的停车场，大多数司机将车直接停放在街道上，这样严重影响了道路的通行能力。应该将停车场向专门化，地下化发展，在宾馆，商场，机关大楼，居民大楼的地下设置社会化的停车场是解决城市交通拥挤，堵塞的一条行之有效的办法。
交通运输是一个复杂的大系统，这个系统必须在严格科学的制度下运行，它不是一个自适应系统，任何违反规章制度的行为都可能导致大系统的局部、甚至“整体”的瘫痪。
交通拥挤和堵塞对策从总体上可分为三大类：
（1） 加强道路建设，以提高交通网络的交通容量；
（2） 加强交通运用与管理以充分发挥现有道路设施的作用，使得交通网络的使用效率最大；
（3） 全面实施交通需求管理以使交通需求在时间、空间上均匀化，交通结构合理化。由于交通基础设施建设工期长，耗资大，在当前资金有限的条件下，解决特定的城市交通问题时，必须事先进行对策的效果分析。
如前所述，要想比较有效的解决城市的交通拥挤，堵塞问题不能单纯的只依靠增加道路面积和长度，而要不断的完善路网系统，调整路网结构和加强交通管理的现代化，以及对单个车辆的控制及引导。首先就交通流量的静态情形是一种理想状态，既假设在一个城市街区内车流速度一定，对单个车辆的控制及引导进行研究分析，给出调控标准。
交通道路网的拓扑性质可以用图论的基本原理来分析。图由“弧”和“顶点”两部分组成，交通道路网的拓扑模型可以抽象认为是由节点（交叉路口）以及弧（道路）组成的有向图。边的方向就是车流的方向。由于道路和交叉路口都有很多属性，这样就可以把始发地和目的地之间的区域交通网抽象成了多属性赋权有向图。
假设：
1. 所有道路一样宽；
2. 每一条道路都不需停车等待；
3. 车流速度恒定；
4. 道路长已知。
5. 从 点到 点所用时间仅与路长有关。
不考虑意外事故对交通的影响。车子所在地设为 点，目的地设为 点。于是车子所要走的路线就可以用P来表述。
： , 两点间距离
v：车流速度
t：从始发地 到目的地 的时间
：P中所有弧长之和
表示道路状况的权重
表示车流速度改变而赋给道路的权重
表示
模型建立
由于假设车速恒定，由 可知，要求从始发地 到目的地 用时最短就可以转化为求道路最短。此时问题可以用以下数学模型描述:
（ * ）
我们将城市道路网描述为一赋权有向图D=(V,U)对每一条有向边 ∈U都存在一l 与这对应，其表示道路两结点间的距离，称之为有向边 的权。
＝
模型的求解
在赋权有向图中，我们选定某个起点 ，终点 .采用迪克特拉（E.W.Dijkstra）算法。Dijkstra方法的基本思想是从 出发，逐步地向外探寻最短路。执行过程中，与每一个点对应，记录下一个数（称为这个点的标号），它或者表示从 到该点的最短路的权（称为P标号）、或者是从 到该点的最短路的权的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p-1步，就可以求出从 到各点的最短路。
对静态的交通加权最短路问题进行了数学建模，但是实际状态中，还有许多因素影响交通运行时间，譬如道路宽度不尽相同，会使车辆流率不同（车流量的大小用车流率表示，车流率是道路上某点单位时间内到达或离开的车辆数，简称流率）；时段高峰期，会造成某一路段在某一时段交通拥挤甚至阻塞，从而使得车流速度降低等，也就是只从静态考虑了实际问题。这一些个因素没有考虑进去，按照理想模型来分析，会导致估计结果粗糙从而失真，不能有效地对单个车辆进行引导控制。于是我们在前面假设的基础上再进行模型的修改：当流量处于动态变化时，把道路宽度，交通阻塞等因素考虑进去。这样一来定点路段上的车行最短时间的问题上比静态情形复杂很多，我们采用因素转化法，将多因素变量转化为单因素变量来建立优化模型。
首先我们可以利用自动的交通检测装置来测量交通网络中各个不同部分的交通流状态，再通过一些电讯设备将这些检测到的信息送到控制中心或电台等，这样就可以知道某一时刻的各个路段的交通状况，从而为我们对司机的行车进行引导提供了信息。
由于加入了影响因素，车流速度随着高峰期拥堵而在一个时间段有所改变。由 知，求用时最短的方案必然有所改变。但是我们可以将车速改变转化为路长改变，即对道路加权改为随时间变化的函数，如速度增大则道路权为正小数，速度减小则把权设为正整数，使得要求用时最短仍能转变成求道路最短。
刚才考虑了车流速度改变的情况，现在来看看交通状况改变，譬如发生交通意外而使道路瘫痪不能行车，或是时段高峰期使得交通拥挤等。这时我们仍可以在一个时间段对道路加权来使问题转变成静态模型，即求道路最短模型。道路的权重可以通过经验给出。当道路不能畅通无阻时，我们设其权重为大于1的正整数，反之设为1。
仍同初始交通加权最短路问题一样，可将始发地和目的地之间的区域交通网抽象成多属性赋权有向图。
由自动的交通检测装置反馈来的数据信息，我们可以给一条道路赋予一定的权重，根据情况程度决定具体权重。
当道路因各种原因使得车流速度受到影响时，我们可以把权重 取值范围设定为〔1，∞），其中 =∞ 表示道路严重阻塞，车辆不能通行； =1 表示车流速度不受影响，可以自由行驶。车流速度改变后，我们可以把权重 的取值范围设定为（0，∞），当 时，表示车流速度增大； 时，表示车流速度减小； =1时，则表示与初始速度相比没有改变。
由以上所述，我们可以把模型建立为
（ ** ）
虽然每一时刻道路状况，车流速度不尽相同，但是经过转换，形成以上模型，就只是参数变化而已，如此一来仍然可以用初始最短路问题的模型求解，这样就大大简化了问题。
在下述Dijkstra方法具体求解步骤中，用P,T分别表示某个点的P标号、T标号， 表示第i步时，具P标号点的集合。为了在求出从 到各点的距离的同时，也求出从 到各点的最短路，给每个点 以一个 值，算法终止时，如果 ，表示在从 到 的最短路上， 的前一个点是 ；如果 ，则表示D中不含从 到 的路； 表示 = 。其中M表示无穷大的数。
模型检验与实用性研究
前面给出了一般性的优化模型，现在我们举个例子对模型进行计算。
如图所示，这是一个单行线交通网，车辆以速度v行驶，每弧旁的数字表示两点间相对距离。现在某出租车要从 出发，通过这个交通网到 去，求所用时间最短的路线。
图5-1
由 可知，若速度等因素没有改变时，根据模型（ * ），用Dijkstra算法直接求解，得从 到 的最短路是 。
假设，此时速度或道路状况改变，则根据模型（ ** ）我们可以得：
不妨设此时车已开向 ，并且车速变为2v（ =0.5）， 到 的路上由于上班高峰期造成了阻塞( =5)， 到 的道路由于不是主干道车流较之前减少畅通率提高 ( =0.6)，其他道路状况没有改变( =1)。此时根据模型（ ** ）：
可求得从 到 用时间最短路线为
实用性研究
优化后的模型，对于实际交通流量控制有着较好的导控作用。在运用此模型时，可通过三个设备获取数据，实现可行性。第一个是车辆设备，二是路边设备，三是控制中心。
车辆设备包括：
⑴ 接收由驾驶员输入数据的操作键盘；
⑵ 从路旁通讯设备接收数据和向该设备发送数据的收发部件；
⑶ 能提供从路旁通讯设备接收到的数据的现实控制板；
⑷ 接收来自路边或中心广播设备传送来的信息的接口。
路边设备包括：
⑴ 记录从中心处理设备传来的数据的路边通讯设备，以及通过嵌入路面的环形线圈和车辆天线与单个车辆进行双向通讯。
⑵ 直接用电缆线来连接中心控制与路边广播设备，再进行车辆通讯。⑶ 自动的交通检测装置，可测量车辆速度以及检测道路状况。
这样，司机把一个他所希望的终点站代码输入到安装在车内的键盘，一旦车辆接近确定的地点时，车上的微型计算机通过车辆天线和一个嵌入路面的回路线圈向路边微机设备传送存贮的代码数据，此微机再将代码数据反馈回控制中心，控制中心利用本文优化模型及给出的算法进行求解，得出合理的行驶路线，经由路边设备反馈给车上的微型计算机，司机通过显示器可以获取最短路线。
由于交通不是单个车辆的，而是众多车辆参与在内的运行，因此交通状况时刻可能改变，这将影响单个车辆行驶路线的改变。本文的导控考虑到此种情况，将导控分时间段进行：
表5-1
低谷期
5:00-
7:30 高峰期
7:30-
9:00 中间期
9:00-
12:00 高峰期
12:00-
13:00 中间期
13:00-
17:30- 高峰期
17:30-
19:00 低谷期
19:00-
23:00
在低谷期内的反馈周期为30分钟，中间期为15分钟，而高峰期则为5分钟一次，因为高峰期道路状况改变快，因此反馈给司机的数据间隔也不能太长。这样就使得本文的模型更具可行性。
温馨提示：内容为网友见解，仅供参考
第1个回答 2007-04-30
通过将车流量的增大或减小转化为路长权重的变化。将交通流量的动态问题转化为静态问题，用解决最短路问题的Dijkstra 方法，给出交通流量实时最优控制的可行性模型及其有效算法。
关键词：交通流, 实时最优控制, 道路加权, Dijkstra 方法
随着国民经济的持续、高速发展，各种机动车尤其是私家车拥有量急剧增加带来了交通运输业的空前繁荣。但是，大多数城市的交通已从过去的局部拥挤演变成为当今的大范围全面紧张，如我国的一个大城市，当处于早晚交通高峰时，交叉路口处的阻车长度长达1000多米，有的阻车车队从一个交叉路口延伸到另一个交叉路口，这时一辆车为通过一个交叉路口，往往需要半个小时以上，还不如步行快，这给城市交通带来了难以承受的负荷。拥挤不仅带来时间的浪费，还导致公交系统运行的无规则性，如公交汽车不能按时到站等，使人们对自己的旅行时间无法估计，耽误工作和计划等。这种紧张状况日趋严重，已成为大城市突出的社会问题之一，也成为国民经济进一步发展的“瓶颈”问题。因此，必须面对现实，解决城市的交通拥挤，堵塞问题。
那么城市交通拥挤、堵塞原因何在呢？分析如下：
（一）、现行交通信号控制方法中交通信号与交通流量不适应。目前，各城市交叉路口使用最为广泛的是单点定周期控制方式。这种控制方式存在的问题有以下几个方面：
1. 对交通流的随机变化无适应能力。由于是定周期方法，因此一旦周期时间和绿信比选定之后，一般就不再经常改动。而交通网络中车流、人流的变化是随机的、经常的，各个周期中交叉路口同一方向上通过的流量可能差异很大。不同的流量对绿灯时间有着不同的要求。所以此种控制方式给出的信号常常不能与客观实际车流的随机变化相适应。我们常常遇到这样的情况：有车辆等待通过的方向信号是红灯，而与此同时无车辆方向的信号却是绿灯，白白浪费了现有路口通行能力。为了克服这一缺点，人们考虑运用概率、统计的方法，在收集了大量交通数据的基础上，对周期时间和绿信比进行离线优化选择，使选出的周期时间和绿信比在概率意义下的合理性有很大提高。但是，这又带来了下面的问题。
2. 需要经常调节控制规律。首先是因为城市土地结构变化很快而带来的车流量变化很快。以往的数据很快便失去了实用价值。因此优化方案不在最优甚至不合理，需要重新进行数据收集，最优方案选择等工作。这一点对发展中城市更为明显。其次是同一路口 、同一方面在每星期中各天的流量是不同的，每天中高峰、平峰、低峰时交通也是不一样的，这些都要求按预先算好的时刻表、日期表调换周期时间和绿信比，局限性很大。并且交通流量的随机性越大，其缺点与明显。
3. 没有考虑各交叉路口的联系。“单点”即指各路口各自进行控制，不管邻近路口的信号灯翻转规律如何。这种各个路口互不配合、互不协调的控制方式人为地给交通流的流动设置了许多阻力。
（二）、信息流通条件极差，无法对乘客和车辆进行诱导和管理。这个问题在交通网络运行畅通的情况下并不明显，但当交通堵塞、交通事故等紧急事件发生时就显得非常突出。然而这些紧急事件却常有发生。每当这时，公共汽车调度站无法知道路上的情况，从而无法对公共汽车的线路、发车频次作恰当调整；其他车辆的司机也得不到信息无法选择较为畅通的线路；在公共汽车站等车的乘客也无法做出决策，是继续等车或是换乘其他车次或是步行等。实际上在许多情况下，只要进行恰当的诱导，道路的拥挤状况就会大大缓解或保证畅通。例如：1984年洛杉矶奥运会期间，由于采用了大量的动态路标显示板，诱导车辆选择恰当的路线，因而，尽管车辆较平时增多很多，但网络中交通流的运行状况却比平时还好。
（三）、停车场的能力不够，位置也不当。这是多年延续下来的旧病，只修路不修停车场。比如，成都火车站东西二环路，那里的批发市场很多，但是，无合理的停车场，大多数司机将车直接停放在街道上，这样严重影响了道路的通行能力。应该将停车场向专门化，地下化发展，在宾馆，商场，机关大楼，居民大楼的地下设置社会化的停车场是解决城市交通拥挤，堵塞的一条行之有效的办法。
交通运输是一个复杂的大系统，这个系统必须在严格科学的制度下运行，它不是一个自适应系统，任何违反规章制度的行为都可能导致大系统的局部、甚至“整体”的瘫痪。
交通拥挤和堵塞对策从总体上可分为三大类：
（1） 加强道路建设，以提高交通网络的交通容量；
（2） 加强交通运用与管理以充分发挥现有道路设施的作用，使得交通网络的使用效率最大；
（3） 全面实施交通需求管理以使交通需求在时间、空间上均匀化，交通结构合理化。由于交通基础设施建设工期长，耗资大，在当前资金有限的条件下，解决特定的城市交通问题时，必须事先进行对策的效果分析。
如前所述，要想比较有效的解决城市的交通拥挤，堵塞问题不能单纯的只依靠增加道路面积和长度，而要不断的完善路网系统，调整路网结构和加强交通管理的现代化，以及对单个车辆的控制及引导。首先就交通流量的静态情形是一种理想状态，既假设在一个城市街区内车流速度一定，对单个车辆的控制及引导进行研究分析，给出调控标准。
交通道路网的拓扑性质可以用图论的基本原理来分析。图由“弧”和“顶点”两部分组成，交通道路网的拓扑模型可以抽象认为是由节点（交叉路口）以及弧（道路）组成的有向图。边的方向就是车流的方向。由于道路和交叉路口都有很多属性，这样就可以把始发地和目的地之间的区域交通网抽象成了多属性赋权有向图。
假设：
1. 所有道路一样宽；
2. 每一条道路都不需停车等待；
3. 车流速度恒定；
4. 道路长已知。
5. 从 点到 点所用时间仅与路长有关。
不考虑意外事故对交通的影响。车子所在地设为 点，目的地设为 点。于是车子所要走的路线就可以用P来表述。
： , 两点间距离
v：车流速度
t：从始发地 到目的地 的时间
：P中所有弧长之和
表示道路状况的权重
表示车流速度改变而赋给道路的权重
表示
模型建立
由于假设车速恒定，由 可知，要求从始发地 到目的地 用时最短就可以转化为求道路最短。此时问题可以用以下数学模型描述:
（ * ）
我们将城市道路网描述为一赋权有向图D=(V,U)对每一条有向边 ∈U都存在一l 与这对应，其表示道路两结点间的距离，称之为有向边 的权。
＝
模型的求解
在赋权有向图中，我们选定某个起点 ，终点 .采用迪克特拉（E.W.Dijkstra）算法。Dijkstra方法的基本思想是从 出发，逐步地向外探寻最短路。执行过程中，与每一个点对应，记录下一个数（称为这个点的标号），它或者表示从 到该点的最短路的权（称为P标号）、或者是从 到该点的最短路的权的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p-1步，就可以求出从 到各点的最短路。
对静态的交通加权最短路问题进行了数学建模，但是实际状态中，还有许多因素影响交通运行时间，譬如道路宽度不尽相同，会使车辆流率不同（车流量的大小用车流率表示，车流率是道路上某点单位时间内到达或离开的车辆数，简称流率）；时段高峰期，会造成某一路段在某一时段交通拥挤甚至阻塞，从而使得车流速度降低等，也就是只从静态考虑了实际问题。这一些个因素没有考虑进去，按照理想模型来分析，会导致估计结果粗糙从而失真，不能有效地对单个车辆进行引导控制。于是我们在前面假设的基础上再进行模型的修改：当流量处于动态变化时，把道路宽度，交通阻塞等因素考虑进去。这样一来定点路段上的车行最短时间的问题上比静态情形复杂很多，我们采用因素转化法，将多因素变量转化为单因素变量来建立优化模型。
首先我们可以利用自动的交通检测装置来测量交通网络中各个不同部分的交通流状态，再通过一些电讯设备将这些检测到的信息送到控制中心或电台等，这样就可以知道某一时刻的各个路段的交通状况，从而为我们对司机的行车进行引导提供了信息。
由于加入了影响因素，车流速度随着高峰期拥堵而在一个时间段有所改变。由 知，求用时最短的方案必然有所改变。但是我们可以将车速改变转化为路长改变，即对道路加权改为随时间变化的函数，如速度增大则道路权为正小数，速度减小则把权设为正整数，使得要求用时最短仍能转变成求道路最短。
刚才考虑了车流速度改变的情况，现在来看看交通状况改变，譬如发生交通意外而使道路瘫痪不能行车，或是时段高峰期使得交通拥挤等。这时我们仍可以在一个时间段对道路加权来使问题转变成静态模型，即求道路最短模型。道路的权重可以通过经验给出。当道路不能畅通无阻时，我们设其权重为大于1的正整数，反之设为1。
仍同初始交通加权最短路问题一样，可将始发地和目的地之间的区域交通网抽象成多属性赋权有向图。
由自动的交通检测装置反馈来的数据信息，我们可以给一条道路赋予一定的权重，根据情况程度决定具体权重。
当道路因各种原因使得车流速度受到影响时，我们可以把权重 取值范围设定为〔1，∞），其中 =∞ 表示道路严重阻塞，车辆不能通行； =1 表示车流速度不受影响，可以自由行驶。车流速度改变后，我们可以把权重 的取值范围设定为（0，∞），当 时，表示车流速度增大； 时，表示车流速度减小； =1时，则表示与初始速度相比没有改变。
由以上所述，我们可以把模型建立为
（ ** ）
虽然每一时刻道路状况，车流速度不尽相同，但是经过转换，形成以上模型，就只是参数变化而已，如此一来仍然可以用初始最短路问题的模型求解，这样就大大简化了问题。
在下述Dijkstra方法具体求解步骤中，用P,T分别表示某个点的P标号、T标号， 表示第i步时，具P标号点的集合。为了在求出从 到各点的距离的同时，也求出从 到各点的最短路，给每个点 以一个 值，算法终止时，如果 ，表示在从 到 的最短路上， 的前一个点是 ；如果 ，则表示D中不含从 到 的路； 表示 = 。其中M表示无穷大的数。
模型检验与实用性研究
前面给出了一般性的优化模型，现在我们举个例子对模型进行计算。
如图所示，这是一个单行线交通网，车辆以速度v行驶，每弧旁的数字表示两点间相对距离。现在某出租车要从 出发，通过这个交通网到 去，求所用时间最短的路线。
图5-1
由 可知，若速度等因素没有改变时，根据模型（ * ），用Dijkstra算法直接求解，得从 到 的最短路是 。
假设，此时速度或道路状况改变，则根据模型（ ** ）我们可以得：
不妨设此时车已开向 ，并且车速变为2v（ =0.5）， 到 的路上由于上班高峰期造成了阻塞( =5)， 到 的道路由于不是主干道车流较之前减少畅通率提高 ( =0.6)，其他道路状况没有改变( =1)。此时根据模型（ ** ）：
可求得从 到 用时间最短路线为
实用性研究
优化后的模型，对于实际交通流量控制有着较好的导控作用。在运用此模型时，可通过三个设备获取数据，实现可行性。第一个是车辆设备，二是路边设备，三是控制中心。
车辆设备包括：
⑴ 接收由驾驶员输入数据的操作键盘；
⑵ 从路旁通讯设备接收数据和向该设备发送数据的收发部件；
⑶ 能提供从路旁通讯设备接收到的数据的现实控制板；
⑷ 接收来自路边或中心广播设备传送来的信息的接口。
路边设备包括：
⑴ 记录从中心处理设备传来的数据的路边通讯设备，以及通过嵌入路面的环形线圈和车辆天线与单个车辆进行双向通讯。
⑵ 直接用电缆线来连接中心控制与路边广播设备，再进行车辆通讯。⑶ 自动的交通检测装置，可测量车辆速度以及检测道路状况。
这样，司机把一个他所希望的终点站代码输入到安装在车内的键盘，一旦车辆接近确定的地点时，车上的微型计算机通过车辆天线和一个嵌入路面的回路线圈向路边微机设备传送存贮的代码数据，此微机再将代码数据反馈回控制中心，控制中心利用本文优化模型及给出的算法进行求解，得出合理的行驶路线，经由路边设备反馈给车上的微型计算机，司机通过显示器可以获取最短路线。
由于交通不是单个车辆的，而是众多车辆参与在内的运行，因此交通状况时刻可能改变，这将影响单个车辆行驶路线的改变。本文的导控考虑到此种情况，将导控分时间段进行：
表5-1
低谷期
5:00-
7:30 高峰期
7:30-
9:00 中间期
9:00-
12:00 高峰期
12:00-
13:00 中间期
13:00-
17:30- 高峰期
17:30-
19:00 低谷期
19:00-
23:00
在低谷期内的反馈周期为30分钟，中间期为15分钟，而高峰期则为5分钟一次，因为高峰期道路状况改变快，因此反馈给司机的数据间隔也不能太长。这样就使得本文的模型更具可行性。
参考文献
[1] 徐吉万、徐冬玲著：《城市交通的计算机控制与管理》，测绘出版社，1988年版
[2] 张建仁等著：《中国交通研究与探索》，人民交通出版社，2003年版
[3] 钱颂迪等著，《运筹学》，清华大学出版社，修订版
[4] 严蔚敏、吴伟民著，《数据结构》，清华大学出版社，C语言版
[5] 唐发根，《数据结构》，科学出版社，2003年9月
[6] 吴孟达、成礼智著，《数学建模的理论与实践》，国防科技大学出版社，1999年8月
Abstract
The volume of traffic is changed into weight of road, so the dynamic problem is changed into static problem, by Dijkstra method of the shortest circuit, get the feasible model of immediately control of traffic and
A effective algorithm.
Key Words: traffic flow , immediately control, adding weight to the road, method of Dijkstr.
关键词：交通流, 实时最优控制, 道路加权, Dijkstra 方法
随着国民经济的持续、高速发展，各种机动车尤其是私家车拥有量急剧增加带来了交通运输业的空前繁荣。但是，大多数城市的交通已从过去的局部拥挤演变成为当今的大范围全面紧张，如我国的一个大城市，当处于早晚交通高峰时，交叉路口处的阻车长度长达1000多米，有的阻车车队从一个交叉路口延伸到另一个交叉路口，这时一辆车为通过一个交叉路口，往往需要半个小时以上，还不如步行快，这给城市交通带来了难以承受的负荷。拥挤不仅带来时间的浪费，还导致公交系统运行的无规则性，如公交汽车不能按时到站等，使人们对自己的旅行时间无法估计，耽误工作和计划等。这种紧张状况日趋严重，已成为大城市突出的社会问题之一，也成为国民经济进一步发展的“瓶颈”问题。因此，必须面对现实，解决城市的交通拥挤，堵塞问题。
那么城市交通拥挤、堵塞原因何在呢？分析如下：
（一）、现行交通信号控制方法中交通信号与交通流量不适应。目前，各城市交叉路口使用最为广泛的是单点定周期控制方式。这种控制方式存在的问题有以下几个方面：
1. 对交通流的随机变化无适应能力。由于是定周期方法，因此一旦周期时间和绿信比选定之后，一般就不再经常改动。而交通网络中车流、人流的变化是随机的、经常的，各个周期中交叉路口同一方向上通过的流量可能差异很大。不同的流量对绿灯时间有着不同的要求。所以此种控制方式给出的信号常常不能与客观实际车流的随机变化相适应。我们常常遇到这样的情况：有车辆等待通过的方向信号是红灯，而与此同时无车辆方向的信号却是绿灯，白白浪费了现有路口通行能力。为了克服这一缺点，人们考虑运用概率、统计的方法，在收集了大量交通数据的基础上，对周期时间和绿信比进行离线优化选择，使选出的周期时间和绿信比在概率意义下的合理性有很大提高。但是，这又带来了下面的问题。
2. 需要经常调节控制规律。首先是因为城市土地结构变化很快而带来的车流量变化很快。以往的数据很快便失去了实用价值。因此优化方案不在最优甚至不合理，需要重新进行数据收集，最优方案选择等工作。这一点对发展中城市更为明显。其次是同一路口 、同一方面在每星期中各天的流量是不同的，每天中高峰、平峰、低峰时交通也是不一样的，这些都要求按预先算好的时刻表、日期表调换周期时间和绿信比，局限性很大。并且交通流量的随机性越大，其缺点与明显。
3. 没有考虑各交叉路口的联系。“单点”即指各路口各自进行控制，不管邻近路口的信号灯翻转规律如何。这种各个路口互不配合、互不协调的控制方式人为地给交通流的流动设置了许多阻力。
（二）、信息流通条件极差，无法对乘客和车辆进行诱导和管理。这个问题在交通网络运行畅通的情况下并不明显，但当交通堵塞、交通事故等紧急事件发生时就显得非常突出。然而这些紧急事件却常有发生。每当这时，公共汽车调度站无法知道路上的情况，从而无法对公共汽车的线路、发车频次作恰当调整；其他车辆的司机也得不到信息无法选择较为畅通的线路；在公共汽车站等车的乘客也无法做出决策，是继续等车或是换乘其他车次或是步行等。实际上在许多情况下，只要进行恰当的诱导，道路的拥挤状况就会大大缓解或保证畅通。例如：1984年洛杉矶奥运会期间，由于采用了大量的动态路标显示板，诱导车辆选择恰当的路线，因而，尽管车辆较平时增多很多，但网络中交通流的运行状况却比平时还好。
（三）、停车场的能力不够，位置也不当。这是多年延续下来的旧病，只修路不修停车场。比如，成都火车站东西二环路，那里的批发市场很多，但是，无合理的停车场，大多数司机将车直接停放在街道上，这样严重影响了道路的通行能力。应该将停车场向专门化，地下化发展，在宾馆，商场，机关大楼，居民大楼的地下设置社会化的停车场是解决城市交通拥挤，堵塞的一条行之有效的办法。
交通运输是一个复杂的大系统，这个系统必须在严格科学的制度下运行，它不是一个自适应系统，任何违反规章制度的行为都可能导致大系统的局部、甚至“整体”的瘫痪。
交通拥挤和堵塞对策从总体上可分为三大类：
（1） 加强道路建设，以提高交通网络的交通容量；
（2） 加强交通运用与管理以充分发挥现有道路设施的作用，使得交通网络的使用效率最大；
（3） 全面实施交通需求管理以使交通需求在时间、空间上均匀化，交通结构合理化。由于交通基础设施建设工期长，耗资大，在当前资金有限的条件下，解决特定的城市交通问题时，必须事先进行对策的效果分析。
如前所述，要想比较有效的解决城市的交通拥挤，堵塞问题不能单纯的只依靠增加道路面积和长度，而要不断的完善路网系统，调整路网结构和加强交通管理的现代化，以及对单个车辆的控制及引导。首先就交通流量的静态情形是一种理想状态，既假设在一个城市街区内车流速度一定，对单个车辆的控制及引导进行研究分析，给出调控标准。
交通道路网的拓扑性质可以用图论的基本原理来分析。图由“弧”和“顶点”两部分组成，交通道路网的拓扑模型可以抽象认为是由节点（交叉路口）以及弧（道路）组成的有向图。边的方向就是车流的方向。由于道路和交叉路口都有很多属性，这样就可以把始发地和目的地之间的区域交通网抽象成了多属性赋权有向图。
假设：
1. 所有道路一样宽；
2. 每一条道路都不需停车等待；
3. 车流速度恒定；
4. 道路长已知。
5. 从 点到 点所用时间仅与路长有关。
不考虑意外事故对交通的影响。车子所在地设为 点，目的地设为 点。于是车子所要走的路线就可以用P来表述。
： , 两点间距离
v：车流速度
t：从始发地 到目的地 的时间
：P中所有弧长之和
表示道路状况的权重
表示车流速度改变而赋给道路的权重
表示
模型建立
由于假设车速恒定，由 可知，要求从始发地 到目的地 用时最短就可以转化为求道路最短。此时问题可以用以下数学模型描述:
（ * ）
我们将城市道路网描述为一赋权有向图D=(V,U)对每一条有向边 ∈U都存在一l 与这对应，其表示道路两结点间的距离，称之为有向边 的权。
＝
模型的求解
在赋权有向图中，我们选定某个起点 ，终点 .采用迪克特拉（E.W.Dijkstra）算法。Dijkstra方法的基本思想是从 出发，逐步地向外探寻最短路。执行过程中，与每一个点对应，记录下一个数（称为这个点的标号），它或者表示从 到该点的最短路的权（称为P标号）、或者是从 到该点的最短路的权的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p-1步，就可以求出从 到各点的最短路。
对静态的交通加权最短路问题进行了数学建模，但是实际状态中，还有许多因素影响交通运行时间，譬如道路宽度不尽相同，会使车辆流率不同（车流量的大小用车流率表示，车流率是道路上某点单位时间内到达或离开的车辆数，简称流率）；时段高峰期，会造成某一路段在某一时段交通拥挤甚至阻塞，从而使得车流速度降低等，也就是只从静态考虑了实际问题。这一些个因素没有考虑进去，按照理想模型来分析，会导致估计结果粗糙从而失真，不能有效地对单个车辆进行引导控制。于是我们在前面假设的基础上再进行模型的修改：当流量处于动态变化时，把道路宽度，交通阻塞等因素考虑进去。这样一来定点路段上的车行最短时间的问题上比静态情形复杂很多，我们采用因素转化法，将多因素变量转化为单因素变量来建立优化模型。
首先我们可以利用自动的交通检测装置来测量交通网络中各个不同部分的交通流状态，再通过一些电讯设备将这些检测到的信息送到控制中心或电台等，这样就可以知道某一时刻的各个路段的交通状况，从而为我们对司机的行车进行引导提供了信息。
由于加入了影响因素，车流速度随着高峰期拥堵而在一个时间段有所改变。由 知，求用时最短的方案必然有所改变。但是我们可以将车速改变转化为路长改变，即对道路加权改为随时间变化的函数，如速度增大则道路权为正小数，速度减小则把权设为正整数，使得要求用时最短仍能转变成求道路最短。
刚才考虑了车流速度改变的情况，现在来看看交通状况改变，譬如发生交通意外而使道路瘫痪不能行车，或是时段高峰期使得交通拥挤等。这时我们仍可以在一个时间段对道路加权来使问题转变成静态模型，即求道路最短模型。道路的权重可以通过经验给出。当道路不能畅通无阻时，我们设其权重为大于1的正整数，反之设为1。
仍同初始交通加权最短路问题一样，可将始发地和目的地之间的区域交通网抽象成多属性赋权有向图。
由自动的交通检测装置反馈来的数据信息，我们可以给一条道路赋予一定的权重，根据情况程度决定具体权重。
当道路因各种原因使得车流速度受到影响时，我们可以把权重 取值范围设定为〔1，∞），其中 =∞ 表示道路严重阻塞，车辆不能通行； =1 表示车流速度不受影响，可以自由行驶。车流速度改变后，我们可以把权重 的取值范围设定为（0，∞），当 时，表示车流速度增大； 时，表示车流速度减小； =1时，则表示与初始速度相比没有改变。
由以上所述，我们可以把模型建立为
（ ** ）
虽然每一时刻道路状况，车流速度不尽相同，但是经过转换，形成以上模型，就只是参数变化而已，如此一来仍然可以用初始最短路问题的模型求解，这样就大大简化了问题。
在下述Dijkstra方法具体求解步骤中，用P,T分别表示某个点的P标号、T标号， 表示第i步时，具P标号点的集合。为了在求出从 到各点的距离的同时，也求出从 到各点的最短路，给每个点 以一个 值，算法终止时，如果 ，表示在从 到 的最短路上， 的前一个点是 ；如果 ，则表示D中不含从 到 的路； 表示 = 。其中M表示无穷大的数。
模型检验与实用性研究
前面给出了一般性的优化模型，现在我们举个例子对模型进行计算。
如图所示，这是一个单行线交通网，车辆以速度v行驶，每弧旁的数字表示两点间相对距离。现在某出租车要从 出发，通过这个交通网到 去，求所用时间最短的路线。
图5-1
由 可知，若速度等因素没有改变时，根据模型（ * ），用Dijkstra算法直接求解，得从 到 的最短路是 。
假设，此时速度或道路状况改变，则根据模型（ ** ）我们可以得：
不妨设此时车已开向 ，并且车速变为2v（ =0.5）， 到 的路上由于上班高峰期造成了阻塞( =5)， 到 的道路由于不是主干道车流较之前减少畅通率提高 ( =0.6)，其他道路状况没有改变( =1)。此时根据模型（ ** ）：
可求得从 到 用时间最短路线为
实用性研究
优化后的模型，对于实际交通流量控制有着较好的导控作用。在运用此模型时，可通过三个设备获取数据，实现可行性。第一个是车辆设备，二是路边设备，三是控制中心。
车辆设备包括：
⑴ 接收由驾驶员输入数据的操作键盘；
⑵ 从路旁通讯设备接收数据和向该设备发送数据的收发部件；
⑶ 能提供从路旁通讯设备接收到的数据的现实控制板；
⑷ 接收来自路边或中心广播设备传送来的信息的接口。
路边设备包括：
⑴ 记录从中心处理设备传来的数据的路边通讯设备，以及通过嵌入路面的环形线圈和车辆天线与单个车辆进行双向通讯。
⑵ 直接用电缆线来连接中心控制与路边广播设备，再进行车辆通讯。⑶ 自动的交通检测装置，可测量车辆速度以及检测道路状况。
这样，司机把一个他所希望的终点站代码输入到安装在车内的键盘，一旦车辆接近确定的地点时，车上的微型计算机通过车辆天线和一个嵌入路面的回路线圈向路边微机设备传送存贮的代码数据，此微机再将代码数据反馈回控制中心，控制中心利用本文优化模型及给出的算法进行求解，得出合理的行驶路线，经由路边设备反馈给车上的微型计算机，司机通过显示器可以获取最短路线。
由于交通不是单个车辆的，而是众多车辆参与在内的运行，因此交通状况时刻可能改变，这将影响单个车辆行驶路线的改变。本文的导控考虑到此种情况，将导控分时间段进行：
表5-1
低谷期
5:00-
7:30 高峰期
7:30-
9:00 中间期
9:00-
12:00 高峰期
12:00-
13:00 中间期
13:00-
17:30- 高峰期
17:30-
19:00 低谷期
19:00-
23:00
在低谷期内的反馈周期为30分钟，中间期为15分钟，而高峰期则为5分钟一次，因为高峰期道路状况改变快，因此反馈给司机的数据间隔也不能太长。这样就使得本文的模型更具可行性。
参考文献
[1] 徐吉万、徐冬玲著：《城市交通的计算机控制与管理》，测绘出版社，1988年版
[2] 张建仁等著：《中国交通研究与探索》，人民交通出版社，2003年版
[3] 钱颂迪等著，《运筹学》，清华大学出版社，修订版
[4] 严蔚敏、吴伟民著，《数据结构》，清华大学出版社，C语言版
[5] 唐发根，《数据结构》，科学出版社，2003年9月
[6] 吴孟达、成礼智著，《数学建模的理论与实践》，国防科技大学出版社，1999年8月
Abstract
The volume of traffic is changed into weight of road, so the dynamic problem is changed into static problem, by Dijkstra method of the shortest circuit, get the feasible model of immediately control of traffic and
A effective algorithm.
Key Words: traffic flow , immediately control, adding weight to the road, method of Dijkstr.
参考资料：http://www.glits.net.cn/bbs/showbbs.asp?bd=11&id=20&totable=1
第2个回答 2007-05-06
随着国民经济的持续、高速发展，各种机动车尤其是私家车拥有量急剧增加带来了交通运输业的空前繁荣。但是，大多数城市的交通已从过去的局部拥挤演变成为当今的大范围全面紧张，如我国的一个大城市，当处于早晚交通高峰时，交叉路口处的阻车长度长达1000多米，有的阻车车队从一个交叉路口延伸到另一个交叉路口，这时一辆车为通过一个交叉路口，往往需要半个小时以上，还不如步行快，这给城市交通带来了难以承受的负荷。拥挤不仅带来时间的浪费，还导致公交系统运行的无规则性，如公交汽车不能按时到站等，使人们对自己的旅行时间无法估计，耽误工作和计划等。这种紧张状况日趋严重，已成为大城市突出的社会问题之一，也成为国民经济进一步发展的“瓶颈”问题。因此，必须面对现实，解决城市的交通拥挤，堵塞问题。
那么城市交通拥挤、堵塞原因何在呢？分析如下：
（一）、现行交通信号控制方法中交通信号与交通流量不适应。目前，各城市交叉路口使用最为广泛的是单点定周期控制方式。这种控制方式存在的问题有以下几个方面：
1. 对交通流的随机变化无适应能力。由于是定周期方法，因此一旦周期时间和绿信比选定之后，一般就不再经常改动。而交通网络中车流、人流的变化是随机的、经常的，各个周期中交叉路口同一方向上通过的流量可能差异很大。不同的流量对绿灯时间有着不同的要求。所以此种控制方式给出的信号常常不能与客观实际车流的随机变化相适应。我们常常遇到这样的情况：有车辆等待通过的方向信号是红灯，而与此同时无车辆方向的信号却是绿灯，白白浪费了现有路口通行能力。为了克服这一缺点，人们考虑运用概率、统计的方法，在收集了大量交通数据的基础上，对周期时间和绿信比进行离线优化选择，使选出的周期时间和绿信比在概率意义下的合理性有很大提高。但是，这又带来了下面的问题。
2. 需要经常调节控制规律。首先是因为城市土地结构变化很快而带来的车流量变化很快。以往的数据很快便失去了实用价值。因此优化方案不在最优甚至不合理，需要重新进行数据收集，最优方案选择等工作。这一点对发展中城市更为明显。其次是同一路口 、同一方面在每星期中各天的流量是不同的，每天中高峰、平峰、低峰时交通也是不一样的，这些都要求按预先算好的时刻表、日期表调换周期时间和绿信比，局限性很大。并且交通流量的随机性越大，其缺点与明显。
3. 没有考虑各交叉路口的联系。“单点”即指各路口各自进行控制，不管邻近路口的信号灯翻转规律如何。这种各个路口互不配合、互不协调的控制方式人为地给交通流的流动设置了许多阻力。
（二）、信息流通条件极差，无法对乘客和车辆进行诱导和管理。这个问题在交通网络运行畅通的情况下并不明显，但当交通堵塞、交通事故等紧急事件发生时就显得非常突出。然而这些紧急事件却常有发生。每当这时，公共汽车调度站无法知道路上的情况，从而无法对公共汽车的线路、发车频次作恰当调整；其他车辆的司机也得不到信息无法选择较为畅通的线路；在公共汽车站等车的乘客也无法做出决策，是继续等车或是换乘其他车次或是步行等。实际上在许多情况下，只要进行恰当的诱导，道路的拥挤状况就会大大缓解或保证畅通。例如：1984年洛杉矶奥运会期间，由于采用了大量的动态路标显示板，诱导车辆选择恰当的路线，因而，尽管车辆较平时增多很多，但网络中交通流的运行状况却比平时还好。
（三）、停车场的能力不够，位置也不当。这是多年延续下来的旧病，只修路不修停车场。比如，成都火车站东西二环路，那里的批发市场很多，但是，无合理的停车场，大多数司机将车直接停放在街道上，这样严重影响了道路的通行能力。应该将停车场向专门化，地下化发展，在宾馆，商场，机关大楼，居民大楼的地下设置社会化的停车场是解决城市交通拥挤，堵塞的一条行之有效的办法。
交通运输是一个复杂的大系统，这个系统必须在严格科学的制度下运行，它不是一个自适应系统，任何违反规章制度的行为都可能导致大系统的局部、甚至“整体”的瘫痪。
交通拥挤和堵塞对策从总体上可分为三大类：
（1） 加强道路建设，以提高交通网络的交通容量；
（2） 加强交通运用与管理以充分发挥现有道路设施的作用，使得交通网络的使用效率最大；
（3） 全面实施交通需求管理以使交通需求在时间、空间上均匀化，交通结构合理化。由于交通基础设施建设工期长，耗资大，在当前资金有限的条件下，解决特定的城市交通问题时，必须事先进行对策的效果分析。
如前所述，要想比较有效的解决城市的交通拥挤，堵塞问题不能单纯的只依靠增加道路面积和长度，而要不断的完善路网系统，调整路网结构和加强交通管理的现代化，以及对单个车辆的控制及引导。首先就交通流量的静态情形是一种理想状态，既假设在一个城市街区内车流速度一定，对单个车辆的控制及引导进行研究分析，给出调控标准。
交通道路网的拓扑性质可以用图论的基本原理来分析。图由“弧”和“顶点”两部分组成，交通道路网的拓扑模型可以抽象认为是由节点（交叉路口）以及弧（道路）组成的有向图。边的方向就是车流的方向。由于道路和交叉路口都有很多属性，这样就可以把始发地和目的地之间的区域交通网抽象成了多属性赋权有向图。
假设：
1. 所有道路一样宽；
2. 每一条道路都不需停车等待；
3. 车流速度恒定；
4. 道路长已知。
5. 从 点到 点所用时间仅与路长有关。
不考虑意外事故对交通的影响。车子所在地设为 点，目的地设为 点。于是车子所要走的路线就可以用P来表述。
： , 两点间距离
v：车流速度
t：从始发地 到目的地 的时间
：P中所有弧长之和
表示道路状况的权重
表示车流速度改变而赋给道路的权重
表示
模型建立
由于假设车速恒定，由 可知，要求从始发地 到目的地 用时最短就可以转化为求道路最短。此时问题可以用以下数学模型描述:
（ * ）
我们将城市道路网描述为一赋权有向图D=(V,U)对每一条有向边 ∈U都存在一l 与这对应，其表示道路两结点间的距离，称之为有向边 的权。
＝
模型的求解
在赋权有向图中，我们选定某个起点 ，终点 .采用迪克特拉（E.W.Dijkstra）算法。Dijkstra方法的基本思想是从 出发，逐步地向外探寻最短路。执行过程中，与每一个点对应，记录下一个数（称为这个点的标号），它或者表示从 到该点的最短路的权（称为P标号）、或者是从 到该点的最短路的权的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p-1步，就可以求出从 到各点的最短路。
对静态的交通加权最短路问题进行了数学建模，但是实际状态中，还有许多因素影响交通运行时间，譬如道路宽度不尽相同，会使车辆流率不同（车流量的大小用车流率表示，车流率是道路上某点单位时间内到达或离开的车辆数，简称流率）；时段高峰期，会造成某一路段在某一时段交通拥挤甚至阻塞，从而使得车流速度降低等，也就是只从静态考虑了实际问题。这一些个因素没有考虑进去，按照理想模型来分析，会导致估计结果粗糙从而失真，不能有效地对单个车辆进行引导控制。于是我们在前面假设的基础上再进行模型的修改：当流量处于动态变化时，把道路宽度，交通阻塞等因素考虑进去。这样一来定点路段上的车行最短时间的问题上比静态情形复杂很多，我们采用因素转化法，将多因素变量转化为单因素变量来建立优化模型。
首先我们可以利用自动的交通检测装置来测量交通网络中各个不同部分的交通流状态，再通过一些电讯设备将这些检测到的信息送到控制中心或电台等，这样就可以知道某一时刻的各个路段的交通状况，从而为我们对司机的行车进行引导提供了信息。
由于加入了影响因素，车流速度随着高峰期拥堵而在一个时间段有所改变。由 知，求用时最短的方案必然有所改变。但是我们可以将车速改变转化为路长改变，即对道路加权改为随时间变化的函数，如速度增大则道路权为正小数，速度减小则把权设为正整数，使得要求用时最短仍能转变成求道路最短。
刚才考虑了车流速度改变的情况，现在来看看交通状况改变，譬如发生交通意外而使道路瘫痪不能行车，或是时段高峰期使得交通拥挤等。这时我们仍可以在一个时间段对道路加权来使问题转变成静态模型，即求道路最短模型。道路的权重可以通过经验给出。当道路不能畅通无阻时，我们设其权重为大于1的正整数，反之设为1。
仍同初始交通加权最短路问题一样，可将始发地和目的地之间的区域交通网抽象成多属性赋权有向图。
由自动的交通检测装置反馈来的数据信息，我们可以给一条道路赋予一定的权重，根据情况程度决定具体权重。
当道路因各种原因使得车流速度受到影响时，我们可以把权重 取值范围设定为〔1，∞），其中 =∞ 表示道路严重阻塞，车辆不能通行； =1 表示车流速度不受影响，可以自由行驶。车流速度改变后，我们可以把权重 的取值范围设定为（0，∞），当 时，表示车流速度增大； 时，表示车流速度减小； =1时，则表示与初始速度相比没有改变。
由以上所述，我们可以把模型建立为
（ ** ）
虽然每一时刻道路状况，车流速度不尽相同，但是经过转换，形成以上模型，就只是参数变化而已，如此一来仍然可以用初始最短路问题的模型求解，这样就大大简化了问题。
在下述Dijkstra方法具体求解步骤中，用P,T分别表示某个点的P标号、T标号， 表示第i步时，具P标号点的集合。为了在求出从 到各点的距离的同时，也求出从 到各点的最短路，给每个点 以一个 值，算法终止时，如果 ，表示在从 到 的最短路上， 的前一个点是 ；如果 ，则表示D中不含从 到 的路； 表示 = 。其中M表示无穷大的数。
模型检验与实用性研究
前面给出了一般性的优化模型，现在我们举个例子对模型进行计算。
如图所示，这是一个单行线交通网，车辆以速度v行驶，每弧旁的数字表示两点间相对距离。现在某出租车要从 出发，通过这个交通网到 去，求所用时间最短的路线。
图5-1
由 可知，若速度等因素没有改变时，根据模型（ * ），用Dijkstra算法直接求解，得从 到 的最短路是 。
假设，此时速度或道路状况改变，则根据模型（ ** ）我们可以得：
不妨设此时车已开向 ，并且车速变为2v（ =0.5）， 到 的路上由于上班高峰期造成了阻塞( =5)， 到 的道路由于不是主干道车流较之前减少畅通率提高 ( =0.6)，其他道路状况没有改变( =1)。此时根据模型（ ** ）：
可求得从 到 用时间最短路线为
实用性研究
优化后的模型，对于实际交通流量控制有着较好的导控作用。在运用此模型时，可通过三个设备获取数据，实现可行性。第一个是车辆设备，二是路边设备，三是控制中心。
车辆设备包括：
⑴ 接收由驾驶员输入数据的操作键盘；
⑵ 从路旁通讯设备接收数据和向该设备发送数据的收发部件；
⑶ 能提供从路旁通讯设备接收到的数据的现实控制板；
⑷ 接收来自路边或中心广播设备传送来的信息的接口。
路边设备包括：
⑴ 记录从中心处理设备传来的数据的路边通讯设备，以及通过嵌入路面的环形线圈和车辆天线与单个车辆进行双向通讯。
⑵ 直接用电缆线来连接中心控制与路边广播设备，再进行车辆通讯。⑶ 自动的交通检测装置，可测量车辆速度以及检测道路状况。
这样，司机把一个他所希望的终点站代码输入到安装在车内的键盘，一旦车辆接近确定的地点时，车上的微型计算机通过车辆天线和一个嵌入路面的回路线圈向路边微机设备传送存贮的代码数据，此微机再将代码数据反馈回控制中心，控制中心利用本文优化模型及给出的算法进行求解，得出合理的行驶路线，经由路边设备反馈给车上的微型计算机，司机通过显示器可以获取最短路线。
由于交通不是单个车辆的，而是众多车辆参与在内的运行，因此交通状况时刻可能改变，这将影响单个车辆行驶路线的改变。本文的导控考虑到此种情况，将导控分时间段进行：
表5-1
低谷期
5:00-
7:30 高峰期
7:30-
9:00 中间期
9:00-
12:00 高峰期
12:00-
13:00 中间期
13:00-
17:30- 高峰期
17:30-
19:00 低谷期
19:00-
23:00
在低谷期内的反馈周期为30分钟，中间期为15分钟，而高峰期则为5分钟一次，因为高峰期道路状况改变快，因此反馈给司机的数据间隔也不能太长。这样就使得本文的模型更具可行性。
参考文献
[1] 徐吉万、徐冬玲著：《城市交通的计算机控制与管理》，测绘出版社，1988年版
[2] 张建仁等著：《中国交通研究与探索》，人民交通出版社，2003年版
[3] 钱颂迪等著，《运筹学》，清华大学出版社，修订版
[4] 严蔚敏、吴伟民著，《数据结构》，清华大学出版社，C语言版
[5] 唐发根，《数据结构》，科学出版社，2003年9月
[6] 吴孟达、成礼智著，《数学建模的理论与实践》，国防科技大学出版社，1999年8月
Abstract
The volume of traffic is changed into weight of road, so the dynamic problem is changed into static problem, by Dijkstra method of the shortest circuit, get the feasible model of immediately control of traffic and
A effective algorithm.
Key Words: traffic flow , immediately control, adding weight to the road, method of Dijkstr
那么城市交通拥挤、堵塞原因何在呢？分析如下：
（一）、现行交通信号控制方法中交通信号与交通流量不适应。目前，各城市交叉路口使用最为广泛的是单点定周期控制方式。这种控制方式存在的问题有以下几个方面：
1. 对交通流的随机变化无适应能力。由于是定周期方法，因此一旦周期时间和绿信比选定之后，一般就不再经常改动。而交通网络中车流、人流的变化是随机的、经常的，各个周期中交叉路口同一方向上通过的流量可能差异很大。不同的流量对绿灯时间有着不同的要求。所以此种控制方式给出的信号常常不能与客观实际车流的随机变化相适应。我们常常遇到这样的情况：有车辆等待通过的方向信号是红灯，而与此同时无车辆方向的信号却是绿灯，白白浪费了现有路口通行能力。为了克服这一缺点，人们考虑运用概率、统计的方法，在收集了大量交通数据的基础上，对周期时间和绿信比进行离线优化选择，使选出的周期时间和绿信比在概率意义下的合理性有很大提高。但是，这又带来了下面的问题。
2. 需要经常调节控制规律。首先是因为城市土地结构变化很快而带来的车流量变化很快。以往的数据很快便失去了实用价值。因此优化方案不在最优甚至不合理，需要重新进行数据收集，最优方案选择等工作。这一点对发展中城市更为明显。其次是同一路口 、同一方面在每星期中各天的流量是不同的，每天中高峰、平峰、低峰时交通也是不一样的，这些都要求按预先算好的时刻表、日期表调换周期时间和绿信比，局限性很大。并且交通流量的随机性越大，其缺点与明显。
3. 没有考虑各交叉路口的联系。“单点”即指各路口各自进行控制，不管邻近路口的信号灯翻转规律如何。这种各个路口互不配合、互不协调的控制方式人为地给交通流的流动设置了许多阻力。
（二）、信息流通条件极差，无法对乘客和车辆进行诱导和管理。这个问题在交通网络运行畅通的情况下并不明显，但当交通堵塞、交通事故等紧急事件发生时就显得非常突出。然而这些紧急事件却常有发生。每当这时，公共汽车调度站无法知道路上的情况，从而无法对公共汽车的线路、发车频次作恰当调整；其他车辆的司机也得不到信息无法选择较为畅通的线路；在公共汽车站等车的乘客也无法做出决策，是继续等车或是换乘其他车次或是步行等。实际上在许多情况下，只要进行恰当的诱导，道路的拥挤状况就会大大缓解或保证畅通。例如：1984年洛杉矶奥运会期间，由于采用了大量的动态路标显示板，诱导车辆选择恰当的路线，因而，尽管车辆较平时增多很多，但网络中交通流的运行状况却比平时还好。
（三）、停车场的能力不够，位置也不当。这是多年延续下来的旧病，只修路不修停车场。比如，成都火车站东西二环路，那里的批发市场很多，但是，无合理的停车场，大多数司机将车直接停放在街道上，这样严重影响了道路的通行能力。应该将停车场向专门化，地下化发展，在宾馆，商场，机关大楼，居民大楼的地下设置社会化的停车场是解决城市交通拥挤，堵塞的一条行之有效的办法。
交通运输是一个复杂的大系统，这个系统必须在严格科学的制度下运行，它不是一个自适应系统，任何违反规章制度的行为都可能导致大系统的局部、甚至“整体”的瘫痪。
交通拥挤和堵塞对策从总体上可分为三大类：
（1） 加强道路建设，以提高交通网络的交通容量；
（2） 加强交通运用与管理以充分发挥现有道路设施的作用，使得交通网络的使用效率最大；
（3） 全面实施交通需求管理以使交通需求在时间、空间上均匀化，交通结构合理化。由于交通基础设施建设工期长，耗资大，在当前资金有限的条件下，解决特定的城市交通问题时，必须事先进行对策的效果分析。
如前所述，要想比较有效的解决城市的交通拥挤，堵塞问题不能单纯的只依靠增加道路面积和长度，而要不断的完善路网系统，调整路网结构和加强交通管理的现代化，以及对单个车辆的控制及引导。首先就交通流量的静态情形是一种理想状态，既假设在一个城市街区内车流速度一定，对单个车辆的控制及引导进行研究分析，给出调控标准。
交通道路网的拓扑性质可以用图论的基本原理来分析。图由“弧”和“顶点”两部分组成，交通道路网的拓扑模型可以抽象认为是由节点（交叉路口）以及弧（道路）组成的有向图。边的方向就是车流的方向。由于道路和交叉路口都有很多属性，这样就可以把始发地和目的地之间的区域交通网抽象成了多属性赋权有向图。
假设：
1. 所有道路一样宽；
2. 每一条道路都不需停车等待；
3. 车流速度恒定；
4. 道路长已知。
5. 从 点到 点所用时间仅与路长有关。
不考虑意外事故对交通的影响。车子所在地设为 点，目的地设为 点。于是车子所要走的路线就可以用P来表述。
： , 两点间距离
v：车流速度
t：从始发地 到目的地 的时间
：P中所有弧长之和
表示道路状况的权重
表示车流速度改变而赋给道路的权重
表示
模型建立
由于假设车速恒定，由 可知，要求从始发地 到目的地 用时最短就可以转化为求道路最短。此时问题可以用以下数学模型描述:
（ * ）
我们将城市道路网描述为一赋权有向图D=(V,U)对每一条有向边 ∈U都存在一l 与这对应，其表示道路两结点间的距离，称之为有向边 的权。
＝
模型的求解
在赋权有向图中，我们选定某个起点 ，终点 .采用迪克特拉（E.W.Dijkstra）算法。Dijkstra方法的基本思想是从 出发，逐步地向外探寻最短路。执行过程中，与每一个点对应，记录下一个数（称为这个点的标号），它或者表示从 到该点的最短路的权（称为P标号）、或者是从 到该点的最短路的权的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p-1步，就可以求出从 到各点的最短路。
对静态的交通加权最短路问题进行了数学建模，但是实际状态中，还有许多因素影响交通运行时间，譬如道路宽度不尽相同，会使车辆流率不同（车流量的大小用车流率表示，车流率是道路上某点单位时间内到达或离开的车辆数，简称流率）；时段高峰期，会造成某一路段在某一时段交通拥挤甚至阻塞，从而使得车流速度降低等，也就是只从静态考虑了实际问题。这一些个因素没有考虑进去，按照理想模型来分析，会导致估计结果粗糙从而失真，不能有效地对单个车辆进行引导控制。于是我们在前面假设的基础上再进行模型的修改：当流量处于动态变化时，把道路宽度，交通阻塞等因素考虑进去。这样一来定点路段上的车行最短时间的问题上比静态情形复杂很多，我们采用因素转化法，将多因素变量转化为单因素变量来建立优化模型。
首先我们可以利用自动的交通检测装置来测量交通网络中各个不同部分的交通流状态，再通过一些电讯设备将这些检测到的信息送到控制中心或电台等，这样就可以知道某一时刻的各个路段的交通状况，从而为我们对司机的行车进行引导提供了信息。
由于加入了影响因素，车流速度随着高峰期拥堵而在一个时间段有所改变。由 知，求用时最短的方案必然有所改变。但是我们可以将车速改变转化为路长改变，即对道路加权改为随时间变化的函数，如速度增大则道路权为正小数，速度减小则把权设为正整数，使得要求用时最短仍能转变成求道路最短。
刚才考虑了车流速度改变的情况，现在来看看交通状况改变，譬如发生交通意外而使道路瘫痪不能行车，或是时段高峰期使得交通拥挤等。这时我们仍可以在一个时间段对道路加权来使问题转变成静态模型，即求道路最短模型。道路的权重可以通过经验给出。当道路不能畅通无阻时，我们设其权重为大于1的正整数，反之设为1。
仍同初始交通加权最短路问题一样，可将始发地和目的地之间的区域交通网抽象成多属性赋权有向图。
由自动的交通检测装置反馈来的数据信息，我们可以给一条道路赋予一定的权重，根据情况程度决定具体权重。
当道路因各种原因使得车流速度受到影响时，我们可以把权重 取值范围设定为〔1，∞），其中 =∞ 表示道路严重阻塞，车辆不能通行； =1 表示车流速度不受影响，可以自由行驶。车流速度改变后，我们可以把权重 的取值范围设定为（0，∞），当 时，表示车流速度增大； 时，表示车流速度减小； =1时，则表示与初始速度相比没有改变。
由以上所述，我们可以把模型建立为
（ ** ）
虽然每一时刻道路状况，车流速度不尽相同，但是经过转换，形成以上模型，就只是参数变化而已，如此一来仍然可以用初始最短路问题的模型求解，这样就大大简化了问题。
在下述Dijkstra方法具体求解步骤中，用P,T分别表示某个点的P标号、T标号， 表示第i步时，具P标号点的集合。为了在求出从 到各点的距离的同时，也求出从 到各点的最短路，给每个点 以一个 值，算法终止时，如果 ，表示在从 到 的最短路上， 的前一个点是 ；如果 ，则表示D中不含从 到 的路； 表示 = 。其中M表示无穷大的数。
模型检验与实用性研究
前面给出了一般性的优化模型，现在我们举个例子对模型进行计算。
如图所示，这是一个单行线交通网，车辆以速度v行驶，每弧旁的数字表示两点间相对距离。现在某出租车要从 出发，通过这个交通网到 去，求所用时间最短的路线。
图5-1
由 可知，若速度等因素没有改变时，根据模型（ * ），用Dijkstra算法直接求解，得从 到 的最短路是 。
假设，此时速度或道路状况改变，则根据模型（ ** ）我们可以得：
不妨设此时车已开向 ，并且车速变为2v（ =0.5）， 到 的路上由于上班高峰期造成了阻塞( =5)， 到 的道路由于不是主干道车流较之前减少畅通率提高 ( =0.6)，其他道路状况没有改变( =1)。此时根据模型（ ** ）：
可求得从 到 用时间最短路线为
实用性研究
优化后的模型，对于实际交通流量控制有着较好的导控作用。在运用此模型时，可通过三个设备获取数据，实现可行性。第一个是车辆设备，二是路边设备，三是控制中心。
车辆设备包括：
⑴ 接收由驾驶员输入数据的操作键盘；
⑵ 从路旁通讯设备接收数据和向该设备发送数据的收发部件；
⑶ 能提供从路旁通讯设备接收到的数据的现实控制板；
⑷ 接收来自路边或中心广播设备传送来的信息的接口。
路边设备包括：
⑴ 记录从中心处理设备传来的数据的路边通讯设备，以及通过嵌入路面的环形线圈和车辆天线与单个车辆进行双向通讯。
⑵ 直接用电缆线来连接中心控制与路边广播设备，再进行车辆通讯。⑶ 自动的交通检测装置，可测量车辆速度以及检测道路状况。
这样，司机把一个他所希望的终点站代码输入到安装在车内的键盘，一旦车辆接近确定的地点时，车上的微型计算机通过车辆天线和一个嵌入路面的回路线圈向路边微机设备传送存贮的代码数据，此微机再将代码数据反馈回控制中心，控制中心利用本文优化模型及给出的算法进行求解，得出合理的行驶路线，经由路边设备反馈给车上的微型计算机，司机通过显示器可以获取最短路线。
由于交通不是单个车辆的，而是众多车辆参与在内的运行，因此交通状况时刻可能改变，这将影响单个车辆行驶路线的改变。本文的导控考虑到此种情况，将导控分时间段进行：
表5-1
低谷期
5:00-
7:30 高峰期
7:30-
9:00 中间期
9:00-
12:00 高峰期
12:00-
13:00 中间期
13:00-
17:30- 高峰期
17:30-
19:00 低谷期
19:00-
23:00
在低谷期内的反馈周期为30分钟，中间期为15分钟，而高峰期则为5分钟一次，因为高峰期道路状况改变快，因此反馈给司机的数据间隔也不能太长。这样就使得本文的模型更具可行性。
参考文献
[1] 徐吉万、徐冬玲著：《城市交通的计算机控制与管理》，测绘出版社，1988年版
[2] 张建仁等著：《中国交通研究与探索》，人民交通出版社，2003年版
[3] 钱颂迪等著，《运筹学》，清华大学出版社，修订版
[4] 严蔚敏、吴伟民著，《数据结构》，清华大学出版社，C语言版
[5] 唐发根，《数据结构》，科学出版社，2003年9月
[6] 吴孟达、成礼智著，《数学建模的理论与实践》，国防科技大学出版社，1999年8月
Abstract
The volume of traffic is changed into weight of road, so the dynamic problem is changed into static problem, by Dijkstra method of the shortest circuit, get the feasible model of immediately control of traffic and
A effective algorithm.
Key Words: traffic flow , immediately control, adding weight to the road, method of Dijkstr
第3个回答 2007-05-04
每天练习练习，多做题，多思考，多提问，上课听讲！
第4个回答 2007-05-14
......
相似回答
