genetic algorithm for car parking assignment

I have:

- a set of cars looking for parking places.

- a set of parking garage managing each a set of these parking places.

What I want is to assign cars to these parking garages while minimizing the total cost. So it is basically an optimization problem. Moreover, I have the condition that for each car, the distance between its destination and the parking garage has to be less than a certain threshold distance otherwise, it won't be accepted.

I tried to solve the problem with simulated annealing but there is nowhere to put the constraint about the threshold distance. I tried to use a penalty in the cost function (a constant big value) to not choose the solutions which do not correspond with no avail. I still get the solutions that should not be accepted.

I found that the genetic algorithm has the possibility to add constraints but I don't know how to customize it to my data. The example of traveling salesman problem is not helping me much.

http://www.mathworks.com/help/gads/examples/custom-data-type-optimization-using-the-genetic-algorithm.html?refresh=true

Any idea on how either to modify simulated annealing to support my condition (which would be the best) or how to shift to genetic algorithm.

[jgg]

Do you have any info an how your data is set-up? It's pretty easy to add constraints:

 x = ga(fitnessfcn,nvars,A,b)

if your first variable corresponds to threshold distance, you can set:

 A = [1,0,0,0...,0];
 b = [cutoff value];

More info would be helpful!

[student beginner]

I am using a matrix Distance where Distance(i,j) is the distance between car i and parking garage j and what i want is to get as result an assignment matrix Assig where Assig(i,j)=1 means car i is assigned to parking garage j

[Image Analyst]

Not sure I understand the grammar of "a set of parking garage managing each a set of these parking places" What exactly does that mean? Do you really mean "a set of parking garages where each garage manages its parking places" or do you mean something different?

[student beginner]

yes that's is it.

[MHN]

student beginner. i need your help on this. can you please give me your email address?

[Image Analyst]

Try this: Search Vision Bibliography for parking

You will find algorithms there. Pick one and code it up.

Answer 1

[Walter Roberson]

You have a discrete optimization problem: car(K) is to be allocated garage x(K), x(K) in 1 : number_of_garages, minimize sum( distance(K, x(K)) for all K, subject to the constraint that the number of cars going to each garage is less than the capacity for the garage. The cars that are too far away, set their distance to infinity -- any non-infinite value will be less than infinity so if there is even one feasible solution found then the constraints will not be violated.

[student beginner]

This is for simulated annealing, right? I have been using a cost function (which is a bit different than only the distance) basically cost(i,j)= distance(i,j) + something else. and what I what to minimize is sum (cost(i,j)) like you said. When the

distance(i,j) > min_dist,

i did put

cost(i,j)= cost(i,j)+ a_very_big_constant

but I am not getting a correct solution. Basically, I plotted the cars and the parking and although I have feasible solution, I am getting assignments where distance(i,j) > min_dist despite the fact that I can see there are choices where distance(i,j) < min_dist.

What value should I put to represent infinity? or is something wrong with my approach?