It's not possible to solve version 1) of the problem in general. To see why, consider a graph with 2 cities, and 2 agents, where the agents start in opposite nodes. Since both agents need to move every turn, they will never meet in the same city.
For version 2), I'm going to make some assumptions that aren't completely clear from your text:
Agents have ...
You could make the actions
Then you can declare the speed of this movement. If you want to go more in depth you can do
This will give control of the speed to the neural networkm but is harder to train, and you should give the speed of the ...