6. APPLICATION

The example shown in Fig. 3 consists of two coupled intersections. Intersection A can switch both phases at arbitrary points of time without loss of time: intersection A is a slave of intersection B. The objective is to minimise the overall writing time of both intersections together. There are 4 tram stops. The intersection must not be 'punished' by waiting time due to these stops. This leads to the first step of the algorithm:

6.1 Information pre-processing

The estimator feeds the algorithm with position data of trams. The data is put into diagrams like shown in Fig. 5, one for each phase. Note that several phases can use the same approach road (tracks), ad for B145 and B15. When several trams arrive together (at A11 e.g.), all followers must be delayed artificially because of the scheduled delay at the tram stop. When a tram passes A11, it is re-scheduled for either B14 or B15 with the default delay at the stop. This is depicted in Fig. 10.

Information pre-processing.

Fig. 10. Information pre-processing.

If the estimated information differs from reality a re-computation is needed. (A tram might need more time to reach the intersection, or might stay longer in a stop as usual.)

6.2 A handy situation

We assume 4 trams in the system. Three at t = 10 for the phases B15, B17 and B19, and one at t = 15 for B20. By incidence vectors the problem can be reduced to a 4-dimensional state space. All following calculations will be done in this subspace.

We introduce the vector f containing the actual fronts of all queues: f = [10, 10, 10, 15]. The matrix Z defines the intermediate times between the phases. The element zij is to be understood as 'time for clearing i due to incoming j. If zij is 0, phases i and j can run simultaneously; if zij = 0, then also zji = 0.

If more than 2 phases shall run simultaneously, the following conditions must hold (p = set of phases to be run):

The following combinations are possible:

(B15), (B17), (B19), (B20),

(B15,B17), (B15,B19), (B17,B20),

6.3 Enumerating the nodes

We introduce the vector r, containing the points of time when a phases switched to red the last time. It must not be reduced to the mentioned subspace. There is a point of time T which indicates the earliest moment for the system to let the next customer pass. To compute T, we first compute the vector t:

It contains the earliest moment for each phase to be switched to green. If by that time no customer's front is in the queue, ti takes on the value of fi:

Finally T is computed as the minimum component of the ti. At T several phases might be enabled. Suppose T = 10, then B15, B17 and B19 are enabled.

To enumerate all nodes correctly, the tree of Dynamic Programming must be timed. All edges of the tree equal a transition in the state space grid. No duplicates are allowed, i.e. a transition must be taken in the earlier moment. Suppose (B15, B17) has been chosen at t =10, then at t = 16 B19 will be enabled and at t = 18 B20. If we choose at t = 16 to wait until t = 18 before making the next phase change, at t = 18 only B20 is enabled, because B19 could have taken on earlier. And thus B19 after B20 will be cancelled as well.

Allowed and forbidden phases.

Fig. 11. Allowed and forbidden phases.

To formalise this we introduce the set of maximal combinations M for each node. M is the set with the least elements, that contains all enabled combinations. For the root node is M = {(B15, B17), (B15, B19)}.

If the set of chosen phases pk in node k does not contain phases that could have been chosen in node k-1 already, only in this case pk is allowed to be checked; otherwise the phase combination is useless or at least not optimal. Or formally, a phase combination can only be selected, if the following equation hold for all j:

If due to the condition, no phase can be selected, the node is dead.

6.4 Bounds

Now we are sure not to compute the same node twice; the Generating Strategy has been implemented. To obtain the best solution,

comparable nodes must be compared and thrown out when they are bad,

Branch and Bound must be applied by (e.g. recursively) implementing a DFS.

Figure 12 shows how fast the algorithm can find the solution of the given handy example:

Solution of the handy example.

Fig. 12. Solution of the handy example.

At the top there is the root node. First the algorithm enable the phases (15,19); we omit the B before the numbers. At t = 16 a new phase can begin, a waiting time of 7 has been collected up to now. Here, phases 17 and 20 are enabled; choosing both together leads to a final node with total waiting time 7. Choosing only one of the phases, or even none, leads to a dead node. Following the next selection from the rood node, (15,17), leads to another node with waiting time 7. 20 cannot be enabled yet because of the intermediate time of 8. Therefore only 19 or none can be enabled, both leading to nodes which can be crossed out because of the bound of 7 we already have found. Choosing a single phase when starting at the root node (or even none) leads every time to a node with a waiting time above the bound of 7. Why selecting 15 and then 19 is not possible? Because of the maximal combination restriction which says that (15,19) together have to be chosen.

Thus the optimal solution is the left-hand path. The solution has been obtained by evaluating 13 nodes instead of 176 nodes for a brute force search through the tree.