Engineering topics
Cassandras, Christos G.
Publications and source records attributed to Cassandras, Christos G..
Cooperative energy and time-optimal lane change maneuvers with minimal highway traffic disruption
Not Available
Optimal control of connected automated vehicles with event/self-triggered control barrier functions
Not Available
Toward model-free safety-critical control with humans in the loop
Not Available
A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
Not Available
Optimizing lane reversals in transportation networks to reduce traffic congestion: A global optimization approach
This paper studies how to reduce the overall travel time of commuters in a transportation network by reversing the direction of some lanes in the network using a macroscopic network-wide perspective. Similar to the Network Design Problem, the lane reversal problem has been shown to be NP-hard given the dependence of the users’ route selection on the lane direction decision. Herein, we propose and compare three efficient methods to solve the routing and lane reversal problem jointly. First, we introduce an alternating method that decouples the routing and lane assignment problems. Second, we propose a Frank–Wolfe method that jointly takes gradient steps to adjust both the lane assignment and routing decisions. Third, we propose a convex approximation method that uses a threshold-based approach to convexify the joint routing and lane reversal objective. The convex approximation method is advantageous since it finds a global optimum solution for the approximated problem and it enables the possibility to include linear constraints. Using this method, we extend the main formulation to be able to limit a maximum number of reversed lanes, as well as to incorporate multiple origin–destination (OD) patterns. We test the proposed methods in a case study using the transportation network of Eastern Massachusetts where our results indicate an overall reduction in travel times of 4.7% by selecting the best 15 reversals. Moreover, using a small test network, we investigate the performance of the lane reversal strategies as a function of the OD demand symmetry. As expected, we observe that when the OD demand is very asymmetric (e.g., for a single OD pair, evacuations, large events), the reduction in travel times is larger than the symmetric case, reaching travel time reductions of 60%.
Optimal routing and buffer allocation for a class of finite capacity queueing systems
The problem of routing jobs to K parallel queues with identical exponential servers and unequal finite buffer capacities is considered. Routing decisions are taken by a controller which has buffering space available to it and may delay routing of a customer to a queue. Using ideas from weak majorization, it is shown that the shorter nonfull queue delayed (SNQD) policy minimizes both the total number of customers in the system at any time and the number of customers that are rejected by that time. The SNQD policy always delays routing decisions as long as all servers are busy. Only when all the buffers at the controller are occupied is a customer routed to the queue with the shortest queue length that is not at capacity. Moreover, it is shown that, if a fixed number of buffers is to be distributed among the K queues, then the optimal allocation scheme is the one in which the difference between the maximum and minimum queue capacities is minimized, i.e., becomes either 0 or 1.
Perturbation analysis of queueing systems with a time-varying arrival rate
The authors consider an M/G/1 queuing with a time-varying arrival rate. The objective is to obtain infinitesimal perturbation analysis (IPA) gradient estimates for various performance measures of interest with respect to certain system parameters. In particular, the authors consider the mean system time over n arrivals and an arrival rate alternating between two values. By choosing a convenient sample path representation of this system, they derive an unbiased IPA gradient estimator which, however, is not consistent, and investigate the nature of this problem.
The effect of model uncertainty on some optimal routing problems
The effect of model uncertainties on optimal routing in a system of parallel queues is examined. The uncertainty arises in modeling the service time distribution for the customers (jobs, packets) to be served. For a Poisson arrival process and Bernoulli routing, the optimal mean system delay generally depends on the variance of this distribution. However, as the input traffic load approaches the system capacity the optimal routing assignment and corresponding mean system delay are shown to converge to a variance-invariant point. The implications of these results are examined in the context of gradient-based routing algorithms. An example of a model-independent algorithm using online gradient estimation is also included.
Efficient parametric analysis of performance measures for communication networks
Efficient techniques for estimating performance measures in communication networks in a steady-state or transient setting are developed. These techniques may be used in a simulation environment or in connection with real-time observations. For Markov chain models, the recently proposed standard clock approach is extended, and a class of real-time algorithms for simultaneously generating multiple sample paths under different parameter sets is presented. Attention is focused on the link crash time estimation problem, where a 'crash' is defined as the first time a buffer overflows, given some initial conditions. An algorithm for estimating crash times under various traffic shocks is derived, where all estimates are obtained in parallel to an actual network's normal operation. An algorithm for crash time estimation of a G/D/1 link model is also derived using a different (perturbation-analysis-based) approach. Finally, extensive simulation results are provided to validate the proposed algorithms and compare them to brute-force simulation.
Stochastic ordering properties and optimal routing control for a class of finite capacity queueing systems
The problem of routing jobs to parallel queues with identical exponential servers and unequal finite buffer capacities is considered. Stochastic ordering and weak majorization properties on critical performance measures are established by means of event-driven inductions. In particular, it is shown that the intuitive 'join the shortest non-full queue' (SNQ) policy is optimal with respect to an overall function that accounts for holding and blocking costs. Moreover, the buffer allocation problem is solved by proving the intuitive result that, for a fixed total buffer capacity, the optimal allocation scheme is the one in which the difference between the maximum and minimum queue capacities is minimized, i.e., becomes either 0 or 1.
A new class of gradient estimators for queueing systems with real-time constraints
Queuing systems are considered where the waiting or sojourn times of customers are constrained by specified deadlines. A performance measure of interest in these systems is the probability that a customer exceeds its assigned deadline. A new class of gradient estimators is presented for such performance measures with respect to various system parameters. The approach is applicable to a general class of problems and is based on efficiently capturing sensitivity information for probabilities of event occurrences from observed sample paths.