genetic algorithm for car parking assignment

2016 3 8
1 个回答
更新时间：2018 12 26
12 次查看（30 天）

0 个投票

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.

6 个评论
显示 4更早的评论 隐藏 4更早的评论

jgg
jgg 2016-3-8
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
student beginner 2016-3-8
编辑：student beginner 2016-3-8
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
Image Analyst 2016-3-8
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?
MHN
MHN 2018-12-26
编辑：MHN 2018-12-26
student beginner. i need your help on this. can you please give me your email address?
Image Analyst
Image Analyst 2018-12-26
Try this: Search Vision Bibliography for parking
You will find algorithms there. Pick one and code it up.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Walter Roberson
Walter Roberson 2016-3-8

0 个投票

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.

1 个评论
显示 -1更早的评论 隐藏 -1更早的评论

student beginner
student beginner 2016-3-8
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?

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Direct Search 的更多信息

产品

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by