S.C. Lew and K.C. Tan (Singapore)
Operations Research, one-way road network problem, conversion algorithm, Paramics
Tan and Lew [1] showed how the optimal one-way road network problem may be solved using the minimum-cut graph model [2] designed for the Module Orientation Problem. However, in the Module Orientation Problem it is assumed that the circuit modules are already in their optimal placement before the graph model is applied. By analogy, the one-way road network should also be in a suitable initial network layout before the minimum-cut graph model can be applied. This paper discusses a conversion algorithm that models a two-way road network as an undirected graph and a one-way road network as a digraph. The problem thus becomes a search for a suitable strongly connected digraph from any given undirected graph. The device of binary number counting is used to model the directionality of digraph's edges, in order to enumerate all possible digraphs. For a road network, only strongly connected graphs are "feasible" hence the concept of strong connectivity is used to weed out the "infeasible" digraphs. Dijkstra's algorithm is next modified to calculate the "network shortest total travel time" in the search for a suitable initial road network layout. The conversion algorithm is tested on a real case study; using the traffic simulation package, Paramics, the resultant digraph is tested against the original two-way network thereby verifying the usefulness of the conversion algorithm.
Important Links:
Go Back
