Using software agents to schedule airline flights

• US 20050246208A1
• Filed: 04/30/2004
• Published: 11/03/2005
• Est. Priority Date: 04/30/2004
• Status: Active Grant

• Current Assignee: Ent Services Development Corporation LP (DXC Technology Company)
• Original Assignee: EDS South Africa (Pty) Ltd. (Perspecta, Inc.)
• Inventors: Langerman, Josef J.
• Granted Patent: US 7,957,987 B2
• Time in Patent Office: Days
• US Class Current: 705/5
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation

Abstract

Airline scheduling may be performed using software agents that participate in a mediated auction. To schedule flights, agents are used to represent airports and aircraft in the process of scheduling aircraft to service flights between airports. Airport agents represent airports that have made requests for flights. Aircraft agents represent aircraft that may be scheduled to service a flight from one airport to another airport. An aircraft agent submits a bid to service a flight. Bids received from multiple aircraft agents for a flight are evaluated and aircraft are selected based on the demand of passengers for the flight, the cost of the aircraft corresponding to the bidding aircraft agents to perform the flight, and the minimization of aircraft costs across all flights being scheduled. A resource manager agent helps to ensure that an aircraft agent does not bid for a flight when the aircraft represented by the aircraft agent is in need of maintenance or is unprofitable.

Claims

1. A computer system for scheduling airline flights, the system comprising a processor connected to one or more input/output devices and a storage device storing flight information having airport software agents, aircraft software agents, and an allocation manager software agent, wherein:

the allocation manager software agent assigns aircraft software agents to flights from airports represented by airport software agents using an assignment methodology that attempts to minimize cost of a particular flight and minimize cost across all of the flights;

each airport software agent represents an airport in a geographic location, is identified by an airport identifier, has flight information for flights identified as departing from the airport represented by the airport software agent, the flight information including a flight identifier, an indication of a destination airport, an indication of a departure time, and a number of passengers for the flight, and is operable to communicate flight information to the allocation manager software agent for flights that are not assigned an aircraft software agent and need to be scheduled;

each aircraft software agent represents an aircraft, is identified by an aircraft identifier, includes a passenger capacity, an overhead cost for each flight regardless of number of passengers on a flight flown by the aircraft, and a passenger cost for each passenger on a flight flown by the aircraft, is operable to receive flight information from the allocation manager software agent of flights that the allocation manager software agent is scheduling, and is operable to submit a bid to the allocation manager software agent to service one of the flights that the allocation manager software agent is scheduling; and

the processor is configured to execute computer-readable instructions associated with each airport software agent, each aircraft software agent, and the allocation manager.

2. The computer system of claim 1 wherein assigning an aircraft software agent to a flight further comprises:

having the allocation manager software agent determine a cost for a flight performed by each aircraft submitting a bid and tentatively assign the lowest cost aircraft to the flight; and

when all flights have been tentatively scheduled, having the allocation manager compare overall cost of all of the flights with a predetermined cost parameter, and schedule the aircraft based on the tentative assignment.

3. The computer system of claim 2 wherein the predetermined cost parameter comprises an optimal cost of servicing all of the flights that is determined by running an optimization process across all of the tentatively scheduled flights.

4. The computer system of claim 3 wherein the optimization process comprises a genetic algorithm.

5. The computer system of claim 1 wherein the flight information comprises a resource manager software agent that is associated with the aircraft software agents, manages the aircraft software agents by enabling and disabling aircraft software agents based on the perceived need of the aircraft represented by the aircraft software agents to fly flights from the airports represented by the airport software agents, and monitors maintenance requirements of the aircraft represented by the aircraft software agents by preventing aircraft software agents that represent aircraft that need maintenance from submitting bids to service the flights.

6. The computer system of claim 1 wherein the flight information comprises an operations manager software agent that reassigns an aircraft software agent to a flight in response to disruptions in the ability of aircraft represented by an aircraft agent to which the flight is assigned originally to service the flight.

7. The computer system of claim 1 wherein each airport software agent represents a simulated airport.

8. The computer system of claim 1 wherein each airport software agent represents an actual airport.

9. The computer system of claim 1 wherein each aircraft software agent represents a simulated aircraft.

10. The computer system of claim 1 wherein each aircraft software agent represents an actual aircraft.

11. The computer system of claim 1 wherein the computer system is used to model scheduling flights to be flown by simulated aircraft represented by the aircraft software agent between simulated airports represented by the airport software agents.

12. The computer system of claim 1 wherein the computer system is used to schedule flights to be flown by actual aircraft represented by the aircraft software agents between actual airports represented by the airport software agents.

13. A method for scheduling flights from between multiple airports to move passengers between the airports, the method comprising:

receiving an indication of flights to depart from an airport, each flight indication including an indication of a number of passengers traveling on each of the flights, an indication of a time at which each of the flights departs, and an indication of a destination for each of the flights;

providing the indication of the flights to aircraft that may service the flights, each aircraft represented by a passenger capacity, an overhead cost for each flight regardless of number of passengers on a flight flown by the aircraft, and a passenger cost for each passenger on a flight flown by the aircraft;

receiving bids from each of the aircraft to service each of the flights, each bid from an aircraft to service a flight representing the cost for the aircraft to service the flight.;

assigning each of the flights to one of the aircraft based on locations of the aircraft, bids received for the flights, and cost of the overall assignment of flights to aircraft.

14. The method of claim 13 wherein the method is performed to model creation of a flight schedule.

15. The method of claim 13 wherein the method is performed to schedule actual flights to be flown.

16. The method of claim 13 further comprising determining if an aircraft from which a bid is received is available to service the flights.

17. The method of claim 16 wherein determining if an aircraft from which a bid is received is available to service the flights comprises determining if the aircraft is in need of maintenance.

18. The method of claim 16 wherein determining if an aircraft from which a bid is received is available to service the flights comprises determining if the aircraft has flown for a maximum allowable number of hours since previous maintenance.

19. The method of claim 13 further comprising reassigning the flight to another aircraft in response to a disruption to the availability of the aircraft to which the flight is assigned originally.

20. The method of claim 13 wherein receiving a bid to service the flight from each of the aircraft comprises receiving from each aircraft an indication of an amount of money to be paid to the aircraft if the aircraft services the flight.

21. The method of claim 20 wherein assigning each of the flights to one of the aircraft based on the overall assignment of flights to aircraft comprises assigning aircraft to the flights such that the amount of money to be paid to the aircraft is minimized.

22. The method of claim 20 wherein receiving from each aircraft an indication of an amount of money to be paid to the aircraft if the aircraft services the flight receiving from each aircraft an indication of an overhead charge and a per passenger charge to be paid to the aircraft if the aircraft services the flight.

23. The method of claim 13 wherein assigning each of the flights to one of the aircraft based on the overall assignment of flights to aircraft comprises assigning each of the flights to the aircraft with a minimum amount of unused capacity on the flight.

24. The method of claim 13 wherein assigning each of the flights to one of the aircraft based on the overall assignment of flights to aircraft comprises assigning each of the flights to an aircraft based on the effect of the assignment to other assignments of aircraft to flights.

25. The method of claim 13 further comprising specifying the aircraft that may service the flights through addition and deletion of aircraft from a set of aircraft that are available to service the flights.

26. An apparatus comprising a computer readable medium having instructions stored thereon that when executed by a machine result in at least the following:

receiving an indication of flights to depart from an airport;

providing the indication of the flights to aircraft that may service the flight;

receiving bids to service each of the flights from each of the aircraft;

assigning each of the flights to one of the aircraft based on the overall assignment of flights to aircraft.

27. The apparatus of claim 26 further comprising determining if an aircraft from which a bid is received is available to service the flights.

28. The apparatus of claim 27 wherein determining if an aircraft from which a bid is received is available to service the flights comprises determining if the aircraft has flown for a maximum allowable number of hours since previous maintenance.

29. The apparatus of claim 26 further comprising reassigning the flight to another aircraft in response to a disruption to the availability of the aircraft to which the flight is assigned originally.

30. The apparatus of claim 27 wherein assigning each of the flights to one of the aircraft based on the overall assignment of flights to aircraft comprises assigning each of the flights to an aircraft based on the effect of the assignment to other assignments of aircraft to flights.