Разделите группу на две части на основе минимально возможного расстояния - PullRequest
Новая
       7

Разделите группу на две части на основе минимально возможного расстояния

0 голосов
/ 02 марта 2019

Я пытаюсь разделить группу из 80 человек на две части.Каждой группе придется отправиться в определенное место.Я пытаюсь разделить группу так, чтобы люди путешествовали как можно меньше.Меня интересует наименьшее общее время в пути, но я также хочу, чтобы оно было сбалансированным, чтобы у нас не было нескольких человек, путешествующих очень далеко, даже если это означает, что у всех остальных будет более короткое расстояние.

Мойданные выглядят примерно так: 

-------------------------------------------------------------
|        Person       |    Distance 1    |    Distance 2    |
|---------------------|------------------|------------------|
|       Person 1      |      0:56:52     |      1:23:50     |
|---------------------|------------------|------------------|
|       Person 2      |      0:42:55     |      0:22:45     |
|---------------------|------------------|------------------|
|       Person 3      |      1:32:35     |      2:23:02     |
-------------------------------------------------------------

Я хотел бы добавить еще один столбец с буквой «А» или «В» в зависимости от того, в какую группу они должны быть помещены. Люди должны быть равномерно распределены междудве группы, чтобы минимизировать квадрат времени прохождения .Я знаю, что может быть какая-то математическая оптимизация, но я просто не знаю, как это сделать.Я использую питона (панд).

1 Ответ

0 голосов
/ 04 марта 2019

Вы можете смоделировать математическую задачу следующим образом.

http://mathb.in/31885?key=216f0d8271c8a65ecbce2faff12735042a4b7684

где x_i равно 1, если путешественник i назначен группе 1, и 0, если назначен группе 2. расстояние дляпутешественник i для группы 1 - это d, а для группы 2 - это d '

Тогда вы можете использовать целочисленные решатели, такие как gurobi / pulp, чтобы выполнить вычисления в python.

Возможны и другие формулировки, в зависимости ото том, как вы определяете "сбалансированный".Я предполагаю, что квадрат общего времени в пути даст вам тот вид разделения, который вы хотите.Вы можете решить эту проблему и посмотреть, нравится ли вам решение, которое вы получаете.Но, возможно, есть и другие формулировки, которые вы можете иметь для баланса.Одним из примеров может быть: «Максимум, что один путешественник должен путешествовать, меньше некоторого« D_high ». В этом случае вы добавите ограничение, например x_i d_i + (1-x_i) d'_i <= D_high </p>

Это сравнительно небольшая проблема для большинства современных решателей, и вы должны получить ответ в считанные минуты.

РЕДАКТИРОВАТЬ: Только что понял, что целлюлоза / gurobi являются линейными решателями. Если вы используете квадрат в качестве цели, которая не является-линейное целое число, и вы больше не можете использовать gurobi / pulp. У вас есть два варианта:

  1. Придерживайтесь нелинейной формулировки и используйте cvxpy (выпуклая оптимизация с открытым исходным кодом, имеет поддержку целых чиселпеременные, насколько я помню)

  2. Перейти к линейной формулировке, где ваша цель - только сумма расстояний, а не квадратная сумма. И наложить линейное ограничение, как я упоминалдо x_i d_i + (1-x_i) d'_i <= D_high, чтобы наложить ограничение на некоторую справедливость </p>

...