A linear programming approach for synthesizing origin-destination (O-D) trip tables based on a partial set of link traffic volumes

This research effort is motivated by the need to quickly obtain origin-destination (O-D) trip information for an urban area, without expending the excessive time and effort usually accompanying survey-based methods. The proposed approach aims to exploit the information contained even in a "partial set" of available link volumes to estimate an O-D trip table.

Recently, a new approach to synthesize a trip table from observed link flows on the network was developed at Virginia Tech. This approach employs a linear programming formulation and is based on a non-proportional assignment, user-equilibrium principle. The model is designed to determine a traffic equilibrium network flow solution that 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 target trip table. A modified column generation technique is employed to solve the problem. The methodology also accommodates a specified prior or target trip table, and drives the solution toward a tendency to match this table using user controlled parameters. The limitation of this approach is that it needs the specification of a complete set of link flows for its accurate operation. Such a requirement limits the applicability of this model to real networks, since link volumes are not always available on all the links of a network.

This research work enhances the above linear programming methodology, adding the capability to estimate OD trip tables even when only a "partial set" of link traffic counts are available. The proposed approach formulates a sequence of linear programs to approximate a fundamentally nonlinear optimization problem that is employed to estimate origin-destination flows, given incomplete network flow information. The research suggests techniques for terminating a given linear program in the sequence, as well as criteria for terminating the sequences of such LPs, and also develops a procedure for continually updating the cost vector from one linear program to the next. Modifications in the column generation technique, necessary to solve the revised model formulation, are also developed.

The enhanced model is evaluated and compared with the maximum entropy approach, which is a popular approach for OD table estimation. These models are evaluated through tests on an artificial network and a real network. The tests aim to evaluate these models using various sets of link volumes and prior table information. The results indicate that the linear programming approach performs better than the maximum entropy approach for most cases. Conclusions and recommendations for future research are also presented.