Engineering PapersSearch

SEARCH · Engineering Papers

Results for “Route optimization”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records

Route Optimization for Offloading Congested Meter Fixes

The Optimized Route Capability (ORC) concept proposed by the FAA facilitates traffic managers to identify and resolve arrival flight delays caused by bottlenecks formed at arrival meter fixes when there exists imbalance between arrival fixes and runways. ORC makes use of the prediction capability of existing automation tools, monitors the traffic delays based on these predictions, and searches the best reroutes upstream of the meter fixes based on the predictions and estimated arrival schedules when delays are over a predefined threshold. Initial implementation and evaluation of the ORC concept considered only reroutes available at the time arrival congestion was first predicted. This work extends previous work by introducing an additional dimension in reroute options such that ORC can find the best time to reroute and overcome the 'firstcome- first-reroute' phenomenon. To deal with the enlarged reroute solution space, a genetic algorithm was developed to solve this problem. Experiments were conducted using the same traffic scenario used in previous work, when an arrival rush was created for one of the four arrival meter fixes at George Bush Intercontinental Houston Airport. Results showed the new approach further improved delay savings. The suggested route changes from the new approach were on average 30 minutes later than those using other approaches, and fewer numbers of reroutes were required. Fewer numbers of reroutes reduce operational complexity and later reroutes help decision makers deal with uncertain situations.

Optimized Route Capability

Optimized Route Capability (ORC) Intelligent Offloading of Congested Arrival Routes

The Optimized Route Capability (ORC) concept is designed to enable intelligent offloading of congested arrival routes. When ORC predicts arrival route congestion as projected excess arrival meter fix delay, automation offers decision support to traffic managers by identifying candidate flights to strategically reroute to alternate meter fixes and alleviate the congestion. This concept was applied to a model of arrival operations into Houston International Airport. An arrival rush from the Northeast was simulated in fast-time to analyze ORC algorithm behavior. The results demonstrate how strategically rerouting a few flights to alternate meter fixes not only has the potential to manage meter fix delay (and possibly the need for traffic management initiatives applied upstream), but may also increase airport capacity utilization and reduce total flight delay.

Zelinski, Shannon

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.

Mohanty, Bibhu

Costs of Limiting Route Optimization to Published Waypoints in the Traffic Aware Planner

The Traffic Aware Planner (TAP) is an airborne advisory tool that generates optimized, traffic-avoiding routes to support the aircraft crew in making strategic reroute requests to Air Traffic Control (ATC). TAP is derived from a research-prototype self-separation tool, the Autonomous Operations Planner (AOP), in which optimized route modifications that avoid conflicts with traffic and weather, using waypoints at explicit latitudes and longitudes (a technique supported by self-separation concepts), are generated by maneuver patterns applied to the existing route. For use in current-day operations in which trajectory changes must be requested from ATC via voice communication, TAP produces optimized routes described by advisories that use only published waypoints prior to a reconnection waypoint on the existing route. We describe how the relevant algorithms of AOP have been modified to implement this requirement. The modifications include techniques for finding appropriate published waypoints in a maneuver pattern and a method for combining the genetic algorithm of AOP with an exhaustive search of certain types of advisory. We demonstrate methods to investigate the increased computation required by these techniques and to estimate other costs (measured in terms such as time to destination and fuel burned) that may be incurred when only published waypoints are used.

TASAR

Evaluation of a Dispatcher's Route Optimization Decision Aid to Avoid Aviation Weather Hazards

This document describes the results and analysis of the formal evaluation plan for the Honeywell software tool developed under the NASA AWIN (Aviation Weather Information) 'Weather Avoidance using Route Optimization as a Decision Aid' project. The software tool aims to provide airline dispatchers with a decision aid for selecting optimal routes that avoid weather and other hazards. This evaluation compares and contrasts route selection performance with the AWIN tool to that of subjects using a more traditional dispatcher environment. The evaluation assesses gains in safety, in fuel efficiency of planned routes, and in time efficiency in the pre-flight dispatch process through the use of the AWIN decision aid. In addition, we are interested in how this AWIN tool affects constructs that can be related to performance. The construct of Situation Awareness (SA), workload, trust in an information system, and operator acceptance are assessed using established scales, where these exist, as well as through the evaluation of questionnaire responses and subject comments. The intention of the experiment is to set up a simulated operations area for the dispatchers to work in. They will be given scenarios in which they are presented with stored company routes for a particular city-pair and aircraft type. A diverse set of external weather information sources is represented by a stand-alone display (MOCK), containing the actual historical weather data typically used by dispatchers. There is also the possibility of presenting selected weather data on the route visualization tool. The company routes have not been modified to avoid the weather except in the case of one additional route generated by the Honeywell prototype flight planning system. The dispatcher will be required to choose the most appropriate and efficient flight plan route in the displayed weather conditions. The route may be modified manually or may be chosen from those automatically displayed.

Dorneich, Michael C.

Advances in optimal routing through computer networks

The optimal routing problem is defined. Progress in solving the problem during the previous decade is reviewed, with special emphasis on technical developments made during the last few years. The relationships between the routing, the throughput, and the switching technology used are discussed and their future trends are reviewed. Economic aspects are also briefly considered. Modern technical approaches for handling the routing problems and, more generally, the flow control problems are reviewed.

Paz, I. M.

Weather Avoidance Using Route Optimization as a Decision Aid: An AWIN Topical Study

The aviation community is faced with reducing the fatal aircraft accident rate by 80 percent within 10 years. This must be achieved even with ever increasing, traffic and a changing National Airspace System. This is not just an altruistic goal, but a real necessity, if our growing level of commerce is to continue. Honeywell Technology Center's topical study, "Weather Avoidance Using Route Optimization as a Decision Aid", addresses these pressing needs. The goal of this program is to use route optimization and user interface technologies to develop a prototype decision aid for dispatchers and pilots. This decision aid will suggest possible diversions through single or multiple weather hazards and present weather information with a human-centered design. At the conclusion of the program, we will have a laptop prototype decision aid that will be used to demonstrate concepts to industry for integration into commercialized products for dispatchers and/or pilots. With weather a factor in 30% of aircraft accidents, our program will prevent accidents by strategically avoiding weather hazards in flight. By supplying more relevant weather information in a human-centered format along with the tools to generate flight plans around weather, aircraft exposure to weather hazards can be reduced. Our program directly addresses the NASA's five year investment areas of Strategic Weather Information and Weather Operations (simulation/hazard characterization and crew/dispatch/ATChazard monitoring, display, and decision support) (NASA Aeronautics Safety Investment Strategy: Weather Investment Recommendations, April 15, 1997). This program is comprised of two phases, Phase I concluded December 31, 1998. This first phase defined weather data requirements, lateral routing algorithms, an conceptual displays for a user-centered design. Phase II runs from January 1999 through September 1999. The second phase integrates vertical routing into the lateral optimizer and combines the user interface into a prototype software testbed. Phase II concludes with a dispatcher and pilot evaluation of the route optimizer decision aid. This document describes work completed in Phase I in contract with NASA Langley August 1998 - December 1998. This report includes: (1) Discuss how weather hazards were identified in partnership with experts, and how weather hazards were prioritized; (2) Static representations of display layouts for integrated planning function (3) Cost function for the 2D route optimizer; (4) Discussion of the method for obtaining, access to raw data of, and the results of the flight deck user information requirements definition; (5) Itemized display format requirements identified for representing weather hazards in a route planning aid.

Source record

Reducing AI RAG Hallucination by Optimizing Routing Techniques

Large Language Models (LLMs), such as ChatGPT, tend to “hallucinate”, meaning they confidently generate false information. Retrieval Augmented Generation (RAG) attempts to diminish hallucination by providing context to the LLM from data stores (indexes) containing relevant information. The LLM uses this context to formulate its response. RAG systems can still suffer from hallucination because of bad embeddings or ineffective routing. For example, a router will often return context from an irrelevant index, resulting in a hallucinated answer. In this study, we aim to minimize the frequency of routing hallucinations by optimizing Index Summary Routing.

97 MATHEMATICS AND COMPUTING

Deploying a Route Optimization EFB Application for Commercial Airline Operational Trials

The Traffic Aware Planner (TAP), developed for NASA Langley Research Center to support the Traffic Aware Strategic Aircrew Requests (TASAR) project, is a flight-efficiency software application developed for an Electronic Flight Bag (EFB). Tested in two flight trials and planned for operational testing by two commercial airlines, TAP is a real-time trajectory optimization application that leverages connectivity with onboard avionics and broadband Internet sources to compute and recommend route modifications to flight crews to improve fuel and time performance. The application utilizes a wide range of data, including Automatic Dependent Surveillance Broadcast (ADS-B) traffic, Flight Management System (FMS) guidance and intent, on-board sensors, published winds and weather, and Special Use Airspace (SUA) schedules. This paper discusses the challenges of developing and deploying TAP to various EFB platforms, our solutions to some of these challenges, and lessons learned, to assist commercial software developers and hardware manufacturers in their efforts to implement and extend TAP functionality in their environments. EFB applications (such as TAP) typically access avionics data via an ARINC 834 Simple Text Avionics Protocol (STAP) server hosted by an Aircraft Interface Device (AID) or other installed hardware. While the protocol is standardized, the data sources, content, and transmission rates can vary from aircraft to aircraft. Additionally, the method of communicating with the AID may vary depending on EFB hardware and/or the availability of onboard networking services, such as Ethernet, WIFI, Bluetooth, or other mechanisms. EFBs with portable and installed components can be implemented using a variety of operating systems, and cockpits are increasingly incorporating tablet-based technologies, further expanding the number of platforms the application may need to support. Supporting multiple EFB platforms, AIDs, avionics datasets, and user interfaces presents a challenge for software developers and the management of their code baselines. Maintaining multiple baselines to support all deployment targets can be extremely cumbersome and expensive. Certification also needs to be considered when developing the application. Regardless of whether the software is itself destined to be certified, data requirements in support of the application and user interface elements may introduce certification requirements for EFB manufacturers and the airlines. The example of TAP, the challenges faced, solutions implemented, and lessons learned will give EFB application and hardware developers insight into future potential requirements in deploying TAP or similar flight-deck EFB applications.

Roscoe, David A.

Efficient Planning of Wind-Optimal Routes in North Atlantic Oceanic Airspace

The North Atlantic oceanic airspace (NAT) is crossed daily by more than a thousand flights, which are greatly affected by strong jet stream air currents. Several studies devoted to generating wind-optimal (WO) aircraft trajectories in the NAT demonstrated great efficiency of such an approach for individual flights. However, because of the large separation norms imposed in the NAT, previously proposed WO trajectories induce a large number of potential conflicts. Much work has been done on strategic conflict detection and resolution (CDR) in the NAT. The work presented here extends previous methods and attempts to take advantage of the NAT traffic structure to simplify the problem and improve the results of CDR. Four approaches are studied in this work: 1) subdividing the existing CDR problem into sub-problems of smaller sizes, which are easier to handle; 2) more efficient data reorganization within the considered time period; 3) problem localization, i.e. concentrating the resolution effort in the most conflicted regions; 4) applying CDR to the pre-tactical decision horizon (a couple of hours in advance). Obtained results show that these methods efficiently resolve potential conflicts at the strategic and pre-tactical levels by keeping the resulting trajectories close to the initial WO ones.

Rodionova, Olga

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.

Towsley, Don

Separation-Compliant, Optimal Routing and Control of Scheduled Arrivals in a Terminal Airspace

We address the problem of navigating a set (fleet) of aircraft in an aerial route network so as to bring each aircraft to its destination at a specified time and with minimal distance separation assured between all aircraft at all times. The speed range, initial position, required destination, and required time of arrival at destination for each aircraft are assumed provided. Each aircraft's movement is governed by a controlled differential equation (state equation). The problem consists in choosing for each aircraft a path in the route network and a control strategy so as to meet the constraints and reach the destination at the required time. The main contribution of the paper is a model that allows to recast this problem as a decoupled collection of problems in classical optimal control and is easily generalized to the case when inertia cannot be neglected. Some qualitative insight into solution behavior is obtained using the Pontryagin Maximum Principle. Sample numerical solutions are computed using a numerical optimal control solver. The proposed model is first step toward increasing the fidelity of continuous time control models of air traffic in a terminal airspace. The Pontryagin Maximum Principle implies the polygonal shape of those portions of the state trajectories away from those states in which one or more aircraft pair are at minimal separation. The model also confirms the intuition that, the narrower the allowed speed ranges of the aircraft, the smaller the space of optimal solutions, and that an instance of the optimal control problem may not have a solution at all (i.e., no control strategy that meets the separation requirement and other constraints).

transportation network

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.

Towsley, Don

Optimal Routing and Control of Multiple Agents Moving in a Transportation Network and Subject to an Arrival Schedule and Separation Constraints

We address the problem of navigating a set of moving agents, e.g. automated guided vehicles, through a transportation network so as to bring each agent to its destination at a specified time. Each pair of agents is required to be separated by a minimal distance, generally agent-dependent, at all times. The speed range, initial position, required destination, and required time of arrival at destination for each agent are assumed provided. The movement of each agent is governed by a controlled differential equation (state equation). The problem consists in choosing for each agent a path and a control strategy so as to meet the constraints and reach the destination at the required time. This problem arises in various fields of transportation, including Air Traffic Management and train coordination, and in robotics. The main contribution of the paper is a model that allows to recast this problem as a decoupled collection of problems in classical optimal control and is easily generalized to the case when inertia cannot be neglected. Some qualitative insight into solution behavior is obtained using the Pontryagin Maximum Principle. Sample numerical solutions are computed using a numerical optimal control solver.

Sadovsky, A. V.

The TASAR Project: Launching Aviation on an Optimized Route Toward Aircraft Autonomy

The Traffic Aware Strategic Aircrew Request (TASAR) concept applies onboard automation for the purpose of advising the pilot of route modifications that would be beneficial to the flight. Leveraging onboard computing platforms with connectivity to avionics and diverse data sources on and off the aircraft, TASAR introduces a new, powerful capability for in-flight trajectory management to the cockpit and its flight crew that is anticipated to induce a significant culture change in airspace operations. Flight crews empowered by TASAR and its derivative technologies could transform from today’s flight plan followers to proactive trajectory managers, taking an initial critical step towards increasing autonomy in the airspace system. TASAR was developed as a catalyst for operational autonomy, a future vision where the responsibilities and authorities of trajectory management reside with the aircraft operator and are distributed among participating aircraft, thus fulfilling a vision dating back decades and enabling a fully scalable airspace system. This NASA Technical Paper maps TASAR to its foundational vision and traces its research and development from initial concept generation to an operational evaluation by a U.S. airline in revenue service, the final stage before technology transfer and commercialization.

Wing, David J.

Impact of Airspace Charges on Transatlantic Aircraft Trajectories

Aircraft flying over the airspace of different countries are subject to over-flight charges. These charges vary from country to country. Airspace charges, while necessary to support the communication, navigation and surveillance services, may lead to aircraft flying routes longer than wind-optimal routes and produce additional carbon dioxide and other gaseous emissions. This paper develops an optimal route between city pairs by modifying the cost function to include an airspace cost whenever an aircraft flies through a controlled airspace without landing or departing from that airspace. It is assumed that the aircraft will fly the trajectory at a constant cruise altitude and constant speed. The computationally efficient optimal trajectory is derived by solving a non-linear optimal control problem. The operational strategies investigated in this study for minimizing aircraft fuel burn and emissions include flying fuel-optimal routes and flying cost-optimal routes that may completely or partially reduce airspace charges en route. The results in this paper use traffic data for transatlantic flights during July 2012. The mean daily savings in over-flight charges, fuel cost and total operation cost during the period are 17.6 percent, 1.6 percent, and 2.4 percent respectively, along the cost- optimal trajectories. The transatlantic flights can potentially save $600,000 in fuel cost plus $360,000 in over-flight charges daily by flying the cost-optimal trajectories. In addition, the aircraft emissions can be potentially reduced by 2,070 metric tons each day. The airport pairs and airspace regions that have the highest potential impacts due to airspace charges are identified for possible reduction of fuel burn and aircraft emissions for the transatlantic flights. The results in the paper show that the impact of the variation in fuel price on the optimal routes is to reduce the difference between wind-optimal and cost-optimal routes as the fuel price increases. The additional fuel consumption is quantified using the 30 percent variation in fuel prices during March 2014 to March 2015.

aircraft scheduling

An Optimization Approach to Support Science Decision Making for Lunar Surface Exploration

Introduction: Scientific exploration is one of the three pillars of NASA’s Moon2Mars architecture, with crew surface extra vehicular activities (EVA) serving a critical enabling function. Development of surface EVA operational planning and execution, specifically integrating science and flight control teams (FCT), is currently being explored through analog scenarios. This integration, exercised, for example, through the Joint EVA and Hu-man Surface Mobility Test Team (JETT), allows for science input on EVA activities in near real-time through a Science Evaluation Room (SER), or Arte-mis science backroom, which integrates with the broader FCT through the Science Officer. The SER works within the FCT to support dynamic EVA planning in response to changes in operational constraints as well as science opportunities and re-prioritization, increasing the mission science return and accelerating the accomplishment of the Moon2Mars science objectives. The SER works within the FCT to provide recommendations to traverse execution in near real-time. One challenge is the requirement to deliver SER inputs to the FCT on operationally relevant timelines. Failure to do so may result in suboptimal execution of science exploration EVAs or even loss of key science objectives. To close this gap, we present a network optimization tool to allow the SER to provide rapid input to the FCT in response to changes in operational constraints or science opportunities. Inputs are predicated on approved science objectives, and clear rationale must be provided to the FCT for any requested change. Accordingly, this tool incorporates the Science Traceability Matrix (STM), SER prioritization scheme, and station characterization and action planning with operational constraints such as duration, traverse speed, and distance to maximize science objectives based on SER priorities, consistent with FCT operational requirements. Method: As a proof of concept, we used an existing linear programing software package used to simulate optimal routes through cellular metabolism. We built a Demonstrative Model with three STM objectives and four stations on a region of the Moon. The objectives were given an arbitrary prioritization and mapped to the stations through four possible crew actions. (Figs. 1 and 2). This station to STM mapping is consistent with the method used by the JETT5 Science Team to develop analog surface EVA science planning. We used a grid system with the landing site at the origin and the four stations placed across the positive x,y quadrant. Actions were assigned to each station and the accomplishment of those actions resulted in a numerical “reward” based on the ability of that action to achieve science objectives. The aggregate reward from each individual STM objective contributes to a global score (Science Yield), weighted by its priority. Operational constraints included a requirement to start and end at the landing site, 5 minutes each for initial station characterization and “clean up,” and variable total EVA time, traverse rate (fixed to 0.5 meters per second in our example), and time to perform each action (10, 5, 7, and 15 min for actions 1, 2, 3, and 4, respectively). Additional constraints and variables will be added in the future (e.g., sample mass, number of stations, traverse route constraints, illumination). Optimization. We converted the connections (arcs) between these stations (nodes) into a mixed integer linear programming optimization problem (arcs = constraints, nodes = variables) with the objective to maximize Science Yield. For any action, the Science Yield is equal to the relevance of that action to an STM objective [3, 2, and 1 point(s) for High, Med., and Low relevance, respectively], multiplied by the STM Objective Priority [3, 2, and 1 point(s) for High, Med., and Low priority, respectively]. This resulted in a model that computes the optimal station and action combination to maximize the Science Yield. These weightings can be adjusted by the SER as desired. Results: We explored three test cases for the Demonstrative Model. First, we set the maximum EVA duration to 120 minutes and computed the optimal route (Fig. 3A). The model suggested per-forming Actions 1 and 2 at Station P01, followed by Actions 1 and 2 at Station P02, and finally Actions 1 and 3 at Station P04 before returning to the Landing Site. Second, we adjusted the STM Objective Priori-ty order and computed the new optimal route (Fig. 3B). Under this situation, the model suggested per-forming all Actions at Station P02 followed by all Actions at Station P03. The previous test cases were relevant to SER planning activities. Next, we explored providing mid-EVA replanning input to the FCT. Scenario: While executing the Route in Fig. 3A the crew finishes at Station P01 and FCT decides that the EVA needs to finish in 45 minutes back at the Landing Site. FCT asks SER to recommend changes to the plan to accommodate this operation-al change. Using the model and incorporating these new constraints (start at Station P01, max. time of 45 min), the model suggested performing Actions 2 and 4 at Station P03 (Fig. 4), requiring 41 minutes to complete and return to the Landing Site. Interestingly, Station 3 was not part of the original route. Using the model, we determined the EVA would need 66 minutes, instead of 45, in order for the original Station P04 to yield a larger Science Yield than Station P03. The parametrization and simulation was per-formed in less than a minute, demonstrating the operational relevance of the approach. Future Efforts: The results from the Demonstrative Model suggest this tool can accelerate SER decision making on operationally relevant timelines. Use in analog activities, such as JETT5 or follow-ons, which have over a dozen stations for a crew to explore and over a dozen actions per station, will provide needed validation of the utility of this tool for planning EVAs, replanning mid-EVA, or planning follow-on EVAs based on previous results. Further integration with FCT execution monitoring tools may provide additional efficiency gains, al-lowing rapid and iterative exploration of operation-al and science decision space by the FCT and SER.

Science Operations