4 ms·
I'm curious how they optimized for this. Perhaps some sort of linear programming or variation of the "traveling salesman" problem?
by goodkarma 18y ago
I'm curious how they optimized for this. Perhaps some sort of linear programming or variation of the "traveling salesman" problem?
- a-priori 18y agoKeeping 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.
- rms 18y agohttp://en.wikipedia.org/wiki/Operations_research http://en.wikipedia.org/wiki/Operations_research This is one of the things that Industrial Engineers actually do. In my opinion the pay is much too low for how hard the math is. Lots of linear/dynamic programming + statistics and all sorts of fun algorithms.
- goodkarma 18y agoI know, I have a degree in it. :)