Let each element be an individual. Consider that an individual is defined such that each individual has a time range, weight, and location.
The goal is to group together individuals whose time ranges overlap while ensuring that, within the group, the sum of the weights of the individuals do not exceed a certain threshold. At the same time, it is desirable to minimize the total distance between the individuals in the group. As many individuals as necessary can be placed into a group as long as the weight constraint is met.
The goal is to have as many individuals grouped (that is at minimum paired) as possible while minimizing the total distance between individuals in groups.
For example, consider an example in the discrete time case where there are ten time intervals. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. The weight threshold is 4 and the location of the individuals are points on the 1-D line of integers. Say that we have the following individuals:
A: time range: [1, 2, 3] | weight: 1 | location: 1 B: time range: [2, 3, 4] | weight: 2 | location: 2 C: time range: [4, 5, 6] | weight: 2 | location: -3 D: time range: [4, 5, 6] | weight: 3 | location: -3
- A and C cannot be grouped because they do not have overlapping time ranges.
- grouping together A and B gives is preferable to grouping together B and C because A and B are closer together.
- C and D cannot be grouped because the sum of their weights exceed 4. Does any one have a recommended algorithm for solving a problem like this?
I’ve looked at the examples in (Studies in Computational Intelligence 666) Michael Mutingi, Charles Mbohwa (auth.) – Grouping Genetic Algorithms_ Advances and Applications-Springer International Publishing (2017). However, none of the grouping algorithms seem very fitting.