I don't like workers in Civilisation games. In the late game they are pretty annoying.
As I read the posts in this thread, the problem of the roads has two important questions:
1) which way the road goes?
2) how the road is built?
Which way the road goes
There may be shortest way from the city to other city, but it may lead through a dangerous area. The player should be allowed to think about it and plan the way around. So I suggest click on the waypoints you want the road to go. Between the waypoints the game calculates the best possible road. The road does not need to end in a city, but it shall always begin in a city or start on some place, that is connected to a city (= road). The road from nowhere to nowhere is nonsense (only possibility is there was once a city, but it was destroyed).
How the road is built
Give people a good reason to go some way, the road appears. If you are a geocacher, you know, what am i talking about (a small path that ends in the centre of bushes). However a road, that is really nice and comfortable requires some effort.
So I suggest: the first level of the road is organic - small road, not too comfortable. You plan the road (see above), people and caravan will use it, but they will be slow. If you want a better road add a production in a city. Each tile will require some amount of work (and possibly some material, such as stone too). Some terrain types may require more effort than the others. The roads are built from the city to their ends. If you generate enough workpoints in the city the road on one tile is upgraded.
Road levels:
1. organic - caravans move at the half speed, the terrain type may slow them down (hills, muds etc.)
2. cart track - caravans move at the basic speed, but the terrain type may slow them down
3. improved cart track - the same as 2, but military units move 50% faster, if they follow the road.
4. paved road - 50% bonus to the speed of the military units and the caravans, the terrain type is ignored
5. improved paved road - 100% bonus to the speed of the military units, 50% to the speed of the caravans and bonus to a commerce