| 联系我们 |
 |
合作经济与科技杂志社
地址：石家庄市建设南大街21号
邮编：050011
电话：0311-86049879 |
|
|
| 经济/产业 |
提要 随着人们生活质量的提高，私家车越来越多，同时城市交通日趋繁忙；交通拥堵已经成为一个实际问题。本文经过优化分析，找出在一天中不同时段城市道路中任意两路口间的最具时效性的路线。
关键词：城市交通；时效性；路线；赋权图
中图分类号：C93 文献标识码：A
一、如何选择城市道路中任意两地间最省时间的路线
如何选择城市道路中任意两地间最省时间的路线，成了城市生活中人们关注的一个话题。先给赋权图G的每个节点记一个T标号（临时标号）或固定标号（P标号）。T标号表示从始点到这一点的最短道路长的上界；P标号则是从始点到这点的最短道路长。每一步把某个点的T标号改变为P标号。这样，一旦终点得到P标号，算法停止。
算法步骤：
（1）给始点v■标上P标号d（v■）=0，给其他各点标上T标号：d（v■）=l■（j=2，3，…N）。N为G的顶点数。其中，l■为边v■到v■的权，若v■、v■两点不是同一条边的两个节点，令l■＝∞。
（2）在所有的T标号中取最小者，譬如d（v■）=l■，则把点v■的T标号改为P标号。
（3）重新计算具有T标号其他点的T标号：将点v■的T标号d（v■）与d（v■）＋l■比较。其中，较小者作为v■的新标号。
一般地，设P＝｛v■v■具有P标号｝，
T=｛v■v■具有T标号｝＝V/P （V为图G的顶点集合）。
令d（v■）=■｛d（v■）｝为该点的P标号，于是v■∈P。把T/｛v■｝中点v■的T标号修改为min｛d（v■），d（v■）＋l■｝。
（4）重复上述步骤，直到vN∈P，这时d（vN）为从v1到vN的最短道路长。
在这个过程中，当P＝N－1时，便会求得起点v1到每一点的最短道路长。
二、验证算法的正确性
由于在任一步，设P中每一点的P标号是从v1到该点的最短道路的长。开始P＝｛v■｝，d（v1）=0这个假设显然是对的；故需要说明：d（v■）=■｛d（v■）｝正是从v■到v■的最短道路长就行啦。实际上，任一条从v■到v■的道路，若通过P内的第一个点是v■，而vp=vk的话，由于所有边长为非负，则这种道路的长不会比d（v■)小。
三、边赋权
根据一天中不同的时段，把不同时段的交通状况分为三个等级：正常、繁忙、拥堵。可令：
l■=（1+?琢ij（t））dij，其中dij为vi到vj两节点间的路程，?琢ij（t）为道路vivj拥堵系数。?琢ij（t）的取值随时间段不同、城市的不同可不尽相同。其中，t为时间变量（表示当事人所处的时间点）。
赋值完成后便可依（一）中算法进行计算。例：
?琢■（t）=0 t∈（0，7）∪（9，11）∪（13，17）∪（19，24）2 t∈（7∶30，8∶30）∪（11∶30，12∶30）∪（17∶30，18∶30）1 其他
?琢■（t）=0 t∈（0，7）∪（9，11）∪（13，17）∪（19，24）1.5 t∈（7∶30，8∶30）∪（11∶30，12∶30）∪（17∶30，18∶30）1 其他
?琢■（t）=0.5 t∈（0，7）∪（9，11）∪（13，17）∪（19，24）0 t∈（7：30，8∶30）∪（11∶30，12∶30）∪（17∶30，18∶30）0 其他
其中，t为时间变量（表示当事人所处的时间点），赋值完成后便可依（一）中算法进行计算。
总之，本文提出的算法过程中，d（vk）起到一个比较的作用，并不代表实际中从起点到终点的最短路程。用该方法可选出一条最优路线，但却并不能计算出走这条路线会比其他路线省多少时间来。另外，本文所提到的赋值方法不一定适合每个城市，赋值方法仅供参考。
（作者单位：华北电力大学科技学院） |
|
|
|
