Traffic information, now available through a number of different sources, is re-shaping the way planners, operators and users think about the transportation network. It provides a powerful tool to mitigate the negative impacts of uncertainty, and an invaluable resource to manage and operate the network in real-time. More information also invites to think about traditional transportation problems from a different perspective, searching for a better utilization of the improved knowledge of the network state. This dissertation is concerned with modeling and evaluating the system-level impacts of providing information to network users, assuming that the data is utilized to guide an Adaptive System-Optimum (ASO) routing behavior. Within this context, it studies the optimal deployment of sensors for the support of ASO strategies, and it introduces a novel SO assignment approach, the Information-Based System Optimum (IBSO) assignment paradigm. The proposed sensor deployment model explicitly captures the impact of sensors' location on the expected cost of ASO assignment strategies. Under such strategies, a-priori routing decisions may be adjusted based on real-time information. The IBSO assignment paradigm leads to optimal flow patterns which take into account the ability of vehicles to collect information as they travel. The approach regards a subset of the system's assets as probes, which may face higher expected costs than regular vehicles in the search for information. The collected data is utilized to adjust routing decisions in real time, improving the expected system performance. The proposed problem captures the system-level impact of adaptive route choices on stochastic networks. The models developed in this work are rigorously formulated, and their properties analyzed to support the generation of specialized solution methodologies based on state-space partitioning and Tabu Search principles. Solution techniques are tested under a variety of scenarios, and implemented to the solution of several case studies. The magnitude and nature of the information impacts observed in this study illustrate problem characteristics with important theoretical, methodological and practical implications. The findings presented in this dissertation allow envisioning a number of practical applications which may promote a more efficient utilization of novel sensing and communication technologies, allowing the full realization of their potential. / text

We study the problem of minimizing the maximum latency of flows in networks with congestion. We show that this problem is NP-hard, even when all arc latency functions are linear and there is a single source and sink. Still, one can prove that an optimal flow and an equilibrium flow share a desirable property in this situation: all flow-carrying paths have the same length; i.e., these solutions are "fair," which is in general not true for the optimal flow in networks with nonlinear latency functions. In addition, the maximum latency of the Nash equilibrium, which can be computed efficiently, is within a constant factor of that of an optimal solution. That is, the so-called price of anarchy is bounded. In contrast, we present a family of instances that shows that the price of anarchy is unbounded for instances with multiple sources and a single sink, even in networks with linear latencies. Finally, we show that an s-t-flow that is optimal with respect to the average latency objective is near optimal for the maximum latency objective, and it is close to being fair. Conversely, the average latency of a flow minimizing the maximum latency is also within a constant factor of that of a flow minimizing the average latenc

abstract: This research develops heuristics to manage both mandatory and optional network capacity reductions to better serve the network flows. The main application discussed relates to transportation networks, and flow cost relates to travel cost of users of the network. Temporary mandatory capacity reductions are required by maintenance activities. The objective of managing maintenance activities and the attendant temporary network capacity reductions is to schedule the required segment closures so that all maintenance work can be completed on time, and the total flow cost over the maintenance period is minimized for different types of flows. The goal of optional network capacity reduction is to selectively reduce the capacity of some links to improve the overall efficiency of user-optimized flows, where each traveler takes the route that minimizes the traveler’s trip cost. In this dissertation, both managing mandatory and optional network capacity reductions are addressed with the consideration of network-wide flow diversions due to changed link capacities. This research first investigates the maintenance scheduling in transportation networks with service vehicles (e.g., truck fleets and passenger transport fleets), where these vehicles are assumed to take the system-optimized routes that minimize the total travel cost of the fleet. This problem is solved with the randomized fixed-and-optimize heuristic developed. This research also investigates the maintenance scheduling in networks with multi-modal traffic that consists of (1) regular human-driven cars with user-optimized routing and (2) self-driving vehicles with system-optimized routing. An iterative mixed flow assignment algorithm is developed to obtain the multi-modal traffic assignment resulting from a maintenance schedule. The genetic algorithm with multi-point crossover is applied to obtain a good schedule. Based on the Braess’ paradox that removing some links may alleviate the congestion of user-optimized flows, this research generalizes the Braess’ paradox to reduce the capacity of selected links to improve the efficiency of the resultant user-optimized flows. A heuristic is developed to identify links to reduce capacity, and the corresponding capacity reduction amounts, to get more efficient total flows. Experiments on real networks demonstrate the generalized Braess’ paradox exists in reality, and the heuristic developed solves real-world test cases even when commercial solvers fail. / Dissertation/Thesis / Doctoral Dissertation Industrial Engineering 2017

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.