The problem explored is that of selecting a fixed number of arcs, representing a subset of the network arcs, referred to as information critical arcs (ICAs), which will be instrumented to collect real-time information, such as travel times, from a transportation network. The objective is to select the ICAs such that the greatest benefit (e.g., in relieving traffic congestion or providing optimal real-time path strategies for onboard route guidance) will be derived. A mathematical formulation of the problem of selecting the ICAs is given. Since the problem as described in this formulation is proved to be NP-hard (which infers that the problem belongs to a class of problems for which there is no known polynomial time solution), a heuristic is proposed, referred to as the critical arc set (CAS) heuristic, for solving the problem. Numerical experiments are conducted on the Texas highway network for assessing the ICAs selected by the CAS heuristic in the context of providing real-time path strategies. The experimental results indicate that for this network, good real-time path strategies can be obtained by instrumenting a fairly small number of the network arcs when the arcs are chosen by the CAS heuristic.
Abstract