Show HN: Performant intracontinental public transport routing in Rust

Show HN: Performant intracontinental public transport routing in Rust(github.com)

167 points by ellenhp 1 year ago | 24 comments

I made a public transport route planning program that's capable of planning journeys across Europe or North America! There's only one other FOSS project I know of (MOTIS/Transitous) that can do transit routing at this scale, and in the testing I've performed mine is about 50x faster. I've spent a few weeks on this project now and it's getting to the point where I can show it off, but the API responses need a lot of work before they're usable for any downstream application.

Example query (Berlin to Barcelona): https://farebox.airmail.rs/plan/52.5176122,13.4180261/41.380...

There are some bugs still. Notably, it's not capable of planning the return trip for this route, nor the reverse of the trip from Seattle to NYC that I gave in the blog post.

Blog post: https://blog.ellenhp.me/performant-intracontinental-transit-...

Repo: https://github.com/ellenhp/farebox

Side-note but in the past some have criticized my writing style and it's been a bit hurtful at times but if you have constructive feedback on the blog post I'd appreciate it. I'm trying to get better at writing. :)

danielhep 1 year ago |

My day job is OpenTripPlanner work, so I absolutely love to see this. I've long thought about what a RAPTOR engine would look like written in Rust. So cool that you've done it. You should share this in the OTP Gitter chat if you haven't already, the people there would love to see it. I wonder if this would be small enough to run on a phone? I have thought about offline trip planning on a phone, but running OTP is out of the question as a graph can be gigabytes and take minutes to load.

ellenhp 1 year ago | |

It's after midnight here so take this with a grain of salt but the generated timetable for the puget sound is taking up about 40 MiB on-disk and the server process is using 100k of RAM I think. Most of the timetable is zero-copy so it can be memory mapped on a platform that supports it. So yes, I think it would run on a phone. See also mobroute, which powers Transito

https://git.sr.ht/~mil/mobroute

https://git.sr.ht/~mil/transito

danielhep 1 year ago | | |

Just curious, are you based in the Puget sound? I'm in Seattle so it would be a funny coincidence.

MaBu 1 year ago | |

I'm not sure how they do it, but Rail planner app for interrail has fully offline train planner.

https://www.eurail.com/en/plan-your-trip/rail-planner-app

tristramg 1 year ago |

Hello,

Great work :) Nice to see alternatives poping up. There used to be navitia https://github.com/hove-io/navitia/ but its company is slowing closing thing, so I would not bet on it for the future.

I’m a co-maintainer of gtfs-structures, if you have any feedback using that crate I’ll be glad to hear from you (specially since you consume a lot of different gtfs, you must have tripped on some issues).

Just out of curiosity, did you consider other algorithms, like CSA? It’s been a while I’m out of the algorithmical stuff, so I’m just wondering pros and cons of different algorithms.

altilunium 1 year ago |

So, how do I add a new public transport route (so it can be indexed in Farebox)?

I tried entering some coordinates as input, but it returned an empty array instead. I’m wondering if this means there’s currently no public transport route added around that location.

arcticbull 1 year ago |

Love this. I really enjoy seeing people build tooling and infrastructure around public transit.

[edit] As someone who reads and writes (and reviews) a ton of writing and technical documentation -- and is very picky about it -- there is nothing at all wrong with this writing style. Literally my only nit is consider incorporating URL shortening, I always bristle at %20 in URIs. Especially ones that wrap.

miniBill 1 year ago |

Where do you get your feeds from? In my experience finding good feeds is the hardest part of working on these projects

epcoa 1 year ago |

This is very cool.

But, bus from New York to St Louis and then backtrack on Amtrak. Ouch. I know the train options from NYP to CHI are slow, but I didn’t think they’re that slow (they’re not)! Nevermind having to take a greyhound for 1000 miles.

ellenhp 1 year ago | |

Yeah I strongly suspect that there's something in the GTFS spec that I'm missing that's resulting in some vehicle journeys not being added to the timetable. This would also explain why it completely fails to find routes on the return trips for some of the examples. I'm still pretty stoked about it and hopeful I'll get the bugs ironed out. :)

edit: also if you look at the Berlin to Barcelona trip you'll see a bus, which makes no sense to me whatsoever, so I suspect that some of the high speed rail trips didn't make it from the GTFS feed into the packed timetable that I'm serving itineraries from.

yorwba 1 year ago | | |

Yeah, Deutsche Bahn can find a route from Berlin Jannowitzbrücke to Barcelona Sants that takes less than 20 hours (as opposed to 2 days) https://www.bahn.de/buchung/fahrplan/suche#sts=true&so=Janno...

Hopefully, the existence of a black-box oracle makes it easier to find out where the gaps are.

wffurr 1 year ago |

Regarding getting better at writing, there was a post recently on improving technical writing, ostensibly about shell scripts to detect passive voice, but it also had a list of recommendations: Style: The Basics of Clarity and Grace as an alternative to Strunk and White, the Chicago Manual of Style, and A Manual for Writers of Research Papers, Theses, and Dissertations specifically for technical writing.

https://news.ycombinator.com/item?id=42407250

ekidd 1 year ago | |

Style: The Basics of Clarity and Grace is an excellent book. I picked it up ages ago, and rather liked it.

A lot of writing advice out there is... weird. There seem to be a couple different varieties. One is "first year university students do X too much, so nobody should do X at all!" This advice is usually "directionally correct" for many writers, but it shouldn't be taken as an absolute. The book Style offers better balanced versions of much of this advice. For example, it shows several examples of when the passive voice can actually increase clarity.

The other bit of weirdness in English-language writing advice goes back several centuries. There was supposedly an "arms race" of grammar advice, where each writer tried to ban more things than the next. The result of this was a bunch of rules that nobody has ever actually followed. Strunk and White is notoriously guilty of this. E.B. White was an excellent writer, but he routinely ignored the rules he proposed. Sometimes he ignored the rules on the very page where he proposed them! This kind of constantly-ignored advice is suspicious, because writing advice should ultimately be based on the common practices of well-respected writers, not on "zombie rules" that have been passed down for centuries without ever having been obeyed.

One good source for telling the "zombie rules" from the useful ones is Merriam-Webster's Dictionary of English Usage. This categorizes advice into rules that good writers actually obey consistently, rules which affect how formal your writing feels, and rules which have no basis in actual practice.

Weirdly, this tendency towards "zombie rules" may be less of an issue in other languages. For all that English-speakers love to make fun of the Académie Française, the Académie's grammar advice seems to be a lot more evidence-based, or at least focused on the well-established differences between spoken and written French.

karussell 1 year ago |

> because last I checked it only works for a single GTFS feed.

(minor) fyi: It works with multiple, comma separated GTFS files.

ellenhp 1 year ago | |

I think my info might be old then! I went and found where I learned that: https://discuss.graphhopper.com/t/does-graphhopper-gtfs-not-...

I may also be conflating inter-agency routing with ingestion of multiple feeds.

DennisL123 1 year ago |

Love it

sebosp 1 year ago |

Wow this is super cool! Will you use something to draw this on a map? If so what? Is it the same data format available in Europe and North America? What is something you suspected was going to be trivial and turned out to be extremely difficult?

kurokawad 1 year ago |

The fact that the software being written in Rust is supposed to be valuable information to be put in the title is interesting.

Nobody would say “Performant intracontinental public transport routing in C++”, or any other combination. It’s just something around the Rust language.

schmichael 1 year ago | |

A quick search of “c++” on HN shows many C++ related posts explicitly mention the language. I would assume many other language specific posts also name the language they’re using to save uninterested parties a click. There’s really nothing particularly interesting about this: it’s a fairly natural pattern in a multilingual community like HN.

littlestymaar 1 year ago | |

> Nobody would say “Performant intracontinental public transport routing in C++”

Turns out people do, actually: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

Obviously it's rarer with C++ than with Rust, but it happens in the same proportion with pretty much every language when its on a popularity boom (we've seen that with JavaScript a decade ago, then Go and python, now Rust).

IshKebab 1 year ago | |

Well, aside from the fact that people do say "in C++"... the fact that it is written in Rust is novel. Rust is still quite a lot less common than C++.

If you were reading an article about a concrete bridge you wouldn't expect "New bridge built out of concrete!" would you? But "New bridge built from 3D printed stainless steel!" is a perfectly reasonable title.

timeon 1 year ago | |

> Nobody would say “Performant intracontinental public transport routing in C++”

Why would you post this before checking?

https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...

Even without checking it makes sense to post "written in C++" (same as written in Rust).

I wonder if some people are lazy to think or just driven by emotions.

TheSisb2 1 year ago | |

It depends on a number of factors, one of which is how the authors perceive the work. Does it stand on its own merits or is it interesting because of the technical decisions? Sometimes it starts as a technical exploration and outgrows itself faster than the author can come to terms with the magnitude of the work.