Approach to algorithm for assignment of resources

Question

We have a requirement to be able to match people with locations based on availability and certain conditions.

Let's say I have a group of people each with 3 types of things they may need to park. A car, a truck and a boat. Each person also indicates their preferred parking location (choices 1, 2 and 3).

I also have a list of parking locations which can handle a certain number of each of those things. The goal is to match everyone up so that we maximum usage. The main requirement is that each individual person has to be able to park everything in the same location OR they don't get to park at all.

Example:
Starting with the parking locations I have:

Lot    Cars    Trucks    Boats
A       2       0         2
B       2       1         3
C       0       5         0

For people I have:

Person    Cars    Trucks    Boats    Choice 1  Choice 2  Choice 3
Tom        2       1         0         A         B         C
Betty      1       0         1         B         C         A
Sam        0       2         0         C         A         B
Pat        3       2         1         A         C         B

My initial thought is to simply sort the people by the number of items they have (largest to smallest). Then attempt to place each one based on choice. IE: I'd try to place Pat first (most items), but couldn't because no lot meets the requirements. Then I'd try Tom, who would go into Lot B. Etc.

Do you know of any issues with that approach?

Bonus points: is there a name for this type of problem?

Answer 1

It's not quite that simple. You'd have to do backtracking in the cases where one person matches multiple lots. Let's say you have the same lots, but the following people:

Person    Cars    Trucks    Boats    Choice 1  Choice 2  Choice 3
Adam       2       0         1         B         A         C
Eve        1       1         0         B         C         A

Adam could fit into B or A, so you let him have his first choice: B. Now Eve can't fit anywhere, even though if Adam was in A, she could fit in B. So you need a means of backtracking to make a different choice for Adam. It's also possible for the ideal solution to not allow someone with the largest request, even if they fit, so you need to take that into account as well.

I don't know if there's a well-known name for this exact problem. The most common name I see for the general problem is "resource allocation."

Answer 2

This seems like a variant of the Knapsack problem however instead of having a single bag you have several and each item has a preference about which bag it belongs to. Consult your local Computer Science department for confirmation.

If it is a Knapsack problem variant then you're into NP-Complete territory in terms of complexity. Which means pragmatically you're looking at an optimisation problem, so find the solution that is as close to optimal as possible.

Answer 3

How about something like this:

Create a list of Lots lots.  
Sort this list by the number of resources (cars + trucks + boats)

While lots is not empty:  
    Lot next_lot = The lot that has the least amount of resources.  
    Find the Person person who fits in this lot and takes up most of its resources.  
    Place person into next_lot.  
    Remove next_lot from lots.

I would imagine that this would minimize fragmentation.