First off, the roaming legendaries only move to a different route when you move to a different route through an outdoor path. If you go through doors to get to another route then they don't move, for example going through a "city gate" or a cave.
In my experience, when you switch routes "outdoors" they normally move to an adjacent route, but occasionally jump to a random place on the map. However, if you move into the route they are currently on (outdoors) then they always jump to a random place. Similarly, flying to whatever route they are on makes them jump to a random route.
So to encounter them you need to go back and forth between a route boundary until they have moved closer, then see if you can get to them via city gates or caves.