3 ms·
Keeping in mind this is a naive analysis of the problem, here's how I think would first try tackling it: I would first presort the stops in clockwise order aro
by a-priori 18y ago
Keeping in mind this is a naive analysis of the problem, here's how I think would first try tackling it:
I would first presort the stops in clockwise order around their common centroid, then optimize it with a stochastic algorithm like simulated annealing. Assign costs separately to distance travelled, right turns, and left turns... something like 1 point per kilometer, plus 0.5 points per right turn, plus 2 points per left turn.
Anyone with more experience with optimization problems, feel free to show me up :)
- anamax 18y agoUPS has far more cost data. For example, UPS knows that turning left from Main to Elm takes 45 seconds while left from Main to 2nd takes 15 seconds. UPS knows how fast you can actually go on different streets. And, it knows how these things vary with time of day and day of week. Hmm. UPS could probably make money selling traffic and planning information.