IP Library › Granted Patent US 12,272,239
Granted Patent B2
US 12,272,239 · App. 17/826,723 · Granted Apr 8, 2025

Systems and methods for dynamic routing of users

Inventors: Hyoshin Park (Greensboro, NC); Larkin Folsom (Mebane, NC)
Assignee: North Carolina Agricultural and Technical State University
G08G1/096811G06N20/00G08G1/0133G08G1/0141G08G1/0145G08G1/096725
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,272,239
App. No.
17/826,723
Granted
Apr 8, 2025
Kind
B2
Abstract

Methods and systems for dynamically providing routes to users of vehicles. In some examples, a method includes determining a first traffic flow model for uninformed drivers of vehicles and determining a second traffic flow model for informed drivers of vehicles. Each of the informed drivers makes driving decisions based on receiving dynamic routes from a traffic routing system. The method includes iteratively updating the second traffic flow model using the first traffic flow model until a convergence criterion is met. The method includes sending, to at least one informed driver, a first dynamic route from a first origin to a first destination using the second traffic flow model.

Claims (32)

1. A method for dynamically providing routes to users of vehicles, the method comprising:

providing, by a traffic routing system including one or more processors and a memory, an uninformed driver model builder implemented using the one or more processors for building a first traffic flow model implemented using the one or more processors for modeling vehicle route and departure time choices of a first plurality of uninformed drivers of vehicles who make vehicle route and departure time choices based on memory of the uninformed drivers and to minimize travel times of the uninformed drivers;

providing, by the traffic routing system, an informed driver model builder implemented using the one or more processors for building a second traffic flow model implemented using the one or more processors for modeling vehicle route and departure time choices of a plurality of informed drivers of vehicles who make the vehicle route and departure time choices using dynamic routes received from the traffic routing system and the dynamic routes are configured to achieve a within day (WD) dynamic system optimal (DSO) equilibrium;

iteratively updating, by the informed driver model builder, the second traffic flow model using the first traffic flow model until a convergence criterion is met; and

sending, by the second traffic flow model, to at least one informed driver and via at least one smart phone navigation application (app), vehicle navigation system, or autonomous driving system associated with the at least one informed driver, a first dynamic route from a first origin to a first destination.

2. The method of claim 1 , wherein building the first traffic flow model comprises building a dynamic network loading (DNL) model using a day-to-day boundedly rational dynamic user equilibrium (BRDUE) algorithm.

3. The method of claim 2 , wherein building the DNL model using the BRDUE algorithm comprises selecting one or more routes based on at least one simulated effective path delay.

4. The method of claim 1 , wherein building the second traffic flow model comprises building a dynamic network loading (DNL) model using a WD DSO algorithm.

5. The method of claim 4 , wherein building the DNL model using the WD DSO algorithm comprises selecting one or more routes based on: at least one path marginal cost (PMC), a utility function based on a travel cost and an information benefit, or both.

6. The method of claim 4 , wherein iteratively updating the second traffic flow model comprises iteratively updating, for each route of a plurality of routes, a demand for the route.

7. The method of claim 4 , wherein iteratively updating the second traffic flow model comprises determining a route decision for at least one informed driver using a multinomial logit model.

8. The method of claim 1 , wherein iteratively updating the second traffic flow model using the first traffic flow model until the convergence criterion is met comprises iteratively updating the second traffic flow model for a fixed number of iterations.

9. The method of claim 1 , wherein sending the first dynamic route via the at least one smart phone navigation app, vehicle navigation system, or autonomous driving system comprises sending the first dynamic route to the at least one vehicle navigation system, causing the at least one vehicle navigation system to present the first dynamic route to the at least one informed driver.

10. The method of claim 1 , wherein sending the first dynamic route via the at least one smart phone navigation app, vehicle navigation system, or autonomous driving system comprises sending the first dynamic route to the at least one autonomous driving system associated with the at least one informed driver.

11. A traffic routing system for dynamically providing routes to users of vehicles, the traffic routing system comprising:

one or more processors and memory storing executable instructions for the one or more processors;

an uninformed driver model builder implemented using the one or more processors for building a first traffic flow model implemented using the one or more processors for modeling vehicle route and departure time choices of a plurality of uninformed drivers of vehicles who make the vehicle route and departure time choices based on memory of the uninformed drivers and to minimize travel times of the uninformed drivers; and

an informed driver model builder implemented using the one or more processors for building a second traffic flow model implemented using the one or more processors for modeling vehicle route and departure time choices of a plurality of informed drivers of vehicles who make the vehicle route and departure time choices using dynamic routes received from the traffic routing system and the dynamic routes are configured to achieve a within day (WD) dynamic system optimal (DSO) equilibrium;

the informed driver model builder for iteratively updating the second traffic flow model using the first traffic flow model until a convergence criterion is met; and

the second traffic flow model for sending, to at least one informed driver and via at least one smart phone navigation application (app), vehicle navigation system, or autonomous driving system associated with the at least one informed driver, a first dynamic route from a first origin to a first destination.

12. The traffic routing system of claim 11 , wherein building the first traffic flow model comprises building a dynamic network loading (DNL) model using a day-to-day boundedly rational dynamic user equilibrium (BRDUE) algorithm.

13. The traffic routing system of claim 12 , wherein building the DNL model using the day-to-day BRDUE algorithm comprises selecting one or more routes based on at least one simulated effective path delay.

14. The traffic routing system of claim 11 , wherein building the second traffic flow model comprises building a dynamic network loading (DNL) model using a WD DSO algorithm.

15. The traffic routing system of claim 14 , wherein building the DNL model using the WD DSO algorithm comprises selecting one or more routes based on: at least one path marginal cost (PMC), a utility function based on a travel cost and an information benefit, or both.

16. The traffic routing system of claim 14 , wherein iteratively updating the second traffic flow model comprises iteratively updating, for each route of a plurality of routes, a demand for the route.

17. The traffic routing system of claim 14 , wherein iteratively updating the second traffic flow model comprises determining a route decision for at least one informed driver using a multinomial logit model.

18. The traffic routing system of claim 11 , wherein iteratively updating the second traffic flow model using the first traffic flow model until the convergence criterion is met comprises iteratively updating the second traffic flow model for a fixed number of iterations.

19. A non-transitory computer readable medium comprising computer executable instructions embodied in the non-transitory computer readable medium that when executed by at least one processor of at least one computer cause the at least one computer to perform steps comprising:

providing an uninformed driver model builder for building a first traffic flow model implemented using the one or more processors for modeling vehicle route and departure time choices of a plurality of uninformed drivers of vehicles who make the vehicle route and departure time choices based on memory of the uninformed drivers and to minimize travel times of the uninformed drivers;

providing an informed driver model builder for building a second traffic flow model implemented using the one or more processors for modeling vehicle route and departure time choices of a plurality of informed drivers of vehicles who make the vehicle route and departure time choices using dynamic routes received from the traffic routing system and the dynamic routes are configured to achieve a within day (WD) dynamic system optimal (DSO) equilibrium;

iteratively updating, by the informed driver model builder, the second traffic flow model using the first traffic flow model until a convergence criterion is met; and

sending, by the second traffic flow model, to at least one informed driver and via at least one smart phone navigation application (app), a vehicle navigation system, or autonomous driving system associated with the at least one informed driver, a first dynamic route from a first origin to a first destination.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 2, 2023
From: PARK, HYOSHIN; FOLSOM, LARKIN
To: NORTH CAROLINA AGRICULTURAL AND TECHNICAL STATE UNIVERSITY
Reel/Frame 063501/0281 →
Continuity (2)
Provisional Application 63194042 · May 27, 2021
Related Publication 20220392343A1 · Dec 8, 2022
References Cited (40)
US 5933100A · Golding · 1999 [cited by applicant]
US 7881863B2 · Uyeki et al. · 2011 [cited by applicant]
US 9275544B2 · Levine et al. · 2016 [cited by applicant]
US 10692370B2 · Elgie et al. · 2020 [cited by applicant]
US 11221229B1 · Mclean · 2022 [cited by examiner]
US 20040039516A1 · Willembrock · 2004 [cited by examiner]
US 20070299599A1 · Letchner et al. · 2007 [cited by applicant]
US 20150319093A1 · Stolfus · 2015 [cited by examiner]
US 20180108251A1 · Macfarlane et al. · 2018 [cited by applicant]
US 20180357892A1 · Dong et al. · 2018 [cited by applicant]
US 20190086224A1 · Sharma · 2019 [cited by examiner]
US 20210029612A1 · Hassan · 2021 [cited by examiner]
EP 1600910B1 · 2009 [cited by applicant]
EP 2515284A1 · 2012 [cited by applicant]
EP 3460407A1 · 2019 [cited by applicant]
Bogers, E. A., et al., “Joint modeling of advanced travel information service, habit, and learning impacts on route choice by laboratory simulator experiments”, Transportation Research Record, 1926(1), 2005, pp. 189-197. [cited by applicant]
Di, X, et al., “Boundedly rational route choice behavior: A review of models and methodologies”, Transportation Research Part B: Methodological, 85, 2016, pp. 142-179. [cited by applicant]
Doan, K., et al., “Dynamic system optimal model for multi-OD traffic networks with an advanced spatial queuing model”, Transportation Research Part C: Emerging Technologies, 51, 2015, pp. 41-65. [cited by applicant]
Du, L., et al. “An adaptive information fusion model to predict the short-term link travel time distribution in dynamic traffic networks”, Transportation Research Part B: Methodological, 46(1), 2012, pp. 235-252. [cited by applicant]
Folsom, L., et al., “Dynamic Mixed Information Strategy for Heterogeneous Network Users and System Optimal Design” 2021 (No. TRBAM-21-02070). [cited by applicant]
Folsom, L., et al., “Dynamic Routing of Heterogeneous Users After Traffic Disruptions Under Q2 a Mixed Information Framework” in Frontiers in Future Transportation, 3, 851069, May 18, 2022, pp. 1-19. [cited by applicant]
Han, K., et al., “Computing dynamic user equilibria on large-scale networks with software implementation”, in Networks and Spatial Economics, 19, 2019, pp. 869-902. [cited by applicant]
Han, K., et al., “Formulation, existence, and computation of simultaneous route-and-departure choice bounded rationality dynamic user equilibrium with fixed or endogenous user tolerance”, 2014, pp. 1-32. [cited by applicant]
Han, K., et al., “Formulation, existence, and computation of boundedly rational dynamic user equilibrium with fixed or endogenous user tolerance”, Transportation Research Part B: Methodological, 79, 2015, pp. 16-49. [cited by applicant]
Jiang, Y. Q., et al., “Macroscopic modeling of pedestrian flow based on a second-order predictive dynamic model”, Applied Mathematical Modelling, 40(23-24), 2016, pp. 9806-9820. [cited by applicant]
Lam, C. P., et al.,. “Improving human-in-the-loop decision making in multi-mode driver assistance systems using hidden mode stochastic hybrid systems”, In 2015 IEEE/RSJ international conference on intelligent robots and… [cited by applicant]
Litescu, S. C et al., “The effect of information uncertainty in road transportation systems”, Journal of computational science. 16, 2016, pp. 170-176. [cited by applicant]
Lu, C. C., et al., “A bi-criterion dynamic user equilibrium traffic assignment model and solution algorithm for evaluating dynamic road pricing strategies”, Transportation Research Part C: Emerging Technologies, 16(4), … [cited by applicant]
Osorio, C et al., “Dynamic network loading: a stochastic differentiable model that derives link state distributions”, Procedia-Social and Behavioral Sciences, 17, 2011, pp. 364-381. [cited by applicant]
Park, H et al., “Anticipatory dynamic traffic sensor location problems with connected vehicle technologies”, in Transportation Science, 52(6), 2018, pp. 1299-1326. [cited by applicant]
Park, H., et al., “Online optimization with look-ahead for freeway emergency vehicle dispatching considering availability. Transportation research part C”, emerging technologies, 109, 2019, pp. 95-116. [cited by applicant]
Peeta, S et al., “System optimal and user equilibrium time-dependent traffic assignment in congested networks”, in Annals of Operations Research, 60(1), 1995, pp. 81-113. [cited by applicant]
Silva, M. C., et al, “A multi-agent system for dynamic path planning”, in 2010 second brazilian workshop on social simulation, 2010, pp. 47-51. [cited by applicant]
Tong, C. O et al., “A predictive dynamic traffic assignment model in congested capacity-constrained road networks”, Transportation Research Part B: Methodological, 34(8), 2000, pp. 625-644. [cited by applicant]
Varia, H. R., et al., “Application of genetic algorithms for joint optimization of signal setting parameters and dynamic traffic assignment for the real network data”, Research in Transportation Economics, 38(1),2013, p… [cited by applicant]
Wardrop, J. G. “Road paper. some theoretical aspects of road traffic research”, Proceedings of the institution of civil engineers, No. 1(3), 1952, pp. 325-362. [cited by applicant]
Yildirimoglu, M., et al “Approximating dynamic equilibrium conditions with macroscopic fundamental diagrams”, Transportation Research Part B: Methodological, 70. 2014, pp. 186-200. [cited by applicant]
Yildirimoglu, M., et al “Equilibrium Analysis and Route Guidance in Large-Scale Networks with MFD Dynamics”, Transportation Research Procedia, 9, 2015, pp. 185-204. [cited by applicant]
Yu, Y., et al.“Day-to-day dynamic traffic assignment with imperfect information, bounded rationality and information sharing”, Transportation Research Part C: Emerging Technologies, 114, 2020, pp. 59-83. [cited by applicant]
Folsom, L., et al., “Information-theoretic navigation and stochastic user equilibrium. Proceedings of the INFORMS Transportation Science and Logistics (TSL) Second Triennial Conference (TSL2020)”, George Mason Universit… [cited by applicant]