I've been involved in solving a similar problem, on the award flight search side. There are about 12,000 direct commercial routes offering award redemption, and the airline websites have different limitations: some only let you search one-way or only round-trip, or only one cabin at a time, or only give hints about available quantities. So you have to formulate the minimal set of queries that will give you complete information. And then given an origin and destination, figure out the valid routings, like you've discovered.
The other really interesting challenge with many of the airline websites are the extreme measures they go to, to block you from crawling their data. My favorite is British Airways, which runs 800 different tests to fingerprint your browser, from generating audio files to drawing to an off-screen canvas, all inside a custom VM with encrypted byte code. (Similar to how I've seen Google obfuscate the ReCaptcha code base.) Surprising to hear that Ryanair makes it so easy to access prices in comparison!
Many moons ago, I worked in the travel industry. Most airlines aren't running their own technology stack -- they are paying someone else $/search to drive their webpage. In a market of razor thin margins, paying per search for you to crawl their flight catalog is a big problem -- thus the arms race. The only way to win at this is to own the catalog, this is why Google bought ITA.
Ryanair is the kind of airline that I would suspect might run their own stack, and therefore not have the same cost structure.
Fun fact: Carl actually implemented the Turing machine construction on slide 28 as a proof of concept and used it to do simple arithmetic (very very slowly) -- you can read the details towards the end of the talk, with screenshots.
Off-topic but related: https://scottscheapflights.com is _amazing_. The Premium sub is worth every penny...my wife and I will be doing a ton more overseas travel in 2019 purely because of the deals this site finds.
I got into churning airline miles then manufactured spending (generating spend on credit card to earn miles) and now have over 10 million miles. I also heard one of the biggest groups of manufactured spend are developers within Google.
I belong to a private slack with over 80 folks doing this as a hobby so we can do first class/business class international travel and hotel stays for free.
If anyone is into it as as well and would like to join a private Slack and contribute, hit me up. A big majority of the group are engineers.
NOTE: this group is for advanced folks only who have been doing this for a while. Think "r/churning level 2"
Also off-topic, I would pay a premium for the deals to be pre-searched for my specific cities/dates. I already pay for scotts premium. But would pay even more if I was able to actually have it look at my calendar and see when I could go on these trips. I miss out on too many due to not being quick enough.
If you want something done right, you have to do it yourself. I spent several hours last night trying to find cheap routes starting from Rio in January and ending up in the Carribean in February. I don't mind stopping a few places in between and spending some time there, I just want the cheapest flights available. Turns out that information is really hard to find without computing it yourself.
As a CS student, I agree it is really refreshing to see basic graph algorithms to be used in a practical, non academic/industry context. I never really see these basic algorithms used in small side projects, so thank you for this!
We (me and friend) are working on the same problem, however we are stuck at the next step. Namely the user interface: how do you let the user search through all the possibilities.
We created some data structures that allow almost instant searching of such routes and we have scrapers running regularly on Ryanair, easyJet, wizzair, and Transavia. You can query the algorithm here: https://algo.tripchemy.com/routes/TSF?year=2019&month=02&day...
Where you want to have a trip of 20 days (4 lovatons, 5 flights) from 10 Feb. Starting and returning to TSF. We also added some scoring for niceness of airports.
What I've been missing is not so much finding the best routes between two airports, but finding the best (ie. least expensive) route from a bunch of departure airports to a number of destination airports.
If I'm in Antwerp, I really don't care much if I have to depart from/return to Brussels Zaventem, Charleroi or Eindhoven, it just doesn't matter. And if the fare is sufficiently cheaper, then Amsterdam, Düsseldorf, Beauvais or Paris is fine too. And I don't have to return to the airport I left from. Typically it's the same for my destination in the case of holidays.
But I still haven't found websites which allowed to do that easily, apart from Google Flights maybe.
Nice. Maybe check out Azuon (they provide a .net app (eugh; sorta runs under wine, though)) - an annual paid service I gladly pay for. It has two interface modes:
- the basic mode allows you to provide sets of origin and destination locations / countries / airports, and a range of dates; gives you results with direct and transfer flights (including all those ryanair+wizzair/easyjet/another-ryanair combos, etc.) and so on - check out how the interface looks like;
- advanced mode allows you to specify multiple hops, with time intervals / date ranges for how long you want to stay at those hops.
If someone were to provide a (paid, etc.) service and some decent platform-agnostic interface (for me personally, an API would do, too:), that'd be super amazing.
- Instead of graph algorithms, we use more algorithms that originate from databases
- Currently the bottleneck is improving server parallelism and filtering/limiting the amount of results (cause the algorithm can send up millions and millions of rows back). Which in a sense is also a frontend problem: which locations do you want to visit?
back when I was a student, I would sometimes spend hours on Ryanair's website to find that type of deals.
My base was Paris and I wanted to go to Stockholm for example. The direct Ryanair flight from Paris to Stockholm was expensive (Let's say 150 euros).
I would manage to find two cheap flights that go for example from Paris to Rome and another one from Rome to Stockholm, both of those for 10 Euros each. The key is to use the big Ryanair hubs as gateway (Milan and Brussels would work really well back in the days)
I would basically lose my whole day traveling to save 80 euros.
Sometimes it backfires though, and when it backfires you are on your own. Once my first flight got super delayed, and I got stuck in Milan for the night. I managed to have Ryanair rebook my second flight for the day.
I think Ryanair wants to be able to propose high prices for direct flights and prevent people from finding those cheaper indirect flights. That's why they don't make it easy to find them.
Most comparison sites will show you these routes, for example Kiwi lets me search indirect flights from where I am in a remote part of Spain to where I live the other side of Europe. There's no direct routes, but it gives me the option of connecting in Barcelona, Stansted or Hahn, or cheaper options if I want more that one stop. It also lets me search a whole month to find the cheapest flights in a given time period, and will provide options with different low-cost airlines if that's cheaper.
However if you book direct through these sites you are going to get the lowest ticketing class. With Ryanair that means you can't take anything more than a small bag onboard (since November you need to pay for a 10kg cabin bag, you can't drop it at the gate for free), and if you are in a group you will not be sitting next to each other, so it may be best to book directly through the airline's site.
The simple reason why Ryanair don't let you book multi-leg flights directly is because they don't want to be responsible for you missing a connection. It's ironic though, as compared to national European airlines I find their punctuality a lot better.
I use https://airwander.com/ when flying overseas, I don't know how well it works for low cost airlines though.
It's a flight search engine that let you filter what connections there are between the cities you want to travel and help you book a single flight that is going to stay there as a stopover. Sometimes it finds some weird flights that doesn't make any sense if you're just trying to reach your destination but if you're just traveling it's quite nice.
Last time I used it I found a overseas flight that stopped in Lisbon but on the way back made a connection in Bologna that was +200 cheaper then the normal flight.
Airwanderer would be something I have been looking for a long time but it does not seem to work so well. Also, is it just my browser or why is it so difficult to see the layovers? I have to click on "fight details" to see this. Why?
http://www.vayama.com Lets me sometimes stay in Ethiopia for free a day when I fly from Asia to Europe. Does not show up on any other website I consult.
Is this better than itasoftware Matrix? I used it twice this year to build more complicated itineraries, including layovers/stopovers or having just one leg (Germany-nyc) be business class on an a380 for only $500 more.
Try playing with it. The advanced controls are very powerful, for example to find layovers, so less than 24 hours (so you don’t incur a likely stopover fare add-on), you can do something like “maxconnect: 1440; minconnect: 1000”. I’m in fact typing this from a 20 hour layover in Vancouver!
I actually wanted to do that but thought the cost/benefit wasn't high enough - I'd pretty much need to manually place all the airports information on the map if I wanted to use the library I was using (Cytoscape).
Visualizing the DFS at the last step was good enough :) Maybe in the future!
Google Flights is generally fine. But sometimes it figures out quite fringe stuff like Stockholm-Dublin roundtrip with a 17 hour layover in Dubai. It was not cheap either. Sounded like something like a global minima.
Why is there no interface that allows searching for flights without specifying exact dates? All I want to do is fly from A to B to A. Maybe stay a week, maybe two. I'm flexible - it doesnt have to be exactly N days starting on the M'th.
Even services that "allegedly" advertise they have that, still require manually clicking every day combination.
I'd fly more often if it was easy. The few times I tried, it would be just faster to drive than go through all possible 900+ day combinations.
Have you seen a site that does that really well, UX-wise?
I'd assume it's two reasons: first that it's hard to get the UX right. There are going to wind up being so many combinations of possibilities that I'm not sure how you'd even sort them in a meaningful way. (E.g. it's unlikely price from lowest to highest will be the most meaningful, the lowest price alone might wind up having 100 different date combinations, so figuring out how to present the options in a meaningful way might just be something we haven't figured out yet.)
But second, it might just be too computationally expensive. You see how slow sites already are just for searching a single date, because there are so many possible combinations of connections to consider, and so many fare rules to calculate prices out of. Now a 2-week range for both start and end results in taking almost 200 times longer. It just might not be feasible, or worth the programming effort. I remember a blog post a long time ago from Kayak (I think?) talking about the insane effort that was required to cache flight fares just so show simple fare comparisons across a few days... and it only worked for the flights that were more commonly searched for.
Hopper does this with our "Flex dates" feature. You can specify a date (up to a year out I think) and stay (anywhere from 4 days to 2 weeks) window for when you want to fly as well as regions you're interested in traveling to, instead of just 1 destination (although we also allow you to select just 1 destination).
It was sort of hidden for a while because we were testing other features, but it's back on the main search screen now.
Disclaimer: I work for Hopper
Edit: Forgot to mention this feature is only available on iOS at the moment...
I think it´s because most of the UX is designed a long time ago. The pricing wasn't too dynamic and search engines/airlines were more focused on business travelers (from which they have more money) and they usually don´t care too much, how much it cost and when they must / want to fly.
We are building our search engine (focus on EU low-cost mainly) which allow what you looking for (even if you want to search this) for example: A -> B [stay 2-6] -> C [stay 10-12] -> A
Finding a cycle of a given length can actually be done in time `O(e^k n^2.3)` where `k` is the length of the cycle, using the cool technique of color coding.
Basically, to find a cycle of length 6, you repeatedly color every node in one of 6 colors at random. Then you look for a cycle with all different colored nodes, which can be done efficiently using dynamic programming.
You succeed in finding a particular 6 cycle exactly if each node in it has gotten a different color, but the chance of this is not bad. In the case of the OP it's even better, since there are probably many such cycles to find.
Somewhat off-topic and shameless plug, I'm working on a meta flight-search engine that finds the cheapest flights from multiple origins to the same destination (i.e. me and some friends who live in another city want to fly to Hong Kong with no particular date in mind, just want the cheapest flights and with overlapping departure/return dates). Does anyone else have a similar need or know of anything that can do this?
[+] [-] smartbit|7 years ago|reply
https://matrix.itasoftware.com/ to get detailed fare rules & restrictions
https://www.expertflyer.com & https://itunes.apple.com/us/app/seat-alerts/id533533342
https://www.checkmytrip.com/ allows entering name & booking-reference and gives all detail
https://www.viewtrip.com/
https://tripcase.com will use name + booking-reference to get detailed PNR information including the first name
https://www.fly.kiev.ua can make a flight reservation without a payment, still gives an 6char booking-reference
[+] [-] GFischer|7 years ago|reply
http://www.ai.mit.edu/courses/6.034f/psets/ps1/airtravel.pdf
Edit: I missed that someone had already linked to them - https://news.ycombinator.com/item?id=18531203
[+] [-] zerowellies|7 years ago|reply
[+] [-] jd20|7 years ago|reply
I've been involved in solving a similar problem, on the award flight search side. There are about 12,000 direct commercial routes offering award redemption, and the airline websites have different limitations: some only let you search one-way or only round-trip, or only one cabin at a time, or only give hints about available quantities. So you have to formulate the minimal set of queries that will give you complete information. And then given an origin and destination, figure out the valid routings, like you've discovered.
The other really interesting challenge with many of the airline websites are the extreme measures they go to, to block you from crawling their data. My favorite is British Airways, which runs 800 different tests to fingerprint your browser, from generating audio files to drawing to an off-screen canvas, all inside a custom VM with encrypted byte code. (Similar to how I've seen Google obfuscate the ReCaptcha code base.) Surprising to hear that Ryanair makes it so easy to access prices in comparison!
[+] [-] toast0|7 years ago|reply
Ryanair is the kind of airline that I would suspect might run their own stack, and therefore not have the same cost structure.
[+] [-] dmbaggett|7 years ago|reply
[+] [-] crikli|7 years ago|reply
[+] [-] micahgoulart|7 years ago|reply
I belong to a private slack with over 80 folks doing this as a hobby so we can do first class/business class international travel and hotel stays for free.
If anyone is into it as as well and would like to join a private Slack and contribute, hit me up. A big majority of the group are engineers.
NOTE: this group is for advanced folks only who have been doing this for a while. Think "r/churning level 2"
[+] [-] brianbreslin|7 years ago|reply
[+] [-] thaumasiotes|7 years ago|reply
[+] [-] daurnimator|7 years ago|reply
[+] [-] SmellyGeekBoy|7 years ago|reply
[+] [-] yosito|7 years ago|reply
[+] [-] abhisuri97|7 years ago|reply
[+] [-] whazor|7 years ago|reply
We created some data structures that allow almost instant searching of such routes and we have scrapers running regularly on Ryanair, easyJet, wizzair, and Transavia. You can query the algorithm here: https://algo.tripchemy.com/routes/TSF?year=2019&month=02&day...
Where you want to have a trip of 20 days (4 lovatons, 5 flights) from 10 Feb. Starting and returning to TSF. We also added some scoring for niceness of airports.
[+] [-] seszett|7 years ago|reply
If I'm in Antwerp, I really don't care much if I have to depart from/return to Brussels Zaventem, Charleroi or Eindhoven, it just doesn't matter. And if the fare is sufficiently cheaper, then Amsterdam, Düsseldorf, Beauvais or Paris is fine too. And I don't have to return to the airport I left from. Typically it's the same for my destination in the case of holidays.
But I still haven't found websites which allowed to do that easily, apart from Google Flights maybe.
[+] [-] wfn|7 years ago|reply
- the basic mode allows you to provide sets of origin and destination locations / countries / airports, and a range of dates; gives you results with direct and transfer flights (including all those ryanair+wizzair/easyjet/another-ryanair combos, etc.) and so on - check out how the interface looks like;
- advanced mode allows you to specify multiple hops, with time intervals / date ranges for how long you want to stay at those hops.
If someone were to provide a (paid, etc.) service and some decent platform-agnostic interface (for me personally, an API would do, too:), that'd be super amazing.
[+] [-] whazor|7 years ago|reply
- Instead of graph algorithms, we use more algorithms that originate from databases
- Currently the bottleneck is improving server parallelism and filtering/limiting the amount of results (cause the algorithm can send up millions and millions of rows back). Which in a sense is also a frontend problem: which locations do you want to visit?
[+] [-] aembleton|7 years ago|reply
[+] [-] warp_factor|7 years ago|reply
My base was Paris and I wanted to go to Stockholm for example. The direct Ryanair flight from Paris to Stockholm was expensive (Let's say 150 euros). I would manage to find two cheap flights that go for example from Paris to Rome and another one from Rome to Stockholm, both of those for 10 Euros each. The key is to use the big Ryanair hubs as gateway (Milan and Brussels would work really well back in the days)
I would basically lose my whole day traveling to save 80 euros. Sometimes it backfires though, and when it backfires you are on your own. Once my first flight got super delayed, and I got stuck in Milan for the night. I managed to have Ryanair rebook my second flight for the day.
I think Ryanair wants to be able to propose high prices for direct flights and prevent people from finding those cheaper indirect flights. That's why they don't make it easy to find them.
[+] [-] fyfy18|7 years ago|reply
However if you book direct through these sites you are going to get the lowest ticketing class. With Ryanair that means you can't take anything more than a small bag onboard (since November you need to pay for a 10kg cabin bag, you can't drop it at the gate for free), and if you are in a group you will not be sitting next to each other, so it may be best to book directly through the airline's site.
The simple reason why Ryanair don't let you book multi-leg flights directly is because they don't want to be responsible for you missing a connection. It's ironic though, as compared to national European airlines I find their punctuality a lot better.
[+] [-] mtrovo|7 years ago|reply
It's a flight search engine that let you filter what connections there are between the cities you want to travel and help you book a single flight that is going to stay there as a stopover. Sometimes it finds some weird flights that doesn't make any sense if you're just trying to reach your destination but if you're just traveling it's quite nice.
Last time I used it I found a overseas flight that stopped in Lisbon but on the way back made a connection in Bologna that was +200 cheaper then the normal flight.
[+] [-] jayalpha|7 years ago|reply
http://www.cleverlayover.com also never worked for me. Good idea, bad executed.
Regarding travel websites, you may want to check out:
https://www.kiwi.com Sometimes finds insane travel routes.
http://www.vayama.com Lets me sometimes stay in Ethiopia for free a day when I fly from Asia to Europe. Does not show up on any other website I consult.
I have also had luck at times with
http://www.opodo.com
http://www.expedia.com (yes, sometimes an old dog still does the trick)
[+] [-] radicality|7 years ago|reply
[+] [-] donjoe|7 years ago|reply
[+] [-] shoyer|7 years ago|reply
[+] [-] jonluca|7 years ago|reply
Visualizing the DFS at the last step was good enough :) Maybe in the future!
[+] [-] catchmeifyoucan|7 years ago|reply
For multi city flights, I've found Google flights does things really well from a UX standpoint, and I believe they support Ryanair.
[+] [-] jnurmine|7 years ago|reply
[+] [-] shshhdhs|7 years ago|reply
[+] [-] kasparsklavins|7 years ago|reply
Even services that "allegedly" advertise they have that, still require manually clicking every day combination.
I'd fly more often if it was easy. The few times I tried, it would be just faster to drive than go through all possible 900+ day combinations.
[+] [-] empath75|7 years ago|reply
These are the results for 'cheapest month' and 'everywhere' from DC
https://www.skyscanner.com/transport/flights-from/wasa/?adul...
[+] [-] crazygringo|7 years ago|reply
I'd assume it's two reasons: first that it's hard to get the UX right. There are going to wind up being so many combinations of possibilities that I'm not sure how you'd even sort them in a meaningful way. (E.g. it's unlikely price from lowest to highest will be the most meaningful, the lowest price alone might wind up having 100 different date combinations, so figuring out how to present the options in a meaningful way might just be something we haven't figured out yet.)
But second, it might just be too computationally expensive. You see how slow sites already are just for searching a single date, because there are so many possible combinations of connections to consider, and so many fare rules to calculate prices out of. Now a 2-week range for both start and end results in taking almost 200 times longer. It just might not be feasible, or worth the programming effort. I remember a blog post a long time ago from Kayak (I think?) talking about the insane effort that was required to cache flight fares just so show simple fare comparisons across a few days... and it only worked for the flights that were more commonly searched for.
[+] [-] thetest3r|7 years ago|reply
[+] [-] rockostrich|7 years ago|reply
It was sort of hidden for a while because we were testing other features, but it's back on the main search screen now.
Disclaimer: I work for Hopper
Edit: Forgot to mention this feature is only available on iOS at the moment...
[+] [-] jirisykora83|7 years ago|reply
We are building our search engine (focus on EU low-cost mainly) which allow what you looking for (even if you want to search this) for example: A -> B [stay 2-6] -> C [stay 10-12] -> A
[+] [-] urtrs|7 years ago|reply
[+] [-] amyjess|7 years ago|reply
[+] [-] findjashua|7 years ago|reply
[+] [-] m__|7 years ago|reply
[+] [-] thomasahle|7 years ago|reply
Basically, to find a cycle of length 6, you repeatedly color every node in one of 6 colors at random. Then you look for a cycle with all different colored nodes, which can be done efficiently using dynamic programming.
You succeed in finding a particular 6 cycle exactly if each node in it has gotten a different color, but the chance of this is not bad. In the case of the OP it's even better, since there are probably many such cycles to find.
[+] [-] frakkingcylons|7 years ago|reply
[+] [-] blackdogie|7 years ago|reply
[+] [-] unknown|7 years ago|reply
[deleted]
[+] [-] vool|7 years ago|reply
If you are looking to take this further, you can find some more info on Ryanair API endpoints here:
https://gist.github.com/vool/bbd64eeee313d27a82ab
[+] [-] rexarex|7 years ago|reply
[+] [-] jaycolson|7 years ago|reply
https://github.com/cloudsquall/flightsearch
[+] [-] zabaki|7 years ago|reply
[+] [-] cal97g|7 years ago|reply
[deleted]