Browsing by Subject "Bilevel optimization"

Now showing 1 - 2 of 2

Network modeling and design : a distributed problem solving approach
(2017-08) Jafari, Ehsan; Boyles, Stephen David, 1982-; Hickman, Mark; Machemehl, Randy; Claudel, Christian; Unnikrishnan, Avinash
This dissertation is concerned with developing new solution algorithms for network modeling and design problems using a distributed problem solving approach. Network modeling and design are fundamental problems in the field of transportation science, and numerous transportation applications such as urban travel demand forecasting, congestion pricing, defining optimal toll values, and scheduling traffic lights all involve some form of network modeling or network design. The first part of this dissertation focuses on developing a distributed scheme for the static traffic assignment problem, based on a spatial decomposition. The objective of the traffic assignment problem is to estimate traffic flows on a network and the resulting congestion considering the mutual interactions between travelers. A traffic assignment model takes as input the network topology, link performance functions, and a demand matrix indicating the traffic volume between each pair of origin-destination nodes. There are efficient algorithms to solve the traffic assignment problem, but, as computational hardware and algorithms advance, attention shifts to more demanding applications of the traffic assignment problem (bilevel programs whose solution often requires the solution of many traffic assignment problem instances as subproblems, accounting for forecasting errors with Monte Carlo simulation of input parameters, and broadening the geographic scope of models to the statewide or national levels.) In Chapter 2, we propose a network contraction technique based on the theory of equilibrium sensitivity analysis. In the proposed algorithm, we replace the routes between each origin-destination (OD) pair with a single artificial link. These artificial links model the travel time between the origin and destination nodes of each OD pair as a function of network demands. The network contraction method can be advantageous in network design applications where many equilibrium problems must be solved for different design scenarios. The network contraction procedure can also be used to increase the accuracy of subnetwork analysis. The accuracy and complexity of the proposed methodology are evaluated using the network of Barcelona, Spain. Further, numerical experiments on the Austin, Texas regional network validate its performance for subnetwork analysis applications. Using this network contraction technique, we then develop a decentralized (distributed) algorithm for static traffic assignment in Chapter 3. In this scheme, which we term a decentralized approach to the static traffic assignment problem (DSTAP), the complete network is divided into smaller networks, and the algorithm alternates between equilibrating these networks as subproblems, and master iterations using a simplified version of the full network. The simplified network used for the master iterations is based on linearizations to the equilibrium solution for each subnetwork obtained using sensitivity analysis techniques. We prove that the DSTAP method converges to the equilibrium solution on the complete network, and demonstrate computational savings of 35-70% on the Austin network. Natural applications of this method are statewide or national assignment problems, or cities with rivers or other geographic features where subnetworks can be easily defined. The second part of this dissertation, found in Chapter 4, deals with network design problems. In a network design problem, the goal is to optimize an objective function (minimize the travel time, pollution, maximize safety, social welfare, etc.) by making investment decisions subject to budget and feasibility constraints. Network design is a bi-level problem where the leader chooses the design parameters, and travelers, as followers, react to the leader’s decision by changing their route. These problems are hard to solve, and distributed problem solving approach can be used to develop an efficient framework for scaling these problems. In the proposed distributed algorithm for network design problems, different planning agencies may have different objective functions and priorities, while a regional agent (state or federal officials) allocates the finding between the urban cities. In this model, the urban planning agencies do their own planning and design independently while capturing the system-level effects of their local decisions and plans. The regional agent has limited and indirect authorities over the subnetworks through budget allocation. In addition to computational advantages for traditional bi-level network design problems, the proposed algorithm can be used to model the linkage between different entities for multi-resolution applications. We develop a solution algorithm based on a sensitivity-analysis heuristic, and test our algorithm on two case studies: a hypothetical network composed of two copies of Sioux Falls network, and the Austin regional network. We evaluate the correctness of the decentralized algorithm, and discuss the benefits of the algorithm in modeling the global impacts of local decisions. Furthermore, the implementation of distributed algorithm on Austin regional network demonstrates a computational saving of 22%.
Operations research models of technology transitions and the role of policy support
(2020-05-05) Brozynski, Max Tomasz; Leibowicz, Benjamin D.; Bickel, James E; Hasenbein, John J; Olmstead, Sheila; Webber, Michael E
Technology exists to fulfill functions in society, and technological innovations are continuously proposed to fulfill a particular function more effectively than an incumbent technology. These innovations are disseminated through society in a process called technology diffusion, and may ultimately replace an incumbent system in what is known as a technology transition. Due to the complex and uncertain underlying processes of technology adoption and diffusion, technical systems are resistant to transition to possibly superior alternatives. To address market, systemic, and structural failures preventing a desired technology transition, a policymaker, or other motivated agent, may strategically intervene to stimulate or accelerate the diffusion process. The success or failure of such policy intervention carries crucial implications for climate change mitigation, healthcare advances, and any other aspect of society that technology touches. However, existing models of optimal technology policy design omit or otherwise offer crude representations of these underlying processes and are largely case-specific at the expense of gleaning generalizable insights. The goal of this dissertation is to advance the operations research modeling of technology transitions and the role of policy support. Through a variety of powerful operations research methodologies and relevant case studies, the individual projects in this dissertation offer novel models of technology transitions and insights into real-world technology policy, especially in the energy and climate domain. The three core chapters of this dissertation begin with the development of an applied energy system optimization model to assess a real-world climate policy, then move on to present two novel theoretical models that yield more general, analytical insights into technology policy decision making. Chapter 2 addresses the growing importance of cities in climate change mitigation with the development of an energy system optimization model for urban-scale decarbonization. Our optimization model determines the least-cost power and transportation technology pathways to achieve a policy goal of net-zero greenhouse gas emissions and is used to analyze the Community Climate Plan adopted by Austin, Texas. We find that the policy objective can be achieved at a modest 2.7% increase in net present power and transportation costs relative to business-as-usual. The optimal decarbonization pathway proceeds through two distinct stages, first reducing power sector emissions, then electrifying transportation. Solar PV expands in the long run with or without the climate plan based on favorable cost projections, but the policy causes wind to replace natural gas as a complement to solar PV. Our findings also highlight the substantial value of intelligently scheduled battery storage operations and electric vehicle charging. While the energy system optimization model of Chapter 2 captures numerous decisions for a complex urban energy system, it carries limiting assumptions about how technology diffusion occurs and the role of a policymaker in supporting a technology transition. Addressing these larger questions motivates the project in Chapter 3, which describes the development of two stylized models of technology policy decision making under uncertainty. The first model is a Markov reward process (MRP) that represents policy interventions with one-time, upfront costs, while the second is a Markov decision process (MDP) that represents interventions with recurring costs. For each model, we derive analytical expressions for the policymaker's willingness to pay (WTP) to raise the probabilities of advancing a technology development or diffusion process at various stages and compare and contrast the behaviors of the MRP and MDP models. Most notably, our analytical findings elucidate how the different cost-accounting schemes and the possibility of regressing from a more advanced development or diffusion stage back to an earlier one affect the WTP. Then, we conduct numerical sensitivity analysis to explore how the optimal technology policy portfolio varies with certain parameters, and present a case study on lithium-ion batteries for electric vehicles to demonstrate the practical application of our model to technology policy decision making. In Chapter 4, we narrow our focus on technology transitions to infrastructure-dependent technologies common in energy, transportation, and telecommunications systems. Policymakers seeking to promote the diffusion of infrastructure-dependent technologies are often confronted with the chicken-and-egg problem: consumers are reluctant to adopt the technology without adequate infrastructure available, and firms are reluctant to invest in infrastructure without a sufficient number of adopters. This chicken-and-egg problem can hinder the diffusion of new technologies and prolong the timeframe over which existing technological systems remain locked-in. In this paper, we formulate a stylized model of technology policy decision making from the perspective of a policymaker who seeks to stimulate the market penetration of an infrastructure-dependent technology. Our model is a bilevel optimization problem in which a policymaker (leader) maximizes net social benefits by setting the levels of two incentives: a subsidy for a profit-maximizing firm (follower) to invest in infrastructure that raises the benefit of adoption to consumers, and a direct subsidy for consumers to adopt the technology. We analytically derive the firm's optimal infrastructure investment response to the upper-level policy decisions, and show that the bilevel model is equivalent to a quadratic program. To bypass non-convexity, we develop a custom solution strategy based on decomposition, and find that it performs better than directly applying an off-the-shelf solver to the potentially non-convex problem. Finally, we present a case study on the diffusion of battery electric vehicles and obtain insights into how a policymaker should allocate resources to charging infrastructure and vehicle incentives. The three projects of this dissertation employ operations research methods to model technology transitions and the role of policy support. While each captures a variety of phenomena affecting technology transitions and optimal technology policy decision making, there remain thought-provoking questions that future research can address. We conclude this dissertation with proposed research directions and contemplate the high-level, real-world implications of this work.