Abstract

We present two heuristics based on constraint technology that solve the problem of generating air traffic management contingency plans, which are used in the case of a catastrophic infrastructure failure within EUROCONTROL, the European Organisation for the Safety of Air Navigation. Of the heuristics presented, one is based on constraint-based local search and tabu search, and the other one is a constraint programming and large neighbourhood search hybrid algorithm. The heuristics show that it is feasible to automate the development of contingency plans, which is currently done by human experts; this is desirable for several reasons, for example it would allow the contingency plans to be generated with an increased frequency. The generated plans were evaluated, by EUROCONTROL, to be at least as good as the human-made ones. Document type: Part of book or chapter of book

Abstract

The aim of this paper is to provide a detailed description of a framework for the estimation of time-sliced origin-destination (OD) trip matrices in a transit network using counts and travel time data of Bluetooth Smartphone devices carried by passengers at equipped transit-stops. A Kalman filtering formulation defined by the authors has been included in the application. The definition of the input for building the space-state model is linked to network scenarios modeled with the transportation planning platform EMME. The transit assignment framework is optimal strategy-based, which determines the subset of paths related to the optimal strategies between all OD pair Document type: Part of book or chapter of book

Abstract

International audience; Preventing aircraft from getting too close to each other is an essential element of safety of the air transportation industry, which becomes ever more important as the air traffic increases. The problem consists in enforcing a minimum distance threshold between flying aircraft, which naturally results in a bilevel formulation with a lower-level subproblem for each pair of aircraft. We propose two single-level reformulations, present a cut generation algorithm which directly solves the bilevel formulation and discuss comparative computational results. Document type: Part of book or chapter of book

Abstract

Publisher Summary This chapter describes a mathematical model for a pipeline infrastructure for CO2 sequestration and utilizes various mathematical programming techniques to find minimum cost strategies for building and operating this pipeline network. The greenhouse gas emissions from direct combustion of fuels can be greatly reduced if they are replaced with hydrogen produced from fossil sources, and if hydrogen production is coupled with capture and secure sequestration of the resulting CO2 at storage sites such as aquifers and depleted hydrocarbon reservoirs. The transportation of CO2 from fossil hydrogen plants to sequestration sites can be accomplished via a pipeline network. The design of this pipeline is an important aspect of the overall energy network. It has been proposed that the CO2 produced at sources such as fossil energy conversion facilities and industrial process plants could be captured, compressed to supercritical pressures, transported via pipelines, and stored in underground geologic formations such as depleted oil and natural gas reservoirs and deep saline aquifers. A nonlinear model of the CO2 pipeline system is described, with appropriate constraints, and the lowest cost system is found using a state-of-the-art nonlinear optimization software called LOQO. The chapter also presents ways to model the behavior of the system over time, and to model the impact of uncertainties. Document type: Part of book or chapter of book

Abstract

In this paper, we present a new Integer Program (IP) for the Air Traffic Flow Management (ATFM) problem. The model we propose provides a complete representation of all the phases of each flights, i.e., the phase of taking-off, of cruising and of landing; suggesting all the actions to be implemented to achieve the goal of safe, efficient, and expeditious aircraft movement. The distinctive feature of the model is that it allows rerouting decisions. These decisions are formulated by means of "local" conditions, which allow us to represent such decisions in a very compact way by only introducing new constraints. Moreover, to strengthen the polyhedral structure of the underlying relaxation, we also present three classes of valid inequalities.\r \r We report short computational times (less than 15 minutes) on instances of the size of the US air traffic control system that make it realistic that our approach can be used as the main engine of managing air traffic in the US. Document type: Part of book or chapter of book

Abstract

In this paper we explore tramp ship routing and scheduling. Tramp ships operate much like taxies following the available demand. Tramp operators can determine some of their demand in advance by entering into long-term contracts and then try to maximise profits from optional voyages found in the spot market. Routing and scheduling a tramp fleet to best utilise fleet capacity according to current demand is therefore an ongoing and complicated problem. Here we add further complexity to the routing and scheduling problem by incorporating voyage separation requirements that enforce a minimum time spread between some voyages. The incorporation of these separation requirements helps balance the conflicting objectives of maximising profit for the tramp operator and minimising inventory costs for the charterer, since these"br/"costs increase if similar voyages are not performed with some separation in time. We have developed a new and exact branch-and-price procedure for this problem. We use a dynamic programming algorithm to generate columns and describe a time window branching scheme used to enforce the voyage separation requirements which we relax in the master problem. Computational results show that our algorithm in general finds optimal solutions very quickly and performs much faster compared to an earlier a priori path generation method. Finally, we compare our method to an earlier adaptive large neighbourhood search heuristic and find that on similar-sized instances our approach generally uses less time to find the optimal solution than the adaptive large neighbourhood search method uses to find a heuristic solution. Document type: Book

Abstract

International audience; The resolution of Air Traffic Control (ATC) conflicts is a constrained optimization problem : the goal is to propose, for a certain number, n, of aircraft, which might be in conflict in a near future, trajectories that satisfy the separation constraints between aircraft, and minimizes the delays due to the conflict's resolution. The type of conflict resolution trajectories we use allows to split the problem in two steps: first we choose, and freeze, what we call a configuration of the problem, i.e. for each aircraft, the direction in which the aircraft is diverted, and for each pair of aircraft, which of the two aircraft passes first at the crossing point of the two aircraft trajectories. We can then compute the optimal trajectories corresponding to this configuration, by solving a simple linear optimization problem. Thus we can use an Genetic Algorithm, along with a linear optimization algorithm, such as the simplex algorithm: the elements of the population, on which the GA operates, code configurations of the problem, and are evaluated using a linear optimization program.The advantage of this approach is that we get, as well as the fitness of an element of the population, the local optima corresponding to the configuration coded by this element. The GA actually searches for the global optimum among these local optima. We applied this methods to conflicts in which up to 6 aircraft are involved, and obtained really promising results. Document type: Part of book or chapter of book

Abstract

The mass adoption of plug-in electric vehicles (PEVs) requires the deployment of public charging stations. Such facilities are expected to employ distributed generation and storage units to reduce the stress on the grid and boost sustainable transportation. While prior work has made considerable progress in deriving insights for understanding the adverse impacts of PEV chargings and how to alleviate them, a critical issue that affects the accuracy is the lack of real world PEV data. As the dynamics and pertinent design of such charging stations heavily depend on actual customer demand profile, in this paper we present and evaluate the data obtained from a $17$ node charging network equipped with Level $2$ chargers at a major North American University campus. The data is recorded for $166$ weeks starting from late $2011$. The result indicates that the majority of the customers use charging lots to extend their driving ranges. Also, the demand profile shows that there is a tremendous opportunity to employ solar generation to fuel the vehicles as there is a correlation between the peak customer demand and solar irradiation. Also, we provided a more detailed data analysis and show how to use this information in designing future sustainable charging facilities. Document type: Part of book or chapter of book

Abstract

Traditional solutions to shortest path problems on time-varying transportation networks use traffic information only at precise moments regardless of considering the fact that the travel time through any link is dependent on the time entering that link. In this study, travel speed rather than travel time on each link is used as the time period dependent parameter to model time-dependent transportation networks, and a First-In-First-Out (FIFO) condition satisfied computational function of link travel time is then deduced based on kinematics. Finally, a temporally adaptive A* shortest path algorithm on this FIFO network is presented, where the time factor is introduced into the evaluation function, and the Euclidean distance divided by the maximum possible travel speed is used as a heuristic evaluator. An experiment on a real road network shows that the proposed algorithm is capable of foreseeing and bypassing forthcoming traffic congestion, at a cost only about 10% more in computational time than the traditional algorithm. In addition, frequent path reoptimization required with use of the traditional algorithm is effectively avoided. Document type: Part of book or chapter of book

Abstract

Traffic Engineering (TE) approaches are increasingly impor- tant in network management to allow an optimized configuration and resource allocation. In link-state routing, the task of setting appropriate weights to the links is both an important and a challenging optimization task. A number of different approaches has been put forward towards this aim, including the successful use of Evolutionary Algorithms (EAs). In this context, this work addresses the evaluation of three distinct EAs, a single and two multi-objective EAs, in two tasks related to weight setting optimization towards optimal intra-domain routing, knowing the network topology and aggregated traffic demands and seeking to mini- mize network congestion. In both tasks, the optimization considers sce- narios where there is a dynamic alteration in the state of the system, in the first considering changes in the traffic demand matrices and in the latter considering the possibility of link failures. The methods will, thus, need to simultaneously optimize for both conditions, the normal and the altered one, following a preventive TE approach towards robust configurations. Since this can be formulated as a bi-objective function, the use of multi-objective EAs, such as SPEA2 and NSGA-II, came nat- urally, being those compared to a single-objective EA. The results show a remarkable behavior of NSGA-II in all proposed tasks scaling well for harder instances, and thus presenting itself as the most promising option for TE in these scenarios. Document type: Part of book or chapter of book