FIELD OF THE INVENTION This invention relates in general to a system and method for determining transit routes between an origin and a destination. It is particularly, but not exclusively, concerned with determining the most appropriate travel options between any two given airports.

BACKGROUND OF THE INVENTION

In the past, reservations systems have allowed airlines the ability to explicitly define routes between two given airports. Each hop in the routing must be defined stating the airlines and/or flight numbers to include. This process is similar in effect to drawing the route map by hand one arc at a time.

However, unlike an airline's route maps in a flight magazine, there is no compound view. Airline users must define a route map between each and every airport pair. As the number of airport pairs increase so does the definition work. Consider an airline servicing 20 airports. This might be covered through 400 sets of rules. An airline servicing 100 airports might need 10,000 rules. This is even more challenging when interline flights are also considered. Consequently, a small carrier may need to manage 50,000 rules.

In this way, prior reservations systems work on an origin/destination basis. Each origin to each destination must have one or more rules in order for the reservations system to display a routing. Each rule defines what is permitted for every segment within the routing.

SUMMARY OF THE INVENTION

The invention is defined in the appended claims to which reference should now be made. In one aspect of the present invention a system for determining a route between an origin and destination in a carrier network having a plurality of nodes is provided. The system comprises receiving means for receiving a request to build a route between the origin and destination, wherein the request comprises data defining the origin and destination; a processing means configured to determine one or more routes between the origin and destination via one or more of the nodes; to determine one or more route rules; and to select one or more of the routes based on the determined route rules. Embodiments of the invention aim to address the above problems by generating different routes in a network. Further, embodiments of the invention may also make connections between flight segments and map flight segments onto the determined routes in the network. This may be performed in response to receiving an availably request or other message requesting specific flight connections for a journey between the origin and destination.

Furthermore, embodiments of the invention aim to avoid building rules on an

origin/destination basis. In some examples, an airline may configure embodiments of the invention to override default behaviour.

Embodiments of the invention provide a system which generates routing information between all city pairs within the airline's network. The routings are generated using system wide and subscriber specific default rules, and subscriber specific exception rules should the airline want to override the default behaviour.

In some aspects a Subscriber Specific City Pair Exception Rule may be applied at the time of routing generation. The system allows a subscriber to maintain unique city pair exception rules. These rules provide the subscriber the capability to influence and produce their desired routings.

Subscriber Specific City Pair Exception Rules may be enforced at the time of routing generation. Whenever a request for flight availability comprises an input city pair which matches a city pair with an exception rule, the routings generated for the city pair are influenced by these exception rules. Embodiments of the invention may comprise a configurable distance rule or/and a list of hubs for a given airline and allow backhaul connections via this hub.

As a single airline or airline alliance cannot satisfy all travel requirements, embodiments of the invention use the same route building capability to extend the reach of the airline's network, on demand, by examining industry flight schedules for alternate airlines that enter or exit the airline's network.

Embodiments of the invention address both automatic discovery of routings and specific flight connections that meet an individual travel requirement. For example, an airline may operate between two airports only at given times of the year or on given days of the week. Thus, when building the route map, it is possible to optionally create variations based on travel date. Once the map has been constructed, embodiments of the invention may perform a second process to identify specific flights that operate at an appropriate time to satisfy a specific travel request.

In some embodiments of the invention, the system/method may only count legs, rather than both leg and segments when applying limits within routes. However, once the routes have been generated, and embodiments of the invention may perform connection building. In this case, both leg and segment are needed as a particular hop may be satisfied at different times by direct non-stop and direct stopping flights. Usually, when performing route generation embodiments of the invention defer to the lower number of stops.

However, when determining whether flight connections are available to meet a specific availability request, embodiments of the invention return available connections only if flights can be found that meet specific rules. Further, embodiments of the invention may use a number of leg count to sort travel options. For example, it may be useful to show direct non stop prior to direct stopping services. Thus, embodiments of the invention may differentiate between a connection which refers to transit between different flights on a given date, and a transfer between two hops on a route.

BRIEF DESCRIPTION OF THE DRAWINGS

An embodiment of the invention will now be described, by way of example only, and with reference to the accompanying drawings, in which:

Figure 1 is a schematic showing an airline route map network as a weighted graph; Figure 2 is a schematic showing a number of different rules used by embodiments of the invention;

Figure 3 is a schematic diagram showing how embodiments of the invention may be used for interline extensions;

Figure 4 is a schematic diagram showing a number of functional components which may be used by embodiments of the invention;

Figure 5 is a flow diagram showing the main steps performed by an embodiment of the invention for applying route related routes for online routes;

Figure 6 is a flow diagram showing the main steps performed by an embodiment of the invention for applying rules for interline connections;

Figure 7 is a schematic diagram showing a network as well as a flow diagram showing the main steps performed when determining availability according to an embodiment of the invention; and _Λ

4

Figure 8 is a schematic diagram showing a further network as well as a further flow diagram showing the main steps performed when determining availability according to an embodiment of the invention. DETAILED DESCRIPTION

The following description is of a system and method for use in the aviation industry, but this is exemplary and other applications of the invention will also be discussed. For example, the system may be used in any environment a user wishes to build transit routes from an origin to a destination using one or more transit providers. For example, embodiments of the invention may find application in the travel and transport industry in general, in particular in the rail and road transport industries.

Usually, it is necessary to differentiate between aircraft movement and passenger movement as passenger movements may be restricted by air traffic freedom rights. The term hop, also referred to as a flight leg, or leg refers to the aircraft movement and specifically, a take off to a subsequent landing. The term flight segment or segment refers to passenger movement, specifically where a passenger embarks on travel on a given flight and the point they disembark travel on the flight. A flight segment may comprise one or more flight legs. For example, it is possible to travel on a single service (flight number) from London to Sydney stopping at Singapore to change aircraft.

A route defines the path between an origin and a destination airport. A direct route is satisfied by a single flight segment from origin to destination. A connecting route requires a transfer or a connection between two different flight numbers. If the connection occurs between the flights marketed by the same airline, then it is referred to as an online connection. If the connection occurs between flights marketed by different airlines, then the connection is referred to as an interline connection. For example, an airline may sell interline connections when they are unable to provide a service from the requested origin to destination. Embodiments of the invention address discovery of a network of flight segments but takes in to account a cost for each flight leg traversed when determining the best paths.

Figure 1 of the accompanying drawings is a schematic diagram of an airline flight network. In figure 1 , any one of the circles labelled A, B, C, D, E, F, or Z may be the origin or destination, or nodes through which a route passes from an origin to a destination. ,_

5

As shown in figure 1 , a number of different routes from origin Z to destination D may be determined. For example:

Route 1 = Z - F - D

Route 2 = Z - A - E - F - D

Route 3 = z - A - E - C - D

Route 4 = z - A - B - C - D

Route 5 = z - A - B - c - E - F- D and so on. Other routes such as A - E - C - D or A - Z - F - D will be discussed in further detail below.

Each hop or leg is characterized by the origin, destination, distance between the origin and destination and optionally one or more preferred or excluded airlines, in particular an airline subscriber. The distance may be approximated by using a great-circle distance algorithm which is calculated from the longitude and latitude of the airports or stations, as described in further detail below.

Each hop may be satisfied by one or more flight segments each of which is characterised by its flight number, airline code, aircraft type, service type, traffic restriction departure and arrival terminal and other applicable criteria as will be known to the person skilled in the art. Thus, the minimum connection time is not a characteristic of one flight because a connection relates to two flights. Each potential flight connection is subject to connection time and traffic restrictions. Traffic restrictions prohibit passenger movements to meet legal requirements for example to restrict a multi-leg international flight from competing in a foreign local market. Both minimum and maximum connection times may apply. The minimum connection time is defined as the shortest time interval required in order to transfer a passenger and his luggage (or alternatively cargo in the context of a cargo shipment) from one flight to a connecting flight, in a specific location or metropolitan area.

The system embodying the invention enables various routes between a point of origin and a destination point to be determined. It may also enable filtering of the resulting list of routes by certain specified criteria. The following description will initially focus on route building and will subsequently describe the process of mapping connections to routes which may be based on an availability request. „

6

In order to build one or more routes, it is first necessary to be aware of the various connecting points or nodes that link the points of origin and destination to other interim destinations. This has previously been achieved by a user manually building the network by defining one or more connection rules that indicate the path between all given points, taking into account any restrictions that might exist on any given segment between a pair of points.

In contrast, embodiments of the invention operate to automatically discover the network of connections or links between each and every airport that an airline services as determined by a database of the airlines flight schedules and airports. Thus, embodiments of the invention build or discover a network, such as that shown in figure 1 , by connecting or linking each and every airport shown in the network. In the context of the aviation industry the database of the network points includes both airport and significant rail or shipping station codes, related cities (metropolitan areas) and countries together with the location in longitude and latitude. Similarly, the flight segments may be obtained from flight schedules managed by the system, received in messages from airlines, or from information consolidators using forms of flight schedule communication defined by the Standard Schedules Information Manual (SSIM), which is maintained by the International Air Transport Association (IATA). Usually, the data is in a text format such as ASCII. The data may be stored in a file such as a text type file and transmitted using standard protocols such as File Transfer Protocol, FTP, although other protocols may be used.

The transit providers included in the route build may optionally represent a subset of all of the possible transit providers, for example, a flight network may include only a single airline or alternatively a given association of airlines. Such a flight network will be referred to herein as an 'online' flight network. Conversely, one or more segments from non- associated airlines that are not connected with the given airline or association of airlines, may be included as 'interline extensions' to a route. Figure 1 is a schematic representation of such a flight network where the connection between Z and A is an interline connection.

As the flight network (or other transit network) is built, the distance between each respective pair of points in the network is determined. This may performed by calculating the great circle distance, i.e. the arc with the shortest distance between two points on the surface of a sphere (the Earth) as measured using a geodesic along the surface of the sphere rather than a straight line through the interior of the sphere. Other schemes for determining the distance between points in the network may be used, for example using a database of ticket point mileage as used in fare calculations.

In the example network shown in figure 1 the arc length between points Z and F in the carrier network has been determined as 4, while the arc length between point Z and A has been determined as 1. Similarly, the arc length between points A and E is determined as 3, the arc length between points A and B is determined as 2, the arc length between points E and F is determined as 6, the arc length between E and C is determined as 5, the arc length between B and C is determined as 4, the arc length between points F and D is determined as 1 , and the arc length between points C and D is determined as 1 . Thus, the arc lengths may be determined based on the distance between respective points as shown in figure 1 . Clearly, it is not necessary to assign a measurement unit, such as mile or kilometre to the arc lengths since the distances or arc lengths are relative to one another. Further, the distances between any of the points may be determined based positional information associated with each point. Alternatively, the distances between points may be performed by querying a look-up table of distances associated with pairs of points.

To reduce the overall number of routings to those that provide the optimal chance of good connections, routings within the network may be weighted by the number of unique flights that operate over each of the arcs that make up the online flight network.

The potential online flight links or connections can then be determined by using a modification of Dijkstra's algorithm to determine the "k" shortest paths through the online flight network for all possible points (city-pairs). The algorithm will now be described with reference to Figure 1 , which shows an online flight network (carrier network 10) of points A, B, C, D, E and F.

In this example, point A will be taken to be the point of origin for the host carrier and point D will be taken to be the destination. Flights within the carrier network 10 connect point A to points B and E and these flights are represented by the lines connecting the respective points and the calculated great-circle distance associated with these connections is indicated adjacent each line. Using the algorithm, the connections from point A to points B and E will be considered and points B and E will be updated with the sum of the distance to reach that point, i.e. B=2, and E=3.

The shortest path determined so far is A-B having a distance of 2. Accordingly, the algorithm considers the connections from B. The only connection is to C and so C is updated with the cumulative distance, i.e. C=6 (since the distance from A-B is 2 and the .

o

distance from B-C is 4). Now the shortest path so far is from A-E and so the algorithm considers the onwards connections from E. The connection to F has a cumulative distance of 9 and so the algorithm updates the route with F=9. The connection to C, via E has a cumulative distance of 8. This is larger than the distance from A-B-C of 6 and so the algorithm does not update the distance to C via B and instead leaves it as C=6.

The shortest path, from A, determined now is to C via B, with possible onward connections to E and D. The distance of C-E is 5 which would result in a total distance of 1 1 . This is longer than the direct flight of A-E and so the distance for E remains at E=3 since the distance from C-D is 1 . The distance for D is set to D=7 via C and B. Finally, the algorithm considers the paths from F as D=9 is the next shortest route because the link to F via E has a cumulative distance of F=9. The distance of F-D is 1 and so the cumulative distance to D, via E and F is 10. This is larger than the value of 7 the algorithm previously calculated and so the distance for D remains at D=7. In this way, the algorithm determines the shortest distance from A to D as 7 with 3 stops being required (including the destination) and the route being determined as A-B-C-D.

If the route requested was in fact from Z to D then it would be necessary to extend the carrier network 10 with an interline flight from Z to one of the points within the carrier network 10. This can be considered to be a second application of Dijkstra's algorithm, but with the connection points defined by the pre-built carrier network 10 and the great-circle distance arc lengths already calculated for the carrier network 10 (host online flight network).

In the example network shown in Figure 1 , the process described above for the route from A to D can be carried out for routes from the other points of origin in the carrier network 10 to destination D or other destinations. The results may be cached in a memory and may identify the best routes determined for a given origin and destination. The results are shown in Table 1 :

Thus, in order to construct the network shown in Figure 1 , the route builder may pre-build one or more routes. The route builder may then cache, in a storage means or memory such as a Random Access Memory or hard drive, the various different paths shown in figure 1 for the host or alliance network. In other words, embodiments of the invention use an may use an algorithm which traverses a graph selecting arcs that move closer to the

destination, unless backhaul permitted at the next airport. The data shown in table 1 above may be stored in a memory or other storage means as an airline route network. The data may include data defining an origin, destination, minimum distance, and minimum number of stops. It may also include data defining the different nodes through which each route from an origin to a destination passes.

Subsequently, if an availability request cannot be met from this network, a repeat request is made to the route builder which asks for the carrier route network to be extended.

Alternatively, one or more routes may be dynamically built in response to receiving an availability request for available connections between an origin and destination. In this way, a dynamic routing and connections system may be provided.

The first route that is determined by the algorithm is usually the best. However, if that route is ignored, the algorithm may determine an alternative, for example, the next shortest route. Thus, the algorithm is efficient because it does not examine all paths, but rather a predetermined number of paths or k shortest paths.

Extensions are covered by interline restrictions in general but with an override at the interline connection airport. For example, it is possible to preclude a specific interline carrier in all cases, preclude certain transfers at a specific airport, or preclude a specific city pair

For example, going from A to D shown in figure 1 , if an airline does not allow backhaul or interline connections, then the best route is selected as A-B-C-D (at cost of 7) shown in table 1 . However if an airline does allow backhaul or inter-carrier connections then the best connection is selected as A-Z-F-D (at a lower cost of 6). As will be apparent from the following description referring to connection building, it is important to distinguish between a connection which relates to one or more flights and a route onto which specific connections are mapped. However, for the purposes of route building, the k shortest paths linking an origin and destination are evaluated.

The following description assumes that the system embodying the invention, which is schematically shown in figure 4 of the drawings, receives a request for routes from origin Z to destination D. In this, Z may be a location which is not serviced by the host carrier. Accordingly, the algorithm may consider the connections from Z, to points A and F. Z-A is the shortest connection (at a distance cost of 1 ) and the best route from A to D has been calculated above (at a distance cost of 7) and so the total distance from Z to D via A is 8 along the route Z-A-B-C-D. The next route from Z to be considered is Z-F at a distance cost of 4. The best route from F to D is the direct connection F-D at a cost of 1 . Thus, the total distance from Z to D via F is 5 along the route Z-F-D.

The shortest or best path from point A to D (via B and C) is shown in Figure 1 as dashed line 1 1 with the minimum great-circle distance displayed. The shortest or best path from F to D is represented in Figure 1 as a dashed line 13 with the minimum great-circle distance displayed. The second figure of 1 in the case of the best route F to D is the number of stops including the destination stop. The second figure of 3 in the case of the best route A- B-C-D - D is the number of stops including the destination stop.

In this manner, the algorithm may consider the carrier network 10 to be made up of a set of predetermined arcs, 1 1 , and 13 shown in figure 1 , and also highlighted in grey in Table 1 above. This simplifies the problem from building routes from anywhere to anywhere on any carrier over a large set of points (nodes) and arcs to one of building a route from, for example, an interline node to any node within the carrier network 10 in combination with the shortest route from the nodes within the carrier network 10 to the final destination.

In other words, embodiments of the invention determine the k shortest paths between a plurality of different origins and destinations. This has the advantage that it is not necessary to determine all of the possible paths between the origins and destinations.

For the host, the algorithm used by embodiments of the invention may loop through all different origins to all different destinations. For example, the algorithm may determine the k shortest paths from origin represented as AAA to destination represented as AAB. This 3- digit code, such as LHR, may represent an airport. The process may then be repeated from origin AAA to designation AAC and so on. This may be subject to one or more rules, described in further detail below.

Each city pair (market) build may be timed. The output of each build may take the form of a log in the form of a lists of comma separated value to facilitate further analysis. The log may comprise one or more of the following data: <market origin>, <market

destination>,<direct GCD>,<time to build city pair in ms>[, <path details>]. The <path details> field may comprise: [ <cumulative path length>[:<segment origin>- <segment destination>-<number flights>] ] For example, with each path highlighted the log may comprise the following data: KBV, EDI, 950, 20, 1150:KBV-LHR-5:LHR-EDI-3, 1300:KBV-FRA-4:FRA-EDI-5. This data defines the market origin as KBV, the destination market as EDI, the Greater Circle Distance is 950, the build time is 20ms, the cumulative path length for the first path is 1 150, the segment origin is KBV, the segment destination is LHR and the number of flights is 5. For the second segment of the first path, the segment origin is LHR, the segment destination is EDI and the number of flights is 3. For the second path, the cumulative path length is 1300, for the first segment of the second path, the segment origin is KBV, the segment destination is FRA and the number of flights is 4. For the second segment of the second path, the segment origin is FRA and the segment destination is EDI and the number of flights is 5. Thus, data defining each route may be defined. The data defining each route may comprise any one or more of distance data, data identifying each node, and data defining the number of nodes connecting the origin to destination, data identifying a number of stops associated with each route, data identifying the number of connections associated with each route and distance data associated with each route.

The one or more routings may be stored in the cache 414 shown in figure 5.

Further, embodiments of the invention usually build routes between metropolitan areas and not just airports by considering, for example, London to be a collection of airports.

The results of the route building process may include one or more of the following route types:

1 . Host direct flights;

2. Host connecting flights;

3. Interline direct flights on preferred flights;

4. Host flights connecting with interline flights on preferred interline flights;

5. Host flights connecting with interline flights on non-preferred interline flights;

6. Interline direct flights on non-preferred flights; and

7. Interline connecting flights on non-preferred flights.

This is described in further detail below with reference to the connection builder 404 and route builder 402 shown in figure 4 of the drawings. With reference to Figure 3, a further online network 22 is shown with online host flights between the points A, B, C, D, E, and H and an interline network 24 with points F and G representing points that can only be reached using interline segments. As previously described, the system may use the host network as a pre-built network; however, it will be necessary to consider extending this pre-built network using interline connections in order to plan a flight route from F to G. For example, supposing the system builds route A-E as previously described, but discards A-H (as this would represent a back-haul connection) and A-C-D-E (as this may violate the maximum number of connections or maximum flight time / distance), then this leaves only route A-B-E and the direct route A-E. The system may then determine that the possible routes from F to G are therefore only either F-A-B-E- G or F-A-E-G in view of the above rules.

Route related rules

As previously mentioned, route building may be subject to one or more rules, such as default rules. Usually, the route related rules are determined prior to building a route in order to limit the type of routes returned by the route builder.

These rules may be overridden for a given origin to destination, or at a specific airport. Some of the route related routes are shown in figure 2 of the drawings. For example, the maximum number of paths to generate for a single city pair may be set to 10. Further, the maximum permitted variance from the city pair mileage may be set at 150%. The maximum number of connections may also be set to 2, for example from AAA to BBB to CCC to DDD.

Usually, embodiments of the invention only determine a limited number of routes between the origin and destination. In the above example, only two routes or paths have been determined. The number of different routes determined may be limited or filtered based on a maximum number of paths for the origin and destination, the maximum variance from the city pair mileage, and the maximum number of connections between the origin and destination. A route may be However, in principle, any one of the following rules / exceptions, rules may apply to route building:

1 . Maximum number of connections allowed for entire routing; I

2. Maximum number of stops allowed for the entire routing

3. Maximum Greater Circle distance

4. Maximum overall path length (for example, not be greater than 200% of the great- circle distance between the origin and destination);

5. Maximum elapsed time;

6. Minimum or/and maximum connection times;

7. Service type exclusion for excluding flights with a given service types;

8. Airline code inclusions / exclusions to modify the flights included from a given airline when determining routings;

9. Metropolitan areas / cross city travel limitation to allow or deny connections into and out of different airports in a given city;

10. Back-haul permission to allow a connecting segment to increase the great-circle distance to the final destination;

1 1 . Country return exclusion (i.e. once a country has been left on a route, it cannot be re-entered)

12. Aircraft type inclusions / exclusions;

13. Maximum flight usage; and

14. Via city or airport inclusions / exclusions for connecting routes. Thus, one or more of the above rules may be applied to route building.

These rules may be categorised into default rules 12, city-pair specific rules 14, connecting airport specific rules 16, interline carrier specific rules 18 and manually added rules 20 as depicted in Figure 2. Each of the rules 12, 14, 16, 18, and 20 rules may be sub-categorised as route related rules and connection related rules. The connection related rules will be described in further detail with reference to the mapping of specific connections to routes.

The routing rules may be airline-specific. For example, if two airlines have similar flight schedules the system embodying the invention build a similar route network. A routing of F- E-C-D compared with F-D is unlikely to be better under any circumstances because it has more stops, more distance associated with it which results in higher costs to the airline which are passed onto the customer.

Usually, the rules are defined by alpha-numeric data such as ASCII data. Referring once again to figure 1 , if an airline allows only two flights and one connection by default, the system will not build any routes from A to D. Thus, one or more of the rules shown in figure 2 may be taken into account when the system embodying the invention builds the routes. Further, an airline may wish to override this behaviour at a specific point. For example, it „ _Λ

14

may be advantageous to prohibit connections between two airports in a city, and only permit this in exceptional circumstances.

With regard to the via city or airport inclusions / exclusions, the designation of a city code representing a city with multiple airports may correspond to the inclusion or exception of all of these airports. The via city or airport cannot however be the origin or final destination of a routing. In some embodiments, a list of hubs for a given airline may be added with backhaul connections being allowed via the airline hubs. Referring now to figure 4, a system diagram of an embodiment of the invention is shown. It is desirable that route generation be as fast as possible, accordingly the system may cache any necessary host flight data (described in further detail below with reference to connection building) before route generation is needed. This pre-built host network may include the application of any relevant rules / exceptions as set out above, referring particularly to figure 2 of the drawings.

As shown in figure 4, the system may comprise a route builder 402 or/and a connection builder 404. The system may also comprise an inventory enquirer 406. The Route Builder 402 may obtain information from a flight schedule cache 408, a connection rules cache 410 and a location information cache 412. The location in formation cache 412 may store data defining the location of each point, node or airport as previously described. The connection rule cache 410 may store the data defining the above mentioned rules.

Further, each of the functional components shown in figure 4 may be independently deployable and may be implemented with one or more Java virtual machine components. However, other programming languages will be known to the skilled person. For example, one or more of the functional components shown in figure 4 may be embodied in a server which may communicate with a network by means of an Application Programming

Interface, API, provided by a WiFi or wired communication network provider. The server 107 may use a particular provider's API to obtain data from external systems, as well as to send data to external systems, such as an airline's computer requesting a particular routing or connection or both.

In some implementations, embodiments of the invention may comprise a web browser which may include code embedded in an applet. The web browser may be

communicatively coupled to external systems such as airline computer servers storing different airline connections available for particular airlines, for example the schedule segment cache 408 described below. This may be performed by wired or wireless „ ,_

15

communication protocols which will be known to the skilled person, for example, using the html programming language and associated web-browsers.

At system start-up, the route builder 402 iterates through all airports operated by each airline subscriber building each host route network according to the route related rules or effecting routing rule set. This is usually done in response to the route builder receiving a request to build a subscriber or carrier network, using wired or wireless communication protocols. Further, as previously described, figure 2 shows how some rules may be used exclusively in route building. Other rules may be used in connection building and some rules such as the number of stops are used in both stages.

Figure 5 illustrates how the effective rule set is determined from the default rules and any overrides applicable to the city pair under construction. Thus, it will be appreciated that the flow diagram of figure 5 may be embodied in an algorithm for building routes such as online routes.

Both the route building or/ and connection rules may be cached in memory, 410. The rules that are in effect for a given city pair may be determined in the following manner. Consider for example three rules:

1 . A default rule (12)

2. A city pair rule for LHR-KUL (14); and

3. A connecting airport rule at FRA (16).

An airline operating LHR, LGW, FRA, KUL, CDG would be bound only using the default rules on LGW to KUL, by the default rules with conflicting attributes overlayed on LHR to KUL and for LGW to FRA transits via FRA the airport rule at FRA.

Route building

A method and system for building online routes, such as the host network comprising points A, B and C will now be described with reference to the system diagram of Figure 4, and the flow diagrams of figures 5 and 6. Usually, it is the route builder which performs the each step shown in the flow diagrams of figures 5 and 6. 1 b

Referring first to figure 5, the method is initiated when a request to build an online connection route between points A and C is received at step 501 . Usually the route builder 402 receives the request directly, as shown in figure 4. The request may be received using wired or wireless communications protocols which will be known to the skilled person, as previously described with reference to figure 4. The method then searches for any city-pair rules relating to points A and C at step 503 and the rule existence is determined at step 505. These rules have previously been described with reference to figures 2 and 4 of the drawings. If city-pair rules do exist for points A and C then these rules are applied for the origin and destination of the route at step 507. It is worth noting at this point that these city-pair rules are not applied for city-pairs other than the origin and destination, for example rules for the pairs A-B and B-C would not be applied in the host network 42. If city-pair rules do not exist for the pair A and C then the airport / city rules for all connection points, excluding the origin and destination, are applied at step 509. In host network this would only correspond to rules for a point B between points A and C. Once again, these rules 12, 14, 16, 18 have been described referring to figure 2 of the drawings.

After step 507 or step 509, depending on the determination made at step 505, the method progresses to step 51 1 wherein the default parameters are applied for any rules not covered by the city-pair rules or airport / city rules covered above. For example, any one or more of the rules shown in figure 2 of the drawings may be applied, in the event that they have not already been applied at step 507 or 509. Finally, at step 513 the A to C route is built as previously described with reference to figures 1 to 3 of the drawings and the host network and the rules applied in the preceding steps.

When the method is applied to generating routes from X to Y comprising a host network having points or nodes A, B, and C with point B between points A and C, with an interline extension from X to A and a further interline extension from C to Y then the method of Figure 6 is used.

Referring to Figure 6, the method is initiated when a request to build an interline connection route between points X and Y is received at step 601 . Usually, the request is received by the route builder 402. The method then searches for any city-pair rules relating to points X and Y at step 603 and the rule existence is determined at step 605.

If city-pair rules do exist for points X and Y then these rules are applied for the origin and destination of the route at step 607. As in the method for online routes, these city-pair rules are not applied for city-pairs other than the origin and destination. If city-pair rules do not exist for the pair X and Y then the airport / city rules for the entry points to the host network 58, are applied at step 609. In the example, this would only correspond to rules for points A and C. It is worth noting that airport / city rules for the connection points in the host network 58 will already have been applied when pre-building the host network 58.

After step 607 or step 609, depending on the determination made at step 605, the method progresses to step 61 1 wherein the default parameters are applied for any rules not covered by the city-pair rules or airport / city rules covered above. Finally, at step 613 the X to Y route is built using the second application of the modified Dijkstra's algorithm described above and the rules applied in the preceding steps for the host network 58 and interline extensions from X to A and from C to Y.

In summary, as previously described, the route builder 402 determines the k shortest routes between 2 points or airports preferably using one or more rules such as the maximum number of connections rule, maximum number of stops, greater circle limit rule, maximum number of different routes or paths rule, maximum distance over the direct routing and any hubs rule, and so on. Usually, routes are discarded by comparing the data defining each route to predetermined data defining the maximum number of connections data defining the maximum number of stops, data defining the greater circle limit, data defining the maximum number of different routes or paths, data defining the maximum distance over the direct routing and any hubs. Usually this data is numeric form and if one or more of the data defining the route has a value which is greater than one or more of the predetermined rule data, then that route is discarded. The retained routes which have been built may be stored in a storage means or cache.

The route builder 402 may also use the summary segment information, which may comprise any one or more of data defining Flight number, Period of operation, Flight segment origin and destination stations, Departure and arrival time, Departure and arrival terminal, and Number of legs. The summary segment information may be stored in a cache 408. This data may be compared to one or more of the predetermined rules shown in figure 2. Routes may be discarded from consideration based on a comparison of the

predetermined rules to one or more of the data stored in the summary segment information stored in the cache 408.

Connection Building „ _n

18

The description so far has focussed on route building. However, knowing the carrier's route network is insufficient for the system to show flight availability. In order to do this, the connection builder 30 builds flight connections over the k-shortest routings returned by the route builder 402. The routings may either be cached or interline extended.

The connection builder builder 404 may iterate through all permutations of flights. The permutaions may then be filtered or sorted based on minimum connection time data. This is usually done in response to the connection builder receiving a request to map specific flight conentions onto one or more routes. The request may be received using standard messaging or protocols known to the skilled person, using wired or wireless communication protocols. Thus, the connection builder may receive the messge or availably request in a simlar manner to which the route builder recives the request to build the route(s) between an origin and destination. The schedule segment cache 408 provides summary segment information for all scheduled flights operating worldwide. This information may comprise data defining:

1 . Flight number

2. Period of operation

3. Flight segment origin and destination stations

4. Departure and arrival time

5. Departure and arrival terminal

6. Number of legs

This data may be represented by alpha-numeric data such as ASCII data, but of course may be represented in other ways.

Connecting rules

One or more effective connection rules may be in effect for a given city pair.

The effective connection rules are briefly described below and may define user preference inputs and applicable connection rule elements which are aggregated together as an effective Connection Rule Set. The Effective Connection Rule Set may comprise any one or more of the following:

• Effective origin-destination rule for the given origin/destination pair, taken from the available connection rule(s) - preset, default, city-pair, interline rules, aggregated and cached before. _{Λ η}

19

• Override the following attributes of the effective origin-destination rule:

o Maximum Enroute-Stop Count with Max Stops in input

o Interline carriers in input.

o Via Locations (inclusion/exclusion airports) in input.

· The Maximum Best Options Limit, taken from the internal preset value (which may be set at 9), and overridden with the Max Options input parameter.

• The Maximum Hop Count, taken from the internal preset value (which may be set at 5), and overridden with Max Connections the input parameter.

• The applicable Manual Rules, for the given Origin-Destination and date.

· Calculated Max Distance, for the given Origin-Destination (the aerial distance

multiplied with the GCD ratio - defined in default rule and overridden by the city-pair rule).

In one embodiment, connection building may be performed by using an algorithm which evaluates each and every permutation of flights between an origin and destination against minimum connecting time data or MCT data.

Usually, the MCT data is stored in a cache or storage means as a table of minimum connecting times and associated data identifying one or more airports. For example, for London Heathrow, LHR, an associated MCT may be one hour. However, the MCT data associated with each airport may be different.

The algorithm may be performed by the connection builder 404 but in principle any processor or computing means may be used to determine the connections. As will be described in further detail below with reference to a specific availability request, the connection builder 404 receives data comprising one or more of:

1 . Origin City/Airport;

2. Destination City/Airport;

3. Marketing Airline (also referred to as subscriber);

4. Departure date/time (Usually, the algorithm finds the travel-options/journeys after this given time on the same date).

The one or more connections may be determined in response to receiving an availability request for connections between an origin and destination on a particular time or/and date or time /or/and date range. This data may be communicated in text format such as ASCI using FTP or other internet protocols known to the skilled person. _2Q

However, other preferences may be included in the received input data such as data defining maximum-enroute-stops, host-only flag, max-options to return, max- connections/hop-count and so on. Usually, the data is in an alpha-numeric format Answering a specific availability request

When the system receives an availability request for a particular or specific connection between an origin and destination, usually embodiments of the invention use a cached 414 or previously determined route network. Subsequently, specific connections are then built over this route. However, using a cached route network is optional, and a route and its associated connections may be dynamically determined in response to an availability request.

The availability request may be received from a call center or website. Further the availability request may be received by wired or wireless communication protocols as previously described.

Referring now to the flow diagram of figure 7 as well as the associated schematic diagram, this example relates to determining availability from one airport, such as Edinburgh airport, referred to as EDI, to another airport, such as Frankfurt, referred to as FRA, via London Heathrow, LHR, or/and Charles DeGaulle, CDG for example.

Figure 8 shows an example flow diagram in the case of interline flights. Typically, routes involving interline flights only include one interline segment at the beginning and one interline segment at the end of the route, as schematically illustrated in figure 8. This allows an airline to extend the reach of their network. This example relates to determining availability from one airport, such as Edinburgh airport, referred to as EDI, to another airport, such as Milan, referred to as MIL, via Charles DeGaulle, CDG for example. Further, in the flow diagram of figures 7 and 8 the numerals A to J may define which functional component, shown in figure 4 of the drawings performs a particular step. However, it will be appreciated that other functional components may perform these steps, such as the other components shown in figure 4.

In either case, referring to the schematic diagram of figure 4, and the flow diagram of figures 7 and 8, in response to receiving an availability request, at steps 701 , 801 , the inventory enquirer 406 obtains information about the available routes, at steps 703, 803 between a given origin and destination from the route builder 402. This may be performed using an inventory enquirer to route builder request. Similarly, the connection builder may „

21

query the route builder directly with a connection builder to route builder, CB-RB, request 40, but other requests will be known to the skilled person.

The CB to RB request allows the connection builder or inventory enquirer to query the route builder for information about available routes between a given origin and destination. The request may be defined as part of a web service for a browser such as internet explorer. The request may therefore provide an interface between the connection builder 404 and the route builder 402.

The CB-RB request 40 may contain one or more of the following fields:

Request originator

Subscriber

Origin and destination (this can be an airport or a city)

Date range

Route type (this can be a bit mask such as that shown in the table below) Route count

Connection airline code

City / airport code

InterlineHopCount (the default value is typically set to 1 )

Further, a similar interface may be provided between the route builder or connection builder and the connection rule cache 410.

This provides the ability to receive information about rules between given O&D. the request may comprise data defining:

• Subscriber

• O&D

• Date Further a similar interface between the route builder or connection builder and the flight schedule segment cache 408 cache may also be provided. This may provide data defining all legs/segments for given Airline, for example in bulk. The request may comprise data defining an Airline Code. In response, the system returns set of legs and segments for given carrier. In all cases, the above data is usually in the form of alpha-numeric data.

The route builder 402 may use the cached network 414, at step 705, 805, as previously described with reference to figures 1 to 6 and subsequently find flights for each hop that operate on the given date. Subsequently, flights may be matched for consecutive hops according to the minimum or/and maximum connection time. The connection builder 404 may then remove unfavourable connections leaving only the best connections, at step 707, as previously described. At step 709, the flight connection builder 404 determines the effective connection rule set using any optional overrides for EDI-FRA and further optional overrides for LHR as a connecting airport. At step 71 1 , matching flights for EDI-LHR and for LHR to FRA are determined by the connection builder 404. At this step, a minimum connection time rule may be applied to remove any invalid connection. At step 713, the best subset of connecting options is determined by the connection builder 404. The best options are then returned by the connection builder 404 to the inventory enquirer 406.

For interline connections, interlineHopCount criteria defining the count of interline segments connecting to the online host network may be provided. This may improve the efficiency of the search algorithm. If the count of routes with interlineHopCount=1 does not satisfy the shortest route search criteria then the system may include routes with interlineHopCount>1 in order to perform a broader search. However, search result for interlineHopCount=1 may contain routes with more than one interline segment if no complete online routes are found, the rules between the origin and destination define an interline connection point or the route building request specifies a given City/Airport Code the requires an interline segment.

The connection builder 404 to route builder 402 request outlined above may use a route type bit mask. Similarly, other data requests/ transfers between the inventory enquirer and route builder or inventory enquire and connection builder shown in figure 4 may also use a route type bit mask. This may be composed as follows:

The availability request only needs to host flights. To improve performance, embodiments of the invention allow the requesting application control of the types of flights they wish to see. For example, host flights only may be requested if the user is not satisfied for the client application to request interline extensions.

Thus, as previously described, in response to the request, the route builder 402 applies the appropriate rules and builds a list of one or more segments required to complete the route. This response may specify the start and end points (i.e. airports) of the segment as well as the carrier that operates the segment. For example a route flying from London Heathrow to Frankfurt on Malaysia Airlines with a connection from Frankfurt to Kiev with S7 Airlines could be recorded as ([MH]LHRFRA-[S7]FRAKBP), and the route builder, in response to the request, may return the information defining the carrier and the hop from London Heathrow. As outlined above, this may be returned as an string of characters such as alphanumeric characters including one or more operator symbols, such as ( or ) or [ or ].

In the following example, a client application requests the inventory enquirer 406 to find flight availability from London Heathrow (LHR) to Sydney (SYD) on 21 March 2015 for the airline XS:

1 . The inventory enquirer 406 receives an availability request, as outlined above. The availability request may be received my wired or wireless communications means known to the skilled person. Usually, the availability request comprises alpha- numeric data such as ASCII data or file. The data may define any one or more of an origin, destination, a departure date and preferably departure time. Usually, the connection building algorithm builds connections within a 24 hour window. The availability request may be specific to a particular airline, for example XS.

2. The inventory enquirer 406 then determines flight connections. In one example, the inventory enquirer 406 requests the flight connection builder 404 to determine connections for LHR to SYD on 21 March for airline XS. In response, the connection builder 404 requests routes from the route builder 402 for LHR to SYD as previously described.

3. The route builder 402 locates cached host routes stored in the cache 414 and if no host routes are present or if specifically requested, dynamically builds interline extensions to the host network, as previously described. In this example, the route builder returns two routes: LHR-SIN-SYD and LHR-LAX-SYD. The data may be received as alpha-numeric data and may comprise any of the information described in the above-mentioned logs. The connection builder 404 then determines flights for each hop or leg in each routing, for example LHR-SIN XS100 and XS102 which means that 2 flights are available for the first leg, namely XS100 and XS102.

Further the connection builder also determines what flights are available for the second hop or leg, and in this example the connection builder finds 2 flights for the _{η Λ}

24

hop SIN-SYD namely XS800 and XS802. In other words, the connection builder maps specific flights onto each routing. The mapping may be performed based on matching origin and destination data associated with each hop or leg to data defining each flight, such as date, origin and destination.

4. The connection builder 404 may optionally exclude connections that are prohibited by traffic restrictions filed against the schedule.

5. The connection builder 404 may also optionally exclude connections that are sub minimum connection time, or exceed the maximum connection time.

6. The connection builder 404 then returns one or more connections based on one or more factors. For example, a list of a plurality of connections between an origin and destination may be provided. One example of a list of connections is:

a. Connection 1 : XS100+XS800

b. Connection 2: XS102+XS802.

7. A best connection may be determined based on end-to-end journey time. For example the connection builder 404 may determine the transit time of each of the above two connections. This may be determined by determining the sum of transit times of each hop or leg which makes up a connection. A best connection may be determined as one which has the shortest end to end journey time. However, other factors, may be taken into account when determining a best connection, and this is described in further detail below.

The algorithm outlined above may compare the results against evaluation criteria. Usually, this functionality is performed by the connection builder (404) shown in figure 4 of the drawings, although it may be implemented on any processor or processing means.

The evaluation criteria may comprise any one or more of data defining:

1 . Number of Non-subscriber flights (usually a smaller value is preferred);

2. Total Elapsed Time (usually a smaller value is preferred);

3. Change of Gauge (least number of changes is preferred);

4. Number of en-route stops (lower number is preferred);

5. Number of hosted carriers (larger number is preferred);

6. Earliest Arrival Time (earlier time is preferred); and

7. Total transit time (lower is preferred).

Thus connection data may be associaed with specific connections which are mapped onto each route. The connection data may define any one or more of a flight identifier which uniquely identifies a particular flight from an origin to a destination, as well as numeric data ₁ _

25

defining the number of non-subscriber flights, numeric data deinfing the total elapsed time, numeric data defining a change of gauge, numeric data defining a number of en-route stops, numerid data define a number of hosted carriers, numeric data defining an ealierst arival time and numeric data definnig a total transit time.

Usually, a connection with the smallest total elapsed travel time is selected. Alternatively, or in addition, a connection with the smallest transit time is selected. Alternatively or in addtion, a connection with the minimum number of stops is selected. This may be subject to all of the connections of each hop having associated connection times between hops being greater than a minimum connection time for each hop.

In this way, embodiments of the invention may evaluate each connection option for every routing and determine a weighting. Embodiments of the invention may then select one or more connections with the flights with the lowest weighting.

After each of the above criteria is determined for each connection, the options are ranked by sorting against the weighted criteria. After all of the evaluation criteria have been performed, then the individual rankings are combined to create a master ranking. Connection rules data typically does not change frequently and does not represent a very large amount of data. Accordingly, it may be preferable that all the connection rules are maintained in a cache. Accordingly, it will be appreciated that a plurality of different flight connections are mapped onto a route network. Flight connections are usually ranked based on one or more of the above criteria

From the foregoing, it will be appreciated that the mobile communication or client device may include a computing device, such as a desktop computer, a laptop computer, a tablet computer, a personal digital assistant, a mobile telephone, a smartphone, a kiosk, an internet enabled television, an internet enabled television receiver, an internet enabled games console or portable games device.

The server may comprise a computer processor running one or more server processes for communicating with client devices. The server processes comprise computer readable program instructions for carrying out the operations of the present invention. The computer readable program instructions may be or source code or object code written in or in any combination of suitable programming languages including procedural programming languages such as C, object orientated programming languages such as C#, C++, Java, scripting languages, assembly languages, machine code instructions, instruction-set- architecture (ISA) instructions, and state-setting data.

The wired or wireless communications networks described above may be public, private, wired or wireless network. The communications network may include one or more of a local area network (LAN), a wide area network (WAN), the Internet, a mobile telephony communication system, or a satellite communication system. The communications network may comprise any suitable infrastructure, including copper cables, optical cables or fibres, routers, firewalls, switches, gateway computers and edge servers.

The system described above may comprise a Graphical User Interface.

Embodiments of the invention may include an on-screen graphical user interface. The user interface may be provided, for example, in the form of a widget embedded in a web site, as an application for a device, or on a dedicated landing web page. Computer readable program instructions for implementing the graphical user interface may be downloaded to the client device from a computer readable storage medium via a network, for example, the Internet, a local area network (LAN), a wide area network (WAN) and/or a wireless network. The instructions may be stored in a computer readable storage medium within the client device.

As will be appreciated by one of skill in the art, the invention described herein may be embodied in whole or in part as a method, a data processing system, or a computer program product including computer readable instructions. Accordingly, the invention may take the form of an entirely hardware embodiment or an embodiment combining software, hardware and any other suitable approach or apparatus.

The computer readable program instructions may be stored on a non-transitory, tangible computer readable medium. The computer readable storage medium may include one or more of an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, a portable computer disk, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk.

Exemplary embodiments of the invention may be implemented as circuit board which may include a CPU, a bus, RAM, flash memory, one or more ports for operation of connected I/O apparatus such as printers, display, keypads, sensors and cameras, ROM, a communications sub-system such as a modem, and communications media.

The flowcharts of Figures 5, 6, 7, and 8 illustrates the operation of an example

implementation of systems, methods, and computer program products according to various embodiments of the present invention. Each block in the flowchart or block diagrams may represent a module comprising one or more executable computer instructions, or a portion of an instruction, for implementing the logical function specified in the block. The order of blocks in the diagram is only intended to be illustrative of an example. In alternative implementations, the logical functions illustrated in particular blocks may occur out of the order noted in the figures. For example, two blocks shown as adjacent one another may be carried out simultaneously or, depending on the functionality, in the reverse order. Each block in the flowchart may be implemented in software, hardware or a combination of software and hardware.

The invention may be defined in the following numbered clauses to which reference should now be made

1 . A system or method for determining routing(s) or/and connection(s) between an origin and destination in a carrier network having a plurality of nodes comprising: a. processing means such as a processor for:

i. determining the k shortest routes between the origin and destination ii. determining one or more routing rules to apply to each route based on data defining each route; and

iii. selecting one of the routes based on the data defining the routes and the determined rules.

2. The system or method of any preceding clause wherein each route is defined by data defining the route as one of a host direct flight, a host connecting flight, an interline direct flight on preferred flights, a host flight connecting with interline on preferred interline flights, an interline direct flight on non-preferred flight.

3. The system or method of any preceding clause wherein the rules comprise one or more of a rule defining the maximum number of connections allowed for entire routing, the maximum overall path length, for example, not be greater than 200% of the great-circle distance between the origin and destination, maximum elapsed time, minimum / maximum connection times; service type exclusion for excluding flights with a given service types, maximum number of stops allowed for the entire Zo

routing, airline code inclusions / exclusions to modify the flights included from a given airline when determining routings, metropolitan areas / cross city travel limitation to allow or deny connections into and out of different airports in a given city; back-haul permission to allow a connecting segment to increase the great- circle distance to the final destination, country return exclusion, for example, once a country has been left on a route, it cannot be re-entered, aircraft type inclusions / exclusions, maximum flight usage; and via city or airport inclusions / exclusions for connecting routes. The system or method of clause 1 further comprising receiving means for receiving an availability request for a connection between the origin and destination wherein the availability request is associated with one or more carriers.

The system or method of any preceding clause further comprising receiving an availability request for a connection between the origin and destination wherein the availability request comprises one or more of data defining the request originator, subscriber, origin and destination, in particular an airport or a city, date range, route type which may comprise a bit mask, route count, connection airline code, city / airport code InterlineHopCount preferably having a default value set to 1 .

The system or method of any preceding clause further comprising determining whether one or more predetermined cached routes match the availability request and in particular wherein if no predetermined routes match the origin and destination data defined in the availability request the processor determined the I shortest paths between the origin and destination data associated with the received availability request preferably based on the cached k shortest routes between a different origin and destination.

The system or method of any preceding clause further comprising determining one or more flights, in particular BA143, for each hop in each routing based on one or more of time, time range, date, date range, and end to end journey time data such as minimum end to end journey time.

A computer-readable storage medium having tangible features that cause a machine reading the medium to perform the method of any preceding claim.