Adding Variation To Grid Path


I’m using a Grid Graph for pathfinding hundreds/thousands of units on a map for a strategy/simulation game. The player can place roads on the grid, and the roads are the same width as one grid cell/node.

Currently all characters follow the exact same path and walk down the center of each cell, so they appear like a chain on the road. I’d like to randomize where on the road they walk, but not so much that they leave the road itself.

I looked into the Alternative Path modifier, however this seems to route them via a different cell so they leave the road, even when the destination is straight ahead.

What would be the best (and most efficient) way of achieving this?

Thanks for the help!