SYSTEMS AND METHODS FOR DYNAMIC ROUTING OF USERS

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

1. A method for dynamically providing routes to users of vehicles, the method comprising: determining a first traffic flow model for a first plurality of uninformed drivers of vehicles; and determining a second traffic flow model for a second plurality of informed drivers of vehicles, wherein each of the informed drivers makes driving decisions based on receiving dynamic routes from a traffic routing system; iteratively updating the second traffic flow model using the first traffic flow model until a convergence criterion is met; and 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.

2. The method of claim 1, wherein determining the first traffic flow model comprises determining 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 determining the dynamic network loading (DNL) model using the day-to-day boundedly rational dynamic user equilibrium (BRDUE) algorithm comprises selecting one or more routes based on at least one simulated effective path delay.

4. The method of claim 1, wherein determining the second traffic flow model comprises determining a dynamic network loading (DNL) model using a within-day dynamic system optimal (DSO) algorithm.

5. The method of claim 4, wherein determining the dynamic network loading (DNL) model using the within-day dynamic system optimal (DSO) algorithm comprises selecting one or more routes based on: at least one path marginal cost (PMC), or 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 choice 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 a first dynamic route comprises sending the first dynamic route to a navigation system in a vehicle of the at least one informed driver, causing the navigation system to present the first dynamic route to the at least one informed driver.

10. The method of claim 1, wherein sending a first dynamic route comprises sending the first dynamic route to an autonomous driving system for the at least one informed driver.

11. A system for dynamically providing routes to users of vehicles, the system comprising: one or more processors and memory storing executable instructions for the one or more processors; and a dynamic traffic router implemented using the one or more processors, wherein the dynamic traffic router is configured for: determining a first traffic flow model for a first plurality of uninformed drivers of vehicles; and determining a second traffic flow model for a second plurality of informed drivers of vehicles, wherein each of the informed drivers makes driving decisions based on receiving dynamic routes from a traffic routing system; iteratively updating the second traffic flow model using the first traffic flow model until a convergence criterion is met; and 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.

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

13. The system of claim 12, wherein determining the dynamic network loading (DNL) model using the day-to-day boundedly rational dynamic user equilibrium (BRDUE) algorithm comprises selecting one or more routes based on at least one simulated effective path delay.

14. The system of claim 11, wherein determining the second traffic flow model comprises determining a dynamic network loading (DNL) model using a within-day dynamic system optimal (DSO) algorithm.

15. The system of claim 14, wherein determining the dynamic network loading (DNL) model using the within-day dynamic system optimal (DSO) algorithm comprises selecting one or more routes based on: at least one path marginal cost (PMC), or a utility function based on a travel cost and an information benefit, or both.

16. The 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 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 choice model.

18. The 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. The system of claim 11, wherein sending a first dynamic route comprises sending the first dynamic route to one of: a navigation system in a vehicle of the at least one informed driver, causing the navigation system to present the first dynamic route to the at least one informed driver; and an autonomous driving system for the at least one informed driver.

20. 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: determining a first traffic flow model for a first plurality of uninformed drivers of vehicles; and determining a second traffic flow model for a second plurality of informed drivers of vehicles, wherein each of the informed drivers makes driving decisions based on receiving dynamic routes from a traffic routing system; iteratively updating the second traffic flow model using the first traffic flow model until a convergence criterion is met; and 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.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0008] FIG. 1 is a diagram illustrating an example mixed objective framework that provides a method for a group of informed drivers to reduce congestion;

[0009] FIG. 2 is a block diagram of an example system for dynamically providing routes to users of vehicles;

[0010] FIG. 3 is a flow diagram of an example method for determining traffic flow models that contain a mixture of informed and uninformed drivers with different routing behaviors towards reaching equilibrium across different time scales;

[0011] FIG. 4 shows a table of notations that summarizes the notations used in this document

[0012] FIG. 5 shows the triangular fundamental diagram; and

[0013] FIG. 6 shows an example of junction dynamics.

DETAILED DESCRIPTION

[0014] This document describes an application of DTA which realistically simulates a transportation network in which drivers have different objectives and different time scales over which they make decisions in an attempt to optimize the system. We define informed drivers as the ones who are given predictive route guidance from a system manager (e.g., traffic operation center) through, for example, global positioning system (GPS)-based applications and assume that these drivers will make a bounded route choice with the provided guidance. Informed drivers are expected to comply with the provided guidance if they are given sufficient incentives and/or if the new route is not noticeably different from the original choice in terms of the cost. Such compliance will become more practical with shared autonomous vehicles that are expected to lower traveler's disutility of travel time through credits from the company for following those suggestions.

[0015] The role of information is especially relevant under expected and unexpected disruptions to infrastructure. Transportation networks are commonly impacted by short-term and long-term disruptions caused by natural or man-made events. For example, a multi-day construction zone on a highway can increase the travel time if travelers continue to follow the same route. Similarly, a post disaster event such as flooding of neighborhood streets or a tree collapse may result in reduced capacity on certain links.

[0016] The methods and systems described in this document use a mixed information framework for providing within-day route suggestions to informed drivers using predicted information about the time-varying route habits of uninformed drivers. The informed users detour from initially proposed routes to minimize network congestion after traffic disruptions, pushing the system toward optimal equilibrium, while uninformed drivers make day-to-day decisions which push the system toward user equilibrium.

[0017] FIG. 1 is a diagram illustrating an example mixed objective framework that provides a method for a group of informed drivers to reduce the within-day congestion caused by uninformed drivers who are making choices based on day-to-day habits on route and departure time after a traffic disruption. Informed drivers are provided with the within-day route guidance based on the anticipated behaviors of uninformed drivers on the network day-to-day, by adjusting route choices toward system optimum.

[0018] In some cases, the day-to-day evolution of traffic flows follows the same framework as the iterative process of DTA models and accurately simulates the iterative day-to-day transition of the adaptive and bounded behavior of uninformed drivers during the disruption of a transportation network. The resulting congestion patterns are caused by uninformed drivers' discrete decision-making processes before reaching equilibrium.

[0019] The day-to-day decision-making of uninformed drivers may result in congestion depending on levels of perturbations and network congestion. The systems and methods described in this document can be used to reduce the congestion caused by uninformed users making day-to-day decisions by strategically rerouting informed drivers. The within-day traffic dynamics are incorporated into the simulation at the end of the day to reoptimize (for example, offline) next day's informed driver strategy considering day-to-day dynamics of uninformed drivers. For an application to a post disaster event, day 1 of the model is after loading within-day travel behaviors of the day of the collapse. The methods and systems can be applied to inform human drivers, Connected Autonomous Vehicles (CAVs) operating in mixed autonomy networks, or both.

[0020] FIG. 2 is a block diagram of an example system 200 for dynamically providing routes to users of vehicles. The system 200 includes a traffic routing system 202 configured for modeling the behavior of uniformed drivers 204 and providing routes to informed drivers 206a-b over a network. The traffic routing system 202 can provide routes over a data communications network 208, e.g., a cellular telecommunications network that communicates wirelessly with computing devices in the vehicles 206a-b. The traffic routing system 202 can provide routes to vehicles 206a where the driver is using a navigation system, to vehicles 206b that are operating autonomously, or both.

[0021] The traffic routing system 202 includes one or more processors 210 and memory 212 storing executable instructions for the one or more processors 210. In operation, the traffic routing system 202 implements a dynamic traffic router using the processors 210 and memory 212 for sending dynamic routes to the informed drivers 206a-b.

[0022] The traffic routing system 202 includes an uninformed driver model builder 214 configured for determining a traffic flow model 216 for the uninformed drivers 204. Determining the traffic flow model 216 can include determining the first traffic flow model comprises determining a dynamic network loading (DNL) model using a day-to-day boundedly rational dynamic user equilibrium (BRDUE) algorithm. Determining the dynamic network loading (DNL) model using the day-to-day boundedly rational dynamic user equilibrium (BRDUE) algorithm comprises selecting one or more routes based on at least one simulated effective path delay. Further examples regarding the traffic flow model 216 for the uninformed drivers 204 is provided below.

[0023] The traffic routing system 202 includes an informed driver model builder 218 configured for determining a traffic flow model 220 for the informed drivers 206a-b. The informed drivers 206a-b make driving decisions based on receiving dynamic routes from the traffic routing system 202. The informed driver model builder 218 is configured for iteratively updating the traffic flow model 220 using the traffic flow model 216 for the uninformed drivers 204 until a convergence criterion is met.

[0024] Determining the traffic flow model 220 can include determining a dynamic network loading (DNL) model using a within-day dynamic system optimal (DSO) algorithm. Determining the dynamic network loading (DNL) model using the within-day dynamic system optimal (DSO) algorithm can include selecting one or more routes based on at least one path marginal cost (PMC). Iteratively updating the second traffic flow model can include iteratively updating, for each route of a plurality of routes, a demand for the route. Iteratively updating the second traffic flow model can include determining a route decision for at least one informed driver using an informed driver Mlogit model. Further examples regarding the traffic flow model 220 are provided below.

[0025] The traffic routing system 202 receives updated traffic data from a traffic information server 222. The traffic information server 222 can provide any appropriate information regarding traffic flow for the uninformed driver model builder 214 and the informed driver model builder 218. For example, the traffic information server 222 can provide live traffic flow data, e.g., from navigation systems in the vehicles 206a-b of the informed drivers. In another example, the traffic information server 222 can provide updates regarding road closures.

[0026] The traffic routing system 202 includes a dynamic traffic assignor 224 configured for sending, to one or more informed drivers 206a-b, dynamic routes using the traffic flow model 220. Sending a dynamic route can include sending the dynamic route to a navigation system in a vehicle 206a of an informed driver, causing the navigation system to present the dynamic route to the informed driver. Sending a first dynamic route comprises sending the first dynamic route to an autonomous driving system 206b for the at least one informed driver.

[0027] The traffic routing system 202 is illustrated in FIG. 2 as being a single computing system; however, in operation, various functions of the traffic routing system 202 can be distributed. For example, the model builders 214 and 218 can be implemented in a separate system from the dynamic traffic assignor 224, such that model building is performed offline and dynamic traffic assignment is performed by a separate system serving users.

[0028] In some examples, the model builders 214 and 218 can be implemented using parallel processing. An additional convenient property of the WD DSO methodology is that it is easily parallelized, allowing further computational improvements over the serial method. The ease of parallelization comes from the fact that each calculation of PMC only considers the effect of one path and departure time on all other paths and departure times. Each PMC calculation is independent of other PMC calculations. Therefore, parallelization can be applied to make the problem more computationally tractable.

[0029] FIG. 3 is a flow diagram of an example method 300 for determining traffic flow models that contain a mixture of informed and uninformed drivers with different routing behaviors towards reaching equilibrium across different time scales. Uninformed drivers make their route and departure time choices based on the memory of their own prior effective travel cost and selfishly seek to minimize their own travel time.

[0030] If all drivers are uninformed, the route choices will iteratively converge to the BRDUE conditions. The informed drivers in the presented model can be, for example, accessing an app, which they use to determine their route and departure time choice. The informed drivers make within-day decisions based on the information presented by the app, which suggests the best routes based on the predicted network state for that day. Unlike the uninformed drivers, informed drivers are given routes that seek to push the system toward WD DSO equilibrium. Informed drivers' route and departure time choices are calculated using a separate within-day DNL procedure. The within-day DNL procedure is used to calculate the PMC for each route and departure time. PMC considers the additional delay on all other drivers when an informed driver chooses a given route and departure time. [0031] Group 1 (Uninformed): Choose route and departure time based on Effective Path Delay, using DTD BRDUE DTA algorithm, influenced the transition between the presence of perturbations and after removal of perturbations. Drivers are selfishly seeking to minimize their own travel time. [0032] Group 2 (Informed): Choose route and departure time using a smart phone navigation app, or other appropriate navigation system, which suggests routes with the least PMC. This is calculated using a within-day DTA algorithm. These drivers are directed to push the system toward DSO, mitigating congestion caused by the inability of uninformed drivers to predict perturbations in the network.

[0033] The extent to which Group 2 (Informed drivers) can be rerouted is subject to additional constraints based on information gained for other informed drivers and their own indifference bands. Informed drivers should be convinced to choose a system optimal route and, in some cases, it will only work over time if the maximum deviation from a user optimal route is within their indifference band, which is defined as a range of total travel times over which the informed travelers are indifferent.

[0034] For example, if the shortest travel time at DUE between an OD pair is Z units and the indifference band for an informed traveler is z units, then informed travelers are convinced to switch their routes and departure times based on their experienced travel time such that their resulting travel time is at most Z+z. In some example, the range of indifference band is up to 400 seconds.

[0035] The method 300 starts from the initialization of the demand for each O-D pair at each departure time without informed drivers switching routes (302), run day to day and within-day DNL until the minimum solution is found in DSO with informed drivers strategy for a fixed number of days. The method 300 includes running the DTD BRDUE DNL model (304) and then calculating a path marginal cost (306). The method 300 includes running the WD DSO O-D DNL model (308) and updating the DSO O-D demand values (310). The method 300 includes checking if a convergence criterion is met (312), and if not, incrementing an iteration (314) and repeating the calculation of PMC, running the WD DSO DNL model, and updating the DSO O-D demand.

[0036] If the convergence criteria is met, the method 300 includes checking if a last day has been reached (316), e.g., a last day specified by a system operator. If so, then the method 300 stops (322). If not, then the method 300 includes incrementing the day (318), updating the BRDUE O-D demand values, and repeating the method 300 starting from running the DTD BRDUE DNL (304).

[0037] FIG. 4 shows a table of notations that summarizes the notations used in this document. The following sections describe examples of building traffic flow models for uninformed drivers and informed drivers.

[0038] Dynamic Network Loading Model

[0039] Consider a traffic network represented by a directed graph G=(, ) consisting of set of all nodes, and set of all directed links. The network is dynamic where set T denote the set of all discrete time interval indices ranging from 1,2, . . . , |T|, where each interval is one time unit wide; for our experiments, we consider each time unit to be 6 seconds.

[0040] Let .Math.N.sup.2 denote the set of all OD pairs with positive demand. In our model, travelers between an OD pair choose the departure time and routes. Denote by d.sub.rs the total demand traveling from node r to node s (assumed to be known apriori). Let K.sub.rs denote the set of all routes connecting OD pair [r, s]∈ where each route k∈K.sub.rs is an ordered sequence of links appearing from start to end. Let K=K.sub.rs be the set of all routes in the network. The flow from node r to node s departing at time t via route k∈K.sub.rs is denoted by h.sub.k(t). Equation (1) defines the flow conservation for each OD pair.

d.sub.rs=Σ.sub.t∈TΣk∈K.sub.k∈K.sub.rsh.sub.k(t) ∀[r, s]∈  (1)

[0041] Next, we describe the dynamic network loading model. Equation 2 denotes the link occupancy, or the number of vehicles on a given link l∈ at time t∈T , which is the difference between the cumulative arrival and departure curves A.sub.l(t) and D.sub.l(t).

o.sub.l(t)=A.sub.l(t)−D.sub.l(t) ∀l∈, t∈T  (2)

[0042] The density p.sub.l(t) on link l at time t is denoted by Equation 3 as a function of the number of lanes on the link (denoted by n.sub.l) and the length of the link (denoted by L.sub.l).

[00001]$\begin{array}{cc}{\rho }_l\left(t\right)=\frac{o_l\left(t\right)}{n_l{L}_i}& \left(3\right)\end{array}$

[0043] This density function can be generalized for any spatial location x measured along the length of a link l at time t, represented as p.sub.l(t, x), by taking the limit of the ratio of total time with the total area in the time space diagram as the area of the region becomes infinitely close to zero centered at point (t, x).

[0044] Models for traffic flow determine the variation of density for different times and locations. The Lighthill-Whitham-Richards (LWR) model assumes a deterministic relationship between density and flow expressed as fundamental diagram and denoted by f.sub.l(⋅) for all links l∈. Incorporating the conservation of vehicles, the partial differential equation (PDE) in Equation 4 is then used to calculate dynamics of density and flow across each link:

∂.sub.tρ.sub.l(t, x.sub.l)+∂.sub.xf.sub.l(ρ.sub.l(t, x.sub.l)=0 x.sub.l∈[a.sub.l, b.sub.l], ∀t∈Tand l∈  (4)

[0045] where x.sub.l is any point along the length of the link l∈ with a.sub.l and b.sub.l denoting the start and end points of the link (assuming a parameterized curve that represents a link in two dimensions).

[0046] In our model, we assume the flow function f.sub.l(⋅) in the LWR model is given by a triangular fundamental diagram as shown in FIG. 5. This fundamental diagram uses two linear functions to approximate the relationship between flow and density on any given link. The intercept of the two functions is the critical density ρ.sub.l.sup.c for the link, while the jam density ρ.sub.l.sup.jam is the location where the function with a negative slope intersects the density axis. Using the triangular fundamental diagram, the flow for a given density, forward wave speed v, and backward wave speed w is given by Equation 5.

[00002]$\begin{array}{cc}{f}_l\left(\rho \right)=\{\begin{array}{cc}v\rho & \rho \in \left[0,{\rho }_l^c\right]\\ -w(\rho -{\rho }_l^{\mathrm{jam}}& \rho \in \left[{\rho }_l^c,{\rho }_l^{\mathrm{jam}}\right]\end{array}& \left(5\right)\end{array}$

[0047] To solve the PDE in Equation 4 we need to know the time-varying rates of maximum flow that can enter each link (link demand) and the time-varying rates of maximum flow that can exit each link (link supply). The time-varying supply and demand functions for each link, denoted by S(ρ.sub.l(t)) and D(ρ.sub.l(t)) respectively, can then be approximated using the triangular fundamental diagram , where C is the link capacity.

[00003]$\begin{array}{c}\begin{array}{cc}D\left({\rho }_l\left(t\right)\right)=\{\begin{array}{cc}v{\rho }_l\left(t\right)& \rho <{\rho }_l^c\\ C& \rho \ge {\rho }_l^c\end{array}& \left(6\right)\end{array}\\ \begin{array}{cc}S\left({\rho }_l\left(t\right)\right)=\{\begin{array}{cc}C& \rho <{\rho }_l^c\\ -w\left({\rho }_l\left(t\right)-{\rho }_l^{\mathrm{jam}}\right)& \rho \ge {\rho }_l^c\end{array}& \left(7\right)\end{array}\end{array}$

[0048] The flow model on each link can be extended to networks with multiple links meeting at junctions, which are nodes with at least one incoming and one outgoing link. Let .Math. denote the set of all junctions. For a given junction n∈, conservation of flow across all links is given by Equation 8 which can be used as additional boundary condition to solve the combined PDEs for each incoming and outgoing link:

Σ.sub.m∈M.sub.nf.sub.m(ρ.sub.m(t, b.sub.m))=Σ.sub.q∈Q.sub.nf.sub.q(ρ.sub.q(t, a.sub.q)) ∀t∈T, n∈  (8)

[0049] To prevent confusion, subscripts m or q are used in this document to indicate the association with inlink m or outlink q.

[0050] Various junction dynamics determine how flows split at each junction. In our model, we consider a path-based DNL that tracks flow on each path. The decision making of users who pass through each junction are considered in FIG. 6 to calculate the actual supply and demand on each of the connecting links. This is accomplished by calculating the proportion of users on an incoming link m∈M who will select the outgoing link q∈Q. Given the cumulative arrival and departure curves, it is possible to determine an entry time for each link τ.sub.m(t) based on the exit time (t) for a link m. Let γ.sub.m,k(t, b.sub.m) denote the proportion of flow leaving link m from its exit point b.sub.m along route k at time t. Following the first-in-first-out principle and using the link entry time for a given exit time, the proportional contribution of an individual path flow to the total flow on a given link at time t can be estimated as follows:

γ.sub.m,k(t, b.sub.m)=γ.sub.m,k(τ.sub.m(t), a.sub.m)  (9)

[0051] In other words, the proportion of flow leaving link m along path k at time t is equal to the proportion of flow entering link m at time τ.sub.m(t). The sum of these proportions on link m over each path containing two connected links m and q gives the total proportion α.sub.m,q(t) of flow entering link q from link m at time t as shown in FIG. 6. That is,

α.sub.m,q(t)=γ.sub.m,k(t, b.sub.m)  (10)

[0052] A distribution matrix .sup.n(t), for a junction n∈ satisfying conservation of flow in Equation 8, is then constructed in Equation 11 to track the distribution of flows between incoming and outgoing links.

.sup.n(t)={α.sub.m,q(t)} ∀m∈M.sub.n, q∈Q.sub.n, n∈  (11)

[0053] The non-junction nodes such as source nodes with no incoming links and sink nodes with no outgoing links consider a simplified traffic dynamics. Sink nodes are assumed to have infinite sink capacity allowing the flow on routes terminating at the sink node to exit. On contrary, source nodes may not be able to load the entire demand if the outgoing links experience queue spillback. A point-queue model is used to account for the dynamics at origin nodes (which includes source nodes or junctions that also act as origins). In the following sections, examples of the uninformed and informed driver models are described.

[0054] Uninformed Driver Model

[0055] We model the day-to-day behavior of drivers after a disruption to the network where drivers adapt their departure time and route choice. Let denote the set of days post disruption indexed by d ranging from 1,2 . . . , ||. The update dynamics of departure time and route choice for uninformed drivers is governed by an iterative structure where travelers adapt their routes to converge to the new post-disruption equilibrium. We approximate this dynamic using a multinomial Logit model described next.

[0056] First, to circumvent exponentially high number of routes, we narrow the set of possible routes over which travelers consider updating their routes. We define canonical routes as the set of routes that deviate from the fastest path (i.e. minimum travel time path) within a specified tolerance. For a traveler departing from O-D pair [r, s]∈ at time t∈T, the set of canonical routes is denoted by .sub.rs(t) and is defined as following:

[00004]$\begin{array}{cc}{\mathrm{rs}}_{}\left(t\right)=\left\{k.Math.k\in K_{\mathrm{rs}},\frac{{\mathrm{TT}}_k\left(t\right)-{\mathrm{TT}}_{\mathrm{rs}}^{*}\left(t\right)}{{\mathrm{TT}}_{\mathrm{rs}}^{*}\left(t\right)}\le \Theta \right\}& \left(12\right)\end{array}$

[0057] where TT.sub.k(t) is the travel time on route k for departure time t, TT*.sub.rs(t) is the travel time on the time-dependent shortest path connecting O-D pair [r, s]∈ for departure time t∈T, and Θ is the driver's perception deviance. We assume Θ to be fixed across all travelers. We note that the canonical route set is time-dependent since shortest path may be different for different departure times.

[0058] Building on the BRDUE model, we update the route and departure time decisions for uninformed drivers using a Multinomial Logit Model (Mlogit). Let (k, t).sub.d denote the choice tuple representing the route and the departure time on day d∈. After executing the select choices on a given day, travelers update their choices (k, t).sub.d+1 for the next day using the MLOGIT model.

[0059] The utility of a choice is approximated using the perceived cost of each route and departure time choice for every O-D pair. We assume homogeneity across all travelers between an origin-destination pair.

[0060] The perceived cost for each route and departure time, in terms of both travel time and schedule delay (early or late arrival), is calculated in Equation 13:

PC.sub.k(t)=TT.sub.k(t)+SCD.sub.k(t) ∀k∈K, t∈T  (13)

[0061] where SCD.sub.k(t) is the schedule delay cost for path k and departure time t, given by Equation 14,

[00005]$\begin{array}{cc}{\mathrm{SCD}}_k\left(t\right)=\{\begin{array}{cc}{\varphi }_e\left({\mathrm{AT}}_k\left(t\right)-{\mathrm{TA}}_{\mathrm{rs}}\right)& \mathrm{if}{\mathrm{AT}}_k\left(t\right)\le {\mathrm{TA}}_{\mathrm{rx}}\\ {\varphi }_l\left({\mathrm{AT}}_k\left(t\right)-{\mathrm{TA}}_{\mathrm{rs}}\right)& \mathrm{if}{\mathrm{AT}}_k\left(t\right)>{\mathrm{TA}}_{\mathrm{rx}}\end{array}\forall kϵK_{\mathrm{rs}},\left[r,s\right]ϵ𝒫,tϵT& \left(14\right)\end{array}$

[0062] where AT.sub.k(t)=t+TT.sub.k(t) is the actual arrival time at the destination for route k and departure time t, TA.sub.rs is the desired arrival time for all travelers associated with the OD pair [r,s] (a single value assumed to be known apriori for each OD pair), ϕ.sub.e is the coefficient of early arrival penalty, and ϕ.sub.l is the coefficient of late arrival penalty. Equation 13 can now be incorporated into the Mlogit model.

[0063] The Mlogit model estimates the probability of choosing an alternative given the utilities across all alternatives. Let C.sub.rs be the set of all alternatives for all travelers across an OD pair [r, s]∈, defined as follows:

C.sub.rs={(k, t)|k∈.sub.rs(t), t∈T}

[0064] For the Mlogit model, the utility of an alternative (k, t)∈C.sub.rs is given by U.sub.(k,t)=−PC.sub.k(t)+ε.sub.(k,t), where ε.sub.(k,t) are the error terms associated with the utilities that are assumed to be independent and identically distributed as a Gumbel distribution with a scale parameter θ>0 and location parameter assumed to be 0. Given the assumptions, the probability of choosing alternative (k, t)∈C.sub.rs for travelers between OD pair [r, s] is given by:

[00006]$\begin{array}{cc}{\left(k,t\right)}_{}=\left(U_{\left(k,t\right)}>\underset{\left(k^{\prime },t^{\prime }\right)\ne \left(k,t\right)}{\underset{\left(k^{\prime },t^{\prime }\right)\in C_{\mathrm{rs}}}{\max }}{U}_{\left(k^{\prime },t^{\prime }\right)}\right)=\frac{\exp \left(-\theta {\mathrm{PC}}_k\left(t\right)\right)}{{.Math.}_{\left(k^{″},t^{″}\right)\in C_{\mathrm{rs}}}\exp \left(-\theta {\mathrm{PC}}_{k^{″}}\left(t^{″}\right)\right)}& \left(15\right)\end{array}$

[0065] and the path flows for a given departure time is computed as:

h.sub.k(t)=d.sub.rs.sub.(k,t) ∀(k, t)∈C.sub.rs, [r, s]∈  (16)

[0066] To model the boundedly-rational behavior of travelers, we consider an indifference band that increases the utility of current alternative thus increasing the likelihood that the traveler continues to stay on the currently chosen alternative over the next day. Adding a superscript d denoting the day of travel, we denote by h.sub.k.sup.d(t) the number of travelers choosing route k at time t on day d. We can then update the flow on next day d+1, by considering the current flow on alternative (k, t) that continues to stay with the same alternative, and the flow from all other alternatives (k′, t′) that switch to the alternative (k, t).

[0067] Equation 17 shows the update of flow from one day to the next.

[00007]$\begin{array}{cc}{h}_k^{d+1}\left(t\right)=h_k^d\left(t\right){\left(k,t\right)\leftarrow \left(k,t\right)}_{}+{.Math.}_{\underset{\left(k^{\prime },t^{\prime }\right)\ne \left(k,t\right)}{\left(k^{\prime },t^{\prime }\right)\in C_{\mathrm{rs}}}}{h}_{k^{\prime }}^d\left(t^{\prime }\right){\left(k,t\right)\leftarrow \left(k^{\prime },t^{\prime }\right)}_{}& \left(17\right)\end{array}$

[0068] where .sub.(k,t)←(k,t) is the probability that travelers choosing alternative (k, t)∈C.sub.rs will continue with the same alternative on the next day, computed as:

[00008]$\begin{array}{cc}{\left(k,t\right)\leftarrow \left(k,t\right)}_{}=\frac{e^{\left(-\theta \times \left({\mathrm{PC}}_k\left(t\right)-\Delta \right)\right)}}{e^{\left(-\theta \times \left({\mathrm{PC}}_k\left(t\right)-\Delta \right)\right)}+{.Math.}_{\underset{\left(k^{″},t^{″}\right)\ne \left(k,t\right)}{\left(k^{″},t^{″}\right)\in C_{\mathrm{rs}}}}{e}^{\left(-\theta \times {\mathrm{PC}}_{k^{″}}\left(t^{″}\right)\right)}}& \left(18\right)\end{array}$

[0069] and .sub.(k,t)←(k′,t′) is the probability that travelers choosing alternative (k′, t′)∈C.sub.rs will switch their alternative to (k, t) on the next day, computed as:

[00009]$\begin{array}{cc}{\left(k,t\right)\leftarrow \left(k^{\prime },t^{\prime }\right)}_{}=\frac{e^{\left(-\theta \times {\mathrm{PC}}_k\left(t\right)\right)}}{e^{\left(-\theta \times \left({\mathrm{PC}}_{k^{\prime }}\left(t^{\prime }\right)-\Delta \right)\right)}+{.Math.}_{\underset{\left(k^{″},t^{″}\right)\ne \left(k^{\prime },t^{\prime }\right)}{\left(k^{″},t^{″}\right)\in C_{\mathrm{rs}}}}{e}^{\left(-\theta \times {\mathrm{PC}}_{k^{″}}\left(t^{″}\right)\right)}}& \left(19\right)\end{array}$

[0070] It is easy to verify that if =0, then .sub.(k,t)←(k′,t′)=.sub.(k,t)←(k,t)=.sub.(k,t), and Equation 17 reduces to Equation 16.

[0071] Informed Driver Model

[0072] Informed drivers in the presented model are given route suggestions that minimize a cost function representing the total system cost. These users seek to reduce congestion faced by all other drivers in the network, but without noticeably penalizing themselves. Such a cost function needs to consider both the system-level cost and the cost to the user when selecting a path and departure time.

[0073] In some examples, the system 202 can use a utility function in building the informed driver model. The utility function considers the travel cost and the benefit in terms of information gained for other drivers in the network. An example utility function is provided below.

[00010]$U_{i,k}={\mathrm{PTT}}_{i,k}-\left(\alpha /.Math.K.Math.\right)\underset{j\in x^i\left(t\right)}{.Math.}\mathrm{\delta \sigma }\left(k_i,k_{j\in x^i\left(t\right)}^{*}.Math.Y,\Psi \right)$

[0074] where k.sub.i is route for driver i, k*.sub.i is a canonical route for driver j, and δσ(k.sub.i, |Υ, ψ) is the variance reduction (e.g., information gain) of k* for driver j∈x.sup.i(t) on link i when driver j runs some other route k given current driver's observation Υ and other drivers' observations ψ under the traffic data variance σ (e.g., standard deviation of travel time) with weights on the observation δ (e.g., number of samples), where x.sup.i(t) is a list of all drivers using link i. The utility function U.sub.i,k is the difference between PTT and the benefit of information gain to all other drivers when driver j takes a detour from path k* to k to gather information. These utility functions perform best under information sharing frameworks and simulations with large amounts of uncertainty. The example utility function presented above can be used to strategically alter the behavior of informed drivers by considering the trade-off of exploration and exploitation. The route with minimum disutility is presented to the informed driver, e.g., through a route suggestion app as being the most preferable route.

[0075] DSO Computation

[0076] Let h={h.sub.k(t)|k∈K, t∈T} denote the departure-rate pattern as a vector of all path flows at different departure times. The DSO formulation is defined using the following optimization problem

[00011]$\begin{array}{cc}\underset{h}{\min }\left(TSC={.Math.}_{k\in K}{.Math.}_{t\in T}{h}_k\left(t\right)\times {\mathrm{PC}}_k\left(t\right)\right)& \left(20\right)\end{array}$

[0077] subject to the following constraints:

[00012]$\begin{array}{cc}\begin{array}{c}{.Math.}_{t\in T}{.Math.}_{k\in K_{\mathrm{rs}}}{h}_k\left(t\right)=d_{\mathrm{rs}}\forall \left[r,s\right]\in \\ h_k\left(t\right)\ge 0\forall k\in K,t\in T\end{array}& \left(21\right)\mathrm{and}\left(22\right)\end{array}$

[0078] where h.sub.k(t) is the departure rate, and PC.sub.k,t is the perceived cost for route k at time t, and TSC is the total system cost.

[0079] A departure rate pattern h is a DSO solution if and only if it is equilibrated based on the corresponding path marginal cost (PMC). The PMC is defined as the increase in total system cost incurred when an additional unit of flow is added to the departure rate pattern h.sub.k(t). The PMC for route k at time t is calculated in Equation 23:

[00013]$\begin{array}{cc}PM{C}_{k,t}=\frac{\partial TSC}{\partial h_k\left(t\right)}=PM{C}_{k,t}^{\mathrm{TT}}+PM{C}_{k,t}^{\mathrm{SCD}}+P{C}_k\left(t\right)& \left(23\right)\end{array}$

[0080] where PMC.sub.k,t.sup.TT is the change in travel time cost for all other users caused by additional flow on route k at time t, PMC.sub.k,t.sup.SCD is the change in schedule delay cost for all other traffic caused by the additional flow on route k at time t, and PC.sub.k(t) is the perceived cost for an individual on route k at time t (Equation 13).

[0081] Naively using a DNL algorithm to calculate the PMC for each path and departure time can be computationally demanding. For a set of all time periods, the naive method requires |z,900 |×|T| DNL solutions per DSO iteration.

[0082] In some examples, we approximate the PMC.sub.k,t.sup.TT using the Bureau of Public Roads (BPR) function since solving the exact path marginal cost is complex due to the non-linear nature of the DNL procedure. While actual DNL is used for daily simulation of revised change in flow, the cost incurred by each traveler's route and departure time choice is estimated with revised BPR function.

[0083] Let's assume that an estimate for the travel time on route k at departure time t can be calculated using the BPR function:

[00014]$\begin{array}{cc}{\mathrm{TT}}_k\left(t\right)\approx t_{0,k}\times \left[1+{\alpha \left(\frac{h_k\left(t\right)}{k_{}}\right)}^{\beta }\right]& \left(24\right)\end{array}$

[0084] where t.sub.0,k is the free flow travel time (defined as the sum of free flow travel time on path links), h.sub.k(t) is the flow (e.g., veh/hr) on route k at time t, C.sub.k is the capacity of route k, and α and β are parameters. We define C.sub.k to be the minimum capacity across all links along the path.

[0085] While the congested links and time of congestion are computed from DNL, we consider the revised BPR to approximate the change in cost to all other paths due to change in flow on path k. To compute the impact of one unit of flow with and without the presence of congestion, we find all the paths that go through congested links in route k and iterate through all of the links in route k. Once the value of PMC.sub.k,t.sup.TT is approximated, the revised destination arrival time is estimated at the destination of route k for a departure time t, and the new value of PMC.sub.k,t.sup.SDC is approximated using Equation 14 as before.

[0086] In some examples, substantial computational improvements are made by only calculating PMC for paths and times which incur congestion and which propagate congestion onto other paths and departure times. This is accomplished by avoiding computing PMC for all uncongested paths and times, since these paths and times are assumed to be traversed at the free flow travel time and have no marginal cost on other paths or departure times. In addition, no PMC calculations are required for other paths and departure times which are unaffected by congestion on a given path at a given time. As shown in the triangular fundamental diagram (Equation 5), there is no impact of an additional vehicle below critical density for the link. Using these methods, the total number of paths and departure times requiring PMC calculation is minimized for a given spatiotemporal distribution of congestion in the network. After PMC for each path is solved, informed drivers make an updated decision using the Informed Driver Mlogit Model (IDMM) described in the next subsection, then the DNL model is executed to generate a new congestion pattern based on the decisions of informed drivers.

[0087] Informed Driver Mlogit Model (IDMM)

[0088] Finding DSO for informed drivers requires multiple iterations of route and departure time decisions. Unlike the MSA and some conventional quadratic programming models, in each subiteration i of DSO computations route and departure time decisions for informed drivers are made using the Mlogit model. Mlogit models are used for alternative-invariant problems, meaning that the regressor does not vary over the alternatives but does vary over the individual. Since the PMC already accounts for the effect that selecting an alternative has on all other alternatives and presents it as a cost which varies only over the individual, the IDMM described in this section can be treated as alternative-invariant.

[0089] Informed drivers also consider route choice over a limited canonical set of routes as defined in Equation 12. For the informed drivers, the utility of an alternative (k,t)∈C.sub.rs is given by U.sub.(k,t)=−PMC.sub.k,t+ε.sub.(k,t). The PMC for each path k and departure time t available to the O-D pair p is calculated for use in the IDMM. As in the previous section, the selection of base alternative for each solution is sequentially selected from the set of paths between the O-D pair and the set of possible departure times.

PMC.sub.k,t=PC.sub.k(t)+PMC.sub.k,t.sup.TT+PMC.sub.k,t.sup.SCD  (25)

[0090] where PMC.sub.k,t.sup.SCD is the sum of schedule delays (Equation 14) for all other paths and departure times when 1 additional unit of flow is added to path k at time t, PMC.sub.k,t.sup.TT is the cost in terms of travel time for all other paths and departure times when 1 additional unit of flow is added to path k at time t, and PC.sub.k(t) is the perceived cost of current flow on path k at time t. Therefore, PMC.sub.k,t is the marginal cost of path k at time t on all other paths and departure times. We can add travel time without schedule delays because if drivers arrive within the desired arrival time window, there is no penalty, however, if not, those will be in the later time window. Having many drivers departing at the same time as an aggregate will incur congestion, which we want to avoid.

[0091] The update of flow from one iteration to the next is governed by the IDMM model. For each OD pair [r, s]∈, the model computes the probability of switching from all other route-departure time tuples (k′, t′)∈C.sub.rs; (k′, t′)≠(k, t) to a given alternative tuple (k, t)∈C.sub.rs. The total probability of choosing route k and departure time t in the next iteration also includes the proportion of drivers who already selected route k at time t and choose not to detour or adjust their departure time. Similarly to the uninformed model, a constant scaling parameter θ.sub.2 (0.04) is used for distribution of utility errors, along with the BR switching threshold Δ.sub.2 (800 seconds), which still applies to informed drivers since not all drivers will be convinced to switch when provided with a predictive alternate route.

[0092] Path flow update from iteration i to i+1 for computing DSO is computed as follows. First, adding a superscript i, DSO denoting the subiteration of DSO computation, we denote by h.sub.k.sup.i,DSO(t) the number of travelers choosing route k at time t in DSO iteration i. We can then update the flow on next iteration i+1, by considering the current flow on alternative (k, t) that continues to stay with the same alternative, and the flow from all other alternatives (k′, t′) that switch to the alternative (k, t). We assume that the uninformed driver flow is unaffected and remains constant in the background for each DSO iteration.

[0093] Equation 26 shows the update of flow from one iteration to the next.

[00015]$\begin{array}{cc}{h}_k^{i+1,\mathrm{DSO}}\left(t\right)=h_k^{i,\mathrm{DSO}}\left(t\right){\left(k,t\right)\leftarrow \left(k,t\right)}_{\mathrm{DSO}}^{}+{.Math.}_{\underset{\left(k^{\prime },t^{\prime }\right)\ne \left(k,t\right)}{\left(k^{\prime },t^{\prime }\right)\in C_{\mathrm{rs}}}}{h}_{k^{\prime }}^{i,\mathrm{DSO}}\left(t^{\prime }\right){\left(k,t\right)\leftarrow \left(k^{\prime },t^{\prime }\right)}_{\mathrm{DSO}}^{}& \left(26\right)\end{array}$

[0094] where .sub.(k,t)←(k,t).sup.DSO is the probability that travelers choosing alternative (k, t)∈C.sub.rs will continue with the same alternative in the next DSO iteration, computed as:

[00016]$\begin{array}{cc}{\left(k,t\right)\leftarrow \left(k,t\right)}_{\mathrm{DSO}}^{}=\frac{e^{\left(-{\theta }_2\times \left({\mathrm{PMC}}_{k,t}-{\Delta }_2\right)\right)}}{e^{\left(-{\theta }_2\times \left({\mathrm{PMC}}_{k,t}-{\Delta }_2\right)\right)}+{.Math.}_{\underset{\left(k^{″},t^{″}\right)\ne \left(k,t\right)}{\left(k^{″},t^{″}\right)\in C_{\mathrm{rs}}}}{e}^{\left(-{\theta }_2\times {\mathrm{PMC}}_{k^{″},t^{″}}\right)}}& \left(27\right)\end{array}$

[0095] and .sub.(k,t)←(k′,t′).sup.DSO is the probability that travelers choosing alternative (k′, t′)∈C.sub.rs will switch their alternative to (k, t) in the next DSO iteration, computed as:

[00017]$\begin{array}{cc}{\left(k,t\right)\leftarrow \left(k^{\prime },t^{\prime }\right)}_{\mathrm{DSO}}^{}=\frac{e^{\left(-{\theta }_2\times {\mathrm{PMC}}_{k,t}\right)}}{e^{\left(-{\theta }_2\times \left({\mathrm{PMC}}_{k^{\prime },t^{\prime }}-{\Delta }_2\right)\right)}+{.Math.}_{\underset{\left(k^{″},t^{″}\right)\ne \left(k^{\prime },t^{\prime }\right)}{\left(k^{″},t^{″}\right)\in C_{\mathrm{rs}}}}{e}^{\left(-{\theta }_2\times {\mathrm{PMC}}_{k^{″},t^{″}}\right)}}& \left(28\right)\end{array}$

[0096] The iterative process of shifting travelers along different alternatives continues until convergence criteria is met. For example, the process can terminate after a fixed number of DSO iterations.

[0097] Although specific examples and features have been described above, these examples and features are not intended to limit the scope of the present disclosure, even where only a single example is described with respect to a particular feature. Examples of features provided in the disclosure are intended to be illustrative rather than restrictive unless stated otherwise. The above description is intended to cover such alternatives, modifications, and equivalents as would be apparent to a person skilled in the art having the benefit of this disclosure.

[0098] The scope of the present disclosure includes any feature or combination of features disclosed in this specification (either explicitly or implicitly), or any generalization of features disclosed, whether or not such features or generalizations mitigate any or all of the problems described in this specification. Accordingly, new claims may be formulated during prosecution of this application (or an application claiming priority to this application) to any such combination of features. In particular, with reference to the appended claims, features from dependent claims may be combined with those of the independent claims and features from respective independent claims may be combined in any appropriate manner and not merely in the specific combinations enumerated in the appended claims.