Browsing by Subject "Markov decision processes"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Dynamic congestion pricing in within-day and day-to-day network equilibrium models(2016-08) Rambha, Tarun; Boyles, Stephen David, 1982-; Bhat, Chandra; Claudel, Christian; Hasenbein, John; Stone, PeterThis dissertation explores two kinds of dynamic pricing models which react to within-day and day-to-day variation in traffic. Traffic patterns vary within each day due to uncertainty in the supply-side that is caused by non-recurring sources of congestion such as incidents, poor weather, and temporary bottlenecks. On the other hand, significant day-to-day variations in traffic patterns also arise from stochastic route choices of travelers who are not fully rational. Using slightly different assumptions, we analyze the network performance in these two scenarios and demonstrate the advantages of dynamic pricing over static tolls. In both cases, traffic networks are characterized by a set of stochastic states. We seek optimal tolls that are a function of the network states which evolve within each day or across days. In the within-day equilibrium models, travelers are assumed to be completely rational and have knowledge of stochastic link-states, which have different delay functions. At every node, travelers observe the link-states of downstream links and select the next node to minimize their expected travel times. Collectively, such behavior leads to an equilibrium, which is also referred to as user equilibrium with recourse, in which all used routing policies have equal and minimal expected travel time. In this dissertation, we improve the system performance of the equilibrium flows using state-dependent marginal link tolls. These tolls address externalities associated with non-recurring congestion just as static marginal tolls in regular traffic assignment reflect externalities related to recurring congestion. The set of tolls that improve system performance are not necessarily unique. Hence, in order to make the concept of tolling more acceptable to the public, we explore alternate pricing mechanisms that optimize social welfare and also collect the least amount of revenue in expectation. This minimum revenue toll model is formulated as a linear program whose inputs are derived from the solution to a novel reformulation of the user equilibrium with recourse problem. We also study day-to-day dynamic models which unlike traditional equilibrium approaches capture the fluctuations or stochasticity in traffic due to route choice uncertainty. Travelers decisions are modeled using route choice dynamics, such as the logit choice protocol, that depend on historic network conditions. The evolution of the system is modeled as a stochastic process and its steady state is used to characterize the network performance. The objective of pricing in this context is to set dynamic tolls that depend on the state of the network on previous day(s) such that the expected total system travel time is minimized. This problem is formulated as an average cost Markov decision process. Approximation methods are suggested to improve computational tractability. The day-to-day pricing models are extended to instances in which closed form dynamics are unavailable or unfit to represent travelers' choices. In such cases, we apply Q-learning in which the route choices may be simulated off-line or can be observed through experimentation in an online setting. The off-line methods were found to be promising and can be used in conjunction with complex discrete choice models that predict travel behavior with greater accuracy. Overall, the findings in this dissertation highlight the pitfalls of using static tolls in the presence of different types of stochasticity and make a strong case for employing dynamic state-dependent tolls to improve system efficiency.Item Fluid and queueing networks with Gurvich-type routing(2015-08) Sisbot, Emre Arda; Hasenbein, John J.; Bickel, James Eric; Cudina, Milica; Djurdjanovic, Dragan; Khajavirad, AidaQueueing networks have applications in a wide range of domains, from call center management to telecommunication networks. Motivated by a healthcare application, in this dissertation, we analyze a class of queueing and fluid networks with an additional routing option that we call Gurvich-type routing. The networks we consider include parallel buffers, each associated with a different class of entity, and Gurvich-type routing allows to control the assignment of an incoming entity to one of the classes. In addition to routing, scheduling of entities is also controlled as the classes of entities compete for service at the same station. A major theme in this work is the investigation of the interplay of this routing option with the scheduling decisions in networks with various topologies. The first part of this work focuses on a queueing network composed of two parallel buffers. We form a Markov decision process representation of this system and prove structural results on the optimal routing and scheduling controls. Via these results, we determine a near-optimal discrete policy by solving the associated fluid model along with perturbation expansions. In the second part, we analyze a single-station fluid network composed of N parallel buffers with an arbitrary N. For this network, along with structural proofs on the optimal scheduling policies, we show that the optimal routing policies are threshold-based. We then develop a numerical procedure to compute the optimal policy for any initial state. The final part of this work extends the analysis of the previous part to tandem fluid networks composed of two stations. For two different models, we provide results on the optimal scheduling and routing policies.