The problem:
Given the coordinates of N people on a regular 2-dimensional plane and N target points-of-interest (POI) on the same plane, determine the set of pairs of people and POIs that minimize the sum of straight-line distances between the locations in each pair. No two people can go to the same POI, and all POIs must be covered.
In other words, if I have 5 trucks that need to go to 5 locations and trucks are interchangeable, where do I send the trucks so that the least amount of fuel is used (assuming fuel use is proportional to distance traveled)?
Discussion:
Brute force would take N factorial. Is there a better way? This would seem to be a pretty common operations research problem, but my google-fu is insufficient.
Best Answer
Copying the comments to get the problem out of the unanswered problems queue, and making it community wiki.
This sounds like the travelling salesman problem. See Algorithm for an exact solution to the Travelling Purchaser Problem
This is known as the assignment problem: en.wikipedia.org/wiki/Assignment_problem - Wikipedia lists some algorithms to solve it in polynomial time.
You're right! More specifically, it is exactly the transportation problem.