A linear programming approach for synthesizing origin-destination (O-D) trip tables from link traffic volumes

Abstract

This research effort is motivated by the need to quickly obtain origin-destination (0-0) trip information for an urban area, without expending the excessive time and effort usually accompanying survey-based methods. The intent is to utilize this information to facilitate diversion of traffic in real time, in the event of congestion-causing incidents such as accidents. The O-D trip table information is a key to successful diversion planning, where user destinations are considered in developing the plans. Traffic volumes on the links of the road network contain information which can be exploited advantageously to derive the trip patterns. This approach of synthesizing a trip table from link volumes, and perhaps using a prior trip table to guide the derivation, has useful applications in the context of diversion planning. Unlike conventional O-D surveys, it has the potential of yielding results quickly, a requisite for real-time applications. This research work details a new methodology for synthesizing origin-destination (0-0) trip tables. The approach, which is based on a non-proportional assignment, user-equilibrium motivated, linear programming model, is the principal component of this dissertation. The model is designed to determine a traffic equilibrium network flow solution which reproduces the link volume data, if such a solution exists. If such alternate solutions exist, then it is designed to find that which most closely resembles a specified target trip table. However. it recognizes that due to incomplete information, the traffic may not conform to an equilibrium flow pattern, and moreover, there might be inconsistencies in the observed link flow data, or there might be incomplete information. Accordingly, the model permits violations in the equilibrium conditions as well as deviations from the observed link flows, but at suitable incurred penalties in the objective function. A column generation solution technique is presented to optimally solve the problem. The methodology also accommodates a specified prior target trip table, and drives the solution toward a tendency to match this table using user controlled parameters. Implementation strategies are discussed, and an illustration of the proposed method is presented using some sample test networks. The results from the model are discussed vis-a-vis other relevant, available approaches. The quality of the results and the computational effort required are used as a set of criteria in the comparisons. The comparisons of test results demonstrate the superiority of the linear programming model over the other models considered. The model is also applied to a real network of Northern Virginia, where congestion problems present a serious concern. As a result of this experience, several implementation strategies relevant to the application of the model on a real network are presented, and some general conclusions are derived. The potential application of the model in real-time traffic diversion planning for the study area is discussed. Recommendations for further research are also presented.