I'm using Genetic Algorithm to create a rota for home-care organisation. All the groundwork is complete, I'm getting the results, but results are not as good as expected. If I calculate fitness for existing rota made by somebody, I get about £6000 (I measure fitness in money - great point for management).
When I run my GA, the best I manage to get is £8K after about 30K generations. So I know the better solution exists and I'm trying to get better result. I have tried different approaches - big population, small population, different number of crossover points, swap-mutation, random-mutation, hill-climber-mutation. And nothing improved the results.
The resulting curve looks like this:
I can run GA much longer, but it does not give me any better results - the curve is just flat horizontal to the right.
I figured that I get quite a lot of duplicated individuals in final population. And that slows down the improvement of the solution. I learned how to find duplicate individuals. But what do I do with them? I have tried replacing them with randomly created solutions, but usually their fitness is much worse then every body else in the solution space, so they get "killed" quite soon without giving any offsprings or other influence to the solution space.
Any ideas/suggestions/papers will be highly appreciated, as I've run out of ideas and research papers and almost no time left.
UPD: some description of the problem: There are number of visits(shifts) that are located in different geographical places (distances between locations are known). Currently I work with 700 visits per week with durations from 30 minutes to 5hrs. There are workers with different levels of contractual arrangements: some have 0 contracted hours - relief workers, there are part-timers and full-timers. I need to allocated workers for every shift in a best possible manner with this factors in mind:
- Minimise travel distance for workers. When they have number of shifts in a day, the locations should be roughly in the same area
- Workers should not do a lot of overtime hours
- Workers should not work less than their contract says
- Workers with 0-contracts should be allocated no or very limited working hours
- Minimise waiting time between shifts. So no situations when somebody starts one visit at 9am to 10am, and next visit is at 6pm.
- There is a limit of total number of hours that can be worked per day
- There is a minimum of working hours per day: nobody should be deployed for only 30-minute visit and no other visits per day.
- At least 2 days off allocated for anybody, but can be more
- At least 2 days off must be adjacent.
And other minor fitness function adjustments. I hope this is sufficient for description.