Towards efficient roadway network topology with pre-processing

A novel pre-processing technique has been devised to facilitate the removal of redundant links that are unlikely to be associated with the optimum path for a given O-D pair. The technique is highly suited for on-line removal of unwanted links as It relies only on simple logic and arithmetic operations. Our investigations based on simulations using Singapore roadway network show that optimum path computations on the preprocessed network are comparable to that using the entire network Moreover, pruning the network in the manner proposed will inevitably expedite the computations of optimum paths further.