Browsing by Subject "Network contraction"

Now showing 1 - 2 of 2

Dynamic pricing and long-term planning models for managed lanes with multiple entrances and exits
(2020-05-15) Pandey, Venktesh; Boyles, Stephen David, 1982-; Bhat, Chandra; Claudel, Christian; Stone, Peter; Hasenbein, John
Express lanes or priced managed lanes provide a reliable alternative to travelers by charging dynamic tolls in exchange for traveling on lanes with no congestion. These lanes have various locations of entrances and exits and allow travelers to adapt their route based on the toll and travel time information received at a toll gantry. In this dissertation, we incorporate this adaptive lane choice behavior in improving the dynamic pricing and long-term planning models for managed lanes with multiple entrances and exits. Lane choice of travelers minimizing their disutility is affected by the real-time information about tolls and travel time through variable message signs and perceived information from past experiences. In this dissertation, we compare various adaptive lane choice models differing in their reliance on real-time information or historic information or both. We propose a decision route lane choice model that efficiently compares the disutility over multiple routes on an express lane. Assuming drivers’ disutility is only affected by tolls and travel times, we show that the decision route model generates only up to 0.93% error in expected costs compared to the optimal adaptive lane choice model, making it a suitable choice for modeling lane choice of travelers. Next, using the decision route lane choice framework, we improve the current dynamic pricing models for express lanes that commonly ignore adaptive lane choice, assume simplified traffic dynamics, and/or are based on simplified heuristics. Formulating the dynamic pricing problem as an MDP, we optimize the tolls for various objectives including maximizing revenue and minimizing total system travel time (TSTT). Three solution algorithms are evaluated: (a) an algorithm based on value-function approximation, (b) a multiagent reinforcement learning algorithm with decentralized tolling at each gantry, and (c) a deep reinforcement learning assuming partial observability of traffic state. These algorithms are shown to outperform other heuristics such as feedback control heuristics by generating up to 10% higher revenues and up to 9% lower delays. Our findings also reveal that the revenue-maximizing optimal policies follow a “jam-and-harvest” behavior where the toll-free lanes are pushed towards congestion in the earlier time steps to generate higher revenue later, a characteristic not observed for the policies minimizing TSTT. We use reward shaping methods to overcome the undesired behavior of toll policies and confirm transferability of the algorithms to new input domains. We also offer recommendations on real-time implementations of pricing algorithms based on solving MDPs. Last, we incorporate adaptive lane choice in existing long-term planning models for express lanes which commonly represent these lanes as fixed-toll facilities and ignore en route adaptation of lane choices. Defining the improved model as an equilibrium over adaptive lane choices of self-optimizing travelers and formulating it as a convex program, we show that long-term traffic forecasts can be underestimated by up to 45% if adaptive route choice is ignored. For solving the equilibrium, we develop a gradient-projection algorithm which is shown to be efficient than existing link-state algorithms in the literature. Additionally, we estimate the sensitivity of equilibrium expected costs with demand variation by formulating it as a convex program solved using a variant of the gradient projection algorithm proposed earlier. This analysis simplifies a complex express lane network as a single directed link, allowing integration of adaptive lane choice for planning of express lanes without significantly altering the components of traditional planning models. Overall these models improve the state-of-the-art of pricing and planning for managed lanes useful for evaluating future express lane projects and for operations of express lanes with multiple objectives.
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%.