Traffic simulators are utilized to solve a variety of traffic-related problems. For such simulators, origin-destination (OD) traffic volumes as mobility demands are required to input, and we need to estimate them. The authors regard an OD estimation as a bi-level programming problem, and apply a microscopic traffic simulation model to it. However, the simulation trials can be computationally expensive if full dynamic rerouting is allowed, when employing multi-agent-based models in the estimation process. This paper proposes an efficient OD estimation method using a multi-agent-based simulator with restricted dynamic rerouting to reduce the computational load. Even though, in the case of large traffic demand, the restriction on dynamic rerouting can result in heavier congestion. The authors resolve this problem by introducing constraints of the bi-level programming problem depending on link congestion. Test results show that the accuracy of the link traffic volume reproduced with the proposed method is virtually identical to that of existing methods but that the proposed method is more computationally efficient in a wide-range or high-demand context.
Traffic simulation is used to solve various traffic problems and inform associated policies such as handling congestion or accidents, controlling
The simulation model and input data must be reliable and realistic to reproduce a realistic traffic situation in a simulator. And in most cases, a single simulator is used for parametric studies by changing some parameters sets. In this research, the authors focus on the reliability of traffic demand as the input data given to the simulator.
We can easily obtain road structure information (e.g., intersection configuration) and observable and controllable information (e.g., traffic light patterns) in the real world. However, traffic demand data, which directly affect link traffic volume, congestion, and service levels, are more difficult to obtain because of their unobservability and significant uncertainties.
Origin-destination (OD) matrices describe traffic demand. An OD matrix consists of traffic demand (traffic volume) for each OD pair, i.e., a pair of an origin and a destination point. Rows and columns of an OD matrix denote origins and destinations, respectively. For example, the
The authors regard OD estimation as a bi-level programming problem and target OD estimation problem for microscopic traffic simulation, especially. In this situation, the same traffic model should be employed in both lower and upper problems to make the input and the output for those problems consistent.
It is concerned that the computational time increases due to the dynamic rerouting in each simulation trial and the increased number of trial iterations when using such a method. Dynamic rerouting is a route search operation required when a vehicle driver faces a high-cost link to pass (e.g., a congested link) during driving along the route acquired by the initial search. Thus, dynamic rerouting is reasonable because it corresponds to each driver’s detour behavior. By introducing dynamic rerouting, vehicles detour to avoid congestion, and consequently, congestions are relaxed. However, each route search operation, including dynamic rerouting, is computationally expensive. In addition, each vehicle driver should know the traffic situation of the route candidates at a specific time point to reroute dynamically. It is concerned to be an unrealistic assumption beyond the vehicle drivers’ capability. The authors propose a way to suppress the number of dynamic rerouting in OD estimation and deal with the problems resulting from this restriction.
Three general approaches are available for OD estimation: statistical approaches, traffic volume optimization approaches with demand assignment, and traffic volume optimization approaches with microscopic simulators. In the statistical approaches, the OD matrices are generated by aggregating survey data, which can come from personal interviews. A typical example is the four-step model [
The traffic volume optimization approaches with demand assignment optimize link traffic volume, i.e., match the volume in the simulation to that in the real world by changing the solution candidates for the OD matrices. The assignment of traffic demand for each link is determined under the assumption of logit-based decision rules and user equilibrium (UE) theory. Most such methods handle traffic flow with stochastic turbulence based on minimum entropy [
The statistical and traffic volume optimization approaches with demand assignment handle wide-ranging and aggregated traffic flows. Therefore, these methods are often applied in macroscopic simulators because of the characteristics of aggregated flow.
Microscopic simulators are also widely used. These simulators seek to capture more detailed traffic phenomena. A multi-agent system (MAS) is commonly used to implement such models. The MAS captures each agent’s autonomous recognition, decision-making, and action. When applied to traffic simulation, the MAS regards each driver or each vehicle as an agent. Entire phenomena such as congestion emerge from the interactions among the drivers. Since this type of modeling directly incorporates the individual behavior of actual drivers, the MAS is suitable for simulating traffic phenomena in the real world at a fine-scale resolution. The MAS employs route search algorithms (e.g., Dijkstra’s algorithm [
Microscopic traffic simulations based on a MAS require OD matrices as traffic demand input data. In one traffic volume optimization approach using a MAS-based simulator for OD estimation, Nguyen et al. applied the DFROUTER tool to SUMO. This tool reconstructs vehicle routes based on detector measurements [
Omrani and Lina proposed a genetic-algorithm (GA)-based approach for OD estimation [
Because drivers’ dynamic rerouting behaviors avoid the uneven distribution of vehicles in a network, bi-level-programming-based approaches employing MAS-based microscopic simulators within the model tend to work well. However, these approaches can involve significantly higher computational costs for the dynamic rerouting process, as each driver search for the shortest path frequently. For example, SPSA requires two simulation runs to determine the gradient [
Nowadays, several OD estimation methods using advanced deep learning models have been proposed [
As mentioned in the previous section, this research aims to solve the OD estimation problem using a MAS-based simulator with restricted dynamic rerouting functions. Here, the simulator allows a vehicle agent to reroute only after finding itself in an unintended route, which can occur when a lane is blocked due to congestion. By restricting dynamic rerouting, it is expected that the computational cost will be reduced and that vehicle drivers’ routing behavior will be more feasible.
However, employing such a restricted MAS-based simulator faces several challenges in the OD estimation process. If high traffic demand is assigned to a low-throughput route in a certain iteration step, congestion may occur at intersections. This is a natural characteristic in real situations, and if full dynamic rerouting is allowed, the demand is adequately distributed to mitigate the congestion. But, when the restricted dynamic rerouting proposed in this paper is employed, a kind of positive feedback occurs so that heavier congestion arises at successive iteration steps. Once congestion incurs stuck of vehicles upstream of the observation point, the link traffic volume, i.e., the number of vehicles that passed the link, is under-measured compared to the link traffic demand, i.e., the number of vehicles that intend to pass the link. In order to resolve this shortage of link traffic volume, more vehicles are assigned to pass the link, regardless of whether it is the congested link or not. Consequently, the congestion becomes even heavier, and the traffic volume is further reduced unexpectedly. This traffic congestion generated by the restricted simulator functions is hereafter referred to as “fictitious congestion”.
To resolve the fictitious congestion problem, the authors introduce upper-bound constraints for link demand reflecting a congested state in the OD estimation process. It is handled outside the simulator used in the OD estimation process. As a result, the proposed method is applicable to simulators even when dynamic rerouting is fully available.
The authors aim to solve the following two problems: (1) calculation cost for bi-level-programming-based OD estimation and (2) fictitious congestion when employing the simulator with restricted dynamic rerouting. Especially, the OD estimation method is not established in context of restricted dynamic rerouting. In this paper, the OD estimation problem is solved based on a framework that deals with OD traffic volume assignment to links by alternately using simulation and optimization of the solution candidate of the OD matrix via a numerical solver. Within this framework, a MAS-based simulator with restricted dynamic rerouting is employed. By using this simplified framework, the computational cost can be substantially reduced. To demonstrate the practical performance of the proposed method, three cases were tested: a low-demand case, a high-demand case with link demand constraints, and a high-demand case without link demand constraints.
A flowchart of the proposed OD estimation method is shown in
Here,
The estimation process starts with an initial OD matrix in vector form,
If the solution does not converge, a new OD matrix candidate is calculated by solving a quadratic programming (QP) problem. When the QP is solved, some constraints corresponding to the congestion situation are considered. The
To simplify the OD estimation problem, the authors assume that the traffic situation is nearly steady during a one-hour simulation. This assumption is based on the fact that link traffic volume is aggregated every hour in many data sources. Importantly, this OD estimation is performed offline, i.e., all the link traffic volumes are determined before the estimation starts. By focusing on a particular one-hour period to be estimated, the model can be considered static. There is no problem discussing the function of dynamic rerouting under the assumption of static conditions because the MAS itself shows a dynamic process. The behavior of an agent means that the environment is dynamically changing for other agents.
The fictitious congestion appears in a simulation during the OD estimation process. In reality, even if congestion occurs, it will be resolved over time due to drivers’ dynamic rerouting behavior. However, under the assumption of the static OD matrix, with the difficulty of detouring as explained in
In the proposed method, the residual between the observed and simulated link traffic volumes is minimized subject to constraints on OD traffic volume, as a kind of QP problem. The optimization problem with the objective function and its constraints is
To solve
This assumption means that the product of matrix
Here,
Based on the relation in
The assumption in
The model described in the previous subsection is a basic optimization model that works well only in a free-flow state for a network. As described in
The number of stuck vehicles
The authors add a constraint regarding stuck vehicles to the optimization problem in
Here,
This constraint is given for a particular link
In addition, to reduce the fictitious congestion, the authors introduce sign inversion of the elements of matrix
The sign inversion is based on typical traffic flow characteristics [
The BPR function, the empirical velocity-traffic volume relation, is often used for traffic assignment in traffic engineering conventionally [
Since the shape of this diagram and the value of the critical density, where the relation of the volume and the density inverses, depends on the links, it is difficult to determine this relation directly. Therefore, it is important to employ congestion detection to estimate congestion situations.
In the numerical experiments in this study, a MAS-based microscopic simulator, ADVENTURE_Mates [
Vehicle searches the shortest travel time route, referring to the mean travel time of each link during the nearest 5 min. If a vehicle cannot keep its desired route because of some unexpected event, e.g., a lane-change failure due to congestion, rerouting is invoked.
The authors conducted 90-min simulations and measured link traffic volumes during the last 60-min for the evaluation. Since there were no vehicles in the initial state and the system was in a transient state for the first 30 min, the authors excluded these irregular states from consideration.
The authors applied the method to a real city road network to test the proposed method. The network and observation point locations are shown in
The north-south and east-west ranges are both approximately 8 km in length. The network is in the central area of Fukui City, Japan. In this network, there are 5,852 possible OD pairs; however, in an effort to simplify, the authors extracted 1336 pairs (
First, the authors assigned a small OD traffic volume-2 veh/h (vehicles per hour)-to all 5,852 possible OD pairs to create the initial OD matrix
A roughly-estimated OD matrix was then obtained by calculating
Then, OD pairs with large OD traffic volumes were extracted.
As seen in the figure, a jump in frequency occurs at 3.7–3.8 veh/h. The authors regarded 3.8 veh/h as a threshold and assumed that the OD pairs with a traffic volume smaller than the threshold were ineffective in terms of the overall traffic phenomena. Therefore, these pairs were excluded to reduce the total number of OD pairs.
The network includes 118 observation points (
In the experiments, the criteria for the congestion detection are set as follows: Duration criterion
Among many evaluation indices, at least it is necessary to evaluate based on the objective function. Thus, the authors confirmed the reproducibility of the link traffic volumes by evaluating the correlation coefficient
In addition, the second index is used. This one indicates the degree of congestion measured as the number of stuck vehicles. Heat maps for this index are used to visually identify and evaluate the congestion range and magnitude. In this study, if the number of stuck vehicles is closer to zero, the result is recognized to be more effective in suppressing fictitious congestion.
The authors considered four experimental cases, as shown in
Verification | Control | Weak | Strong | |
---|---|---|---|---|
Permitting vehicle collision | Yes | No | No | No |
Congestion detection | No | No | Yes | Yes |
Congestion measurement timing* | N/A | N/A | 30 min | 60 min |
Critical number of stuck vehicles |
N/A | N/A | 5 | 10 |
Sign inversion of |
No | No | Yes | Yes |
Note: * Values denote the elapsed time after the start of simulations.
The latter category is composed of three cases: Control, Weak and Strong. In all three cases, vehicle collisions should be avoided. In the Control case, congestion detection is not considered. If traffic volume is large, fictitious congestion is expected to occur. As the label suggests, this case is used as the reference case for the group. In contrast, congestion detection, as described in the previous section, is considered in both the Weak and Strong cases. The differences between the Weak and Strong cases are (1) the timing of the congestion measurement, i.e., the threshold used to judge congestion, and (2) sign inversion. In the Strong case, the constraints are applied to more links than in the Weak case.
The proposed method was verified in the free-flow condition using five trials with different random seeds for the simulator. The results are shown in
Proposed method | Yang et al. [ |
Omrani et al. [ |
|
---|---|---|---|
RRMSE[%] | 14.8–16.9 | 21.6–29.9 | 15 |
Correlation coefficient | 0.97–0.99 | 0.93–0.96 | N/A |
Method for upper-level optimization | QP | SPSA | Parallel GA |
Dynamic rerouting | Restricted | Fully available | Fully available |
Under the free-flow assumption, the traffic situations reproduced by the three approaches showed no substantial differences regardless of whether the full dynamic rerouting functions were available, as congestion rarely occurred. Furthermore, all three methods produced small RRMSEs and large correlation coefficients. Namely, we can judge the proposed model has a similar estimation performance as the methods of Yang et al. and Omrani et al.
The link traffic volume reproducibilities under congestion conditions are shown in
Proposed method | Yang et al. [ |
Shafiei et al. [ |
|
---|---|---|---|
RMSE[veh/h] | 70–80 | N/A | 20.79 |
Iterations to minimum RMSE | 3–4 | 3–4 | N/A |
Method for upper-level optimization | QP | SPSA | Gradient-based optim. |
Dynamic rerouting | Restricted | Fully available | Fully available |
In all cases, the RMSEs were observed at the 3rd or 4th iteration step, and increased subsequently. This can be explained by the fact that congestion grew worse in later iterations. There were no significant differences among the cases in terms of their RMSE. The number of iteration steps needed to produce a feasible optimal result with the proposed method was nearly identical to that for Yang et al.’s method [
Next, the results were compared to a study by Shafiei et al. [
Shafiei et al. pointed out that if the gradient of the objective function was simply used for updating the OD matrix solution candidate, it would be invalid under congested conditions. Though their approach is similar to the congestion detection method employed in this research, as given in
Here, subscript
Shafiei et al. calculated the second term of
As a result of testing their approach on a small-scale network, Shafiei et al. obtained an RMSE of 20.79 in a heavy congestion scenario. Clearly, this is much smaller than the RMSE of 70–80 obtained in the present study. The authors consider that the difference arises from the dynamic rerouting feature implemented in the traffic simulator used by Shafiei et al. In terms of distributing demand, full dynamic rerouting affects each vehicle’s routing strategy dynamically, whereas the presently proposed method affects traffic volume statically outside the simulation. Therefore, the authors doubt that the larger RMSE for the proposed method arises from fictitious congestion occurring in the simulation.
The change of the total number of stuck vehicles, which is calculated simply by summing all values for all links, is shown in
The results also show that the total number of stuck vehicles increases monotonically at each iteration in all cases. In iteration steps 1–4, since the total number of generated vehicles increases with each iteration, there is an increase in the total number of stuck vehicles. In later iteration steps, as noted in
The authors used a simulator with restricted dynamic rerouting to reduce the computational time in the OD estimation process. The most calculation-expensive operation in the simulation is the route search. In Dijkstra’s algorithm, the origin of the A* algorithm, the worst-case time complexity is
Here, considering additional assumptions, the formulation is expressed like
Quadratic programming was used in this study reduce the number of simulation runs in one iteration, and a majority of the computational time is consumed in the simulation portion of the procedure. For example, the mean values in one iteration of the Control case were 131.4 s in running simulation and 38.6 s in running QP solver. Even in the free-flow state, the computational time for the simulation predominates in the OD estimation. Our work supports that 75% of the computation time is spent in routing operation through a simulation run [
Here,
When dealing with extremely large networks, the QP solver may take longer computational time than the simulation. The worst-case time complexity for the QP algorithm is roughly approximated as
If we need to reduce the time for solving QP, reducing the number of variables is preferable. Since it is possible to conduct clustering for the results of a traffic simulation [
In this paper, the OD estimation problem was formulated as a bi-level programming problem; the authors introduced congestion detection into the process of updating the OD matrices (upper-level optimization) to combine with a MAS-based microscopic simulator (lower-level optimization) with restricted dynamic rerouting. Because full dynamic rerouting functions are computationally expensive, restricted dynamic rerouting was used to reduce the computational cost. At the same time, a congestion detection was introduced to suppress excess traffic demand that cannot be treated well by the restricted dynamic rerouting. Although the congestion detection was combined with restricted dynamic rerouting, the method can also be applied to a simulator with full dynamic rerouting. The proposed congestion detection could reduce fictitious congestions that result from restricting dynamic rerouting. Test results showed that stuck vehicles were reduced by 12%. The reduction of fictitious congestion can improve the numerical stability of the entire estimation method.
Additionally, the reproducibility of link traffic volume using the proposed method proved to be nearly the same as that of existing methods. At the same time, the proposed method is computationally more efficient since the calculation cost of dynamic rerouting is reduced. This advantage is particularly evident when targeting wider-area or higher-demand conditions. However, the proposed method guarantees that reproducibility at the link without observation. It is required additional observation points or additional data source to fit the volume at such a link, velocities or other measurements. The authors regard it as for future task.
Importantly, the proposed method can be applied to any other traffic simulators that can output link traffic volume and the number of stuck vehicles. In addition, the proposed approach of adding information to the analysis may contribute to enhancing the efficiency of NN-based methods. For example, the authors have shown in the previous work [
It would be prudent for future work to consider utilizing other observable traffic attributes as data sources for validation. For example, as described in
The first author was supported by the H-UTokyo Lab. Energy Project.