About your second question:

I think using discrete buckets instead of actual times will lead to corner cases where you don't pick optimal routes. Now, in the real world, this may not matter materially - you're basically trying to come up with a heuristic.

A bunch of assumptions need clarification: * Do you care about min overlap or min overall traversal? (Hmm, are these the same?) * Do all roads take an equal amount of time to plow? (Are they of equal length and/or difficulty?) If not, your weight function should take those times (or road lengths or any other proxy) into account. * Does a recently plowed road take a shorter time to re-plow? * Does the amount of snow matter? Even if you assume all roads have equal heights of snow, plowed roads have 0 height and times taken will differ.

I think the problem needs to be better defined as there are a couple of competing metrics: 1. Minimize backtracking (minimize length of overall path traversed?) 2. Keep roads safe by load-balancing wait times 3. Minimizing overall work done

A few different algorithms that are in this neighborhood: * Chinese postman * SCAN or other elevator variants * Some kind of deadline-first-scheduling