Bei verkehrspolitischen und infrastrukturellen Massnahmen folgen als wesentliche Nachfrageveränderungen vor allem Routen- und Verkehrsmittelwahleffekte. Mit der Anwendung der sequentiellen Routen- und Verkehrsmittelwahlmodelle, ist bei solchen Massnahmen aus verschiedenen Gründen eine konsistente und gesamthafte Gleichgewichtslösung nicht möglich. Das Ziel dieser Untersuchung war, ein konsistentes und verfeinertes Verfahren zu entwickeln, mit dem die Routen- und Verkehrsmittelwahl simultan bzw. in einem Schritt als eine Entscheidung berechnet werden kann. Neben dem Gleichgewicht bei der Verteilung der Verkehrsnachfrage auf die Alternativen, war die konsistente Schätzung der Modellparameter für die Bewertung von Einflussfaktoren bei den Entscheidungen hier eine weitere wichtige Anforderung. Das Modell ist in der Lage, ein realitätsentsprechendes Verhalten der Verkehrsteilnehmer, sowohl bei schwach, als auch bei stark belasteten Strassennetzen, zu beschreiben. Die unterschiedliche Wahrnehmung der Reisekosten der Verkehrsteilnehmer und die Netzüberbelastungen werden durch ein stochastisches Nutzergleichgewicht abgebildet. Das entwickelte Verfahren ermöglicht es: - die Nachfrageaufteilung mit einem konsistenten Gleichgewicht zwischen Verkehrsangebot und Verkehrsnachfrage zu berechnen. Dabei wird ein Gleichgewicht nicht nur innerhalb des Strassen- oder Schienennetzes, sondern zwischen allen verfügbaren Alternativen (unabhängig vom Verkehrsmittel) gesucht. - durch die iterative Kalibration der Modellparameter und die Nachfrageaufteilung ein konsistentes Gleichgewicht zwischen den geschätzten Modellparametern für die Nutzenfunktion und der Nachfrageaufteilung auf die vorhandenen Alternativen (Routen) zu berechnen. - mit einem stochastischen Nutzergleichgwicht die unterschiedliche Wahrnehmung der Nutzen bzw. der generalisierten Kosten der Verkehrsteilnehmer bei der Nachfrageaufteilung zu berücksichtigen. - die Auswirkungen von Angebotsveränderungen auf die Verkehrsmittelwahl und Routenwahl durch simultane Modellierung der Entscheidungen konsistent und ohne Rückkoppelungschritte zu berechnen.

This research contributes to the state of the art and state of the practice in solving a very important and computationally challenging problem in the areas of urban transportation systems, operations research, disaster management, and public policy. Being a very active topic of research during the past few decades, the problem of developing an efficient and practical strategy for evacuation of real-sized urban traffic networks in case of disasters from different causes, quickly enough to be employed in immediate disaster management scenarios, has been identified as one of the most challenging and yet vital problems by many researchers. More specifically, this research develops fast methods to find the optimal integrated strategy for traffic routing and traffic signal control to evacuate real-sized urban networks in the most efficient manner. In this research a solution framework is proposed, developed and tested which is capable of solving these problems in very short computational time. An efficient relaxation-based decomposition method is proposed, implemented for two evacuation integrated routing and signal control model formulations, proven to be optimal for both formulations, and verified to reduce the computational complexity of the optimal integrated routing and signal control problem. The efficiency of the proposed decomposition method is gained by reducing the integrated optimal routing and signal control problem into a relaxed optimal routing problem. This has been achieved through an insight into intersection flows in the optimal routing solution: in at least one of the optimal solutions of the routing problem, each street during each time interval only carries vehicles in at most one direction. This property, being essential to the proposed decomposition method, is called "unidirectionality" in this dissertation. The conditions under which this property exists in the optimal evacuation routing solution are identified, and the existence of unidirectionality is proven for: (1) the common Single-Destination System-Optimal Dynamic Traffic Assignment (SD-SODTA) problem, with the objective to minimize the total time spent in the threat area; and, (2) for the single-destination evacuation problem with varying threat levels, with traffic models that have no spatial queue propagation. The proposed decomposition method has been implemented in compliance with two widely-accepted traffic flow models, the Cell Transmission Model (CTM) and the Point Queue (PQ) model. In each case, the decomposition method finds the optimal solution for the integrated routing and signal control problem. Both traffic models have been coded and applied to a realistic real-size evacuation scenario with promising results. One important feature that is explored is the incorporation of evacuation safety aspects in the optimization model. An index of the threat level is associated with each link that reflects the adverse effects of traveling in a given threat zone on the safety and health of evacuees during the process of evacuation. The optimization problem is then formulated to minimize the total exposure of evacuees to the threat. A hypothetical large-scale chlorine gas spill in a high populated urban area (downtown Tucson, Arizona) has been modeled for testing the evacuation models where the network has varying threat levels. In addition to the proposed decomposition method, an efficient network-flow solution algorithm is also proposed to find the optimal routing of traffic in networks with several threat zones, where the threat levels may be non-uniform across different zones. The proposed method can be categorized in the class of "negative cycle canceling" algorithms for solving minimum cost flow problems. The unique feature in the proposed algorithm is introducing a multi-source shortest path calculation which enables the efficient detection and cancellation of negative cycles. The proposed method is proven to find the optimal solution, and it is also applied to and verified for a mid-size test network scenario.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses on two kind of games, bimatrix games and the traffic assignment problem. The Lemke-Howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, which we call the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses on two kind of games, bimatrix games and the traffic assignment problem. The Lemke-Howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, which we call the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses on two kind of games, bimatrix games and the traffic assignment problem. The Lemke-Howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, which we call the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation.

This dissertation aimed to improve travel time estimation for the purpose of transportation planning by developing a travel time estimation method that incorporates the effects of signal timing plans, which were difficult to consider in planning models. For this purpose, an analytical model has been developed. The model parameters were calibrated based on data from CORSIM microscopic simulation, with signal timing plans optimized using the TRANSYT-7F software. Independent variables in the model are link length, free-flow speed, and traffic volumes from the competing turning movements. The developed model has three advantages compared to traditional link-based or node-based models. First, the model considers the influence of signal timing plans for a variety of traffic volume combinations without requiring signal timing information as input. Second, the model describes the non-uniform spatial distribution of delay along a link, this being able to estimate the impacts of queues at different upstream locations of an intersection and attribute delays to a subject link and upstream link. Third, the model shows promise of improving the accuracy of travel time prediction. The mean absolute percentage error (MAPE) of the model is 13% for a set of field data from Minnesota Department of Transportation (MDOT); this is close to the MAPE of uniform delay in the HCM 2000 method (11%). The HCM is the industrial accepted analytical model in the existing literature, but it requires signal timing information as input for calculating delays. The developed model also outperforms the HCM 2000 method for a set of Miami-Dade County data that represent congested traffic conditions, with a MAPE of 29%, compared to 31% of the HCM 2000 method. The advantages of the proposed model make it feasible for application to a large network without the burden of signal timing input, while improving the accuracy of travel time estimation. An assignment model with the developed travel time estimation method has been implemented in a South Florida planning model, which improved assignment results.

Transport demand planning in South Africa is a neglected field of study, using obsolete methods to model an extremely complex, dynamic system composed of an eclectic mix of First and Third World transport technologies, infrastructure and economic participants. We identify agent-based simulation as a viable modelling paradigm capable of capturing the effects emerging from the complex interactions within the South African transport system, and proceed to implement the Multi-Agent Transport Simulation Toolkit (MATSim) for South Africa's economically important Gauteng province. This report describes the procedure followed to transform household travel survey, census and Geographic Information System (GIS) data into an activity-based transport demand description, executed on network graphs derived from GIS shape files. We investigate the influence of network resolution on solution quality and simulation time, by preparing a full network representation and a small version, containing no street-level links. Then we compare the accuracy of our data-derived transport demand with a lower bound solution. Finally the simulation is tested for repeatability and convergence. Comparisons of simulated versus actual traffic counts on important road network links during the morning and afternoon rush hour peaks show a minimum mean relative error of less than 40%. Using the same metric, the small network differs from the full representation by a maximum of 2% during the morning peak hour, but the full network requires three times as much memory to execute, and takes 5.2 times longer to perform a single iteration. Our census- and travel survey-derived demand performs significantly better than uniformly distributed random pairings of home- and work locations, which we took to be analogous to a lower bound solution. The smallest difference in corresponding mean relative error between the two cases comes to more than 50%. We introduce a new counts ratio error metric that removes the bias present in traditional counts comparison error metrics. The new metric shows that the spread (standard deviation) of counts comparison values for the random demand is twice to three times as large as that of our reference case. The simulation proves highly repeatable for different seed values of the pseudo-random number generator. An extended simulation run reveals that full systematic relaxation requires 400 iterations. Departure time histograms show how agents 'learn' to gradually load the network while still complying with activity constraints. The initial implementation has already sparked further research. Current priorities are improving activity assignment, incorporating commercial traffic and public transport, and the development and implementation of the minibus taxi para-transit mode. Copyright / Dissertation (MEng)--University of Pretoria, 2009. / Industrial and Systems Engineering / unrestricted

Optimalizace toku v síti je klasickou aplikací matematického programování. Tyto modely mají, mimo jiné, široké uplatnění také v logistice, kde se tak snažíme docílit optimálního rozdělení dopravy, např. vzhledem k maximalizaci zisku, či minimalizaci nákladů. Toto pojetí ovšem často problém idealizuje, poněvadž předpokládá existenci jediného rozhodovatele. Takový přístup je možný ve striktně organizovaných sítích jako např. v logistických sítích přepravních společností, železničních sítích či armádním zásobování. Úloha ''Traffic Assignment Problem'' (TAP) se zaměřuje na dopady teorie her na optimalizaci toku, tj. zkoumá vliv více rozhodovatelů na celkové využití sítě. V práci se zaobíráme úlohou TAP s působením náhodných vlivů, k čemuž využíváme metod stochastické a vícestupňové optimalizace. Dále zkoumáme možnosti zlepšení stávajícího využití sítě za rozhodnutí autoritativního rozhodovatele, kterému je umožněn zásah do samotné struktury sítě, k čemuž využíváme víceúrovňové programování.

Given the increasing consciousness toward the environmental footprint of mobility, accommodating environmental objectives in existing transport planning strategies is imperative for research and practice. In this paper, we use the link macroscopic fundamental diagram (MFD) model to develop optimal routing strategies that minimize total system emissions (TSE) in multiple origin-destination (OD) networks. Piecewise linear (PWL) functions are used to approximate MFD for individual links, and to define link-level emissions. Dynamic network constraints, non-vehicle holding constraints, and convex formulations of the PWL functions are considered. Thus, the system-optimum dynamic traffic assignment (SO-DTA) problem with environmental objectives is formulated as a mixed integer linear program (MILP). Finally, on a synthetic network, numerical examples demonstrate the performance of the proposed framework.

The increase in truck traffic on highways has brought many problems and challenges to transportation planning and traffic operation, including traffic congestion, transportation system deficiency (insufficient truck parking, etc.), safety, infrastructure deterioration, environmental impacts (air quality and noise), economic development, and so forth. Along with the increase in truck traffic, the need for developing a statewide truck freight demand model has grown so that a state can estimate truck traffic at any point on its highways. The most significant hurdle to including freight transportation in the transportation modeling process is that most of the demand forecasting methodologies currently available were developed for passenger trips, not freight trips. This type of modeling methodology usually makes an assumption that freight trips follow the same behavioral mechanism as passenger trips. In order to overcome the weakness of using a typical four-step demand forecasting modeling process, the concept of commodity flow models (CFMs) can be used to develop a truck freight flow model. It is widely accepted that focusing on the freights enables CFMs to capture more accurately the fundamental economic mechanisms that drive freight movements. The type of commodity being carried is one of the most important characteristics of truck movements, and it is sometimes a challenge to obtain such information from the carriers. Thus, lately, the integration of the freight flow modeling and land use modeling has emerged as an alternate tool to estimate freight movements than the previously developed models. In this study, county-level multiple regression models relating land use to commodity flow were developed using a geographical information system and statistics. Then, a statistical/mathematical statewide commodity flow distribution model was developed by using a physical friction factor (physical distance), a statistical friction factor (Euclidean distance), and economic factors (differences of population and difference of employment among the counties). The commodity flow distributed among truck traffic analysis zones (TTAZs) by the statewide commodity flow distribution model were converted to truck trips and the resulting truck trips were assigned to Utah's truck routes using the all-or-nothing assignment procedure of TransCAD and a genetic algorithm. Truck freight data from the US Census Bureau's Commodity Flow Surveys, which have become available to the public for free via the Internet, enabled the development of a commodity flow based statewide truck freight demand model. It was found that the integration of the freight flow and land use data could be a practical method for modeling tuck traffic demand on state-wide truck routes although the current level of data availability on commodity flow and land use data still constrains the full capability of this type of modeling.