1. Make roads cost travel weariness
2. Make roads randomly stomp unpaved tiles between signposts as they are traversed, so a stomped trail would appear over time, the same event can remove vines.
3. Make stomped roads cost less travel weariness
4. Make paved roads cost even less travel weariness, heavily used roads will be easier to pave because they will be already stomped
Since vines will be created and removed randomly sometimes paving will decay. That would require people to periodically walk the road and check the condition of paving. Unmaintained but used roads will evolve towards dirt roads.
Loading maps is a problem. Possible solution is to count uses for each road globally and individually per map. Difference between two counters is the number of traverses that should be applied to a map when it is loaded. In other words for each road on the map, the map will remember what was the global counter value when it was recently updated.