Engineering Papers⌕ Search

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 73 records · Page 4

Quantum computing for a profusion of postman problem variants

In this paper we study the viability of solving the Chinese Postman Problem, a graph routing optimization problem, and many of its variants on a quantum annealing device. Routing problem variants considered include graph type, directionally varying weights, number of parties involved in routing, among others. We put emphasis on the explanation of how to convert such problems into quadratic unconstrained binary optimization (QUBO) problems. QUBO is one of two equivalent natural paradigms for quantum annealing devices, the other being the Ising Model. We also expand upon a previously discovered algorithm for solving the Chinese Postman Problem on a closed undirected graph to decrease the number of constraints and variables used in the problem. Optimal annealing parameter settings and constraint weight values are discussed based on results from implementation on the D-Wave 2000Q and Advantage. Results from classical, purely quantum, and hybrid algorithms are compared.

97 MATHEMATICS AND COMPUTING↗

Quantum Routing and Entanglement Dynamics Through Bottlenecks

To implement arbitrary quantum circuits in architectures with restricted interactions, one may effectively simulate all-to-all connectivity by routing quantum information. We consider the entanglement dynamics and routing between two regions only connected through an intermediate “bottleneck” region with few qubits. In such systems, where the entanglement rate is restricted by a vertex boundary rather than an edge boundary of the underlying interaction graph, existing results such as the small incremental entangling theorem give only a trivial constant lower bound on the routing time (the minimum time to perform an arbitrary permutation). We significantly improve the lower bound on the routing time in systems with a vertex bottleneck. Specifically, for any system with two regions 𝐿,𝑅 with 𝑁 𝐿 ,𝑁 𝑅 qubits, respectively, coupled only through an intermediate region 𝐶 with 𝑁 𝐶 qubits, for any 𝛿 > 0 we show a lower bound of Ω⁢(𝑁$^{1−𝛿}_{𝑅}$/√𝑁 𝐿⁢ 𝑁 𝐶 ) on the Hamiltonian quantum routing time when using piecewise time-independent Hamiltonians, or time-dependent Hamiltonians subject to a smoothness condition. We also prove an upper bound on the average amount of bipartite entanglement between 𝐿 and 𝐶,𝑅 that can be generated in time 𝑡 by such architecture-respecting Hamiltonians in systems constrained by vertex bottlenecks, improving the scaling in the system size from 𝑂⁡(𝑁 𝐿⁢ 𝑡) to 𝑂⁡(√𝑁 𝐿⁢ 𝑡). As a special case, when applied to the star graph (i.e., one vertex connected to 𝑁 leaves), we obtain an Ω⁡(√𝑁 1−𝛿 ) lower bound on the routing time and on the time to prepare 𝑁/2 Bell pairs between the vertices. We also show that, in systems of free particles, we can route optimally on the star graph in time Θ⁡(√𝑁) using Hamiltonian quantum routing, obtaining a speedup over gate-based routing, which takes time Θ⁡(𝑁).

97 MATHEMATICS AND COMPUTING↗

Applying the Cognitive Space Gateway to Swarm Topologies

NASA's future vision for interplanetary networking includes a lunar network, Cube Satellite (CubeSat) constellations, and deep space robotic missions, comprising what could be viewed as a network of networks. Delay-tolerant networking (DTN) architecture and protocols provide a standard network layer among these varying scenarios and mitigate many challenges of the space environment, such as long delays, unplanned service interruptions, and asymmetric links. The Cognitive Space Gateway (CSG) is a routing method in a DTN architecture that uses spiking neural networks as the learning element to optimize routing decisions in a complex environment. This work aims to further develop cognitive networking technologies in several critical areas, including DTN, the CSG algorithm, CubeSat swarm topologies, and cloud services. To test the algorithm in a realistic scenario, the emulated network topology is based on a CubeSat swarm. The swarm may function as a mesh of nodes or as a hub-and-spoke network. An emulation environment will be built upon a commercial cloud service, such as Amazon Web Services (AWS) Elastic Compute Cloud. The cloud environment may enable a flexible, lower maintenance approach versus a multi-hop network based in a physical laboratory. The cloud platform will provide a secure environment allowing for collaboration among government and academic entities.

Ricardo Lent↗

Network-Control Algorithm

Algorithm developed for optimal routing of packets of data along links of multilink, multinode digital communication network. Algorithm iterative and converges to cost-optimal assignment independent of initial assignment. Each node connected to other nodes through links, each containing number of two-way channels. Algorithm assigns channels according to message traffic leaving and arriving at each node. Modified to take account of different priorities among packets belonging to different users by using different delay constraints or imposing additional penalties via cost function.

Chan, Hak-Wai↗

Introducing Tropical Geometric Approaches to Delay Tolerant Networking Optimization

Delay Tolerant Networking (DTN) is the standard approach to the networking of space systems with the goal of supporting the Solar System Internet (SSI). Current space networks have a small scale and often depend on rigorously scheduled (pre-determined) contact opportunities; this manual approach inhibits scalability. The goal of this paper is to recast these scheduling problems in order to apply the optimization machinery of tropical geometry. Contact opportunities in space are dependent on such factors as orbital mechanics and asset availability, which induce time-varying connectivity; indeed, end-to-end connectivity might never occur. Routing optimization within this structure is classically difficult and typically utilizes Dijkstra's algorithm as applied to contact graphs. Alternatively, we follow the successes of tropical geometry in train schedule optimization, job assignments, and even traditional networking, by extending this approach to this more general (i.e. disconnected) problem space. These successes imply tropical geometry provides a useful framework in the context of DTNs, starting with applications to queuing theory and long-haul links. Recently, tropical geometry has been applied to parametric path optimization on graphs with variable edge weights. In this work, we extend these advances to account for the problem of routing in a space network, and find that tropical geometry is well-suited to the challenges offered by this new setting, including contact schedules featuring probabilities. Our approach leverages the combinatorial nature of the problem to give feasible shortest path trees in the presence of variable channel conditions and latency, evolving topologies, and uncertainty inherent in space routing. We discuss our tropical approach to DTN for two Python implementations, a Verilog Tropical ALU implementation, tropical frameworks for other parametric graph problems, and solution stability. Lastly, a program for future work is included to illuminate the path ahead.

Delay Tolerant Networking↗

Minimizing Energy Use of Mixed-Fleet Public Transit for Fixed-Route Service

Affordable public transit services are crucial for communities since they enable residents to access employment, education, and other services. Unfortunately, transit services that provide wide coverage tend to suffer from relatively low utilization, which results in high fuel usage per passenger per mile, leading to high operating costs and environmental impact. Electric vehicles (EVs) can reduce energy costs and environmental impact, but most public transit agencies have to employ them in combination with conventional, internal-combustion engine vehicles due to the high upfront costs of EVs. To make the best use of such a mixed fleet of vehicles, transit agencies need to optimize route assignments and charging schedules, which presents a challenging problem for large transit networks. We introduce a novel problem formulation to minimize fuel and electricity use by assigning vehicles to transit trips and scheduling them for charging, while serving an existing fixed-route transit schedule. We present an integer program for optimal assignment and scheduling, and we propose polynomial-time heuristic and meta-heuristic algorithms for larger networks. We evaluate our algorithms on the public transit service of Chattanooga, TN using operational data collected from transit vehicles. Our results show that the proposed algorithms are scalable and can reduce energy use and, hence, environmental impact and operational costs. For Chattanooga, the proposed algorithms can save $145,635 in energy costs and 576.7 metric tons of CO 2 emission annually.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Analysis of a Dynamic Multi-Track Airway Concept for Air Traffic Management

The Dynamic Multi-track Airways (DMA) Concept for Air Traffic Management (ATM) proposes a network of high-altitude airways constructed of multiple, closely spaced, parallel tracks designed to increase en-route capacity in high-demand airspace corridors. Segregated from non-airway operations, these multi-track airways establish high-priority traffic flow corridors along optimal routes between major terminal areas throughout the National Airspace System (NAS). Air traffic controllers transition aircraft equipped for DMA operations to DMA entry points, the aircraft use autonomous control of airspeed to fly the continuous-airspace airway and achieve an economic benefit, and controllers then transition the aircraft from the DMA exit to the terminal area. Aircraft authority within the DMA includes responsibility for spacing and/or separation from other DMA aircraft. The DMA controller is responsible for coordinating the entry and exit of traffic to and from the DMA and for traffic flow management (TFM), including adjusting DMA routing on a daily basis to account for predicted weather and wind patterns and re-routing DMAs in real time to accommodate unpredicted weather changes. However, the DMA controller is not responsible for monitoring the DMA for traffic separation. This report defines the mature state concept, explores its feasibility and performance, and identifies potential benefits. The report also discusses (a) an analysis of a single DMA, which was modeled within the NAS to assess capacity and determine the impact of a single DMA on regional sector loads and conflict potential; (b) a demand analysis, which was conducted to determine likely city-pair candidates for a nationwide DMA network and to determine the expected demand fraction; (c) two track configurations, which were modeled and analyzed for their operational characteristic; (d) software-prototype airborne capabilities developed for DMA operations research; (e) a feasibility analysis of key attributes in the concept design; (f) a near-term, transitional application of the DMA concept as a proving ground for new airborne technologies; and (g) conclusions. The analysis indicates that the operational feasibility of a national DMA network faces significant challenges, especially for interactions between DMAs and between DMA and non-DMA traffic. Provided these issues are resolved, sectors near DMAs could experience significant local capacity benefits.

Wing, David J.↗

Wind-Optimal Trajectories for Multirotor eVTOL Aircraft on UAM Missions

Distributed electric propulsion powered electric vertical takeoff and landing aircraft are expected to enable urban air mobility. Low specific energy of onboard lithium-ion polymer batteries and wind conditions impose constraints on flight endurance. Therefore, from the safety and efficiency perspective, planning and flying minimum energy trajectories are important.The primary motivation for this paper is to determine if there is an operational benefit to flying wind-optimal trajectories for short flights (less than 60 miles) in the urban environment. This study employs wind-optimal trajectories for a NASA-proposed conceptual multirotor aircraft flight in the urban environment. The optimal control model presented includes a wind model for quantifying the effect of wind on the trajectory. The optimal control problem is numerically solved using the direct method. Energy consumption and flight duration flying wind-optimal trajectories between origins and destinations in a metropolitan area are compared with energy consumption and flight duration flying on the great-circle paths between the same origin and destination pairs to determine the operational benefit of wind-optimal routing for short flights.The flight duration results for different scenarios are validated using a simulation tool designed and developed by NASA for exploring advanced air traffic management concepts. In summary,this research study suggests that for short flights in an urban environment, the wind-optimal trajectories have a very slight (insignificant) operational advantage over the great-circle trajectories in terms of energy consumption and flight duration. As expected, headwinds and tailwinds along the route of flight have a significant impact on energy consumption and flight duration.

Urban Air Mobility↗

Wind-Optimal Lateral Trajectories for a Multirotor Aircraft in Urban Air Mobility

The primary motivation for this paper is to quantify the operational benefits (energy consumption and flight duration) of flying wind-optimal lateral trajectories for short flights (less than 60 miles) anticipated in the urban environment. The optimal control model presented includes a wind model for quantifying the effect of wind on the lateral trajectory. The optimal control problem is numerically solved using the direct collocation method. Energy consumption and flight duration flying wind-optimal lateral trajectories are compared with corresponding values obtained flying great-circle paths between the same origin and destination pairs to determine the operational benefits of wind-optimal routing for short flights. The flight duration results for different scenarios are validated using a simulation tool designed and developed at NASA for exploring advanced air traffic management concepts. This research study suggests that for short flights in an urban environment, operational benefits of the wind-optimal lateral trajectories over the corresponding great-circle trajectories in terms of energy consumption and flight duration per flight are dependent on: i) wind field’s spatial variability, ii) wind magnitude, iii) the direction of route relative to the wind field, and iv) cruise segment length. The operational benefits observed in realistic flyable wind scenarios are less than 2.5%; these could be translated to an equivalent of a maximum of 2 min of cruise flight duration savings in the urban air mobility environment. As expected, headwinds and tailwinds along the flight route most significantly impact energy consumption and flight duration.

Wind-Optimal Trajectory, Lateral Path, Urban Air M↗

CostMAP: an open-source software package for developing cost surfaces using a multi-scale search kernel

Cost surfaces are a crucial aspect of route optimization and least cost path (LCP) calculations and are used in awide range of disciplines including computer science, landscape ecology, and energy-infrastructure modeling. Linear features introduce akey weakness to traditional routing calculations along cost surfaces because they cannot identify whether moving from acell to its adjacent neighbors constitutes crossing alinear barrier (increased cost) or following acorridor (reduced cost). Following and avoiding linear features can drastically change predicted routes. We introduce an approach to address this adjacency issue using asearch kernel that determines these critical barriers and corridors. We have built this method into anew Java-based open-source software package– CostMAP (cost surface multi-layer aggregation program)– which calculates cost surfaces and cost networks using the search kernel. CostMAP allows users to input multiple GIS data layers and to set weights and rules for developing aweighted-cost network. We compare CostMAP performance with traditional cost surface approaches and show significant performance gains– both following corridors and avoiding barriers– by modeling the movement of alarge terrestrial animal– the Baird’s Tapir (Tapirus bairdii)– in amovement ecology framework and by modeling pipeline routing for carbon capture and storage (CCS).

58 GEOSCIENCES↗

exnehilo7/fielddata-lite-iOS-app

Field Expedition Routing and Navigation (FERN) is an IOS app funded by the Center for Bioenergy Innovation (CBI). It allows an end user to make trips to collect novel data points. It allows user to return to previously surveyed points to collect more data. It calculates the optimal route to use to sample points needed for return trips. A companion php/database application is required for full functionality. Links to this open source project are in the README. FERN can use the default GPS on an Iphone but it also optimized for Arrow Gold GPS. Other external GPS could be supported by modifying this code and adding the proper routines.

Hopp, Daniel↗

Non-unimodal and non-concave relationships in the network Macroscopic Fundamental Diagram caused by hierarchical streets

Unimodal, concave relationships between average network productivity and accumulation or density aggregated across spatially compact regions of urban networks—so called network Macroscopic Fundamental Diagrams (MFDs)—have recently been shown to exist on homogeneous street networks. When present, MFD relationships facilitate the modeling of traffic congestion at a regional level and have led to the development of various regional traffic control strategies. However, real street networks are not homogeneous—they generally have a hierarchical structure where some streets (e.g., arterials) promote higher mobility than others (e.g., local roads). Here, this paper examines how the presence of hierarchical roadway structures may potentially cause non-unimodal patterns in a network's MFD. These are observed using three types of tools: analytical models of simple network structures, simulations of various idealized roadway networks, and empirical data. The impacts of street hierarchy depend on how vehicles use different roadway types to move within the network; i.e., their routing strategy. The findings suggest that the presence of roadway hierarchies may lead to MFDs that have non-unimodal or non-concave patterns on the free-flow branch when vehicles route themselves according to user equilibrium principles, which is closest to what would be observed in realistic situations. Such patterns are contrary to what is traditionally assumed in most MFD-based modeling frameworks. However, the unimodal and concave MFD should be expected under system optimal routing conditions that maximize network productivity for a given traffic state.

42 ENGINEERING↗

Comparing in planta accumulation with microbial routes to set targets for a cost-competitive bioeconomy

Plants and microbes share common metabolic pathways for producing a range of bioproducts that are potentially foundational to the future bioeconomy. However, in planta accumulation and microbial production of bioproducts have never been systematically compared on an economic basis to identify optimal routes of production. A detailed technoeconomic analysis of four exemplar compounds (4-hydroxybenzoic acid [4-HBA], catechol, muconic acid, and 2-pyrone-4,6-dicarboxylic acid [PDC]) is conducted with the highest reported yields and accumulation rates to identify economically advantaged platforms and breakeven targets for plants and microbes. The results indicate that in planta mass accumulation ranging from 0.1 to 0.3 dry weight % (dwt%) can achieve costs comparable to microbial routes operating at 40 to 55% of maximum theoretical yields. These yields and accumulation rates are sufficient to be cost competitive if the products are sold at market prices consistent with specialty chemicals ($20 to $50/kg). Prices consistent with commodity chemicals will require an order-of-magnitude-greater accumulation rate for plants and/or yields nearing theoretical maxima for microbial production platforms. This comparative analysis revealed that the demonstrated accumulation rates of 4-HBA (3.2 dwt%) and PDC (3.0 dwt%) in engineered plants vastly outperform microbial routes, even if microbial platforms were to reach theoretical maximum yields. Their recovery and sale as part of a lignocellulosic biorefinery could enable biofuel prices to be competitive with petroleum. Muconic acid and catechol, in contrast, are currently more attractive when produced microbially using a sugar feedstock. Ultimately, both platforms can play an important role in replacing fossil-derived products.

59 BASIC BIOLOGICAL SCIENCES↗

Workload Considerations in Urban Air Mobility

Urban air mobility (UAM) is receiving increased attention in aviation as a system for passenger and cargo-carrying new entrants in urban airspace. In order to develop a safe and efficient system, numerous possible concepts of operation for UAM are being explored throughout industry and research domains, the features and assumptions of which may differ according to near, medium and far term operations. Much of the current research into the development of UAM has dominantly focused on technological and engineering capabilities, such as vehicle development. Although these areas of research are essential to furthering UAM, research into the role of the human operator in UAM is limited. The research described in this paper aims to begin to address this gap by investigating the capabilities and implications of human operators as traffic managers in the UAM system, focusing on near-term UAM operations. A human in the loop air traffic control simulation was used to investigate the effect of UAM traffic density, airspace routes and communication procedures on subjective workload and efficiency-related task performance. Findings indicate that medium and high-density operations were associated with high workload. A reduction in verbal communications through a letter of agreement, and optimized routes, were associated with reduced workload and increased performance efficiency. However, even with these adjustments, reported workload remained high, particularly during the high-density scenario. Future research should focus on the human operator roles and responsibilities, and the amount of involvement, in UAM system management. Particular focus should be directed on the impact of reduced human operator involvement and increased automation, on the safety and efficiency of UAM operations and the integration of UAM with traditional air traffic management.

Edwards, Tamsyn↗

Automated Flight Routing Using Stochastic Dynamic Programming

Airspace capacity reduction due to convective weather impedes air traffic flows and causes traffic congestion. This study presents an algorithm that reroutes flights in the presence of winds, enroute convective weather, and congested airspace based on stochastic dynamic programming. A stochastic disturbance model incorporates into the reroute design process the capacity uncertainty. A trajectory-based airspace demand model is employed for calculating current and future airspace demand. The optimal routes minimize the total expected traveling time, weather incursion, and induced congestion costs. They are compared to weather-avoidance routes calculated using deterministic dynamic programming. The stochastic reroutes have smaller deviation probability than the deterministic counterpart when both reroutes have similar total flight distance. The stochastic rerouting algorithm takes into account all convective weather fields with all severity levels while the deterministic algorithm only accounts for convective weather systems exceeding a specified level of severity. When the stochastic reroutes are compared to the actual flight routes, they have similar total flight time, and both have about 1% of travel time crossing congested enroute sectors on average. The actual flight routes induce slightly less traffic congestion than the stochastic reroutes but intercept more severe convective weather.

Ng, Hok K.↗

Optimal guidance with obstacle avoidance for nap-of-the-earth flight

The development of automatic guidance is discussed for helicopter Nap-of-the-Earth (NOE) and near-NOE flight. It deals with algorithm refinements relating to automated real-time flight path planning and to mission planning. With regard to path planning, it relates rotorcraft trajectory characteristics to the NOE computation scheme and addresses real-time computing issues and both ride quality issues and pilot-vehicle interfaces. The automated mission planning algorithm refinements include route optimization, automatic waypoint generation, interactive applications, and provisions for integrating the results into the real-time path planning software. A microcomputer based mission planning workstation was developed and is described. Further, the application of Defense Mapping Agency (DMA) digital terrain to both the mission planning workstation and to automatic guidance is both discussed and illustrated.

Pekelsma, Nicholas J.↗

Exploring Human Factors Issues for Urban Air Mobility Operations

Urban air mobility (UAM) is currently receiving increased attention in the aviation literature as a new entrant into the airspace. Although the introduction of UAM offers the potential for significant benefits, it also creates the potential for fundamental change to the current air traffic management system. Several concepts are being explored to enable the development of a safe and efficient UAM system for near, mid and far term operations. A concept of operations for near term operations proposes several assumptions. Concepts for roles and responsibilities of human operators such as air traffic controllers propose different degrees of involvement. Identifying and exploring human factors issues is therefore a critical next step in the forward progression of concept development. A human-in-the-loop air traffic control simulation was used to investigate the effect of UAM traffic density and changes in current airspace routes and communication procedures on subjective controller workload and efficiency-related task performance. Findings indicate that although subjective workload was manageable for low density operations, medium and high density operations led to unmanageable levels of workload, leading to refusals to allow more vehicles into controlled airspace. By implementing a letter of agreement, verbal communications were reduced which were associated with reduced workload. Optimized routes were also associated with reduced workload and increased performance efficiency. Although these adjustments can positively support controller performance, workload still remained high during the high density UAM traffic scenarios. It is therefore suggested that, in order for UAM operation to become scalable, human operators will be required to work differently compared to current air traffic controllers. Future research should focus on the level and type of human operator or controller involvement and mated systems, to ensure safety and efficiency within UAM operations.

Air Traffic Management↗

Transportation Hub Infrastructure Expansion: Decision Support Under Uncertainty

The Athena project (www.athena-mobility.org) has worked to investigate the relationship between the Dallas-Fort Worth Airport (DFW) and the greater Dallas area in order to better understand and therefore better inform future decision-making regarding the critical infrastructure that influence mobility between the airport and the city. Through this work, infrastructure related to curbside pickup and drop-off, parking, public transit, and the road network congestion were identified as critical to the operation of the DFW transportation hub. The infrastructure analysis and expansion aspect of the Athena project is focused on the restructuring of the CTA curb as a hierarchical curb and the building or repurposing of parking infrastructure as the interplay between these two areas. Many sources of uncertainty exist that may impact future airport and transportation hub operations, such as passenger volume growth, population demographic changes over time, electric vehicle (EV) adoption rates, and autonomous vehicle (AV) adoption rates. Due to these sources of uncertainty, we have selected for our research a modeling framework that can capture various types of uncertainty and hedge against those uncertainties in the optimization process. We analyze road network and curb congestion, the rise of transportation networking companies, trends in parking usage, existing policies around this infrastructure, airport revenue streams, and other contributing factors to enable infrastructure decision making with less uncertainty. To accomplish this wholistic analysis, we have developed a novel multi-stage, multi-period stochastic optimization model which considers the airport's decisions from 2025-2045 under different possible future macro trajectories and day-to-day variations in operational conditions captured as "annual representation of operations" scenarios with respective probabilities. This model has also been designed to leverage the outputs of various efforts under the Athena project to create a combined decision framework for infrastructure decisions. These various efforts include the route optimization model, the ASPIRES simulation, the mode choice model, and the SUMO traffic simulation. Our computational experiments of this system at scale have resulted in a working version of our infrastructure model which enables the explicit representation and consideration of various sources of uncertainty in the decision process to enable robust, flexible decision-making. This model has been effectively run on NREL's HPC system, Eagle, with large numbers of stochastic scenarios and shows promise as a scalable tool for robust consideration of uncertainties in airport planning. We have tested our model using 30,240 operational circumstances in total, resulting in a problem with more 200 million variables. This model was solved in several different configurations, and a workflow to simulate the performance of the infrastructure model results was developed and deployed. In general, our results indicate that a combination of remote parking, remote curb infrastructure, and dynamic pricing can generate revenue, reduce emissions, accommodate emerging technologies such as AVs and EVs, and manage airport passenger growth over time. We note the success of the proposed strategy depends on the data collection and forecasting abilities of DFW. We have also seen that the AV adoption by TNCs might necessitate larger amounts of remote curb. The results of this work inform strategies for airport infrastructure decision making, as well as demonstrate the value of an adaptable model, but also indicate that there are avenues remaining where further research would be of value.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗