Пусть каждый элемент индивидуален. Учтите, что индивид определен так, что у каждого человека есть диапазон времени, вес и местоположение.
Цель состоит в том, чтобы объединить людей, чьи временные диапазоны перекрываются, при этом гарантируя, что в группе сумма весов людей не превысит определенный порог. В то же время желательно минимизировать общее расстояние между людьми в группе. В группу может быть включено столько людей, сколько необходимо, при условии соблюдения ограничения по весу. Пусть будет N индивидуумов (в практической реализации предположим не более 5000 человек).
Цель состоит в том, чтобы как можно больше группировалось (как минимум, в паре) групп, при этом сводя к минимуму общее расстояние между людьми в группах. Эта проблема, кажется, NP-трудная, поэтому я не ищу глобального минимума, но хороших решений.
Например, рассмотрим пример в случае дискретного времени, когда существует десять временных интервалов. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Порог веса равен 4, а местонахождение людей - это точки на 1-й строке целых чисел.
Скажем, что у нас есть следующие лица:
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 и C не могут быть сгруппированы, потому что они не имеют перекрывающихся диапазонов времени.
- Группировка A и B дает предпочтительнее, чем группировка B и C, потому что A и B. ближе друг к другу.
- C и D не могут быть сгруппированы, потому что сумма их весов превышает 4.
У кого-нибудь есть рекомендуемый алгоритм для решения такой проблемы?
Я смотрел на примеры в (Исследования в области вычислительной разведки 666), Майкл Мутинги, Чарльз Мбохва (авт.) - Группировка генетических алгоритмов_ Достижения и приложения - Springer International Publishing (2017). Однако ни один из алгоритмов группировки не выглядит очень подходящим.
Различные способы понять / интерпретировать эту проблему:
Интерпретация 1: Проблема упаковки в бункер
Цель состоит в том, чтобы найти раздел индивидов таким образом, чтобы в каждом разделе временные интервалы всех членов перекрывались. Общая сумма «вес» каждого раздела ниже определенного порога (обратите внимание, что ни один человек не будет превышать порог веса). Общая сумма «расстояния» (рассчитывается путем суммирования расстояния, полученного из каждого раздела) сводится к минимуму. Как только несколько отдельных разделов образуются.
Интерпретация 2:
См. Ниже
Мой непрактичный подход к этой проблеме
Шаг 1: Определение личности
Individual:
Time Range: [2, 3, 4]
Weight: 2
Location: -3
Шаг 2: Поиск потенциально совместимых по времени лиц
Представьте себе, что 24-часовой день определяется как 24-часовые корзины. Каждый бин представляет один час. Например, корзина с индексом 6 представляет 6 утра. Давайте назовем это расписанием.
Мы помещаем людей в эти корзины в зависимости от их временного диапазона. Например, если диапазон времени Джона равен [1, 2], а диапазон времени Уилсона - [2, 3], то расписание будет заполняться следующим образом:
[ [] , [John] , [John, Wilson], [Wilson], [] , ... , [] ]
Здесь можно сгруппировать людей в одной корзине.
Устаревшие
Шаг 3: Создание жизнеспособных групп на основе ограничения веса
Давайте определим предел веса группы равным 4.
Для каждого бина в расписании мы генерируем группы, которые соответствуют весу
ограничение (сумма весов лиц ниже 4).
Обратите внимание, что мы можем пропустить корзины с одним или несколькими лицами. Вот,
каждая группа имеет следующие характеристики:
Group:
Individuals: [ Person1, Person2, ... ]
Weight: INT (computed by summing weight of individuals)
Distance: FLOAT (computed by finding distance sum between individuals)
Мы берем все созданные нами группы и храним их вместе в
список называется viable_groups.
Шаг 4: Поиск наилучшего набора групп
Мы оптимизируем группы / разбиения, находя множество непересекающихся
группы, такие, что общая сумма расстояния минимизирована.
Проблема с этим подходом
К шагу 3 этот подход становится невозможным в вычислительном отношении, потому что мы
генерировать все возможные группы по перечислению.
UPDATE:
Шаг 1: Новое определение «Индивидуальный»
В начале, каждый человек рассматривается как единая группа:
Group:
members: [person1]
time range: [0, 1, 2, 3, 4, 5]
weight: 2
location: -3
Шаг 2: тот же, что и раньше
Шаг 3: сортировка временных интервалов по населению
Временные интервалы сортируются по количеству одноэлементных групп в этом интервале в порядке убывания. После сортировки временной ряд с наибольшим количеством одноэлементных групп занимает первое место.
Шаг 4: объединить группы, пока объединение невозможно
Начиная с первого временного интервала, постройте график таким образом, чтобы узлы были группами, а ребра представляли расстояние между двумя группами. Ребро существует между двумя группами только в том случае, если их весовая сумма не превышает максимальную вместимость. Например, пусть пороговое значение веса равно 4 и рассмотрим следующие одноэлементные группы:
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
Отмечает, что из 3 возможных ребер существуют следующие ребра:
group1 -- 3 -- group2
group1 -- 4 -- group3
Это потому, что group2 - group3 превышает весовой порог 4.
Теперь мы находим ребро с наименьшим значением и объединяем два конечных узла. После объединения двух узлов мы пересчитываем ребра на основе нового набора доступных узлов и повторяем, пока ребер не существует.
В приведенном выше примере мы объединили бы group1 и group2 для получения:
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
Теперь, если мы пересчитаем ребра, мы увидим, что ребер не существует. Итак, мы закончили с первым тайм-бином.
Далее мы удаляем все одиночные группы, члены которых перекрываются с участниками в последующих временных бинах. Например, в этом случае, если в последующем мы найдем group1, group2 или group3, мы удалим эти группы.
мы повторяем процесс слияния, который мы выполнили для первых временных интервалов.
Мы повторяем это до последнего раза.
Это мой подход, и я понимаю, что он не самый эффективный. У кого-нибудь есть рекомендации по улучшению? Пожалуйста, дайте мне знать в комментариях, если какая-либо часть объяснения неясна!