Optimizing a Parking Lot Problem. What algorithims should I use to fit the most amount of cars in the lot?

Question

What algorithms (brute force or not) would I use to put in as many cars (assume all cars are the same size) in a parking lot so that there is at least one exit (from the container) and a car cannot be blocked. Or can someone show me an example of this problem solved programmatically.

The parking lot varies in shape would be nice but if you want to assume its some invariant shape that is fine.

Another Edit: Assume that driving distance in the parking lot is not a factor (although it would be totally awesome if it was weighted factor to number of cars in lot).

Another Edit: Assume 2 Dimensional (no cranes or driving over cars).

Another Edit: You cannot move cars around once they are parked (its not a valet parking lot).

I hope the question is specific enough now.

Answer 1

Is your definition of efficiency the greatest number of parking spots in a lot of a given size and shape (assuming that each car can be driven away without moving any other car)? If so, it is a packing problem, not a knapsack problem, and it sounds NP to me, but the range of solutions for any real-world lot being so small it could be solved with an practical exhaustive search.

Answer 2

I think it may be technically NP complete. But I think that you could develop an intelligent set of solutions, each one building off of the experience with the last, and algorithmically choose a best solution from the calculated set. You may not be able to prove it is the best possible solution. But from a practical standpoint, you have an optimized parking lot, so does it really matter that given an infinite amount of time you would have squeezed 3 more cars in there?

Answer 3

This is basically equivalent to bin-packing, with the added requirement that an exit be in a particular place and all the cars can exit -- which is itself a hard problem!

So your problem is at least NP-hard.

Answer 4

Well, let's simplify/concreteify a bit. Assume that our cars are unit squares, the parking lot is N x N, and we need to enter/exit from the lower left corner. A simple pattern gets the lot almost 2/3 full with cars (shown for N=12):

+------------+
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
             |
  -----------+

I can prove that the best you can possibly do is to get the lot 2/3 full. Imagine that you build up the empty spaces by starting with a completely full garage and driving out a (currently reachable) car one at a time. Each time you remove a car, you produce up to 3 newly reachable cars, and remove one once-reachable car (now an empty space). So for every space you make, you create at most 2 more reachable cars. To make 2/3 N^2 reachable cars, you need to make at least 1/3 N^2 spaces, and that's all the squares you have. So you can fill the garage at most 2/3 full.

The simple pattern above is asymptotically optimal, as its density approaches 2/3 as N -> infinity. (Kinda boring, I was hoping some tree-looking pattern would do better.)