Multiclass Probit-Based Origin–Destination Estimation Using Multiple Data Types

Since the mid-1970s, there has been interest in estimating origin–destination (O–D) matrices from observable network flow data. For the most part, these efforts have focused on creating either a static or a dynamic O–D table for a single vehicle class (automobiles) and have assumed that the only data available are link counts. Because there is a growing interest in truck movements in urban areas, there is a clear need for O–D estimation methods that treat multiple vehicle classes simultaneously. Estimating O–D tables for trucks is of substantial interest to transportation planners because trucks impose different levels of pavement damage than cars, they have different emission characteristics, they have different accident patterns, and they may be subject to different types of flow controls. It is also important to recognize that there are several different size classes of trucks, whose O–D patterns are likely to be different from one another; this emphasizes the need for general multiclass O–D estimation methods.

Modern traffic-sensing technology offers an increasing ability to classify vehicles as they are counted as well as to create data that are more informative than simple link counts, including output from video detectors, GPS-based (Global Positioning System) vehicle location systems, automatic vehicle identification (AVI) systems, etc. Loop detectors buried in the roadway normally collect link counts of total vehicles; however, single-loop detectors, which are ubiquitous, cannot reliably distinguish a truck from a car. These total counts have been considered usable for single-class (automobile) O–D estimation, but the increasing sophistication of traffic sensors supports multiclass O–D estimation; thus, improved methods for using this better data need to be developed.

The purpose of this research is to develop an improved method for multiclass O–D estimation that is designed specifically to accept a variety of data types that are not limited to just link counts. It is also of interest to test the effectiveness of multiclass O–D estimation under conditions of varying amounts and types of available data. To accomplish these goals, the authors have created a bilevel optimization model where the upper level adjusts entries in the O–D tables for multiple vehicle classes simultaneously and the lower level relates the estimated O–D volumes to link and path flows in the network using a probit model of path choice for individual drivers.

The remainder of the paper is organized as follows. The first section reviews previous efforts at truck-only O–D estimation and previous multiclass models. The next section presents the model formulation, including a discussion of how various types of sensor (or other) data may be used for the multiclass O–D estimation; the solution algorithm for the model is also described. In the next section, insights from computational experiments on a small test network under varying conditions of data availability are highlighted. Conclusions and suggestions for future research are presented in the last section.

A review of the extensive work on O–D estimation for a single vehicle class is outside the scope of this paper, but it is important to relate the current work to some previous multiclass efforts, particularly those oriented toward truck O–D estimation. List and Turnquist (1994, 1995) propose a method for estimating multiclass truck O–D tables using proportional assignment assumptions; they apply their technique in the New York City metropolitan area. The procedure uses various types of data, including several types of vehicle classification counts that different transportation agencies in the New York area have collected for a variety of special purposes. An extended version of this technique (List et al. 2002) has been instituted as a part of the best-practice model for ongoing use in the New York City area.

Al-Battaineh and Kaysi (2007) provide another example of truck flow estimation using a combination of link count data and regional input–output economic data for Ontario. One of the interesting ideas their work represents is that truck movements are connected to economic activity, so regional economic data may be of help in estimating truck flows. This builds on the general concept that link counts of traffic (truck or otherwise) are not the only useful source of data for estimating O–D tables; further, there is value in creating methods that can integrate a wider variety of data types.

A major difficulty with truck-only O–D estimation methods is that they do not account for the interactions of trucks and automobiles in congested networks. A more complete approach would be to simultaneously estimate separate O–D tables for several vehicle classes (i.e., automobiles and various truck size classes), accounting for the different operating characteristics of the various vehicle classes and their interactions in creating equilibrium flows in the network. However, this clearly is a more complex estimation problem than the single-class models and depends on separating some of the observed data (although not necessarily all) by vehicle class.

There has been very limited work done on estimating O–D tables for multiple vehicle classes, but a noteworthy effort of this type is found in Wong et al. (2005). They develop a formulation and solution algorithm for a five-class problem (autos, taxis, buses, light trucks, and large trucks) for use in Hong Kong, assuming that available data are classified link counts and that the network flows satisfy deterministic user equilibrium (DUE) assumptions. Raothanachonkun et al. (2005, 2006) and Ha et al. (2007) also outline multiclass estimation models using varying assumptions regarding the nature of the multiclass network flows; however, they provide few details of model implementation.

Because some newer types of traffic sensors may provide more information than simple link counts, it is important to have a model formulation that can use this information. Most previous O–D estimation efforts either assume a proportional assignment mechanism (especially for trucks) or are based on DUE assumptions. If the underlying assumption of the model is that traffic flows reflect DUE conditions, then path flows for individual O–D pairs are not uniquely identified and data related to path flows are not readily usable in the O–D estimation. However, if it is assumed that the network flows represent stochastic user equilibrium (SUE), then there is a set of identifiable path flows associated with the equilibrium, and the data on path flows becomes of significant value in the O–D estimation process. Furthermore, the SUE assumption allows for errors in perception on the part of drivers as they make route choice decisions, offering a richer view of equilibrium flows in the network. There has been limited work on using a logit-based SUE model in single-class O–D estimation (Maher et al. 2001). Even less attention has been paid to a probit-based model. The underlying assumption of the probit model (that uncertain route characteristics, or drivers’ perceptions of those characteristics, are approximately normal) is intuitively appealing, but the computations required for assigning traffic to a network using probit-based methods are significantly more complex than the computations for a logit-based assignment. The solution method proposed by the authors can solve a real-world-sized problem without computational issues while using a more appealing probit model.

The following section describes a probit-based model for multiclass O–D estimation that is designed to accept multiple types of data, including link counts (aggregated or separated by vehicle class), partial path information (e.g., turning movements or AVI data), and nontraffic data such as truck trip generation based on economic activity.

Daganzo (1982) showed that the equilibrium conditions for a SUE flow pattern in a network can be written as the following set of nonlinear equations:where $x_a^m$ = class $m$ volume on link $a$; $q_{ij}^m$ = class $m$ volume for O–D pair $ij$; and $p_{ij}^{am}(Q,c)$ = link utilization coefficients (i.e., the fraction of the class $m$ O–D volume for pair $ij$ that appears on link $a$). These link utilization coefficients are functions of both the vector of costs on the links of the network ($c$) and of the O–D volumes themselves (where $Q$ is the collection of all $q_{ij}^m$ elements).

The SUE conditions represented in Eq. (1) can be incorporated into the O–D estimation process in two different ways. One way is to incorporate the conditions directly as constraints into the optimization for determining the O–D elements. Maher et al. (2001) refers to this approach as equilibrium programming [following terminology that Garcia and Zangwill (1981) define]. A second way is to formulate a bilevel model; here, the upper-level problem adjusts the $q_{ij}^m$ values and the lower-level problem finds link flows, given those values. The bilevel approach is used here.

Under ideal conditions, the link count data will separate each of the defined vehicle classes, and there will be counts available for all of the network links; however, this is unlikely to be the case in practice. The observed values for the link volumes may correspond to aggregations of the defined vehicle classes, and there may not be observations for all of the links. The available observations will be indexed by $l$, and the set of all observed link counts will be indexed as $\tilde{X}$. The count for observation $l$ will be denoted as ${\tilde{x}}_l$ and include vehicles from a set of classes $M_l$. The relevant link for observation $l$ will be denoted as $a_l$. The observed link count data and the observations’ connection to the O–D tables for individual vehicle classes under the SUE conditions can be written as follows:

In addition to the link count data, other types of observations like turning movements or partial path movements may also be available to support the O–D estimation process. An assumed form of constraints representing nonlink count data (for an observation indexed by $l$) can be expressed as follows:where $B_l$ = observed value; and the $u_{ij}^{ml}$ values = specified coefficients. Constraint Eq. (3) states that some linear combination of elements in the estimated O–D tables (for a subset of vehicle classes denoted $M_l$ and a subset of the O–D pairs $ij$ in the set $N_l$) should sum to an observed value. This is a relatively general form because the set $N_l$ may have any combination of $ij$ pairs in it; the set $M_l$ may contain one or more vehicle classes. If a prior estimate of the O–D matrix for one or more vehicle classes is available, that information can be used via Eq. (3), but the expression in Eq. (3) admits a much wider variety of data.

Before proceeding to a discussion of how Eqs. (2) and (3) form the basis for an O–D estimation process, it is worth digressing briefly to a discussion of how various types of sensors can create usable observed values for ${\tilde{x}}_l$ and $B_l$.

A series of experiments has been developed to test the concepts and solution algorithm. These experiments are designed to test the performance of the solution method under varying conditions and with varying types of data. The tests in this section are performed on a version of the Sioux Falls (SF) network, shown in Fig. 2. This network, first constructed and used by LeBlanc et al. (1975), has since become a standard test network for many types of transportation network algorithms. The basic structure of the network has been retained from the original version used by LeBlanc et al. (1975), but for the current testing, O–D tables and link characteristics have been created that enhance the network’s usefulness as a test bed for the multiclass O–D estimation algorithm. Through SUE calculation, the generated trip table produce link and path flows for each vehicle class. The authors then sample link counts, turning observations at intersections, etc., and create observations that may be separated by vehicle class or aggregated in various ways. This creates a test environment where different sets of assumed data can be specified and the algorithm can be run to estimate multiclass O–D tables. Because the original correct O–D tables are known, the result of various experiments can be evaluated by comparing the estimated tables with the correct tables. The known O–D values are not themselves used as data in any of the tests. The tests are performed using three vehicle classes: automobiles, medium trucks, and large trucks.

To check whether the solution has converged, root mean square (RMS) is used as a criterion. RMS is a statistical measure of the magnitude of a varying quantity. It measures how close the two values or two sets of values are. The calculation of RMS is shown in Eq. (5)where ${\tilde{\mathit{q}}}_{\mathit{nij}}^{\mathit{m}}$ = O–D volume estimated in $n$th iteration for vehicle class m from origin $i$ to destination $j$; and ${\mathit{N}}_{\mathit{m}}$ = number of O–D pairs for vehicle class m.

The termination criteria for the algorithm is set to be maximum 200 iterations or RMS of two successive iterations of O–D volume estimates $<0.1$, whichever comes first. An RMS of 0.1 means on average the squared error of an O–D pair between the two successive iterations is 1%. From experiments performed, most tests converge at approximately 10–30 iterations. If a test does not converge even at 60 iterations, normally it will go all the way until the preset maximum iteration. When this happens, the objective value is normally just bouncing back and forth around the optimum value without much improvement. Therefore setting maximum iteration to 200 should be enough. After the termination criteria are met, the code will output the last set of O–D pairs calculated from the optimization.

RMS can only ensure that the successive two optimization results are close enough. However, it does not necessarily mean that the estimation is close enough to the correct value. The estimation error is computed by the percent difference between the estimated value and true value [Eq. (6)]where ${\tilde{q}}_{ij}^m$ = estimated O–D volume for vehicle class m from origin $i$ to destination $j$; $q_{ij}^m$ = true O–D volume for vehicle class m from origin $i$ to destination $j$; and ${ϵ}_{ij}^m$ = estimation error for O–D pair from $i$ to $j$ for vehicle class m.

A set of estimation errors can be derived for each test run, one for each O–D pair. An O–D pair is considered as estimated acceptably correctly if the estimation error is within $\pm 5\%$. The percentage of O–D pairs and corresponding volumes estimated correctly for each vehicle class and overall can be used as performance measures to compare the results between different tests.

The O–D estimation method developed in this research is designed to include multiple vehicle classes whose O–D patterns are different and to accommodate a wider variety of data types than most previous O–D estimation methods, which only rely on link volume counts. This is particularly important for estimating truck O–D matrices along with O–D patterns for auto traffic. It is important to recognize that there are several different size classes of trucks, the O–D patterns of which are likely to be different from one another. There have been several previous efforts to estimate truck O–D matrices independently from automobiles, but the obvious interactions between auto traffic and truck traffic imply that there is a clear need for O–D estimation methods that can treat multiple vehicle classes simultaneously.

For multiclass O–D estimation, it is vital to have data that distinguish among vehicle classes. Modern traffic-sensing technology has an ever-increasing ability to classify vehicles as they are counted as well as to create data that are more informative than simple link counts. The O–D estimation method developed here creates an important new tool for transportation planners who are interested in truck movements (for several size classes) as well as automobile movements and to take advantage of the increasing sophistication of traffic-sensing technology. Use of the SUE assumption for network assignment creates a mechanism for using a wider variety of observed data types that may be related to path flows rather than just link counts. This is an important new capability for taking advantage of increasing sophistication in traffic-sensing technology.

Testing the method developed here on a widely used small test network has verified its ability to successfully estimate O–D tables when sufficient data are available. This has also led to important conclusions about the likely success of multiclass O–D estimation under more typical scenarios of data availability:

Several avenues for further research are suggested. First, additional work to create a more scalable computational process is necessary. The authors have demonstrated proof-of-concept for the multiclass probit-based O–D estimation model, but scaling the computations to large networks remains an ongoing challenge. Second, the experiments done here motivated particular interest in sensor location concerns. That is, with a limited budget for sensor acquisition and deployment, what locations and types of sensors should be selected to maximize the effectiveness of the data for O–D flow estimation across multiple vehicle classes? This sensor location problem is built upon the O–D estimation process developed here by considering the information content of different types of observations.

Extending the methodology to allow dynamic O–D tables is also an important direction. It is clear that both auto flows and truck flows change during the day, and they may change fairly rapidly during certain time periods, such as rush hours. More effective flow control and traffic management across the day, and across different vehicle classes, requires better understanding of the temporal variation of O–D flows. Much progress has been made in recent years in developing dynamic traffic assignment methods for predicting network flows if the O–D flow rates are known. The challenge is to build methods for inferring the O–D flows from these methods and corresponding real-time observations of traffic flows. There are methods focused only on auto traffic, but little has been done in the domain of multiclass dynamic O–D estimation that might apply to both automobiles and trucks.

As more and more types of data becoming available, combine and infer data on emissions and energy consumptions using this model is also an avenue worth pursuing.

This research was supported in part by Xerox Corporation and the U.S. Department of Transportation through the Region II University Transportation Research Center. This support is gratefully acknowledged, but the authors are solely responsible for the content and findings of the paper.