Maybe more complex roads with need to choose not only order of the cities but also order of the crossroads. And maybe some roads would occasionally be blocked by bandits or angry folk? Hard to say!
