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. Let there be N individuals (assume at most 5000 individuals in a practical implementation).
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. This problem appears to be NP-hard so I am not looking for a global minimum but a good solutions.
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.
Different Ways to Understand / Interpret This Problem:
Interpretation 1: Bin-Packing Problem
The goal is to find a partition of the individuals such that, within each partition, time ranges of all members overlap. The total 'weight' sum of each partition is below a certain threshold (note that no single individual will exceed the weight threshold). The total 'distance' sum (computed by summing the distance derived from each partition) is minimized. As few one individual partitions are formed.
My Impractical Approach For This Problem
Step 1: Defining an individual
Individual: Time Range: [2, 3, 4] Weight: 2 Location: -3
Step 2: Finding Potentially Time-Compatible Individuals
Imagine that a 24-hour day is defined as 24 one-hour bins. Each bin represents one hour. For example, the bin at index 6 represents 6 am. Let's call this the timetable.
We place individuals into these bins based on their time range. For example, If John's time range is [1, 2] and Wilson's time range is [2, 3], then the timetable will be populated as follows:
[  , [John] , [John, Wilson], [Wilson],  , ... ,  ]
Here, individuals in the same bin could potentially be grouped.
Step 3: Generating Viable Groups Based On Weight Constraint
Let's define the weight limit of a group to be 4.
For each bin in the timetable, we generate groups that meet the weight constraint (the sum of the weights of the individuals is below 4). Note we can skip over the bins with one or fewer individuals. Here, each group has the following characteristics:
Group: Individuals: [ Person1, Person2, ... ] Weight: INT (computed by summing weight of individuals) Distance: FLOAT (computed by finding distance sum between individuals)
We take all of the groups we generated and store them together in a list called viable_groups.
Step 4: Finding the best set of groups
We optimize the groups / partitioning by finding the set of disjoint groups such that the total distance sum is minimized.
Problem with this approach
By step 3, this approach becomes computationally infeasible because we generate all possible groups by enumeration.
Step 1: New Definition of 'Individual'
In the beginning, each individual is treated as a singleton group:
Group: members: [person1] time range: [0, 1, 2, 3, 4, 5] weight: 2 location: -3
Step 2: same as before
Step 3: sort time bins by population
Time bins are sorted by the number of singleton groups in that bin in descending order. After the sort, the time bin with the most number of singleton groups is ranked first.
Step 4: merge groups until no merge is possible
Starting with the first time bin, construct a graph such that the nodes are the groups and the edges represent the distance between two groups. An edge exists between two groups only if their weight sum does not exceed the maximum capacity. For example, let the weight threshold be 4 and consider the following singleton groups:
group1: members: [person1] time range: [0, 1, 2] weight: 1 location: -3 group2: members: [person2] time range: [0, 1, 2, 3] weight: 2 location: 0 group3: members: [person3] time range: [0, 1] weight: 3 location: 1
Notes that out of the 3 possible edges, the following edges exist:
group1 -- 3 -- group2 group1 -- 4 -- group3
This is because group2 - group3 exceeds the weight threshold of 4.
Now we find the edge with the smallest value and merge the two end nodes. After merging the two nodes, we recompute the edges based on the new set of nodes available, and we repeat until no edges exist.
In terms of the above example, we would merge group1 and group2 to obtain:
group12: members: [person1, person2] (union of members) time range: [0, 1, 2] (intersection of time ranges) weight: 3 (sum of weights) location: 1.5 (center between two locations) group3: members: [person3] time range: [0, 1] weight: 3 location: -3
Now, if we recompute the edges, we see that no edges exist. Thus, we are done with the first time bin.
Next, we remove all of the singleton groups that have members that overlap with the members in subsequent time bins. For example, in this case, if we find either group1, group2, or group3 in the subsequent, we remove those groups.
we repeat the merging process we performed on the first time bins.
We repeat this until the last time bin.
This is my approach so far, and I realize it's not the most efficient. Does anyone have recommendations for improvements? Please let me know in the comments if any part of the explanation is unclear!