Dynamic Dual Graph Model for Turn Delays on Road Networks
道路转向延迟的动态对偶图模型

Traditional dual graph modeling turn delays at road intersections are ill-suited to the time-dependent route planning in the travel information services, due to the ignorance of time-dependency of transportation networks. With introducing a time factor into a dual graph, a dynamic dual network model is presented, where the links in the original network are mapped into the nodes in the dual network, and the turns in the original network are mapped into the links in the dual network. Besides, the First-In-First-Out(FIFO) condition is defined for this dynamic dual network, and two relevant arrival-time computational formulas are then given out. The classical label-setting shortest path algorithm is temporally adapted to the dynamic dual network by the definition of origin-destination dual node sets and time-dependent dual node labels. An experiment on a real road network shows that the proposed model is suitable for dealing with the turn delays, and saved about 16 percent travel time in the real-time route planning.