Особый случай группировки координат

Question

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

Answer 1

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

Задача также нуждается в дополнительных уточнениях, например, сколько учеников может поместиться в данном автомобиле.Допустим, столько, сколько вы хотите.

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

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

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

Answer 2

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

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

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