Travel Planning system that relaxes constraints to produce answers involving multiple sales channels/PNRs/tickets per answer

• US 20080140462A1
• Filed: 12/07/2006
• Published: 06/12/2008
• Est. Priority Date: 12/07/2006
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: de Marcken, Carl G.
• Application Number:
  US11/635,395
• Publication Number:
  US 20080140462A1
• Time in Patent Office: Days
• US Class Current: 705/6
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

Techniques for producing a travel solution comprised of multiple travel units are disclosed. The techniques include sending a travel planning query having a partition specification to a travel planning system. The travel planning system processes the travel query to produce solutions based on partitions. Possible partitions can include passenger name records (PNRs), tickets or sales channels for the returned solutions. Processing can involve relaxing constraints, rules or regulations on solutions and re-pricing solutions, as multiple tickets, by partitioning the solutions by a partition. Tickets can be produced for different portions of the multiple travel units from the travel solution using different selling methods or points of sale channels.

Claims

1. A method for producing a travel solution comprised of multiple travel units, the method comprising:

sending a travel planning query to a travel planning system, the travel query including a specification of whether or not to expand a search space to include multiple passenger name records, or tickets or sales channels;

relaxing constraints, rules or regulations on solutions, if the solutions are priced or sold as multiple tickets; and

processing the travel query under the relaxed constraints, rules or regulations, to produce solutions, with the solutions including a specification of possible partitions of the solutions; and

pricing the solutions based on the relaxed constraints, rules or regulations.

2. The method of claim 1 further comprising:

determining if the solutions contain one-ticket constraint violations.

3. The method of claim 3 wherein if the solutions contain one-ticket constraint violations,

repeating pricing of the solutions on a portion of the solutions to validate the multiple-ticket validity of the solutions.

4. The method of claim 3 wherein if the solutions do contain one-ticket constraint violations,

selling the solutions as a single ticket, or re-priced as a single ticket with the constraints included in the ticket for additional assurance of its validity.

5. The method of claim 3 further comprising:

splitting the journey according to the lowest-priced solution.

6. The method of claim 5, if the solutions include constraint violations:

splitting the solutions according to at least one of

placing two fares that are incompatible on different tickets,

placing two carriers that are incompatible on different tickets or

placing multiple passengers that use different booking codes on different tickets.

7. The method of claim 5 wherein splitting further comprises:

representing entities that comprise a solution as vertices in a graph structure;

determining if edges exist between any two vertices, indicating that those two vertices are incompatible in a ticket or PNR.

8. The method of claim 7 wherein splitting further comprises:

collapsing vertices that need to appear together on a ticket by replacing the vertices with a single vertex that has all edges going to it that go to any of the vertices that were collapsed.

9. The method of claim 7 wherein splitting further comprises:

executing a minimal graph coloring algorithm over the graph such that entities that are assigned the same color are placed on the same ticket for re-pricing.

10. The method of claim 7 wherein entities include flights and fares.

11. A computer program product residing on a computer readable medium for producing a travel solution comprised of multiple travel units, the computer program product comprising instructions for causing a computer to:

send a travel planning query to a travel planning system, the travel query including a specification of whether or not to expand a search space to include multiple passenger name records, or tickets or sales channels;

relax constraints, rules or regulations on solutions, if the solutions are priced or sold as multiple tickets; and

process the travel query under the relaxed constraints, rules or regulations, to produce solutions, with the solutions including a specification of possible partitions of the solutions; and

price the solutions based on the relaxed constraints, rules or regulations.

12. The computer program product of claim 11 further comprising instructions to:

determine if the solutions contain one-ticket constraint violations.

13. The computer program product of claim 12 wherein if the solutions contain one-ticket constraint violations, the instructions:

repeat pricing of the solutions on a portion of the solutions to validate the multiple-ticket validity of the solutions.

14. The computer program product of claim 13 wherein if the solutions do contain one-ticket constraint violations, the instructions:

issue the solutions as a single ticket, or re-priced as a single ticket with the constraints included in the ticket for additional assurance of its validity.

15. The computer program product of claim 13 further comprising instructions to:

split the journey according to the lowest-priced solution.

16. The computer program product of claim 15, if the solutions include constraint violations, the instructions:

split the solutions according to at least one of

place two fares that are incompatible on different tickets,

place two carriers that are incompatible on different tickets or

place multiple passengers that use different booking codes on different tickets.

17. The computer program product of claim 15 wherein instructions that split further comprises instructions to:

represent entities that comprise a solution as vertices in a graph structure.

determine if edges exist between any two vertices, indicating that those two vertices are incompatible in a ticket or PNR.

18. The computer program product of claim 17 wherein instructions to split further comprises instructions to:

collapse vertices that need to appear together on a ticket by replacing the vertices with a single vertex that has all edges going to it that go to any of the vertices that were collapsed.

19. The computer program product of claim 17 wherein instructions to split further comprises instructions to:

apply a minimal graph coloring algorithm over the graph such that entities that are assigned the same color are placed on the same ticket for re-pricing.

20. The computer program product of claim 17 wherein entities include flights and fares.