Stochastic User Equilibrium (SUE) models allow the representation of the perceptual and preferential differences that exist when drivers compare alternative routes through a transportation network. However, as an effect of the used choice models, conventional applications of SUE are based on the assumption that all available routes have a positive probability of being chosen, however unattractive. In this paper, a novel choice model, the Bounded Choice Model (BCM), is presented along with network conditions for a corresponding Bounded SUE. The model integrates an exogenously-defined bound on the random utility of the set of paths that are used at equilibrium, within a Random Utility Theory (RUT) framework. The model predicts which routes are used and unused (the choice sets are equilibrated), while still ensuring that the distribution of flows on used routes accords to a Discrete Choice Model. Importantly, conditions to guarantee existence and uniqueness of the Bounded SUE are shown. Also, a corresponding solution algorithm is proposed and numerical results are reported by applying this to the Sioux Falls network.

Traffic congestion on urban road networks has been recognized as one of the most serious problems with which modern cities are confronted. It is generally anticipated that Dynamic Route Guidance Systems (DRGS) will play an important role in reducing urban traffic congestion and improving traffic flows and safety. One of the most critical issues in designing these systems is in the development of optimal routing strategies that would maximize the benefits to overall system as well as individual users. Infrastructure based DRGS have advantage of pursuing system optimal routing strategy, which is more essential under abnormal traffic conditions such as non-recurrent congestion and natural disaster. However user compliance could be a problem under such a strategy, particularly when some of equipped drivers are urged not to choose minimum travel time path for the sake of improving the total network travel time. On the other hand, In-vehicle based DRGS can utilize the user-specified route selection criteria to avoid "Braess Paradox" under normal traffic conditions. However, it may be of little use under abnormal traffic conditions and high DRGS market penetration. In conducting the comparative analysis between system optimal strategy and user equilibrium strategy, significant differences were found within the mid-range traffic demand. The maximum total travel time difference occurs when the level of traffic demand is half of the system capacity. At this point, system optimal route guidance strategy can save more than 11% of the total travel time of user equilibrium route guidance strategy. The research proposes an adaptive routing strategy as an efficient dynamic route guidance under non-recurrent traffic congestion. Computation results show that there is no need to implement system optimal routing strategy at the initial stage of the incident. However, it is critical to use system optimal routing strategy as freeway and arterial are getting congested and the queue delay in freeway increases. The adaptive routing strategy is evaluated using Traffic simulation model, INTEGRATION. According to simulation results using an ideal network, the travel time saving ratio is maximum when both arterial and freeway have normal traffic demand under incident. In case of a realistic network, the adaptive routing strategy also proved to save the total travel time between 3% to 10% over the traditional user equilibrium routing strategy. The reduction of total travel time increases as the incident duration increases. Consequently, it is concluded that the adaptive routing strategy for DRGS is more efficient than using user equilibrium routing strategy alone. / Ph. D.

Cette thèse porte sur les modèles d'équilibre dynamique sur un réseau de transport et de leurs applications à l'affectation de trafic. Elle vise à proposer une formulation à la fois générale, mathématiquement rigoureuse et microéconomiquement cohérente de l'équilibre dynamique. Une attention toute particulière est accordée à la représentation de la demande de transport et plus spécifiquement à la modélisation des hétérogénéités dans les préférences des usagers du réseau, ainsi que de leurs stratégies de choix d'horaires dans leurs déplacements. Tout d'abord nous exprimons l'équilibre dynamique comme un jeu de Nash avec un continuum de joueurs. Cette formulation nous permet d'obtenir un résultat d'existence. Celui-ci s'applique notamment au plus simple des modèles d'équilibre dynamique, où les usagers sont identiques et ne choisissent pas leurs horaires de départ. Ensuite, nous présentons deux modèles d'équilibre pour lesquels une solution analytique peut être établie. Le premier est une généralisation du modèle de goulot de Vickrey. Alors que Vickrey considère une distribution des horaires préférés d'arrivée en forme de S, nous traitons de distributions quelconques. Le deuxième modèle proposé est un réseau à péage avec deux routes et des usagers dont la valeur du temps est distribuée. Ce modèle nous permet d'investiguer les efficacités relatives de différentes stratégies de tarification et de voir comment celles-ci sont affectés par le niveau d'hétérogénéité dans la valeur du temps. Pour finir, un modèle calculable est présenté et des méthodes de résolution sont proposées. Le modèle est testé sur le réseau routier national. Par ailleurs, il est exploité pour tester une tarification modulée en fonction du temps dont l'objectif est d'atténuer la congestion lors des grands départs de vacances / This thesis is focused on dynamic user equilibrium (DUE) models and theirapplications to traffic assignment. It aims at providing a mathematically rigorous and general formulation for the DUE. Particular attention is paid to the representation of transport demand and more specifically to trip scheduling and users with heterogeneous preferences.The DUE is first expressed as a Nash game with a continuum of players. It strongly relies on up-to-date results from mathematical economics. This formulation allows to prove an existence result for DUE. This results notably applies to one of the simplest dynamic user equilibrium model, where users are homogeneous and departure time choice is not allowed.Then, two simple DUE models for which the solutions can be derived analytically are presented. The first one is a generalization of the Vickrey's bottleneck model. Whereas Vickrey assumed that the distribution of preferred arrival time is S-shaped, we consider more general distributions. In the second model, we have a two-route tolled network where users are continuously heterogeneous with respect to their value of time. This allows us to conduct a study on the relative efficiencies of various pricing strategy and how it is affected by the level of heterogeneity in users' value of time.Finally, a computable model is designed and corresponding solution methods are proposed. A test on the french national road network is conducted. The model is used to assess an hypothetical time-varying pricing scheme intended to ease summer traffic congestion

Aprendizagem por reforço multiagente (do inglês, MARL) é uma tarefa desafiadora em que agentes buscam, concorrentemente, uma política capaz de maximizar sua utilidade. Aprender neste tipo de cenário é difícil porque os agentes devem se adaptar uns aos outros, tornando o objetivo um alvo em movimento. Consequentemente, não existem garantias de convergência para problemas de MARL em geral. Esta tese explora um problema em particular, denominado escolha de rotas (onde motoristas egoístas deve escolher rotas que minimizem seus custos de viagem), em busca de garantias de convergência. Em particular, esta tese busca garantir a convergência de algoritmos de MARL para o equilíbrio dos usuários (onde nenhum motorista consegue melhorar seu desempenho mudando de rota) e para o ótimo do sistema (onde o tempo médio de viagem é mínimo). O principal objetivo desta tese é mostrar que, no contexto de escolha de rotas, é possível garantir a convergência de algoritmos de MARL sob certas condições. Primeiramente, introduzimos uma algoritmo de aprendizagem por reforço baseado em minimização de arrependimento, o qual provamos ser capaz de convergir para o equilíbrio dos usuários Nosso algoritmo estima o arrependimento associado com as ações dos agentes e usa tal informação como sinal de reforço dos agentes. Além do mais, estabelecemos um limite superior no arrependimento dos agentes. Em seguida, estendemos o referido algoritmo para lidar com informações não-locais, fornecidas por um serviço de navegação. Ao usar tais informações, os agentes são capazes de estimar melhor o arrependimento de suas ações, o que melhora seu desempenho. Finalmente, de modo a mitigar os efeitos do egoísmo dos agentes, propomos ainda um método genérico de pedágios baseados em custos marginais, onde os agentes são cobrados proporcionalmente ao custo imposto por eles aos demais. Neste sentido, apresentamos ainda um algoritmo de aprendizagem por reforço baseado em pedágios que, provamos, converge para o ótimo do sistema e é mais justo que outros existentes na literatura. / Multiagent reinforcement learning (MARL) is a challenging task, where self-interested agents concurrently learn a policy that maximise their utilities. Learning here is difficult because agents must adapt to each other, which makes their objective a moving target. As a side effect, no convergence guarantees exist for the general MARL setting. This thesis exploits a particular MARL problem, namely route choice (where selfish drivers aim at choosing routes that minimise their travel costs), to deliver convergence guarantees. We are particularly interested in guaranteeing convergence to two fundamental solution concepts: the user equilibrium (UE, when no agent benefits from unilaterally changing its route) and the system optimum (SO, when average travel time is minimum). The main goal of this thesis is to show that, in the context of route choice, MARL can be guaranteed to converge to the UE as well as to the SO upon certain conditions. Firstly, we introduce a regret-minimising Q-learning algorithm, which we prove that converges to the UE. Our algorithm works by estimating the regret associated with agents’ actions and using such information as reinforcement signal for updating the corresponding Q-values. We also establish a bound on the agents’ regret. We then extend this algorithm to deal with non-local information provided by a navigation service. Using such information, agents can improve their regrets estimates, thus performing empirically better. Finally, in order to mitigate the effects of selfishness, we also present a generalised marginal-cost tolling scheme in which drivers are charged proportional to the cost imposed on others. We then devise a toll-based Q-learning algorithm, which we prove that converges to the SO and that is fairer than existing tolling schemes.

No description available.

Aprendizagem por reforço multiagente (do inglês, MARL) é uma tarefa desafiadora em que agentes buscam, concorrentemente, uma política capaz de maximizar sua utilidade. Aprender neste tipo de cenário é difícil porque os agentes devem se adaptar uns aos outros, tornando o objetivo um alvo em movimento. Consequentemente, não existem garantias de convergência para problemas de MARL em geral. Esta tese explora um problema em particular, denominado escolha de rotas (onde motoristas egoístas deve escolher rotas que minimizem seus custos de viagem), em busca de garantias de convergência. Em particular, esta tese busca garantir a convergência de algoritmos de MARL para o equilíbrio dos usuários (onde nenhum motorista consegue melhorar seu desempenho mudando de rota) e para o ótimo do sistema (onde o tempo médio de viagem é mínimo). O principal objetivo desta tese é mostrar que, no contexto de escolha de rotas, é possível garantir a convergência de algoritmos de MARL sob certas condições. Primeiramente, introduzimos uma algoritmo de aprendizagem por reforço baseado em minimização de arrependimento, o qual provamos ser capaz de convergir para o equilíbrio dos usuários Nosso algoritmo estima o arrependimento associado com as ações dos agentes e usa tal informação como sinal de reforço dos agentes. Além do mais, estabelecemos um limite superior no arrependimento dos agentes. Em seguida, estendemos o referido algoritmo para lidar com informações não-locais, fornecidas por um serviço de navegação. Ao usar tais informações, os agentes são capazes de estimar melhor o arrependimento de suas ações, o que melhora seu desempenho. Finalmente, de modo a mitigar os efeitos do egoísmo dos agentes, propomos ainda um método genérico de pedágios baseados em custos marginais, onde os agentes são cobrados proporcionalmente ao custo imposto por eles aos demais. Neste sentido, apresentamos ainda um algoritmo de aprendizagem por reforço baseado em pedágios que, provamos, converge para o ótimo do sistema e é mais justo que outros existentes na literatura. / Multiagent reinforcement learning (MARL) is a challenging task, where self-interested agents concurrently learn a policy that maximise their utilities. Learning here is difficult because agents must adapt to each other, which makes their objective a moving target. As a side effect, no convergence guarantees exist for the general MARL setting. This thesis exploits a particular MARL problem, namely route choice (where selfish drivers aim at choosing routes that minimise their travel costs), to deliver convergence guarantees. We are particularly interested in guaranteeing convergence to two fundamental solution concepts: the user equilibrium (UE, when no agent benefits from unilaterally changing its route) and the system optimum (SO, when average travel time is minimum). The main goal of this thesis is to show that, in the context of route choice, MARL can be guaranteed to converge to the UE as well as to the SO upon certain conditions. Firstly, we introduce a regret-minimising Q-learning algorithm, which we prove that converges to the UE. Our algorithm works by estimating the regret associated with agents’ actions and using such information as reinforcement signal for updating the corresponding Q-values. We also establish a bound on the agents’ regret. We then extend this algorithm to deal with non-local information provided by a navigation service. Using such information, agents can improve their regrets estimates, thus performing empirically better. Finally, in order to mitigate the effects of selfishness, we also present a generalised marginal-cost tolling scheme in which drivers are charged proportional to the cost imposed on others. We then devise a toll-based Q-learning algorithm, which we prove that converges to the SO and that is fairer than existing tolling schemes.

Aprendizagem por reforço multiagente (do inglês, MARL) é uma tarefa desafiadora em que agentes buscam, concorrentemente, uma política capaz de maximizar sua utilidade. Aprender neste tipo de cenário é difícil porque os agentes devem se adaptar uns aos outros, tornando o objetivo um alvo em movimento. Consequentemente, não existem garantias de convergência para problemas de MARL em geral. Esta tese explora um problema em particular, denominado escolha de rotas (onde motoristas egoístas deve escolher rotas que minimizem seus custos de viagem), em busca de garantias de convergência. Em particular, esta tese busca garantir a convergência de algoritmos de MARL para o equilíbrio dos usuários (onde nenhum motorista consegue melhorar seu desempenho mudando de rota) e para o ótimo do sistema (onde o tempo médio de viagem é mínimo). O principal objetivo desta tese é mostrar que, no contexto de escolha de rotas, é possível garantir a convergência de algoritmos de MARL sob certas condições. Primeiramente, introduzimos uma algoritmo de aprendizagem por reforço baseado em minimização de arrependimento, o qual provamos ser capaz de convergir para o equilíbrio dos usuários Nosso algoritmo estima o arrependimento associado com as ações dos agentes e usa tal informação como sinal de reforço dos agentes. Além do mais, estabelecemos um limite superior no arrependimento dos agentes. Em seguida, estendemos o referido algoritmo para lidar com informações não-locais, fornecidas por um serviço de navegação. Ao usar tais informações, os agentes são capazes de estimar melhor o arrependimento de suas ações, o que melhora seu desempenho. Finalmente, de modo a mitigar os efeitos do egoísmo dos agentes, propomos ainda um método genérico de pedágios baseados em custos marginais, onde os agentes são cobrados proporcionalmente ao custo imposto por eles aos demais. Neste sentido, apresentamos ainda um algoritmo de aprendizagem por reforço baseado em pedágios que, provamos, converge para o ótimo do sistema e é mais justo que outros existentes na literatura. / Multiagent reinforcement learning (MARL) is a challenging task, where self-interested agents concurrently learn a policy that maximise their utilities. Learning here is difficult because agents must adapt to each other, which makes their objective a moving target. As a side effect, no convergence guarantees exist for the general MARL setting. This thesis exploits a particular MARL problem, namely route choice (where selfish drivers aim at choosing routes that minimise their travel costs), to deliver convergence guarantees. We are particularly interested in guaranteeing convergence to two fundamental solution concepts: the user equilibrium (UE, when no agent benefits from unilaterally changing its route) and the system optimum (SO, when average travel time is minimum). The main goal of this thesis is to show that, in the context of route choice, MARL can be guaranteed to converge to the UE as well as to the SO upon certain conditions. Firstly, we introduce a regret-minimising Q-learning algorithm, which we prove that converges to the UE. Our algorithm works by estimating the regret associated with agents’ actions and using such information as reinforcement signal for updating the corresponding Q-values. We also establish a bound on the agents’ regret. We then extend this algorithm to deal with non-local information provided by a navigation service. Using such information, agents can improve their regrets estimates, thus performing empirically better. Finally, in order to mitigate the effects of selfishness, we also present a generalised marginal-cost tolling scheme in which drivers are charged proportional to the cost imposed on others. We then devise a toll-based Q-learning algorithm, which we prove that converges to the SO and that is fairer than existing tolling schemes.