The Hotspot Problem in Air Traffic Management consists of optimally rescheduling a set of airplanes that are forecast to occupy an overcrowded region of the airspace, should they follow their original schedule. We first provide a MILP model for the Hotspot Problem using a standard big-M formulation. Then, we present a novel MILP model that gets rid of the big-M coefficients. The new formulation contains only simple combinatorial constraints, corresponding to paths and cycles in an associated disjunctive graph. We report computational results on a set of randomly generated instances. In the experiments, the new formulation consistently outperforms the big-M formulation, both in terms of running times and number of branching nodes.

Abstract Trains running through railway lines often accumulate some delay. When this happens, rescheduling and rerouting decisions must be quickly taken in real time. Despite the fact that even a single wrong decision may deteriorate the performance of the whole railway network, this complex optimization task is still basically performed by human operators. In very recent years, the interest of train operators to implement automated decision systems has grown. Not incidentally, the railway application section (RAS) of INFORMS has issued a challenge devoted to this problem concomitantly with the INFORMS Annual Meeting 2012. In this article, we describe two heuristic approaches to solve the RAS problem based on a mixed integer linear programming formulation, and we report computational results on the three RAS instances and on an additional set of instances defined on a more congested network. Computational results on the challenge test bed show that our algorithms positively compare with other approaches to the RAS problem. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 62(4), 315–326 2013

A digraph is upward planar if it has a planar drawing such that all the edges are monotone with respect to the vertical direction. Testing upward planarity and constructing upward planar drawings is important for displaying hierarchical network structures, which frequently arise in software engineering, project management, and visual languages. In this paper we investigate upward planarity testing of single-source digraphs; we provide a new combinatorial characterization of upward planarity and give an optimal algorithm for upward planarity testing. Our algorithm tests whether a single-source digraph with n vertices is upward planar in O(n) sequential time, and in O(log n) time on a CRCW PRAM with $n \log \log n/\log n$ processors, using O(n,) space. The algorithm also constructs an upward planar drawing if the test is successful. The previously known best result is an O(n 2 )-time algorithm by Hutton and Lubiw [Proc. 2nd ACM--SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, pp. 203--211]. No efficient parallel algorithms for upward planarity testing were previously known.