If this was not frowned upon on StackOverflow, the correct answer would recommend a commercial API.

That said, if I were to implement this from scratch, I would not start with a positive list of cities. Rather, I would implement a couple of patterns like: "from X to Y", "X to Y", ""to Y from X".

But invariably there are going to be ambiguities. How do you deal with a city called "from to" :-D? How to you parse "from from to to to from"? I'd probably tokenize it using place lists, like

    "from (from to) to (to from)"
    "from (from to) (to to) from"
    "from from (to to) to from"
    ...

and then, maybe assigning probabilities to each parsing, decide that the first one is most likely.

A side comment, for someone like me who isn't an NLP expert, it seems strange that there are no libraries that let me parse a string accoring to some rules in all possible ways (like a tree) and pick the one that is most probable. I'm sure this exists, but it is hard to search for...