14 ms·
Ryanair, Hamiltonian Cycles, and using graph theory to find cheap flights (2018)
- huron 7y agoNice 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.
- polishdude20 7y agoYeah 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.
- semi-extrinsic 7y agoYeah, no point in going via an extra city if you're not going to stay there for at least a day!
- deepnotderp 7y agoCouldn't you just add time as another dimension?
- eltados 7y agoLike the idea ! Wouldn't using the data of something like https://www.skyscanner.net/ https://www.skyscanner.net/ give you better data, across multiple airline
- polishdude20 7y agoDo 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!
- jonluca 7y agoI 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.js https://github.com/jonluca/blog/blob/master/js/ryanair-graph...
- beatthatflight 7y agoI'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!
- jjcm 7y agoI 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.
- beatthatflight 7y agohmm, 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.
- skeletonjelly 7y agoAlways enjoy your posts on OzBargain!
- beatthatflight 7y agothanks, I appreciate it! Nice to hear it helps.
- fireworks10 7y agoSimilarly, https://skiplagged.com 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.
- Analemma_ 7y agoThis is a dangerous gamble though. Airlines can and do ban people for life when they discover this.
- ghaff 7y agoThat 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.
- Scoundreller 7y agoThe other gamble being that many airlines oversell flights and may “upgrade” you to a direct flight to your paid destination.
- ghaff 7y agoIt'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.
- daenz 7y agoTake a look at https://amoffat.github.io/held-karp-gpu-demo/ https://amoffat.github.io/held-karp-gpu-demo/ It can easily solve 16 nodes in under 50ms by running in WebGL
- aberforth123 7y agoOr we stop promoting flights at all, cheap or expensive, just an idea to keep CO2 levels down.
- xxpor 7y agoAll of aviation contributes 2% of CO2 emissions. We have bigger fish to fry.
- jonplackett 7y agoHave 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.
- svara 7y agoFrom https://en.m.wikipedia.org/wiki/Individual_action_on_climate_change 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).
- derefr 7y agoThe 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.
- landgenoot 7y agoI 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 https://github.com/landgenoot/airtrip-finder
- sphix0r 7y agoWe (me and a friend) did something similar for multi city round trips within Europe (https://tripchemy.com 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=5&length=7 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 https://github.com/Whazor/Roundtrip
- samschooler 7y agoIs 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?
- giansegato 7y agoSkyscanner does support multiple trips, doesn't it?
- sphix0r 7y agoThe 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?
- woutr_be 7y agoI'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?
- sphix0r 7y agoWe crawl the fare information ourself from the airlines'websites.
- 7y ago
- 3xblah 7y ago"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) https://en.wikipedia.org/wiki/OAG_(company)
- notahacker 7y agotbf, 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.
- 3xblah 7y agoDo 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.
- deleted 7y ago[deleted]
- zulln 7y agoNot as cool, but https://www.eightydays.me/ https://www.eightydays.me/ is really convenient to book multi-city trips intra-europe.
- jonas21 7y ago> 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.
- derefr 7y agoThe 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.)
- lotsofpulp 7y ago> 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.
- smogcutter 7y agoI 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.
- 7y ago
- boultonmark 7y agoOr just use the extraordinary product https://www.kiwi.com https://www.kiwi.com
- dzhiurgis 7y agoWhat 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...
- alteria 7y agoWell 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.
- dzhiurgis 7y agoYep 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...
- hncommenter13 7y agoOne 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-complexity/ITA-software-travel-complexity.pdf http://www.demarcken.org/carl/papers/ITA-software-travel-com... [1] https://news.ycombinator.com/item?id=4639490 https://news.ycombinator.com/item?id=4639490
- kilotaras 7y agoFind 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.