How do travel search engines combine flights

Question

I'm curious about how the flight/train search engines combine the results from multiple sources. For example, let's say I'm asking to go from London to Paris, and let's assume there are no direct flights for whatever reason. However, there is a flight from London to Lille (North of France), and then a train from there to Paris. An extreme example would be where there is no direct connection either, but you can get to your destination by combining plane, train, bus and finally taxi or a ride-sharing service.

How would a search engine effectively find the best option? It has access to a basic API from each provider that allows it to ask for rides from point A to B at a specific time. It does not have a database of all available rides and flights though, it can only query each provider's API but those queries are quite slow (if you have to do hundreds of them) and costly, so the objective is to minimize the amount of queries.

I'm thinking about making a small ride-sharing comparator as a side project (and maybe include bus/train/taxi as well) and I'm not sure where to start or if this is even doable considering the constraints.

I believe my problem is not simply about "connecting the dots" - the suggested questions assume that you know all the dots and you just need to find the best path. In my case it's a bit different because not only do I not know the best path, but I do not even know which "dots" do I have. I can make queries such as "is there a ride from A to B" but I can't ask "give me all the rides you offer", which means I'm looking for advice on how can I efficiently query for potential "dots" without using the bruteforce approach of asking for all possible combinations (which would DoS the provider's site).

Answer 1

Path- finding algorithms such as A* routinely do this using some cost function (e.g. Distance, time, or even waiting-time) and heuristics to select the most promising candidate for expanding the path (e.g. If possible departure from same station/airport, and distance between arival point and target).

The basic schema would be:

• use a sorted queue
• pick the first path on queue, or your departure point. If reached target you have the optimal path
• expand it on the end point by looking for all the compatible travel possibilities
• calculate the "cost" (in your case the travel time) of each new expanded path as well as the heuristic for reaching target
• put all these paths in the queue and sort it
• loop again until you're over

You have variants depending on which heuristic you take, which cost (or set of cost) you want to minimize), how you combine cost and heuristic, if you prune some irrelevant expansion, and whether you stop when target is reached or go on to collect several alternatives.

In all these algorithms, the path is expanded one step per iteration, without having to know all the points or path in the graph. When presenting the results, the path might have to be agregated in order to hide the obvious but irrelevant segments (e.g. All the towns on the train route)

If the API you're querrying does not provide all the departures from a given note, you have to introduce in the algorithm additional heuristics based strategies, such as:

• caching previous replies on other requests, so to build up a map of potential existing segments (e.g if there was a flight between A And B on a day, there might be one onaother day, probably around same time). However you'd still need to check/confirm for the current travel.
• identifying intermodal hub nodes (e.g. Start with limited set of known hubs such as London, Paris, Franfurt, and expand list automatically based on statistics) and if no direct path is found, start breaking down the path using these hub nodes (still making use of the cost/distance heuristics)
• take rules of to avoid plane/train for shorter distances.

There are a lot of strategies that can be considered. But as soon as you enter such a fuzzy approach (e.g. You have to advance in the blind) your performance will heavily rely on your heuristics and a lot of fine tuning will be required. The easiest way will still be a partnership with services offering you a "list of departures" API