Optimization of travel routes

Knowledge is Power! (Francis Bacon)

1. General

Optimization is a science in the mathematical field that can be used for decision-making in many areas. When it comes to the beam network, the task could be to find the cheapest way between 2 points, to find the most scenic route or to find the quickest way. For a start, we will assume here (of course!) that the travelers are regular, daily commuters, that want to get to their destinations as fast as possible. This is usually (but not always) also the cheapest route. Let us, then, see how we would allow our beamcars to find the quickest way to travel to their assigned destinations.

The Routing table is the tool hat we would use. It will help us to find the "best" route, regardless of our definition of "best". It can be stored centrally in the system, or at the nodes, for the beamcars to consult whenever they have to choose way at a divergence node. Or the table could be stored in each beamcar´s computer.

General The routing table Which nodes apply? If the routing table becomes too unvieldy Using other Routing Criterias

2. The Routing Table

SwedeTrack® has opted for this last solution for the FLYWAY® system, i.e. storing the routing table in each beamcar, because: The table could then be accessed quicker and more reliably It would reduce communications needs It would reduce the work load of the stationary computers The table could more easily be individually suited to each beamcar. I.e. the node would not have to start looking for an individual routing table for each car. The last point is motivated by the fact that different cars have different options, and occasionally also at different times. Heavy vehicles would not be allowed to travel on the lightest beams, for instance. Or cargo-vehicles carrying combustible goods might not be allowed to travel on certain routes. But when not carrying combustible goods, they would be allowed to use those routes.

figure 2:1.

Thus; the content of routing tables could vary according to: the urgency status of each individual beamcar, i.e. how soon it has to arrive at its station, relative to other traffic type of service it is performing at the moment time of day day of week according to special circumstances (beam repair, accidents, fotball tornaments) different criteria for different passenger categories individual preferenses of traveler. We will look at each of these in turn on this page. It should be added that the FLYWAY® system will store individual routing tables in each beamcar, and generalized routing tables in each node. This is mainly for backup purposes, in case a beamcar has computer problems. But in a future, this might serve a compatibility service as well. These generalized routing tables could help beamcars from other systems, that do not have their own routing tables. The table in figure 2:2 is based on the simple network in figure 2:1. See text below.

Example of a routing table Nodes 1 2 3 4 5 6 7 8 9 10 1 - 15 - - - 22 - - - - 2 10 - 30 21 - 17 - - - - 3 - 30 - - 26 - - - - - 4 - 21 22 - 14 - 20 - - - 5 - - 26 14 - - 26 - 20 - 6 22 - - - - - 11 25 - - 7 - 17 - 20 25 11 - 25 18 - 8 - - - - - 25 25 - 35 - 9 - - - - 20 - - 35 - 12 10 - - - - - - - - 12 - figure 2:2.

Constructing the table Now, then, to explain how a routing table is constructed, let´s take a look at an example; a small network like the one in figure 2:1 above. To make it simple, it only has 10 nodes, and our only weight criteria here will be travel time, and the travel times (in minutes) are indicated with blue numbers. Some connections are only one way. In one instance (between nodes 1 and 2) the travel time varies according to in which direction the car travels (just to complicate things a bit!). The table could then be constructed by listing the starting nodes on the y-axis (i.e. vertically, on the left) and the destination nodes on the x-axis (horisontally). Starting at node 1 and using it as departure node, then, going to node 2, one gets 15 minutes travel time. Going from node 1 to node 6, one gets 22 minutes. Then there are no more immediate destinations to be reached from node 1, so we move on to node 2. Using 2 as departure node we get 10 minutes to node 1, 30 minutes to node 3, 21 minutes to node 4 and 17 minutes to node 6. We get no listing towards node 7, because that connection is one-way in the opposite direction. After node 2, we move to node 3 and, using 3 as departure node, calculate the travel times to neighboring nodes in a similar fashion. This procedure results in the table in figure 2:2, where these time values are filled in horizontally for each departing node.

This table, stored as a database in each vehicle´s computer, would, in the FLYWAY® system, get its data by way of 5 different procedures (See figure 2:3 below): By initial figures, as shown in this example, from centrally stored information, whenever a new or reconditioned beamcar is ready for duty on the network By updating these figures from the central storage whenever the network is expanded or altered in some way By altering these figures according to set schedules, that could come from internal or external sources (for instance, certain beams might be one-way in the other direction at certain hours, or a certain route may not be used at night (it passes by a hospital!) By customizing the data for the individual vehicle, as mentioned above (i.e. it might not be allowed to travel certain routes) By including dynamic updates, caused by traffic congestion or accidents, making certain routes temporarily impassable. This information would come from nearby nodes or from central computers. Now, considering the table in figure 2:2 that we have just constructed, we find that it provides the information the car needs, i.e: Which nodes are connected to each other for a given travel direction How long it would take to travel between the nodes in question.

But clearly, the information in the table in figure 2:2 is not sufficient to enable a car to calculate a route. If it has to travel from node 1 to node 7, for instance, it only finds a "dash" in that position of the table. There are too many empty spaces in the table; the data has to be complemented. This is done by an iterative process, where all possible routes in figure 2:1 are calculated, and their corresponding total travel times are stored. As an example, the first "dash" is found when travelling from node 1 to node 1. Clearly, that´s irrelevant information; we would get a diagonal line of such "dashes" across the table. The next "dash", then, from node 1 to node 3, how is that figure calculated? Well, going over node 2, we get 15 + 30 = 45 minutes. Next, going by way of 1-6-7-2-3, we get 22+11+17+30=80 minutes. We cannot go from node 6 to node 2 directly, since it is one-way in the opposite direction. Carrying on like this, through the whole network, we get a list of different alternatives for travelling from 1 to 3. We take the "best" value out of all these (i.e. 45 minutes), and put into the appropriate place, together with the applicable route. Then we move on to the next "dash", which is for the route between nodes 1 and 4, and repeat this procedure. The resulting table would resemble the one in figure 2:4, where the intermediate nodes are listed in bold numbers in the squares, along the time figures. As an example, if one wants to travel from node 1 to node 9, one finds that the 2 best options would be; going over nodes 6 and 7, which would take 51 minutes, or going over nodes 6 and 8, which would take 82 minutes.

figure 2:3 See explanatory text above.

But this example (the table in figure 2:4 below) is, in a way, not complete. In principle, ALL possible routes for a given pair of start and destination nodes should be listed. As a compromise, it would be sufficient to calculate the 3 or 4 best routes for each source-destination pair, and put them in this table. But, someone might object, why not satisfy oneself with the one best route, and put that one in the table, for each source-destination pair? No, that would defeat the purpose of the table. It would be simple to administrate a network where the cars always took the same route for a given pair of start and destination nodes. But the routing has to be dynamic; there has to be choices, since the traffic situation changes all the time. This influences the figures in the table, as it is constantly being updated. The "best" route might suddenly no longer be the "best", and the car then has to quickly opt for the second best route. This second (or third) best route do not then have to be calculated, they are available in this table and can be fetched right away.

3. Which Nodes Apply?

The cars stop in depots, at stations and the like; they never stop at the nodes themselves. So which nodes are being used for routing decisions? The general rule is that the next upcoming node is the start node and the last node the car passes before the actual destination is the destination node. If you study the addressing system, you will notice that it is constructed in this manner; the address of the destination station (or whatever) ties in logically with the address of the foregoing node. It might happen, of course, that the beamcar arrives at a station, belonging to a node that it has not actually "passed". But the node itself is just a logical "point" in an imaginary model of the network. The node computer, by contrast, will, in addition to simulating this point, also adminstrate an area of beams, where addresses of beams and berths follow the address of that node. This computer is actually filling 2 roles; in this second role it should more properly be referred to as "regional computer". It might be thought that a beamcar could find itself in a situation where it has a free option which way to travel from its departure point, because the alternatives are equally good. Take the situation in the figure at right (figure 3:1). The beamcar has to travel from point A to a station that is reached by way of node 4. From that point (i.e. point A), the routes over nodes 2 or 3 are of equal lenght; 3 + 5 = 8 minutes. Now, point A could belong to either node 2 or 3, in which case the actual travel route would be over that respective node, because the distance would then be calculated from that node (and come to 5 minutes instead of 8).

But if point A should belong to node 1, then the car has to use some other criteria. Since one alternative will always be listed before another in the routing table, the nearest choice would be to take the first alternative, i.e. the car would probably travel over node 2. figure 3:1 Would this manner of figure travel routes influence the calculated travel times, as announced to the passengers? No, these travel times are only used for calculating the "best" routes through the network. Remember, the definition of "best" does not necessarily have to do with travel times; other criteria might be more important. The travel times as announced to passengers would be based on information where the beamcar is at the moment, where it wants to go, and the general traffic situation. This is quite another table with static and dynamic information which has nothing to do with the routing table.

4. If the Routing Table becomes too unvieldy

With today´s fast computers, the routing table can be allowed to grow to a considerable size without compromising performance. From a computer´s point of view, there is plenty of time to decide upon the route to travel. A table containing up to 5.000 nodes should not be a problem. Nevertheless, it is possible to subdivide big networks into smaller units, where cars mostly will be expected to stay in their own areas. During the simulation phase of big networks in the planning stage, it might be necessary to subdivide them in order to trim certain parameters. It will then be an extra simulation task, when these parameters are trimmed, to integrate the various parts in the final simulation phase. All beamcars should, however, have routing tables for the rest of the network as well, stored in their computers or readily accessible for download from a node computer. These tables should be updated whenever the network is altered. This also applies to scheduled changes, i.e. changes to the network configuration that apply only at certain hours at certain days (an example of this would be one-way beams that switch to carrying traffic in the opposite direction during certain hours). The only part that need not be updated is dynamic changes that pertain to other parts of the network. The beamcars won´t need this information until they has to travel to any of these other areas. At that time, they will have to send a request to the first node in that area that they will encounter, for dynamic information for the destination area, as well as all areas it will pass through in order to get there. After receiving these updates, the cars will then have to listen for regional update information as they travel, and treat that information in the same manner as those cars that belong in those areas.		Updating the Routing Table From the listing above, it can be seen that the routing table is kept up-to-date in several ways: When a new car is introduced into the network, it loads the table from the central computer system. Whenever the beam network is altered, update information is broadcast from the central computer. An acknowledgement of receipt will be expected from each car, and the system will "tick off" every car that responds. The time-scheduled alterations are likewise stored in a file, which is loaded into a new car and kept updated by broadcasts. Acknowledgements from each car that accept these alterations will likewise be required by the system, and that car is thus "ticked off". Individual characteristics of the car are added in 2 ways: Permanent characteristics (such as dimensions or weight) that influence which beams it might travel, are stored in a separate file, and always added to the routing table, whenever that information is changed. Temporary characteristics (such as if the car is carrying combustible goods or whatever) are stored in another file, when applicable, and an indicator is set. This information is then added to the routing table in a similar manner, provided this indicator is set. The implication is that a car with such cargo might not be permitted to travel certain routes. Dynamic updates are treated as in point 2 above, except that the cars will not be required to send an acknowledgement of receipt.

5. Using Other Routing Criterias

We have elsewhere written about criteria for assigning the best route, and we have mentioned above that factors such as: the individual beamcar type of service it is performing at the moment time of day and day of week according to special circumstances (beam repair, accidents, fotball tornaments) different criteria for different passenger categories individual preferenses of traveler distance, travel time and energy costs. should be weighted in. The FLYWAY® system will use the TCP/IP-protocol for data comminications, and this provides it with facilities such as the OSPF-protocol. The OSPF-protocol allows us to give priority to some routes (and some vehicles) when deciding upon routing directions. These are evaluations that could be added to the nodes' routing tables, both manually and dynamically, as the occassions arise. In the last instance, the altered evaluations would reflect changes in the network, and be transmitted between the nodes with LSA-packets. Let's see examples of how they could be used. Capacity of a Link: Could be used to limit the size or weight of vehicles using this route. Delay factor of a Link: Could be used to tell other nodes the highest speed permitted on this route, or, rather, give the time that it would take to travel along this route. Throughput factor of a Link: Could be used to estimate the number of vehicles per time unit the the route can handle at the present (thus, a figure that could vary over time. The reason being, of course, that the route has to receive traffic from feeder beams).

Number of packets waiting for transmission on a Link: Could be used to tell other nodes that a node is overloaded and cars are queueing. Load balancing: Could be used to randomly (maybe) distribute cars going in the same direction over several topologically parallell beams. Security requirements of a Link: Could be used to indicate that certain routes are restricted to certain cars or type of cars. Maybe the routes are privately owned? Number of hops: Could be used to make some routes less attractive than other alternatives. Maybe they pass by a hospital or similar place, where one would want to keep the traffic at a minimum, so long as there are other comparable routes available. The task, then, is to assign proper "weights" to all these criteria mentioned, according to their relative importance. The result would be used to create the real routing table, the one that the beamcars would actually be using. If this is done carefully and sensibly, one would have an automatic beam traffic system that would really operate at an optimum. On the page "The Intelligent FlyWay® Beamcar" we have suggested some such values.