combinatoric grouping optimization problem based on time interval overlap, weight constraint, and distance minimization

Question

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

Note:

• 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.

Interpretation 2:

See Below

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.

OUTDATED

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.

UPDATE:

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!

Answer 1

Okay, I will attempt to give a new approach. Note that I am not sure to understand all features and issues. Moreover, the most adapted strategy probably depends strongly on data.

Assumptions

I make the following assumptions, i can eventually adpat my answer if one is wrong.

• there are $N$ persons to group ($N \approx 1000-5000$)
• each person $p$ has a time range (soonest to latest $[S[p], L[p]]$) which may not be discrete but is not interrumpted. So $p$ is available for any $t$ in $[S[p], L[p]]$.
• each person $p$ has a weight strictly positive ($W[p] > 0$).
• each person $p$ has location value $P[p]$
• in a group, all persons have to share a time lapse of at least $dt$
• the total weight of a group should not be greater than $w_{max}$

The number of person alone should be minimized. Then the total distance in group should be minimized $D = \sum_{grp} max_{p \in grp}(P[p])-min_{p \in grp}(P[p])$.

Build the meeting graph

So you should indeed first build a graph $G(v, e)$ where each person is a vertex and an edge between two persons means they can be in the same group. This is of course an undirected graph. The weight of the edges $d$ represents the distance between the two persons

So let's sort persons with increasing soonest time $S$. Then you can find simply all the edges of the graph with this algorithm:

for p from 1 to N:
    for k from p+1 to N:
        if L[k]-S[p] > dt:
            break
        if W[k]+W[p] < w_max:
            add edge (k, p) of weight d=|P[k]-P[p]|

In this graph $G$, a group has to be a clique respecting weight constraint. The distance of the group is the maximum edge of the clique.

Start grouping

Your structure for groups should be a list $groups$ of list containing element in each group (initially empty) and an array $G[p]$ giving for each $p$, -1 if it is not grouped, else the index of the group of $p$ in $groups$.

For better performances, you can also track the distance and the total weight of each group.

Now loop on persons $p$, if $p$ is alone try to group it else continue.

Let's consider all neighbors $k$ of $p$ in $G$ and find the move that minimize the distance increase $\Delta D$:

• If $k$ is alone ($G[k] = -1$), you can group up $k$ and $p$, the cost in distance is the edge weight $\Delta D = d$.

• If $k$ is already grouped, check if $p$ can be added to $groups[G[k]]$, it should have an edge to every element and the total weight should not pass $w_max$:

  • if it is possible, You can compute the $\Delta D$ of such grouping which can be 0.
  • else if only one element prevent $p$ from coming consider re-assigning it (see below)
  • else just ignore this group.

Re-assignment

The idea is to do something like in Hungarian algorithm. You can first ignore to make the algorithm run without, but it may increase performances especially to reduce the number of isolated element.

When an element $p$ should be re-assigned, you start building a tree with this element being the root. This tree explores the possibilities of re-assignment. So $p$ cannot join some groups because it does not share any time lapse with one of the elements of the group or because weight would pass threshold.

List all the elements $e_i$ of the group that would let $p$ join if removed. Add all the $e_i$ to the tree as children of $p$. In the tree the edges are indexed with the $\Delta D$. Then for each $e_i$, look for the assignment leading to the lowest $\Delta D$. It may recursively ask for a new re-assignment, making you looking deeper in your tree.

An important point, is that in your recursions, you may encounter again a person which is already in the tree. Keep only the lightest path to it. At the end keep the all the path root to leaf that minimize the total $\Delta D$. All edge of this path is a re-assignment you actually do.

Annealing

Now, you obtain some grouping which is probably not optimal. You can try to do some annealing to improve the state. For instance, break some of the groups with the largest distance and try to assign their elements again.

Example

Some illustration of the method.

You want basically to assign $p$ here. The nodes are the person with blue edge between them if they share a time slot. The edge is red if it is selected to make a group. The values in the nodes are the index of the person but also their location value (just to make this example clearer), weights are not a problem in this example. The location of $p$ is 0.

So we build the assignment tree for $p$. $p$ is the root and it can either go with $6$ to form a new group ($\Delta D = 6$), either go in {$1,2,5$} group but $5$ has to be removed from the group ($\Delta D = -2$).

So add 5 in the tree and investigate on what $5$ can join instead. It can go in {$3, 4$} group removing $4$ ($\Delta D = 1$). And $4$ finally may join $6$ ($\Delta D = 2$). You found node $6$ again but with a lightest distance (total $\Delta D = 1$).