Какой подход будет подходящим для кластеризации клиентов на основе местоположения посадки и отбрасывания

Question

Есть некоторые люди, которые хотят путешествовать из какого-то пункта погрузки в другое место.Все пункты выдачи находятся в городе А, а все точки отбрасывания - в городе В. Где А! = B. Как группировать людей таким образом, чтобы общее расстояние, пройденное на машине до сбора и отбрасывания всех клиентов, было минимальным.Поскольку большинство автомобилей способны перевозить до 4 человек, желательно использовать полную вместимость каждого автомобиля.Каждый кластер будет назначен водителю автомобиля, который может отказаться от поездки, и в этом случае он будет передан следующему водителю.

Answer 1

См. Ответ на этот вопрос: Вариант алгоритма K-означает с равным размером кластера для алгоритма кластеризации в кластеры одинакового размера (в вашем случае 4).

Для обработкиограничение "разные города", определить каждого клиента как набор точек, состоящий из их точки получения в городе A и точки высадки в городе B, и определить расстояние между двумя клиентами как сумму расстояния между их пунктами получения ирасстояние между их местами высадки.Среднее значение из списка кортежей будет представлять собой кортеж, составленный из среднего значения местоположений получения и среднего количества мест размещения.Определения этих двух функций должно быть достаточно для реализации K-средних.

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