Hacker News new | past | comments | ask | show | jobs | submit login
Ryanair, Hamiltonian Cycles, and using graph theory to find cheap flights (2018) (jonlu.ca)
207 points by jonluca on Jan 20, 2020 | hide | past | favorite | 81 comments



We (me and a friend) did something similar for multi city round trips within Europe (https://tripchemy.com).

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=2020&month=02&day...

It's based on the following Open source project which my friend made back in the day https://github.com/Whazor/Roundtrip


I've always wondered how things like this work; how do you actually get all the routes and price information? Do you need to scrape every route on every possible data individually?


We crawl the fare information ourself from the airlines'websites.


Great website, although I have one minor nitpick.

When searching for flights to or from London it's not clear which airport is which out of LTN, LGW and STN.

Screenshot: https://i.vgy.me/J1F0j1.png

Would it be possible to add the IATA code in brackets (after London) and possibly another item in the dropdown for all London Airports?


Cool site! Curious to know what do you use for scraping, without getting blocked?


Thanks a lot! We use scrapy[1]. Our crawler's behavior is very polite so most of them won't block us. Easyjet for example is very strict against crawlers and will block most of them(and us).

[1] https://scrapy.org/


> Easyjet for example is very strict against crawlers and will block most of them(and us).

It seems that easyJet has outsourced its anti-scraping protection to the company called "Distil Networks"[1].

I wonder how could they block screen scrapers using Chrome on Android with mobile IP addresses.

[1] https://www.youtube.com/watch?v=43wh3beHSBo


Is there a reason this wouldn’t work in the US (obvi the prices would be higher). But hypothetically could you support North America and or South America?


The only thing is that we have the crawl US airlines and support an additional currency(USD). So yes, there is no reason why this shouldn't work for North and South America. Do you think there is a market for this in America?


Skyscanner does support multiple trips, doesn't it?


> Ryanair is a wonderful example of two extremes - it’s one of the worst possible airlines that nickel and dimes you for everything, it’s not a great employer, and it is rated the worst European airline; however, it’s dirt cheap.

I fail to see how these are two different extremes. More like two sides of the same coin.


The natural reading of the “worst” part, to me, is that Ryanair is a business built on greed. These sound like the practices of a company whose owners want to squeeze all the money they can out of it in a short-term sense, leaving none “in” the company to grow it or pay its employees well.

And you’d expect such a business to have high margins; i.e. to be charging a lot for a little, maximizing earnings at the expense of reputation.

But instead, Ryanair is extremely low margin. Which actually is surprising. (I mean, not in an economic sense; the greedy Ryanair would die, where the cheap Ryanair would, and does, live, serving a niche. But it’s still surprising in the sense that it means that the archetype you were expecting to apply—that of the greedy owner—probably doesn’t.)


I don’t see how this reasoning follows. The business model is pretty clear - shave everything to the bone and make your profit on volume. It’s like Aldi or wal-mart for air travel. If they had high margins they’d just get their lunch eaten by someone offering better service at the same price (with lower margins). It’s certainly not incompatible with greed.

Edit: reread your last pp and obviously this isn’t news to you. I just don’t share the greed = margins expectation.


Interpreting low-cost low-service providers as 'greed' strikes me as naive. How else would you expect a business to cut costs and prices to the bone, other than by reducing service?

Costco, while blessed with a better reputation, is similar. The prices are low in large part because the experience of a Costco store is extremely barebones: limited variety of items, required to buy in bulk, everything is just on the pallets they came on, the store is literally a warehouse with a cement floor, customer service is very limited etc. That's not them being greedy either, it's fundamental to how their business works.


It’s interesting that you bring up Costco because their business model doesn’t quite work the same way.

Costco employees are paid very well compared to other retail and warehouse employees. The average Costco shopper is also more affluent than a typical Walmart or Target shopper.

Costco customer service is not limited at all. It’s the best in the industry. They have notoriously generous return policies. As long as it’s not electronics, you can return basically anything at any time. The electronics section also tacks on another year warranty compared to other retailers.

Many items in Costco aren’t actually generally the best deal around. Again, they cater to high income families. Yes, the low-labor warehouse environment with very few SKUs reduces costs, but it not a low-end experience. Only bulk staple foods are truly great deals, many items in the middle section (home goods) and electronics can be found for cheaper elsewhere with little difference in quality.

The analogy you might be looking for is Amazon. They use contracted employees for deliveries and overworked, underpaid non-union warehouse employees. They have very little emphasis on delivering genuine goods and don’t mind selling off-brand stuff as long as it’s the cheapest option. They use market dominance as a replacement for decent service and products: who else can run their own delivery service?


To be clear, it’s not the low-cost part that sounds like greed on the part of the owners; it’s the low-paid employees and worst-rated service that sounds like greed. Those are more often things you see from companies who are “penny wise and pound foolish”; companies like, say, Comcast.


The low-paid employees are the reason they can keep costs so low. This is circular reasoning. While everyone can provide examples of new services that provide similar costs but have happier employees, it can't sustain long term because money is a thing. All the snazzy new services will one day become dominant because they have well funded VC backing and/or actually better service than competition, and then the shareholders will work on clawing back their investment by raising prices / slashing costs etc.

As a consumer, I'm no longer loyal to one brand for almost anything (including such essentials as my laptop) because someone will come by and offer me cheaper service, but I don't want to enable the newcomer to take over the market because it'll come back to bite me. But people like me are more discerning than the normal consumer.


> And you’d expect such a business to have high margins; i.e. to be charging a lot for a little, maximizing earnings at the expense of reputation.

Only if that business had a monopoly. As Ryanair has competition, and Ryanair doesn’t provide any service that others won’t or can’t, one would not expect high margins.


"I traversed down the state tree until I found the allAirportsList property, which contained all the airport keys and the locations to which they flew. I extracted this state (over 1MB of route information) and could now build a graph representation of airport connections."

In the 90's, I can remember a pocket-sized, printed guide by a company called OAG. I used to call it "the OAG Guide". I can remember getting a copy of this for free. It listed every schedule for every route for every airline. I can also remember getting similar pocket-sized guides from certain airlines listing all their routes and schedules for each route.

When the task of planning routes comes up, I sometimes think of those old printed guides and wonder if this could be cited as an example where certain information was actually more easily accessible before the www became popular than after.

https://en.wikipedia.org/wiki/OAG_(company)


I used to call it "the OAG Guide".

The official name was "Official Airline Guide," and it was considered an indispensable part of any office.

It first went online as OAGEE (Official Airline Guide Electronic Edition) on CompuServe. It was a massive driver of business accounts to CompuServe, and I believe the first place the average Joe could book airline tickets online.

Then the internet happened...


Aside from the cost of CompuServe, OAGEE was free?


I really don't remember. CompuServe did have some content that you had to pay extra for, but that mostly came later, and I believe OAGEE was available at or very close to launch.


tbf, you'd need a lot of time on your hands to do what the OP did with a paper guide. If you just want to know 'can I go to Paris and Brussels and back to Venice again in three flights' you can do that with three queries on Ryanair's website, which is actually less painful than battling through the upsell screens you'll be greeted with when you come to buy the tickets, never mind booking with their callcentre in the nineties...

And if you wanted to analyse large numbers of routes for business purposes then back in the nineties, you'd have probably found it easier to buy OAG's analyser tool or an airline spreadsheet file than digitise thousands of route pairs from a paper timetable, which you can still do if you don't want to write a scraper.


Do the paper timetables even exist anymore?

I never tried to "analyse large numbers of routes for business purposes" using those free printed guides, but I did use them sometimes when planning trips, real or imaginary.

Rather than "can I go to Paris and Brussels and back to Venice again in three flights" what I wanted to know was "what airlines fly between cities 1, 2, 3, etc. and what are all of departure and arrival times for the flights they have on those routes."

Today I might use that information when deciding what to price information I want to scrape.

I wonder if today there is a digital source of that information, free for public access. Probably not.


There's no shortage of flight search engines that will let you know what airlines fly between cities [including nearby cities and connecting flights] and what flight arrival and departure times they have over a given week, completely for free, with up to date price info. Can't think of any normal trip planning scenario where I'd rather browse a chunky book to obtain a flights longlist and then phone a reservations agent to ask for quotes for each flight on it instead of hitting the query tool on Kayak/Skyscanner once per city pair and seven day window and getting all that information with availability and price.

Though timetable enthusiasts can still buy paper guides from OAG for a lot less than their data in usable-for-analysis form, apparently.


Based on my experience in Italy, Lufthansa offices still offer free copies at the ticketing counter. I’m not too sure how many people buy tickets at the airport nowadays, let alone do so with a paper timetable, but they are still there! :-)


I’m not too sure how many people buy tickets at the airport nowadays

Many people. Mostly business people who need to be somewhere on short notice. Until very recently, my wife was in this group.


If you need to travel on short notice, isn't it faster to book online rather than lining up at the airport?

Or does the airport ticketing desk have a later cutoff time?


If you need to travel on short notice, isn't it faster to book online rather than lining up at the airport?

In her situation, no. The phone would ring at 5am, she'd get dressed and grab her "go" bag and walk down to the subway, then buys her ticket (usually one-way) at the airport counter.

In theory she could try to book tickets on her phone on the train, but connectivity can be iffy on the train, and buying an expensive airline ticket is not the sort of thing you want to take unnecessary chances with. (Think double-purchases, false purchases, etc...)


Sometimes not and yes. Online ticket purchases are routed through a protocol which has an earlier cut off time after which the ticket is in “airport control” and purchased or changes happen in-person. https://travel.stackexchange.com/questions/111197/what-does-...


One of the founders of ITA Software, which became Google's flight search, discussed some interesting issues in airline fare search [0]. I don't have enough of a CS background to fully understand all of this, but the message is pretty clear: it's complicated.

There was also an HN thread from 2012 discussing ITA's use of Lisp.[1]

[0] http://www.demarcken.org/carl/papers/ITA-software-travel-com...

[1] https://news.ycombinator.com/item?id=4639490


Nice work. To be truly usable though you need to ensure that the flight times match up. There's no point flying to an intermediary airfield to find that your connection flight left 30 minutes ago.


Yeah this would ideally now be used if you want to make a trip to each city and stay for a day or so and not care about what time the flights leave.


Yeah, no point in going via an extra city if you're not going to stay there for at least a day!


Couldn't you just add time as another dimension?


I'm fairly decent at finding flight deals for my side hustle site, I know where and when to look (for Australian flights especially). I have some automation scripts (using python/selenium). But this takes it to the next level! Bravo, bravo!


I don’t suppose you’d mind sharing your scripts? I’m in a long distance relationship between SF and Sydney, so flights are a very regular occurrence for both of us. Anything that surfaces savings is highly welcome.


hmm, they're quite customised to my site and not very nice reading ;). If you contact me on our website/FB, with some more detail, I'll see what I can do. We also promote deals there and on FB to San Francisco when we see them.


Always enjoy your posts on OzBargain!


thanks, I appreciate it! Nice to hear it helps.


Like the idea ! Wouldn't using the data of something like https://www.skyscanner.net/ give you better data, across multiple airline


Or just use the extraordinary product https://www.kiwi.com


What annoys me with Kiwi is it doesn't work with business class... Enter Auckland <> Europe, outbound any day in March, return any day in September...

"We couldn't find your trip."

Also, it's cities filter is doesn't seem to work. Try putting search above, but economy and inverse cities. It's going to be dominated by flights from London which you can deselect LHR as much as you want to. London sucks for transit if you are outside of UK.

Edit: Google Flights are no better here. Lots of carriers hide biz class prices from Google or take ages to load (some time out happens in Google) or straight up lie ("Ooops! the price has increased" since you last search 10 seconds ago - I'm looking at you Qatar) or mixes in some random Economy class flights out of nowhere...


Well if you're looking for Europe <> ANZ fares in J, stuff out of ARN,OSL,GOT, etc. is fairly competitively priced.

The good news is that with business class fares, the problem space is smaller, so finding and learning the patterns is very doable.


Yep Air India got some decent prices recently from ARN to SYD (which I've tried and while I'm fine with quite run down upholstery near broken seats, the biggest problem was seat was too short to fully stretch, hence lack of sleep).

The best I've found yet was one of the Chinese carriers Melbourne to Moscow return for 1650 euros...


Find route can probably be made way more efficient by using meet in the middle technique.

Instead of finding all 6 hops from start and checking if it's the end find 3 hops from start, 3 hops from end and just intersect two sets.


Take a look at https://amoffat.github.io/held-karp-gpu-demo/

It can easily solve 16 nodes in under 50ms by running in WebGL


Do you know if there are any nice UI implementations of this around? I'm interested in building on your work to make a more fully featured site!


I don't believe in this exact format, no.

The code is fairly trivial though - Cytoscape does most of the heavy lifting https://github.com/jonluca/blog/blob/master/js/ryanair-graph...


Similarly, https://skiplagged.com surfaces potentially cheaper multi-leg flights that have a layover in your destination city.

For example if you are wanting to travel from A->B, a flight that goes A->B->C may be cheaper than A->B if A->C is a competitive route.


This is a dangerous gamble though. Airlines can and do ban people for life when they discover this.


That is certainly the common wisdom. As is throwing away return legs if a round-trip is cheaper. I've done it at various times for various good reasons--mostly changes in plans. And I doubt anyone is going to get banned for doing it now and then. But if you do it every week? Maybe.


The other gamble being that many airlines oversell flights and may “upgrade” you to a direct flight to your paid destination.


It's probably not even so much because of overselling which I don't see a lot of these days at least where and when I fly. But, if travel goes sideways because of weather/mechanical issues/etc., as far as the airline is concerned it's the ultimate destination it needs to get you to.


I did something similar with that API a couple of years ago. My goal was to travel the most possible kilometers at minimal costs:

https://github.com/landgenoot/airtrip-finder


Not as cool, but https://www.eightydays.me/ is really convenient to book multi-city trips intra-europe.


Or we stop promoting flights at all, cheap or expensive, just an idea to keep CO2 levels down.


If all flights in the world stopped, it would have almost no effect on CO2. It would however bring the world economy to a grinding halt.

We need to focus on interventions that will actually make a difference. Sadly, most of those are through government regulation, which most major economies are unwilling to do.


The second phrase of your response contradicts the first. :)


> It would however bring the world economy to a grinding halt.

I think you overestimate the importance of flights to the world economy. If all flights ended tomorrow, the world economy would chug along and hardly notice. Banning trains, trucks or ships would be devastating to the world economy though.

> We need to focus on interventions that will actually make a difference. Sadly, most of those are through government regulation, which most major economies are unwilling to do.

Both those interventions would actually hurt the world economy.

Let me guess, you take a lot of flights every year? Can't defend flights under the false assumption it'll hurt the world economy and then support "interventions" that will actually hurt the world economy.


All interventions will hurt the economy. If they didn't then they would already be happening as the most efficient use of capital.

But all flights worldwide only account for 2% of all CO2.

Industrial output accounts for 22% and electricity 28%.

If we regulated all electricity to be carbon neutral, that would make electricity cost more and harm the economy, but it would have a huge effect on emissions.

Flying just isn't that important to climate change, but it is quite important to the economy. Not a lot of goods move by air, but people do. A lot of the world depends on tourism. For some countries, it is the main contributor to their GDP.

Yeah, I fly a few times a year, sometimes to the other side of the planet, for business. And also for tourism where I spend a bunch of money buying local goods.

I also use a lot of energy. I pay extra to make sure that energy all comes from carbon neutral sources. That makes a much bigger difference to climate change than using a plane.


People like the above commenter likes to ban flights, because they themselves are unlikely to _need_ flights very often, and so proportionally pay a less price for such a ban (and the positive effects are shared equally across the globe).

Let's see if they propose the same argument if the banning was for driving, or some other form of carbon emission that affects them a lot more (like food, or heating).


> Not a lot of goods move by air, but people do.

This simply isn't true. More people use the NYC metro in one day than people fly in the entire US over an entire year. Comparatively speaking, hardly anyone flies compared to using trains, buses, cars and every other major form of transportation.

> A lot of the world depends on tourism.

No. The world depends on oil, gas, etc. The world depends on transportation of goods. The world depends on manufacturing and production. The world doesn't depend on flights.

> I also use a lot of energy. I pay extra to make sure that energy all comes from carbon neutral sources. That makes a much bigger difference to climate change than using a plane.

No. It makes no difference. Other than allowed privileged people to pat themselves on the back.

I agree with you that flights make up a tiny fraction of overall emissions. But you are completely wrong about the impact of flying on the world economy. Ending flights won't bring the "world economy to a grinding halt." Just like ending flights would have neglible effects on overall emissions, it'll have neglible effects on the world economy. But use whatever rationalization to fly if it helps you sleep at night.


"Aviation’s global economic impact (direct, indirect, induced and catalytic) is estimated at US$ 2,960 billion, equivalent to 8% of world Gross Domestic Product (GDP)."

https://www.icao.int/Meetings/wrdss2011/Documents/JointWorks...


> direct, indirect, induced and catalytic

Nice.

> is estimated at US$ 2,960 billion, equivalent to 8% of world Gross Domestic Product (GDP).

Doesn't this prove my point? And that's including every conceivable thing possibly related to aviation ( direct, indirect, induced and catalytic ). Not just flights. Not quite, "grind down to a halt" is it?

For the last time, if flights stopped, the world economy isn't going to grind down to a halt. Flights are luxuries more than anything. The world can survive without luxuries. The oil industry, gas industry, international shipping, railroads, trucks, etc can bring the world economy to a grinding halt. Not sure why you are still arguing when objectively, your statement was wrong.

Why not just say instead of "the world economy grinding to a halt", you meant to say "the world economy will be slightly inconvenienced"?


All of aviation contributes 2% of CO2 emissions. We have bigger fish to fry.


A single flight (per passenger) from NYC to London is equivalent to 11% of the annual carbon footprint of an average UK citizen: https://www.bbc.com/news/science-environment-49349566

Because of the altitude the emissions are worse than those emitted at sea level.

We have a lot more cars on the road than airplanes in the sky, so reducing their carbon footprint would have a bigger impact. But on an individual basis, flying is one of the most carbon intensive travel options.


>annual carbon footprint of an average UK citizen

However annual carbon footprint of a regular citizen is completely meaningless in the greater scheme of things. Stop shifting the blame onto regular people, we're not going to give up on civilisation just because some monopolies are burning coal and gas.


> Stop shifting the blame onto regular people,

I'm not, probably the opposite. I'm stating that if you choose to fly a ~5hr flight, you're contributing 11% more carbon than the average person does all year. In other words, by reducing the demand for flying you can have a greater impact on reducing emissions than the average person could.


but if you didn't board that flight, the flight would still happen, and the efficiency just dropped since it carried one less passenger.

Unless you can convince a large amount of passengers to not travel at all (and i meant not travel, rather than switch to a different mode of transport), there is no reducing carbon emissions.


> but if you didn't board that flight, the flight would still happen, and the efficiency just dropped since it carried one less passenger.

At some point, less revenue = less flights. Even dropping demand by 200 people on a route would cause a reduction in flights. It's a long way off from making a huge impact, but individuals can decide how they want to vote with their dollar and every dollar and every reduction counts.

Sure, a huge reduction in carbon emissions will probably come from a technology breakthrough, but we can help accelerate the demand for that tech by reducing demand for current carbon emitting activities.


Ah.. The "tackle the bigger fish first argument" - It's a false one: tackle all the independent paths at once because they are not linked. 2% is huge, its 1/50th of the burden. There are 250 economies worldwide, its larger than several nation states yet nation states are taking action.

You know where I got this? Gen. Groves. During the Manhattan project, asked if they should do one of two choices he said do both. This later paid back when it turned out thermal diffusion could pre enrich the feed for other techniques like the calutron and improve its efficiency.


But there are some actions that can deliver huge gains immediately (e.g., replacing coal plants by almost anything else) for a low cost (both in terms of money and reduced standard of living / reduced growth). Reducing air travel is great, but there are few alternatives and not doing it at all anymore would drastically change modern society.

A carbon tax would make that discussion moot though: It can be adjusted dynamically to follow a defined CO2 reduction schedule, and carbon savings would come from low hanging fruit first, and ultimately affect everything.


You have to weigh multiple costs, though. What's the cost of waiting to find out if the one huge gain is enough, versus the cost of doing them all right now?

It seems like a lot of the small changes with small impacts could actually cause a larger ripple effect which might end up causing the larger changes. Perhaps small changes, once accumulated, could be the key?


Have you come across any lists of what the most carbon emitting things are - on a personal level?

I’m kinda curious what difference different lifestyle choices really make. Eg going vegan for a year vs no flights for a year vs getting green electricity.


From https://en.m.wikipedia.org/wiki/Individual_action_on_climate...

""" Several scientific studies have shown that when people, especially those living in developed countries but more generally including all countries, wish to reduce their carbon footprint, there are a few key "high-impact" actions they can take such as: having one fewer child (58.6 tonnes), living car-free (2.4 tonnes), avoiding one round-trip transatlantic flight (1.6 tonnes), and eating a plant-based diet (0.8 tonnes). These differ significantly from much popular advice for "greening" one's lifestyle, which seem to fall mostly into the "low-impact" category. """

... although I have seen air travel clearly dominate car use in other sources. Obviously it depends on how you use the car and what type it is.

Also, not having children being so impactful seems to assume that emissions are proportional to population, which seems doubtful to me (haven't looked into the original sources though).


There are a few "carbon footprint calculators" out there which can give you an idea based on your lifestyle.

Here's one that looks reasonable: https://www.carbonfootprint.com/calculator.aspx. The largest share of my emissions was from flights, making up 7 tons of my 14 ton total.

So you might think the best single change I could make would be to stop flying. But the same website quotes $8/ton to offset my carbon footprint. So an even better single change would be to donate $100/year to some initiative to upgrade cooking stoves in Africa, or whatever the current best-value project is.


The Effective Altruism answer is probably to take all the energy you’d put into lifestyle changes, and put it instead into earning money to donate to environment lobbyists, so as to change corporate behavior.


Do you (or anyone else reading) have any info on the personal VS corporate proportion of the problem?

Like, how much difference does it make to do anything personally?

What's the lowest hanging fruit on corporate action?


It would be nice to have proper alternative though.


I'm completely clueless about aviation but what might it take to make aircrafts electric (if it's even possible at all)?




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: