Method and means for traffic route control

• US 6,427,114 B1
• Filed: 02/07/2001
• Issued: 07/30/2002
• Est. Priority Date: 08/07/1998
• Status: Expired due to Fees

• Current Assignee: Dinbis AB
• Original Assignee: Dinbis AB
• Inventors: Olsson, Kjell
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): To, Tuan C
• Application Number:
  US09/762,477
• Time in Patent Office: 538 Days
• Field of Search: 701/117, 701/118, 701/119, 701/209, 701/210, 701/25, 701/26, 340/905, 340/995, 340/934, 303/96
• US Class Current: 701/117
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities

Abstract

The invention concerns a method and means for control of traffic on a network by route control. The method and the means are based on functions in a traffic management system. The invention includes control of traffic from a first route, which passes a bottleneck, which can be a part of the network, e g a node or a link, with low capacity relative to the demand of traffic through the node or the link,—to at least another alternative route. That alternative route is separated from the first route at a node upstream of the bottleneck and is routing at least parts of the traffic another road passing the bottleneck of the first route. The method is built on several cooperating method steps and route control can be applied on several different hierarchic levels in the network, locally and more comprehensive. Essential method steps are estimating and controlling traffic margins on selected links and nodes in the network and utilizing those margins at the route control. The invention concerns traffic control of vehicles on a road network as a first hand application. But the method can also be used for other applications, as traffic control of data packets on a communication network.

Claims

1. A method of a traffic management system for control of transport units, TUs, as vehicles (e g for roads, rails, air or sea) or data packets on a network as e g a road network for road vehicles and a data communication network for data packets, and where the network is consisting of links and nodes, where individual TUs are travelling according to the respective TU'"'"'s route, and the traffic management system provides actions for control of routes of TUs, utilizing that there are more than one route from a given position on the network to a given destination, and that the route control includes a route control process, where a narrow section on a first route is estimated having less capacity than the traffic demands, and where an alternative second route, at least excluding the said narrow section, is identified and estimated to be able to handle an added flow, reducing the flow of the first route, and based on the said estimations an action is selected to control process includes keeping a large capacity on the second, and that the goal for the route control process includes keeping a large capacity on the network, avoiding or reducing traffic collapses and blocking of traffic flows, comprising:

a. a route control process handling the inherent variations of the traffic, including determination of traffic margins, where a traffic margin for a link or node includes at least one of a flow margin, MF, and a storage margin, MS, where;

a1. MF constitutes a margin, which is related to the difference between the flow-capacity, C, of a part of the network and the considered flow level at the same said part, and

a2. the storage margin MS is a measure on the remaining storage possibility of TUs, which can be utilized at a part of the network,

b. selecting flow threshold values, TFs, at various parts of the network, and comparing a TF with an estimated dynamic flow demand, DL, on the same part of the network, and for DL growing larger than TF, the difference, MD, between TF and DL will grow negative, and control processes are selectively initiated, including control of traffic margins at a part of the network according to at least one of (b1-b4);

b1. considering the flow level TF, a corresponding MF is related to C-TF, and from that MF-level MF might be decreased, utilizing possibilities to increase the flow above TF on the said part of the network,

b2. decreasing MS by storing TUs, utilizing possibilities to increase the input flow above the output flow,

b3. handling peaks in DL variations, which give rise to negative MDs, by using (b1) or (b2), and utilizing possibilities to increase the respective MF or MS at smaller input flow demands,

b4. controlling the traffic margins while dynamically increasing MD by increasing TF or changing a part of DL at the said part of the network to another part of the network,

c. controlling the flow on the network concerning the said TF levels, and that predicted or estimated negative demand margin, MD, is detected for a first link or node on a first route for a time period, tnd, and that the traffic management system supports at least one of control of traffic margins according to (c1) and route control according to (c2);

c1. the said negative MD is handled on the said first link or node by decreasing traffic margins for the link,

c2. the demand margin is increased on the said first link by a process comprising an identification of a second alternative route, with estimated large enough demand margins for receiving an added sub-flow for the concerned time period, and rerouting a corresponding sub-flow to the second alternative route from the first.

2. A method according to claim 1, comprising:

supplementing the method sub-step (c2) with at least one of (c3), (c4) and (c5);

c3. a limiting demand margin of the second alternative route is handled by decreasing the traffic margins for the limiting links or nodes of the route,

c4. the demand margin is increased on the said second link by a process comprising an identification of a third alternative route, with estimated large enough demand margins for receiving an added sub-flow for the concerned time period, and rerouting a corresponding sub-flow to the third alternative route from the second or first,

c5. the sub-step (c3) or (c4) is performed for one or more further alternative routes.

3. A method according to claim 1, including handling of dynamic uncertainties in estimations on traffic parameters, where relative deviations from the real parameter values are dependent of the length of the studied time period, comprising:

a. analyzing at least one group-member'"'"'s predicted or estimated values from a group consisting of;

predicted and estimated traffic flows, estimated and given flow capacity values, estimated and predicted storage margins, estimated and predicted values of said MF, MS, C and DL and estimated and predicted effects, AR, of route control actions, for deviations from the real values respective effects of the said group-member, and

b. utilizing that uncertainties about the real values of the group are influencing the uncertainties in the route control process and thereby the estimation of involved margins, and

c. estimating the uncertainties of the route control process by comparing estimated values on selected parameters with resulting values on the said parameters based on measurements during the route control process, and

d. limiting the size of the uncertainties by successively updating parameter values of the route control process based on the said comparisons.

4. A method according to claim 1, comprising:

a. utilizing that said parameters for margins, thresholds, capacities, and levels, including the said MF, MS, C, DL and TF can be related to each other and be expressed in different ways, and

a1. including such ways and equivalent parameters in method steps, which are similar or equivalent with the corresponding method steps in claim (1), where the following is one example;

a method step requiring that the flow on the network is controlled concerning a TFM level, which are related to needs for traffic margins, where a margin, MTF, is C-TFM and is based on a need originating from uncertainties in estimations of traffic parameters, including at least one of the parameters of the said group of MF, MS, C, DL and TF or an equivalent group, which are involved in the route control processes, and

a2. estimating uncertainties in the method steps based on deviations between estimated and real values, where the uncertainty values are estimated according to a selection of a group of deviations, where the said group can consist of various types of deviations, ranging from individual parameter deviations to a complete deviation for a whole route control process, and

a3. updating the estimated uncertainty values using an updating process on a selected group of deviations, and at the updating of said estimations, preferably using statistical methods to determine sizes of critical traffic margins dependent on the probability for the deviations in the route control process exceeding the traffic margins.

5. A method according to claim 1, where a first route is analyzed together with alternative routes of the whole or parts of the first route for rerouting of parts of traffic from the first route to at least one of the alternative routes, comprising:

performing route control according to the following steps, where index i can identify different links in the different steps (a), (b) and (c);

a. the flow Ipi is predicted on link (Li) and prediction uncertainty dlpi is estimated, and the flow capacity Ci and the threshold value TF are determined;

b. the storage, Spi, of the transport units TUs is predicted for link (Li), with storage capacity Si, and the uncertainty dSpi considered;

c. dynamic traffic margins Mi for in-flow on link (i) is constituted by a combination of the flow margin MFi, which is estimated from Ipi relative at least one of Ci and TFi, and selectively the storage margin MSi, which is estimated from Spi relative at least one of Si and a threshold value, TSi;

d. a bottleneck is identified for a node (Nb) and/or link (Lb), where a bottleneck at the node Nb implies that at least one upstream link Lb would be regarded a bottleneck, and at least one route through the bottleneck is identified as a first route (Rf), containing a bottleneck;

e. the steps (a, b, c) above are performed for the route (Rf) with the link Li, i=b, and selectively for upstream links (i=b−

1;

etc), and for at least an alternative route (Ra), which deviates from (Rf) at a node (Na) upstream (Nb) or (Lb) and with the link Li, I=a+1, and selectively downstream links (i=a+2;

etc) with nodes;

f. decision on action (AR) for control of a certain flow, I(Ra, Rf), from (Rf) to (Ra) implying that I(Lb) decreases and I(a+1) obtains a rerouted flow;

g. decision in point (f) above is aimed at improving traffic on the network and selected criteria for decision are based on an analysis on selected links and nodes with an extent corresponding to at least one of conditions g1-g4 below;

g1. the predicted flow margin MF on selected links on Ra is estimated to handle the rerouted flow I(Ra, Rf) during a selected time period;

g2. the traffic problems on selected links on Ra and Rf, after rerouting, are estimated being less than on Rf, without rerouting;

g3. the predicted storage margin MS on Ra together with MF on Ra is estimated to handle the rerouted flow I(Ra, Rf) during a selected time period;

g4. uncertainties in predictions and variations in flows imply uncertainties in results of route control actions AR, and if the result would be, in spite of selected criteria for the decision in point (f), worse than a given condition, step (h) would be performed below;

h. at detection or estimating or prediction of problems with rerouting actions (AR), analysis of the steps (a, b, c) above is performed selectively for upstream links for selective action(AL) for upstream limitation of flow to the problem area, where AL selectively [] utilizes the dynamic margins of the analysis at the implementation of flow limitation;

selectively point (h) is combined with correction or addition of route control actions AR.

6. A method according to claim 1, concerning route control on local level, where the analysis and the route control actions are limited to the links closest to the bottleneck on the first route, Rf, and the closest links on the alternative route, Ra, comprising:

a1. using a local control process operating close to the narrow section, and handling short term traffic variations by control of flows and traffic margins,

a2. including short time periods in the predictions in the analysis, corresponding to the transport travel times of the links, or to the traffic control period of the nodes or shorter intervals, and

b1. analyzing the dynamics of the traffic flows in the said short time periods out from a selected link and in to selected downstream links, and including the flow of the node from the selected link in the traffic management, and

b2. controlling flow from a link on Rf to a link on Ra by the route control process, including prediction, control and follow-up of the traffic for the said short time periods.

7. A method according to claim 1 for route control at sub-area level, where a sub-area is identified as the sub-area within which route control is done regarding flow at the concerned narrow section, and where the sub-area is a larger area of the network than the local area, comprising:

analyzing possibilities to redistribute the flows on the sub-area network, and concerning possibilities to reroute flows already before they have reached the local area,

performing route control over longer distances and with connected uncertainties over several links and nodes, whereby the concerned time periods grow longer and the route control includes longer traffic variations with longer time perspective for implementing and continuity in route control actions, and

handling short-term dynamic changes selectively with other actions, including local traffic control and upstream flow limitation.

8. A method according to claim 1, comprising:

controlling network on an upper level, where the network includes several sub-areas and connections between those, and doing route control on the network considering flow at the sub-area with the concerned narrow section, and

rerouting the concerned flows already before they have reached the sub-area, and including analysis of large distances to the narrow section for route control of larger traffic volumes during long time periods, and

analyzing strong loads of the concerned sub-area, and directing flows around or away from the sub-area by the network control and thereby creating more space for route control at local and sub-area level, and

handling short-term dynamic changes selectively with other actions, including local traffic control and upstream flow limitation.

9. A method according to claim 1, comprising:

at least one (a) and (b),

a. constituting a first traffic margin including a first flow margin up to the level when traffic collapses and queue starts to grow, and the capacity being the free-flow capacity,

b. constituting a second traffic margin including a second flow margin up to the level when a queue has started to grow, and the capacity is determined from the queue-flow capacity.

10. A method according to claim 1, comprising;

estimating a first storage capacity Si from how many transport units TUs, that can be stored without stored TUs blocking any exit flow from the link, and

estimating a second storage capacity Si from how many TUs that can be stored at the link, including those blocking the exit flows.

11. A method according to claim 1, where a flow of a link composed of sub-flows, where a sub-flow can concern a given route or traffic at a given direction at a downstream node, characterized in;

that there is defined at least one of traffic margin, flow margin and storage capacity for at least one sub-flow on the link.

12. A method according to claim 1, where transport units TUs on an access link are stored for further transport through a node to an exit link, comprising:

arranging the storage capacity Si for a link to be at least partly non-FIFO, whereby FIFO is meant that first in is first out from the link, and

controlling traffic, utilizing control possibilities to sustain large sub-flows on the link for other routes, while a first route with limited exit flow from the link is controlled by storing TUs without those TUs blocking the said other routes.

13. A method according to claim 1, where the traffic control includes a function which limits the speed, with which the traffic flows are allowed to grow on the network, comprising:

a. supplying flows in a first node to the downstream links, limiting flows to ration values, FRn(t), which are updated in time, and said ration values are estimated using information about downstream loads, FLn(t), of links and nodes and the demand on flow levels, DL1(t); and

b. increasing the ration values when they are lower than the demand and the traffic loads are lower than selected flow level values, FCn, which have controlled margins up to the respective flow capacities; and

limiting the increase rate of ration values, in such a way that sudden large increases of demands are resulting in successive smaller increases of the rations in time, and that thereby response times are obtained for the network and that those response times and traffic margins are adapted to give time for route control to be initiated and performed for avoiding overloading of parts of the network; and

c. analyzing demands exceeding the rations on various positions on the network, regarding routes from TU-sources to their destinations, and utilizing information about the demands as input for estimating or predicting downstream flows; and

d. including the said estimation or prediction of flows at updating estimated or predicted demands on the network.

14. A method according to claim 1 concerning vehicles, in which there is equipment, whereby information about routes can be transferred in a form, which in a continuation can be utilized by the traffic management system, comprising:

including information, which at least is concerning direction at the closest downstream node,

including information, which is used by the traffic management system at estimation of traffic flows into downstream links,

using the said information for decreasing uncertainty in the flow estimations at traffic control, utilizing smaller traffic margins.

15. A method according to claim 14, comprising:

including information concerning the route on several downstream links, which is further decreasing the uncertainty at prediction of downstream link flows,

utilizing the decreased uncertainty regarding several downstream links for an improved control of future conditions and selection of actions on several links upstream a link with predicted traffic problems.

16. A method according to claim 1 concerning vehicles, in which there is navigation equipment, characterized in;

that the traffic management system is giving control information concerning route control in a form that in a continuation can be utilized by the navigation equipment in the vehicle for providing a new route.

17. A method according to claim 1 concerning vehicles, characterized in;

that a guiding principle at the traffic control is not to let in more traffic into a part of a road network, than what the said road network part can handle, and with a part of a road network it is meant at least one of (a)-(e) below;

a. a road network, including networks separated as different responsibility areas;

b. a larger traffic route, motorway etc.

c. a sub-network, with interfaces through given access and exit roads;

d. a road-link, including downstream node;

e. a node;

that control for limitation of the in-flow at the connection of the road network part is selectively arranged according to at least one of the following alternatives (f)-(i);

f. at the said connection;

g. at least at one upstream link or node;

h. at least at one of links and nodes in position several steps upstream;

i. a selected combination of (f), (g) and (h);

where the limitation at (f) is analyzed regarding further control actions in a short term and distance perspective, while (g) and further (h) are analyzed regarding longer time and distance perspectives in prediction and control processes,

that there is route control of traffic flows around or from a road network part, into which the in-flow is limited, to another road network part, which has got capacity for larger in-flows.

18. A method according to claim 1, for traffic management of data packets on a communication network consisting of links and nodes, where the nodes are constituted of means which distribute data packets from access links to respective exit link according to the respective packet'"'"'s route and the traffic management contains actions for control of packets'"'"' routes, utilizing that there are more than one route from a given position on the network to a given destination, comprising:

transferring information about traffic on the network with corresponding speed as the speed of transport units, i e the data packets, where the said information is transferred in the form of data packets on the same physical network or by an alternative method, where some route control is distributed to nodes in the network, and

utilizing local area control with fast information transfer between neighboring nodes for handling short term traffic variations considering small traffic margins, and

utilizing route control on sub-area level for unloading the local route control of a narrow section on its local network from longer term traffic peaks, by allowing little more time consuming information transfer between nodes within the sub-area and corresponding longer or more complicated rerouting of routes, and

utilizing route control on network area level for still longer time perspective, allowing corresponding time periods for information transfer and rerouting of routes within its action area, and for unloading strongly loaded sub-areas from corresponding longer term traffic peaks.

19. Means for performing the method according to claim 1 in a traffic management system for traffic management on a road network consisting of links and nodes, where individual vehicles are travelling on the network according to the respective vehicle'"'"'s route and the traffic management provides actions for control of vehicle'"'"'s routes, utilizing that there are more than one route from a given position on the network to a given destination, and supplementing the basic means of the traffic management system with road based sensors and control means, comprising:

a. computer units, which include processes for route control and control of traffic margins, and that central computer units for superior control of network or sub-areas alternatively can be replaced by or supplemented with distributed functions in local computer units at the nodes of the network, and that control information is communicated between computer units;

b. control means, which get information from control processes in computer units and provide route control information for further use by TU, including the drivers of the vehicles;

c. sensors, which obtain information about vehicles at the connections with nodes, and that this information is communicated to control processes in computer units;

and means for control processes comprising;

d. a route control process handling the inherent variations of the traffic, including determination of traffic margins, where a traffic margin for a link or node includes at least one of a flow margin, MF, and a storage margin, MS, where;

d1. MF constitutes a margin, which is related to the difference between the flow-capacity, C, of a part of the network and the considered flow level at the same said part, and

d2. the storage margin MS is a measure on the remaining storage possibility of TUs, which can be utilized at a part of the network,

e. selecting flow threshold values, TFs, at various parts of the network, and comparing a TF with an estimated dynamic flow demand, DL, on the same part of the network, and for DL growing larger than TF, the difference, MD, between TF and DL will grow negative, and control processes are selectively initiated, including control of traffic margins at a part of the network according to at least one of (e1-e4);

e1. considering the flow level TF, a corresponding MF is related to C-TF, and from that MF-level MF might be decreased, utilizing possibilities to increase the flow above TF on the said part of the network,

e2, decreasing MS by storing TUs, utilizing possibilities to increase the input flow above the output flow,

e3. handling peaks in DL variations, which give rise to negative MDs, by using (b1) or (b2), and utilizing possibilities to increase the respective MF or MS at smaller input flow demands,

e4. controlling the traffic margins while dynamically increasing MD by increasing TF or changing a part of DL at the said part of the network to another part of the network,

f. controlling the flow on the network concerning the said TF levels, and that predicted or estimated negative demand margin, MD, is detected for a first link or node on a first route for a time period, tnd, and that the traffic management system supports at least one of control of traffic margins according to (f1) and route control according to (f2);

f1. the said negative MD is handled on the said first link or node by decreasing traffic margins for the link,

f2. the demand margin is increased on the said first link by a process comprising an identification of a second alternative route, with estimated large enough demand margins for receiving an added sub-flow for the concerned time period, and rerouting a corresponding sub-flow to the second alternative route from the first.

20. Means according to claim 19, characterized in;

that a sensor or corresponding vehicle means are based on at least one of (a)-(i) below;

a. optical sensor based on at least one of;

photo detector, video camera, camera and other opto-electronic means for detection of signals from vehicle means;

b. according to (a) where said vehicle means are constituted of blinkers;

c. according to (a) where the said signal is given at a given position or at a given situation providing a message;

d. according to (a) where the vehicle means are made as displays or other presentation units;

e. according to (d) where the presentation unit contains symbols, which indicate a part of the road network and the planned vehicle route on the road network part;

f. sensors detecting the position of vehicles on a part of a link, and where this position is related to driving directions in a downstream node;

g. the sensor is a radio receiver, receiving information from a transmitter in the vehicle;

h. according to (g) but with IR, light or acoustics as transmission media instead of radio;

i. according to (a) where a vehicle means is the vehicle license plate.

21. Means according to claim 19, characterized in;

that the control means is based on at least one of (a) to (g) below;

a. presentation means implemented at the road for information to the vehicle driver;

b. according to (a) where the presentation means contain symbols, which indicate a road network part and the given vehicle route on the road network part;

c. according to (a) where the concerned vehicle is indicated with at least a part of license plate information, e g one or more significant figures;

d. according to (a) where the information about given driving direction in downstream node is constituted of a symbol or text, e g an established arrow-symbol on a VMS;

e. the control means includes a radio transmitter, which gives information to the vehicle radio receiver;

f. according to (e) utilizing mobile telephone technology;

g. according to (e) but with IR, light or acoustics as transmission media instead of radio.

22. Means according to claim 19, characterized in;

that vehicles are equipped with at least one of the means according to (a)-(e) below;

a. navigation means, which gives the vehicle driver information about given route;

b. according to (a) where the navigation means provides a new route at deviations from the earlier;

c. according to (a) where the navigation means is updated with new control information from the traffic management system, through the driver or directly through the communication media;

d. according to (a) where the information of the navigation means about routes concerning at least the closest part of the route, is transferred to the vehicle information means, through the driver or directly through the communication media;

e. input means where the driver is putting in information about routes, concerning at least the closest part of the route, for further transfer to the vehicle information means.

23. Means for performing the method according to claim 1 in a traffic management system for traffic management on a communication network consisting of links and nodes, where individual data packets are travelling on the network according to the respective packet'"'"'s route and the traffic management contains actions for controls of packets'"'"' routes, utilizing that there are more than one route from a given position on the network to a given destination, supplementing the basic means of the traffic management system with communication network based nodes and links, comprising:

a. computer units, which include processes for route control and control of traffic margins, and that central computer units for superior control of network or sub-areas alternatively can be replaced by or supplemented with distributed functions in local computer units at the nodes of the network, and that control information is communicated between computer units;

b. control means, which get information from control processes in computer units and provide route control information for further use by TUs, here data packets;

c. sensors, which obtain information about data packets at the connections with nodes, and that this information is communicated to control processes in computer units;

d. control means and sensors, which alternatively are included in local computer units,

and means for control processes comprising;

e. a route control process handling the inherent variations of the traffic, including determination of traffic margins, where a traffic margin for a link or node includes at least one of a flow margin, MF, and a storage margin, MS, where;

e1. MF constitutes a margin, which is related to the difference between the flow-capacity, C, of a part of the network and the considered flow level at the same said part, and

e2. the storage margin MS is a measure on the remaining storage possibility of TUs, which can be utilized at a part of the network,

f. selecting flow threshold values, TFs, at various parts of the network, and comparing a TF with an estimated dynamic flow demand, DL, on the same part of the network, and for DL growing larger than TF, the difference MD, between TF and DL will grow negative, and control processes are selectively initiated, including control of traffic margins at a part of the network according to at least one of (f1-f4);

f1. considering the flow level TF, a corresponding MF is related to C-TF, and from that MF-level MF might be decreased, utilizing possibilities to increase the flow above TF on the said part of the network,

f2, decreasing MS by storing TUs, utilizing possibilities to increase the input flow above the output flow,

f3. handling peaks in DL variations, which give rise to negative MDs, by using (b1) or (b2), and utilizing possibilities to increase the respective MF or MS at smaller input flow demands,

f4. controlling the traffic margins while dynamically increasing MD by increasing TF or changing a part of DL at the said part of the network to another part of the network,

g. controlling the flow on the network concerning the said TF levels, and that predicted or estimated negative demand margin, MD, is detected for a first link or node on a first route for a time period, tnd, and that the traffic management system supports at least one of control of traffic margins according to (g1) and route control according to (g2);

g1. the said negative MD is handled on the said first link or node by decreasing traffic margins for the link,

g2. the demand margin is increased on the said first link by a process comprising an identification of a second alternative route, with estimated large enough demand margins for receiving an added sub-flow for the concerned time period, and rerouting a corresponding sub-flow to the second alternative route from the first.

24. Means according to claim 23, characterized in;

that storage means are arranged at nodes for arriving data packets from communication links;

that control information as control packets, is sent between nodes on the network or on a control network;

that control packets, which are sent upstream opposite the direction of the data packets, deliver information to the traffic management system in upstream nodes about downstream traffic, including traffic margins.

25. Means according to claim 24, characterised is;

that storage means are arranged at nodes for arriving data packets from communication links;

that control information as control packets, is sent between nodes on the network or on a control network;

that control packets, which are sent upstream opposite the direction of the data packets,

deliver information to the traffic management system in upstream nodes about downstream traffic, including traffic margins.