In this paper we characterize the "price of anarchy", i.e., the inefficiency between user and system optimal solutions, when costs are non-separable, asymmetric and nonlinear, generalizing earlier work that has addressed "price of anarchy" under separable costs. The generalization models traffice equilibria, competitive multi-period pricing and competitive supply chains. The bounds established in the paper are tight and explicitly account for the degeee of asymmetry and nonlinearity of the cost function. We introduce and alternate proof method for providing bounds that uses ideas from semidenfinite optimization. Finally, in the context of nulti-period pricing our analysis establishes that user and system optimal soulutions coincide.

Fluid dynamics models provide a powerful deterministic technique to approximate stochasticity in a variety of application areas. In this paper, we study two classes of fluid models, investigate their relationship as well as some of their applications. This analysis allows us to provide analytical models of travel times as they arise in dynamically evolving environments, such as transportation networks as well as supply chains. In particular, using the laws of hydrodynamic theory, we first propose and examine a general second order fluid model. We consider a first-order approximation of this model and show how it is helpful in analyzing the dynamic traffic equilibrium problem. Furthermore, we present an alternate class of fluid models that are traditionally used in the context of dynamic traffic assignment. By interpreting travel times as price/inventory-sojourn-time relationships, we are also able to connect this approach with a tractable fluid model in the context of dynamic pricing and inventory management. Finally, we investigate the relationship between these two classes of fluid models. / Singapore-MIT Alliance (SMA)

This dissertation focuses on modeling parking search behavior in traffic assignment models. Parking contributes greatly to urban traffic congestion. When the parking supply is scarce, it is very common for a vehicle to circle around for a considerable period just for an open parking spot. This circling or "cruising" add additional traffic flow onto the network. However, traditional traffic assignment models either ignore parking completely or simply treat it in limited ways. Most traffic assignment models simply assume travelers just directly drive from their origin to their destination without considering the parking search behavior. This would result in a systematic underestimation of road traffic flows and congestion which may mislead traffic managers to give inappropriate planning or control strategies. Models which do incorporate parking effects either constrain their implementation in limited small networks or ignore the stochasticity of parking choice by drivers. This dissertation improves upon previous research into network parking modeling, explicitly capturing drivers' behavior and stochasticity in the parking search process, and is applicable to general networks. This dissertation constructs three types of parking search models. The first one is to model a single driver's parking search process, taking into account the likelihood of finding parking in different locations from past experience as well as observations gained during the search itself. This model uses the a priori probability of finding parking on a link, which reflects the average possibility of finding a parking space based on past experience. This probability is then adjusted based on observations during the current search. With these concepts, the parking search behavior is modeled as a Markov decision process (MDP). The primary contribution of the proposed model is its ability to reflect history dependence which combines the advantages of assuming "full reset" and "no reset" . "Full reset" assumes the probability of finding a parking space on a link is independent of any observations in the current search, while "no reset" assumes the state of parking availability is completely determined by past observations, never changing once observed. For instance, assume that the a priori probability of finding parking on a link is 30%. "Full reset" implies that if a driver drives on this link and sees no parking available, if he or she immediately turns around and drives on the link again, the probability of finding parking is again 30% independent of the past observation. By contrast, "no reset" implies that if a parking space is available on a link, it will always be available to return to in the future at any point. This dissertation develops an "asymptotic reset" principle which generalizes these principles and allows past observations to affect the probability of finding parking on a link and this impact weakens as time goes by. Both full reset and no reset are shown to be special cases of asymptotic reset. The second problem is modeling multiple drivers through a parking search equilibrium on a static network. Similar to the first type of problem, drivers aim to minimize their total travel costs. Their driving and parking search behaviors depend on the probabilities of finding parkings at particular locations in the network. On the other side, these probabilities depend on drivers' route and parking choices. This mutual dependency can be modeled as an equilibrium problem. At the equilibrium condition no driver can improve his or her expected travel cost by unilaterally changing his or her routing and parking search strategy. To accomplish this, a network transformation is introduced to distinguish between drivers searching for parking on a link and drivers merely passing through. The dependence of parking probability on flow rates results in a set of nonlinear flow conservation equations. Nevertheless, under relatively weak assumptions the existence and uniqueness of the network loading can be shown, and an intuitive 'flow-pushing" algorithm can be used to solve for the solution of this nonlinear system. Built on this network loading algorithm, travel times can be computed. The equilibrium is formulated as a variational inequality, and a heuristic algorithm is presented to solve it. An extensive set of numerical tests shows how parking availability and traffic congestion (flows and delays) vary with the input data. The third problem aims at developing a dynamic equivalent for the network parking search equilibrium problem. This problem attempts to model a similar set of features as the static model, but aims to reflect changes in input demand, congestion, and parking space availability over time. The approach described in the dissertation is complementary to the static approach, taking on the flavor of simulation more than mathematical formulation. The dynamic model augments the cell transmission model with additional state variables to reflect parking availability, and integrates this network loading with an MDP-based parking search behavior model. Finally, case studies and sensitivity analysis are taken for each of the three models. These analyses demonstrate the models' validity and feasibility for practice use. Specifically, all the models show excess travel time and flow on the transportation networks because of taking into account the "parking search cruising" and can show the individual links so affected. They all reflect the scattered parking distribution on links while traditional traffic assignment models only assign vehicles onto specified destination nodes. / text

Network design decisions, especially those pertaining to urban infrastructure, are made by a central authority or network leader, and taking into consideration the network users or followers. These network decision problems are formulated as non-linear bi-level programming problems. In this work, a continuous network design problem (CNDP) and discrete network design problem (DNDP) bi-level optimization programs are proposed and solved in the context of transportation planning. The solution strategy involved reformulation and linearization as a single-level program by introducing the optimality conditions of the lower level problem into the upper level problem. For the CNDP, an alternative linearization algorithm (modified least squares partitioning, MLSPA) is proposed. MLSPA takes into consideration the current arc capacity and potential expansion to find a reduced set of planes to generalize the flow-capacity surface behavior. The concepts of flow capacity surface was introduced as a way to model of congested network and capture the effect of capacity on travel time/cost. It was found that the quality of the linear approximation depends on the goodness of fit the bottleneck arcs. The proposed approach was tested with well-known benchmark problems in transportation which yielded promising results in terms of efficiency, without sacrificing solution quality.

This thesis concerns the development of novel feasible direction type algorithms for constrained nonlinear optimization. The new algorithms are based upon enhancements of the search direction determination and the line search steps. The Frank-Wolfe method is popular for solving certain structured linearly constrained nonlinear problems, although its rate of convergence is often poor. We develop improved Frank--Wolfe type algorithms based on conjugate directions. In the conjugate direction Frank-Wolfe method a line search is performed along a direction which is conjugate to the previous one with respect to the Hessian matrix of the objective. A further refinement of this method is derived by applying conjugation with respect to the last two directions, instead of only the last one. The new methods are applied to the single-class user traffic equilibrium problem, the multi-class user traffic equilibrium problem under social marginal cost pricing, and the stochastic transportation problem. In a limited set of computational tests the algorithms turn out to be quite efficient. Additionally, a feasible direction method with multi-dimensional search for the stochastic transportation problem is developed. We also derive a novel sequential linear programming algorithm for general constrained nonlinear optimization problems, with the intention of being able to attack problems with large numbers of variables and constraints. The algorithm is based on inner approximations of both the primal and the dual spaces, which yields a method combining column and constraint generation in the primal space. / The articles are note published due to copyright rextrictions.