The example shown in Fig. 3 consists of two coupled crossings. Crossing A can switch both phases at arbitrary points of time without loss of time whereas crossing B is not able to do so. The objective is to minimise the overall waiting time of both crossings together. The crossing must not be 'punished' by waiting time due to tram stops.
The estimator feeds the algorithm with tram position data. Note that several phases can use the same approach road (tracks), as for B14 and B15. When several trams arrive together, 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. 8.
Fig. 8. Information pre-processing
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 thus possible:
(B15), (B17), (B19), (B20),
(B15,B17), (B15,B19), (B17,B20),
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.
Fig. 9. Allowed and forbidden phases
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. 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.
To formalise this we introduce the set of maximal combinations M for each node. M is the set with the least elements containing all enabled combinations. For the root node, 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 holds for all j:
If due to the condition, no phase can be selected, the node is dead.
Fig. 10 shows how fast the algorithm can find the solution of the given handy example using Branch and Bound in addition (marked by B below the dots).
Fig. 10. Solution of the handy example
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.