Simple and fast trip generation for large scale traffic simulation

A large-scale traffic simulator with microscopic model requires trip generation for millions of vehicles. To achieve a realistic result, the trip generation should provide a variety of trips between pairs of locations from Origin-Destination (OD) table reflecting the choices of drivers. Shortest paths take long time to generate and often differ from the choices of drivers. We propose a simple and fast tree-based algorithm in this paper. Our algorithm mixes shortest path trees starting from some location nodes in each subarea of the OD table as preprocessing and then generates trips by probabilistically traversing the mixed shortest path trees. Experiments reveal that the tree-based algorithm runs much faster than the naive one. We also confirm that, under certain conditions on the granularity of the OD table, the results of simulation using trips generated by our algorithm do not differ much from traffic conditions observed in the real world.