Специальный случай группировки координат

Question

Я пытаюсь написать программу для размещения студентов в автомобилях для приведения в движение на мероприятие. У меня есть адреса для каждого учащегося, и я могу геокодировать каждый адрес, чтобы получить координаты (адреса достаточно близки, чтобы я мог просто использовать евклидовы расстояния между координатами.) Некоторые из студентов имеют автомобили и могут управлять другими. Как я могу эффективно группировать студентов в автомобилях? Я знаю, что группирование обычно выполняется с использованием таких алгоритмов, как K-Mean, но я могу только найти алгоритмы для группировки N точек в M произвольных групп. Мои группы имеют определенный размер и расположение. Где я могу начать? Я просто жадный алгоритм гарантирует, что первые назначенные автомобили имеют минимальную дистанцию, но, как я полагаю, средний уровень будет высоким.

Answer 1

Скажите, что вы пытаетесь свести к минимуму пройденное пройденное расстояние. Очевидно, что проблема коммивояжера - это особый случай вашей проблемы, поэтому ваша проблема NP-hard. Это ставит нас в область алгоритмов эвристики/аппроксимации.

Проблема также требует некоторой дополнительной спецификации, например, как много студентов могут поместиться в данной машине. Скажем, сколько угодно.

Как насчет того, чтобы вы разрешили его как минимальное остовное дерево, укорененное в конечном месте назначения. Тогда каждый ученик с автомобилем отвечает за сбор всех своих дочерних узлов. Таким образом, общее расстояние пробегалось не более чем на 2x общей длины остовного дерева, которое находится там непосредственно. Конечно, это смешно, потому что узлы рядом с корнем будут управлять мега-автобусом вместо автомобиля в этом случае.

Итак, вы начинаете играть в упаковочную игру, где вы пытаетесь заполнить автомобили жадно.

Я знаю, что это не решение, но это может помочь вам лучше определить проблему.

Answer 2

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

Группа студентов вместе на расстоянии. Найдите расстояние между всеми наборами двух учеников. Начните с самых близких учеников и добавьте их в группу и продолжайте добавлять до тех пор, пока все учащиеся не станут группами. Если ученики находятся за пределами порогового расстояния, например, 50 миль, не объединяйте их в группу (это приведет к тому, что несколько учеников пойдут соло). Если у студентов есть автомобили различного размера, прекратите добавлять их, когда максимальный размер автомобиля достигнут между учащимися в группе (и в зависимости от того, что вы пытаетесь добавить).

Для поиска оптимального (вы спросили об эффективном) решении потребуется более определенная проблема, которая кажется, что у вас ее нет. Если бы вы хотели устранить отдельные драйверы, хотя, взяв вышеуказанное решение и специальный корпус, выбросы, работая их индивидуально в группы и заменяя людей вокруг смежных групп, чтобы соответствовать им, могли найти очень сильное решение.