How to minimize distance traveled by n people over m locations

user_8684591 0
Viewed 306

This is a real-life problem, not homework. I'll use specific numbers in the question.

My client has a very large warehouse with 16,000 locations. They want to physically count the quantity in 200 locations, selected randomly, to verify the quantity the computer system has is accurate.

I know how to select exactly 200 locations at random (Knuth TAOCP).

The distance between locations is easy to calculate. The warehouse is arranged in aisles (like a big box store). Basically, what I learned as the taxi-cab metric (delta X + delta Y).

Assume they will assign 4 people to this task. How do I generate a list of locations for each person that will minimize the total distance traveled by the people?

For the general algorithm, the number of locations to be counted and the number of people assigned to the task would be input parameters.

To help you answer, I have decades of experience, but I am self-taught. I'm guessing this is a good problem for dynamic programming (watched the MIT lecture series recently), but have never implemented that. Stuck on forming the recursion.

Or maybe some other algortihm. It's not a ton of data points, so maybe a brute force approach?

If other tags are appropriate, please suggest them. If you care to post code snippets, any language is fine.

algorithm
2 Answers

Given the "total cost" criterion and the random scattering of the locations, I expect that the optimal path will be to have one worker cover most or all of the 200 locations; the other 3 will count only isolated pockets of inventory that pop up near the start/end point, S.

For a general attack, I recommend that you send your four workers in different directions from S. From there, take a greedy approach: find the location nearest to any of the four workers; send that worker to said point. Continue until all locations are visited. Note that you have S as both the first and last point for each worker.

Now, process each worker's route to minimize total distance traveled for that worker.

Finally, "perturb" each path. Pick a random location and remove it from its path. Re-assign it to the path with the least incremental cost for that location. Continue this reassignment until you achieve, say 1000 iterations with no change of assignment.

user_47851850

This sounds like a multiple traveling salesman problem. You can choose random locations in a preprocessing step, and add a token "starting" location.

There are a few model definition languages that will allow you to declare a formal model that can be passed to a solver. You may need a license for GAMS or AMPL. Julia's JuMP package is provides a nice and free model definition language that is pretty easy to use.

As a practical matter, you may need to minimize the max of individual travel times if the inventory checking is time sensitive.

user_45859630
Related