No; nor does it need the overhead of having to navigate through several lists to get to the desired URI when it could infer the full URI from the very beginning.

You are free to type in any URI you like. In fact, a REST client can save links (bookmarks) or cache payloads that contain these links / forms (templates). But don't expect the server to not change things. So being able to navigate is a form of resilience. For me, thats worth to have with what you call "overhead". I call it a sane tradeoff.

Inferring the URI rather than pointlessly downloading ten end points to walk the full options list every time, also seems sane; the former doesn't seem like "doing it wrong".

Caching doesn't solve the problem of "what if I want to look up the travel time between this other city and this other city via this other means".

What do you mean to look up travel times? I'd provide a resource that you can POST to and the server computes the travel time. There is no caching useful here. But way to create the request (like a form) can be provided by a document. And this document can be cached by a client.

The request will be idempotent so it shouldn't be a POST. But if it's a GET, then you're telling me I shouldn't tell the client where to put the start and end city in a request URI?

In theory you could have a query that return a list of cities and a url for each, with that url being a query to get you the second city list.

Right, which means that if I followed the REST principle (clients don't construct URIs), then every request must make an extra, unnecessary round trip for every parameter. Which sounds quite pointless.

Yes sounds like it. Plus if the option is a geo coordinate then it's impractical to list them all. I don't see the problem with meta data or assumed knowledge.