Search

Consider a LCFS-PR $M/G/1$ queue and assume that at time $t = 0$, there are $n+2$ customers $c_1,c_2,...,c_{n+1},c$ who arrived in that order such that $t = 0$ is the arrival time of $c$. Then, the externalities which are generated by $c$ is the total waiting time that would be saved by $c_1,c_2,...,c_{n+1}$ if $c$ reduced his service requirement to zero. Motivated by some applications, this work is about the minimization of the externalities variance under various constraints.

In road traffic networks, large traffic volumes may lead to extreme delays. These severe delays are caused by the fact that, whenever the maximum capacity of a road is approached, speeds drop rapidly. Therefore, the focus in this paper is on real-time control of traffic input rates, thereby aiming to prevent such detrimental capacity drops. To account for the fact that, by the heterogeneity within and between traffic streams, the available capacity of a road suffers from randomness, we introduce a stochastic flow model that describes the impact of traffic input streams on the available road capacities. Then, exploiting similarities with traffic control of telecommunication networks, in which the available bandwidth is a stochastic function of the input rate, and in which the use of effective bandwidths have proven an effective input rate control framework, we propose a similar traffic rate control policy based on the concept of effective bandwidths. This policy allows for increased waiting times at the access boundaries of the network, so as to limit the probability of large delays within the network. Numerical examples show that, by applying such a control policy capacity violations are indeed rare, and that the increased waiting at the boundaries of the network is of much smaller scale, compared to uncontrolled delays in the network.

Due to recurrent (e.g. daily or weekly) patterns and non-recurrent disruptions (e.g. caused by incidents), travel times in road networks are time-dependent and inherently random. This is challenging for travelers planning a future trip, aiming to ensure on-time arrival at the destination, while also trying to limit the total travel-time budget spent. The focus of this paper lies on determining their optimal departure time: the latest time of departure for which a chosen on-time arrival probability can be guaranteed. To model the uncertainties in the network, a Markovian background process is used, tracking events affecting the driveable vehicle speeds on the links, thus enabling us to incorporate both recurrent and non-recurrent effects. It allows the evaluation of the travel-time distribution, given the state of this process at departure, on each single link. Then, a computationally efficient algorithm is devised that uses these individual link travel-time distributions to obtain the optimal departure time for a given path or origin-destination pair. Since the conditions in the road network, and thus the state of the background process, may change between the time of request and the advised time of departure, we consider an online version of this procedure as well, in which the traveler receives departure time updates while still at the origin. Finally, numerical experiments are conducted to exemplify a selection of properties of the optimal departure time and, moreover, quantify the performance of the presented algorithms in an existing road network -- the Dutch highway network.

To improve the routing decisions of individual drivers and the management policies designed by traffic operators, one needs reliable estimates of travel time distributions. Since congestion caused by both recurrent patterns (e.g., rush hours) and non-recurrent events (e.g., traffic incidents) leads to potentially substantial delays in highway travel times, we focus on a framework capable of incorporating both effects. To this end, we propose to work with the Markovian Velocity model (MVM), based on an environmental background process that tracks both random and (semi-)predictable events affecting the vehicle speeds in a highway network. We show how to operationalize this flexible data-driven model in order to obtain the travel time distribution for a vehicle departing at a known day and time to traverse a given path. Specifically, we detail how to structure the background process and set the speed levels corresponding to the different states of this process. First, for the inclusion of non-recurrent events, we study incident data to describe the random durations of the incident and inter-incident times. Both of them depend on the time of day, but we identify periods in which they can be considered time-independent. Second, for an estimation of the speed patterns in both incident and inter-incident regime, loop detector data for each of the identified periods is studied. In numerical examples that use road network detector data of the Dutch highway network, we obtain the travel time distribution estimates that arise under different traffic regimes, and illustrate the advantages compared to traditional travel-time prediction methods.

Despite measures to reduce congestion, occurrences of both recurrent and non-recurrent congestion cause large delays in road networks with important economic implications. Educated use of Intelligent Transportation Systems (ITS) can significantly reduce travel times. We focus on a dynamic stochastic shortest path problem: our objective is to minimize the expected travel time of a vehicle, assuming the vehicle may adapt the chosen route while driving. We introduce a new stochastic process that incorporates ITS information to model the uncertainties affecting congestion in road networks. A Markov-modulated background process tracks traffic events that affect the speed of travelers. The resulting continuous-time routing model allows for correlation between velocities on the arcs and incorporates both recurrent and non-recurrent congestion. Obtaining the optimal routing policy in the resulting semi-Markov decision process using dynamic programming is computationally intractable for realistic network sizes. To overcome this, we present the EDSGER* algorithm, a Dijkstra-like shortest path algorithm that can be used dynamically with real-time response. We develop additional speed-up techniques that reduce the size of the network model. We quantify the performance of the algorithms by providing numerical examples that use road network detector data for The Netherlands.