I am using genetic algorithm to solve the multiple-traveling-salesman problem. It work fine when I have only one constraint (distance) for my fitness function: ie: the lower the total distance, the better are the chances of the individual to survive.
But now I want to add other contraints like:
time-windows: for example: salesman1 (S1) work between 9h and 17h, city1 (C1) is open between 9h and 12h and C2 is open between 11h and 13h.
capacity: S1 have a vehicle with a capacity of 10 boxes (whatever the unit), C1 wants 2 boxes and C2 will give 3 boxes.
competence: S1 have a refrigerated vehicle, S1 needs perishable goods, and so on.
Also, I consider a constraint to be soft when an individual can survive a generation (have more chances) even if it the constraint is not fully satisfied (ie: distance, time-window). Where a hard constraint must be satisfied in order for the individual to survive (ie: capacity, competence).
I am already ok with the genetic representation and the technology I should use to solve this.
So far, this is what I came up with to implement my fitness function:
For each individual:
(1) I will calculate/assign a score for each constraints separately:
1 / kmwhere
kmis the total distance traveled by each salesman
1 / secondwhere
secondis the difference in second between the actual time (when the salesman vist the city) and the city time-window, for each city
1 / boxwhere
boxis the number of over/under load of the salesman vehicles
+1for each city if the assigned salesman satisfy the required competence
(2) I will multiply each constraint score by a factor (a kind of priority, this is what makes each constraint hard or soft?)
distance score * 20
time-windows score * 20
capacity score * 30
competence score * 30
(3) Then sum all those results. This sum will be the fitness cost, the higher the beter.
- fist, am I in the right direction?
- is there recommended/general ways to implements a multi-objectives fitness functions?
- how can I make those constraints hard or soft?
- how can I prevent premature optimization or local optima (ie: all constraints are satisfied except the distance, but individuals with beter distance optimization keep dying because they perform bad in the fitness function)?
Other advices are very welcome!
PS: sorry about my choice for the tags, I do not have the reputation to create new tags, I would have tag it at least with genetic-algorithm!