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?
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.
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".