Data processing: vehicles – navigation – and relative location – Navigation – Determination of travel data based on the start point and...
Reexamination Certificate
2001-04-11
2002-05-28
Nguyen, Tan (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Determination of travel data based on the start point and...
C701S301000, C340S970000, C342S120000
Reexamination Certificate
active
06397142
ABSTRACT:
FIELD OF THE INVENTION
A method and system for using tertiary operations in repairing Grounded Aircraft Routes, and more particularly a method and system for swapping flight sequences among a Grounded Aircraft Route, and two Available Aircraft Routes to cure the irregularities in the Grounded Aircraft Route in real time while maintaining time and space feasibility in both the Available Aircraft Routes and the Grounded Aircraft Route.
U.S. patent application Ser. No. 09/364,157 filed on Jul. 30, 1999, and assigned to the assignee of the present invention.
BACKGROUND OF THE INVENTION
U.S. patent application Ser. No. 09/364,157, which is assigned to the assignee of the present application, discloses a real time aircraft optimization engine that uses Unary, Binary, and Three-Way Operations for repairing a Grounded Aircraft Route, a route of an aircraft which has been grounded for a specific period of time. The Unary Operations cancel and uncancel or do nothing to the Grounded Aircraft Routes. The Binary Operations repair a Grounded Aircraft Route through actions performed with one Available Aircraft Route, a route of an aircraft which is available for use in a solution of a flight schedule irregularity. Tertiary Operations are used to repair a Grounded Aircraft Route through actions with two Available Aircraft Routes. The system in which the aircraft optimization engine of the above patent application operates is illustrated in FIG.
1
.
Referring to
FIG. 1
, a functional block diagram of the environment in which the invention operates is shown, where a user interface referred to as an Optimization Server
1
is in electrical communication with a user by way of a bidirectional communication path
2
, and receives a request for optimal solutions to a specific flight schedule disruption. In response to the request, the Optimization Server
1
initializes an Aircraft Optimization Engine
3
by way of a bi-directional communication path
4
, and provides the Aircraft Optimization Engine
3
an Aircraft Problem Specification. The Aircraft Optimization Engine
3
processes the Aircraft Problem Specification and generates a set of optimal solutions including aircraft reassignments and flight modifications to overcome the disruption. The solutions are transmitted over communication path
4
, and through the Optimization Server
1
and bi-directional path
2
to the user.
The Aircraft Optimization Engine
3
further initializes a Crew Optimization Engine
5
by way of a bi-directional communication path
6
to determine whether the optimal flight solutions are efficiently supported by flight and service crews.
During operation, the Aircraft Optimization Engine
3
and the Crew Optimization Engine
5
communicate by way of bi-directional communication paths
10
and
11
, respectively, with a memory system such as a disk storage unit
9
having stored therein memory objects containing all of the data used by the engines to solve problems. For example, the memory objects include instances of Station, Market, Aircraft, Fleet, Subfleet, Maintenance, and Flight classes, and are created and updated by the Data Collection Unit
12
and the Data Update Unit
13
, respectively.
The Data Collection Unit
12
receives complete information for stations, markets, aircraft, fleets, subfleets, maintenance, and flights from the user by way of bi-directional communication path
14
. Thereafter, the Data Collection Unit
12
creates memory objects which are supplied by way of a bi-directional communication path
15
for storage in the disk storage unit
9
, and at memory locations specified by a Memory Mapping Unit
16
along a bi-directional communication path
17
. Further, the Data Update Unit
13
receives revisions to the memory objects from the user over a bi-directional communication path
18
, and supplies corrections through a bi-directional communication path
19
to the objects identified by the Memory Mapping Unit
16
.
The Memory Mapping Unit
16
receives control signals from the user over a bi-directional communication path
20
, and in response thereto identifies the addresses of the memory objects in the disk storage unit
9
which are being operated upon. By means of the Memory Mapping Unit
16
and the Data Update Unit
13
, the user is able to keep the data stored in the Disk Storage Unit
9
current with the data being supplied to the user by way of communication path
2
.
At any given time, the memory objects of the Disk Storage Unit
9
reflect the existing flight environment, including identifications of protected flights which are not to be canceled or delayed; flight sequences or routes for each aircraft; the stations or airports to be used by the aircraft; the fleets and subfleets assigned to each station; station closure times; fleet arrival and departure curfews; inviolable and violable maintenance schedules; aircraft seat capacities; fleet operational ground times; operations costs; flight disruption costs; subfleet disruption costs; and revenue and passenger information for each scheduled flight.
The Aircraft Problem Specification received by the Aircraft Optimization Engine
3
upon being initialized by a request from the user, further includes the identification of grounded aircraft; the stations where aircraft groundings have occurred; the start and end times of each of such groundings; the identification of available aircraft; the identification of protected flights; recovery period start and end times; maximum allowable flight delays; and flight cancellation and ferry creation restraints.
Based upon the above information a solution comprised of flight delays and cancellations, Ferry Flight creations, as well as aircraft reassignments is produced.
In the prior art invention disclosed in the above patent application, a solution is sought by first executing Unary Operations, then Binary Operations, and lastly Three-Way Operations until all Available Aircraft Routes have been processed to achieve solutions for all Grounded Aircraft Routes. See
FIG. 3
of the above patent application. More particularly, Available Aircraft Routes are chosen two at a time, and a local neighborhood search is performed (i.e., the above set of operations are performed on the Grounded Aircraft Route to identify time and space feasible solutions), and thereafter two additional Available Aircraft Routes are chosen and the process repeated.
One Binary Operation that is disclosed is a Swap Operation in which flight sequences of one route are replaced with flight sequences of another route. A Three-Way Swap also is disclosed which is comprised of removing a first sequence of flights from a Grounded Aircraft Route, removing a second sequence of flights from a first Available Aircraft Route, removing a third sequence of flights from a second Available Aircraft Route, replacing the first sequence with the second sequence of flights, replacing the second sequence with the third sequence of flights, and replacing the third sequence with the first sequence of flights.
The above Three-Way Swap Operation requires three entities to be considered through a brute force method which is time consuming because three flights are considered at a same time, which is not tolerable in an environment demanding real time solutions such as occurs in aircraft flight schedules. In order to alleviate this problem, a solution is sought which would reduce problem complexity to a consideration of only two aircraft at a time by taking advantage of conditions found while performing Binary Operations that could be used in Tertiary Operations including Three-Way Swap Operations in accordance with the present invention. That is certain states found while performing Binary Operations are later used in Tertiary Operations in real time.
SUMMARY OF THE INVENTION
The definitions set forth in the Description of Preferred Embodiments and U.S. patent application Ser. No. 09/364,157 apply to this summary.
An improved method for conducting local neighborhood searches among three or more aircraft routes to cure any irregularity in a Grounded Ai
CALEB Technologies Corp.
Lester Gerald E.
Nguyen Tan
Tran Dalena
LandOfFree
Tertiary operation for repairing irregularities does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Tertiary operation for repairing irregularities, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tertiary operation for repairing irregularities will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2860642