Graphical Genetic Algorithm

1 Get Data

We will conveniently use the same parameters and generated data from Part II. Recall system wide parameters were set to the values of :

SERVICE_WIDTH = 601
SERVICE_HEIGHT = 601
NUMBER_OF_WORKERS = 8
NUMBER_OF_JOBS = 5

1.1 Generated Jobs

jobs = [
{'site': 'j:ciweit', 'x': 405, 'y': 241},
{'site': 'j:gogo','x': 129, 'y': 116},
{'site': 'j:egre', 'x': 186, 'y': 134},
{'site': 'j:acoxec', 'x': 206, 'y': 558},
{'site': 'j:adoh', 'x': 487, 'y': 519}
]

1.2 Generated Workers

workers = [
{'name': 'amehwu-mi', 'x': 248, 'y': 170},
{'name': 'otokde-oi', 'x': 171, 'y': 482},
{'name': 'uvuhgi', 'x': 178, 'y': 309},
{'name': 'evihob', 'x': 227, 'y': 217},
{'name': 'meaf', 'x': 472, 'y': 535},
{'name': 'oosu', 'x': 573, 'y': 572},
{'name': 'iiezyi', 'x': 285, 'y': 337},
{'name': 'piakse', 'x': 140, 'y': 127}
]

1.3 Service Days

The days available for jobs to be completed by workers are defined as a list of their first character. If desired, we could limit the list to Monday through Friday. Or for more complex scheduling rules, consider 14 days. Here we consider Monday through Friday for one week.

days = [ 'M', 'T', 'W', 'R', 'F' ]

2. Encoding

2.1 Representation

This is the representation of the input data to be used in the solution process. Here, a solution is now three dimensional and describes the assignments for each worker for each day. Alternatively, the collection of each workers schedule could define a solution. We will choose the former.

2.2 Evaluation

We now have a three dimensional solution space, Worker x Job x Day. We will continue to refer to the primary objective of minimizing worker travel time, using distance as the primary metric. With additional considerations for day, we can determine the total distance traveled by each worker, to each site, for each day by :

a.) calculating the distance between each worker and each job site

b.) multiplying job-worker distances by assignment solution per day

c.) sum all resultant values of each day in the week

This resultant value indicates how good a solution is.

Alluded to in Part II, this models requires a few other constraints. Currently, there is only a penalty for not servicing a job. This may result in unbalanced work loads between workers, and now, days. As a decision maker, we will define a maximum workload per day and per week.

We will need to ensure that workers service a job only once per day. (This may seem frequent, but the time is relative. This problem could also represent weekly or monthly visits.) Violations will be scaled and added to the distance score of the solution.

Constraint violation penalty

number of jobs / week < 4 1,000

number of jobs / day < 4 1,000

number of workers / job == 1 1,000

score = sum of distances / day +
1,000*penalty1 +
1,000*penalty2 +
1,000*penalty3

3. Population

The population, is now a list of solutions, where each is a list of user-job assignments (list of lists) for each day (another list): Member x Day x User x Job. In the same way as was detailed in Part II, these candidate solutions will be evaluated, be ranked, be selected for offspring generation, generate offspring, and potentially be culled.

4. Genetic Algorithm

The primary mechanics remain the same, shown in Part I and Part II. Since a solution is now a degree larger, it is necessary to modify the crossover and mutation methods. We will still utilize the methods previously established for modifying a worker-job assignments for each day.

For discussion in this section we will refer to the worker-job assignment as a "gene". In a similar manner, we can identify a day as a "chromosome".

4.1 Updated Offspring Generation

The crossover process, the means of generating the offspring members, will still operate at a gene level. For each chromosome, for each gene position, its value will be randomly selected from either parent 1 or 2. (Thus, the offspring will result in identical chromosomal structure.)

4.2 Updated Mutations

Recall, the defined mutation methods were: randomize, clear, and flip. As the crossover progresses, there exists a possibility for gene level mutations. After selecting a parent gene to copy, the possibility of a mutation would alter the offspring's resultant values.

Conclusion

This second implementation of the genetic algorithm includes some additional considerations for handling multiple day worker schedules. Though we found a solution, we can only assume it is good. There is no guarantee because finding the optimal solution (set) in such a large solution space would take a considerable amount of time. In such a case, it would be good to validate the genetic algorithm assignment search. Comparing derived solutions with the known optimal of a smaller solution space would provide such insight. Such discussion will be reserved for another series.

The best found solution, while minimizing worker travel distance and penalties, could still use some tuning for such things as worker load balancing. The later image illustrates this. Notice that workers "otokde-oi" and "meaf" are not assigned any jobs. Conversely, workers "amehwu-mi" and "uvuhgi" have a high work load. Also, it may be preferable for workers to be consistent in working specific jobs. All considerations that would likely result in a better solution.

Jehovah. You have given us work. You have given us rest. Please help the reader to embrace both.