SEARCH · Engineering Papers

Results for “Mixed Integer Programming”

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.

SourceResearch connectionFrom yearThrough year

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

67 records · Page 4

All sources NASA NTRS DOE OSTI

NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Hybrid Monte Carlo Tree Search Approach

We present the Multi-Route Weighted Package Delivery Problem (MRWPDP) and a scalable solution methodology as a major step towards enabling an airspace deconfliction service for drone delivery operations. The problem is motivated by Strategic deconfliction under the FAA’s “Unmanned Aircraft Systems Traffic Management” Concept of Operations. MRWPDP falls under a class of vehicle routing and scheduling problems, and as such is NP-Hard. In MRWPDP, a graph network is given which consists of depots, drop-off sites, and multiple routes connecting the two. In addition, routes are weighted by the associated ground risk and total travel distance for package delivery. The goal is to optimally schedule the departure time and assign routes to a known set of vehicles at the depot. We propose a heuristic solution to the problem by borrowing techniques from Mixed Integer Linear Programming (MILP), Constraint Programming, and Monte Carlo Tree Search (MCTS). The resulting hybrid framework is MCTS with Bound-and-Prune (BP) and rapid simulated updates (U), or MCTS-BP-U. This approach is able to quickly provide a feasible solution for MRWPDP, even for large problem instances up to 1000 vehicles. We provide a MILP formulation of MRWPDP and compare its performance against MCTS-BP-U in terms of solution quality. An agent-based model simulation is conducted as a final step to validate the efficacy of our approach.

air traffic scheduling↗

NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Hybrid Monte Carlo Tree Search Approach

air traffic scheduling↗

NASA NTRSDate not supplied

Rolling Horizon with K-Position Search Method for Strategic Deconfliction of Package Delivery UAS

In this research, the strategic deconfliction of unmanned aircraft systems for an urban package delivery environment with two depots and multiple drop-off locations is studied. This research aims to formulate a mathematical model to compute both the departure sequence and scheduled time of departure for each unmanned aircraft system at a depot, considering temporal constraints at en-route crossing waypoints and depots for strategic deconfliction. However, the problem formulation results in an NP-hard mixed-integer nonlinear programming problem for the global optimal solution, so instead, a "rolling horizon with𝑘-position search"heuristic method is developed. The simulation studies show that an increase in the value of𝑘(the parameter used to determine the size of the local neighborhood) reduces the average ground delay at the cost of an increase in the computation time for a given problem size. The study also shows an order of magnitude increase in the maximum number of flights scheduled with the integration of rolling horizon (time decomposition) compared to those without the integration of rolling horizon in the heuristic algorithm for a given computation time cut off.

UTM↗

NASA NTRSDate not supplied

Rolling Horizon with K-Position Search Method for Strategic Deconfliction of Package Delivery UAS

This research focuses on the strategic deconfliction of unmanned aircraft systems (UAS) in an urban package delivery environment with two depots and multiple drop-off locations. Since the formulated mixed-integer nonlinear programming (MINLP) problem is non-deterministic polynomial-time (NP) hard, a heuristic algorithm called "rolling horizon with k-position search (KPS)" is used to compute the departure sequence and scheduled time of departure (STD) of each UAS at a depot, considering temporal constraints at en-route crossing waypoints and depots for strategic deconfliction. The simulation studies show that an increase in the value of k (local neighborhood search) in the KPS reduces the average ground delay at the cost of an increase in the computation time for a given number of UAS, size of the rolling horizon window, and number of depots involved in the local neighborhood search. The studies also show that for a given rolling horizon window, the computation time increases exponentially with an increase in the total number of UAS flights when serial processing the local neighborhood search of KPS (with k > 1) and drops by an order of magnitude upon performing the local neighborhood search of KPS using parallel processing instead of serial processing. The computation time drops with the reduction in air traffic complexity of a scenario for a given number of flights, k (local neighborhood search), and rolling horizon window.

UTM↗

NASA NTRS1992

Menu-Driven Solver Of Linear-Programming Problems

Program assists inexperienced user in formulating linear-programming problems. A Linear Program Solver (ALPS) computer program is full-featured LP analysis program. Solves plain linear-programming problems as well as more-complicated mixed-integer and pure-integer programs. Also contains efficient technique for solution of purely binary linear-programming problems. Written entirely in IBM's APL2/PC software, Version 1.01. Packed program contains licensed material, property of IBM (copyright 1988, all rights reserved).

Viterna, L. A.↗

NASA NTRSDate not supplied

Scheduling Position, Navigation and Time Service Requests from Non-dedicated Lunar Constellations

This paper presents a centralized scheduler that satisfies user requests for Position, Navigation, and Time (PNT) services from an ad-hoc, non-dedicated orbital constellation around the Moon. Traditional, dedicated GNSS networks provide service 24/7, which allows users to acquire localization services at-will. For ad-hoc networks, a coordinated schedule is needed to ensure Quality of Service (QoS) guarantees for user localization, while satisfying non-dedicated assets’ usage constraints. This scheduler bridges this coordination gap by leveraging Mixed Integer-Linear Programming (MILP) to schedule this “as-needed” localization service while respecting the constraints on each asset. In upcoming decades there is expected to be a substantial increase in Lunar missions. Many of these missions will feature low-cost surface assets near the moon’s polar regions and small-sat science missions in orbit. Most missions need PNT capabilities to ensure safe operations and meet their science objectives, but low-cost missions may not be able to support the large power, mass, and weight that a weak GNSS or DSN based navigation solution would entail. Asset localization has been demonstrated using a decentralized extended Kalman Filter (DEKF) in the previously presented Lunar Autonomous PNT System (LAPS). Within the LAPS simulation environment, a module has been developed to generate the coordinated user-asset schedules described above; this Service Scheduler Module (SSM) allows for complete end-to-end testing of the entire system. Within SSM, a user service request consists of a location on the Lunar surface, a cumulative service duration, and a window in which service must occur. SSM takes as input these requests and the LAPS-predicted positional degree of precision as the QoS for each available set of orbital assets. A simple, baseline MILP model is formulated to provide the highest-precision service balanced across all requests. To reflect the non-dedicated nature of the constellation, this baseline model is augmented with additional asset-specific load capacity constraints or availability constraints. The load capacity constraints limit total time spent providing service, and the availability constraints reflect blockout times or availability windows when the assets are not otherwise occupied. SSM outputs two schedules: the user schedule to indicate their service times and expected QoS, and a satellite schedule to be transmitted to the orbiting constellation, describing when each non-dedicated asset provides PNT service. SSM is predominantly implemented in MATLAB and allows the use of any MILP solver to generate the resulting schedules. This paper describes the SSM - LAPS interface, how the output of LAPS is used to construct the MILP, and how SSM provides user localization service while satisfying constraints. It will also demonstrate the tool’s flexibility for formulating schedules for the end user and the constellation, focusing on scenarios that match real-world proposed missions. It will detail how SSM can be used to compare the addition of load capacity constraints, satellite availability constraints, and QoS guarantees for the users. Finally, we describe how SSM can be used to support the design of the ad-hoc constellation itself. The resulting integrated capability will support the design of future ad-hoc Lunar PNT networks, enabling high-quality, low-cost Lunar exploration

Swarm↗

NASA NTRS2018

Next Generation Aircraft Design Considering Airline Operations and Economics

Traditional approaches to design and optimization of a new system often use a system-centric objective and do not take into consideration how the operator will use this new system alongside other existing systems. When the new system design is incorporated into the broader group of systems, the performance of the operator-level objective can be sub-optimal due to the unmodeled interaction between the new system and the other systems. Among the few available references that describe attempts to address this disconnect, most follow an MDO (Multidisciplinary Design Optimization)-motivated sequential decomposition approach of first designing a very good system and then providing this system to the operator who, decides the best way to use this new system along with the existing systems. This paper addresses this issue by including aircraft design, airline operations, and revenue management "subspaces"; and presents an approach that could simultaneously solve these subspaces posed as a monolithic optimization problem rather than the traditional approach described above. The monolithic approach makes the problem an expensive Mixed Integer Non-Linear Programming problem, which are extremely difficult to solve. To address the problem, we use a recently developed optimization framework that simultaneously solves the subspaces to capture the "synergy" in the problem that the previous decomposition approaches did not exploit, addresses mixed-integer/discrete type design variables in an efficient manner, and accounts for computationally expensive analysis tools. This approach solves an 11-route airline network problem consisting of 94 decision variables including 33 integer and 61 continuous type variables. Simultaneously solving the subspaces leads to significant improvement in the fleet-level objective of the airline when compared to the previously developed sequential subspace decomposition approach.

Roy, Satadru↗

NASA NTRS2017

Efficient Trajectory Options Allocation for the Collaborative Trajectory Options Program

The Collaborative Trajectory Options Program (CTOP) is a Traffic Management Initiative (TMI) intended to control the air traffic flow rates at multiple specified Flow Constrained Areas (FCAs), where demand exceeds capacity. CTOP allows flight operators to submit the desired Trajectory Options Set (TOS) for each affected flight with associated Relative Trajectory Cost (RTC) for each option. CTOP then creates a feasible schedule that complies with capacity constraints by assigning affected flights with routes and departure delays in such a way as to minimize the total cost while maintaining equity across flight operators. The current version of CTOP implements a Ration-by-Schedule (RBS) scheme, which assigns the best available options to flights based on a First-Scheduled-First-Served heuristic. In the present study, an alternative flight scheduling approach is developed based on linear optimization. Results suggest that such an approach can significantly reduce flight delays, in the deterministic case, while maintaining equity as defined using a Max-Min fairness scheme.

Traffic Management Initiative (TMI)↗

NASA NTRS1987

Optimization of orbital assignment and specification of service areas in satellite communications

The mathematical nature of the orbital and frequency assignment problem for communications satellites is explored, and it is shown that choosing the correct permutations of the orbit locations and frequency assignments is an important step in arriving at values which satisfy the signal-quality requirements. Two methods are proposed to achieve better spectrum/orbit utilization. The first, called the delta S concept, leads to orbital assignment solutions via either mixed-integer or restricted basis entry linear programming techniques; the method guarantees good single-entry carrier-to-interference ratio results. In the second, a basis for specifying service areas is proposed for the Fixed Satellite Service. It is suggested that service areas should be specified according to the communications-demand density in conjunction with the delta S concept in order to enable the system planner to specify more satellites and provide more communications supply.

Wang, Cou-Way↗

NASA NTRS1993

Stochastic search in structural optimization - Genetic algorithms and simulated annealing

An account is given of illustrative applications of genetic algorithms and simulated annealing methods in structural optimization. The advantages of such stochastic search methods over traditional mathematical programming strategies are emphasized; it is noted that these methods offer a significantly higher probability of locating the global optimum in a multimodal design space. Both genetic-search and simulated annealing can be effectively used in problems with a mix of continuous, discrete, and integer design variables.

Hajela, Prabhat↗

NASA NTRS1994

A Fortran-90 Based Multiprecision System

The author has developed a new version of his Fortran multiprecision computation system that is based on the Fortran-90 language. With this new approach, a translator program is not required - translation of Fortran code for multiprecision is accomplished by merely utilizing advanced features of Fortran-90, such as derived data types and operator extensions. This approach results in more reliable translation and also permits programmers of multiprecision applications to utilize the full power of the Fortran-90 language. Three multiprecision datatypes are supported in this system: multiprecision integer. real and complex. All the usual Fortran conventions for mixed mode operations are supported, and many of the Fortran intrinsics, such as SIN, EXP and MOD, are supported with multiprecision arguments. This paper also briefly describes an interesting application of this software, wherein new number-theoretic identities have been discovered by means of multiprecision computations.

Bailey, David H.↗

NASA NTRS2008

Efficient G(sup 4)FET-Based Logic Circuits

A total of 81 optimal logic circuits based on four-gate field-effect transistors (G(sup 4)4FETs) have been designed to implement all Boolean functions of up to three variables. The purpose of this development was to lend credence to the expectation that logic circuits based on G(sup 4)FETs could be more efficient (in the sense that they could contain fewer transistors), relative to functionally equivalent logic circuits based on conventional transistors. A G(sup 4)FET a combination of a junction field-effect transistor (JFET) and a metal oxide/semiconductor field-effect transistor (MOSFET) superimposed in a single silicon island and can therefore be regarded as two transistors sharing the same body. A G(sup 4)FET can also be regarded as a single device having four gates: two side junction-based gates, a top MOS gate, and a back gate activated by biasing of a silicon-on-insulator substrate. Each of these gates can be used to control the conduction characteristics of the transistor; this possibility creates new options for designing analog, radio-frequency, mixed-signal, and digital circuitry. One such option is to design a G(sup 4)FET to function as a three-input NOT-majority gate, which has been shown to be a universal and programmable logic gate. Optimal NOT-majority-gate, G(sup 4)FET-based logic-circuit designs were obtained in a comparative study that also included formulation of functionally equivalent logic circuits based on NOR and NAND gates implemented by use of conventional transistors. In the study, the problem of finding the optimal design for each logic function and each transistor type was solved as an integer-programming optimization problem. Considering all 81 non-equivalent Boolean functions included in the study, it was found that in 63% of the cases, fewer logic gates (and, hence, fewer transistors) would be needed in the G(sup 4)FET-based implementations.

Vatan, Farrokh↗

NASA NTRS2002

SMEX-Lite Modular Solar Array Architecture

For the most part, Goddard solar arrays have been custom designs that are unique to each mission. The solar panel design has been frozen prior to issuing an RFP for their procurement. There has typically been 6-9 months between RFP release and contract award, followed by an additional 24 months for performance of the contract. For Small Explorer (SMEX) missions, with three years between mission definition and launch, this has been a significant problem. The SMEX solar panels have been sufficiently small that the contract performance period has been reduced to 12-15 months. The bulk of this time is used up in the final design definition and fabrication of flight solar cell assemblies. Even so, it has been virtually impossible to have the spacecraft design at a level of maturity sufficient to freeze the solar panel geometry and release the RFP in time to avoid schedule problems with integrating the solar panels to the spacecraft. With that in mind, the SMEX-Lite project team developed a modular architecture for the assembly of solar arrays to greatly reduce the cost and schedule associated with the development of a mission- specific solar array. In the modular architecture, solar cells are fabricated onto small substrate panels. This modular panel (approximately 8.5" x 17" in this case) becomes the building block for constructing solar arrays for multiple missions with varying power requirements and geometrical arrangements. The mechanical framework that holds these modules together as a solar array is the only mission-unique design, changing in size and shape as required for each mission. There are several advantages to this approach. First, the typical solar array development cycle requires a mission unique design, procurement, and qualification including a custom qualification panel. With the modular architecture, a single qualification of the SMEX-Lite modules and the associated mechanical framework in a typical configuration provided a qualification by similarity to multiple missions. It then becomes possible to procure solar array modules in advance of mission definition and respond quickly and inexpensively to a selected mission's unique requirements. The solar array modular architecture allows the procurement of solar array modules before the array geometry has been frozen. This reduces the effect of procurement lead-time on the mission integration and test flow by as much as 50%. Second, by spreading the non-recurring costs over multiple missions, the cost per unit area is also reduced. In the case of the SMEX-Lite procurement, this reduction was by about one third of the cost per unit area compared to previous SMEX mission-unique procurements. Third, the modular architecture greatly facilitates the infusion of new solar cell technologies into flight programs as these technologies become available. New solar cell technologies need only be fabricated onto a standard-sized module to be incorporated into the next available mission. The modular solar array can be flown in a mixed configuration with some new and some standard cell technologies. Since each module has its own wiring terminals, the array can be arranged as desired electrically with little impact to cost and schedule. The solar array modular architecture does impose some additional constraints on systems and subsystem engineers. First, they must work with discrete solar array modules rather than size the array to fit exactly within an available envelope. The array area is constrained to an integer multiple of the module area. Second, the modular design is optimized for space radiation and thermal environments not greatly different from a typical SMEX LEO environment. For example, a mission with a highly elliptical orbit (e.g., Polar, SMEX/FAST) would require thicker coverglasses to protect the solar cells from the more intense radiation environment.

Lyons, John↗