Алгоритм кластеризации для бумажных мальчиков

Question

Мне нужна помощь в выборе или создании алгоритма кластеризации в соответствии с определенными критериями.

Представьте, что вы управляете персоной доставки газет.

• У вас есть набор уличных адресов, каждый из которых геокодирован.
• Вы хотите сгруппировать адреса так, чтобы каждый кластер был назначен сотруднику доставки.
• Количество лиц, осуществляющих доставку, или кластеров не фиксировано. При необходимости я всегда могу нанять больше сотрудников службы доставки или уволить их.
• Каждый кластер должен иметь примерно одинаковое количество адресов. Однако у кластера может быть меньше адресов, если адреса кластера более распределены. (Можно сформулировать иначе: минимальное количество кластеров, где каждый кластер содержит максимальное количество адресов, а любой адрес в кластере должен быть разделен максимальным расстоянием.)
• Для бонусных баллов, когда набор данных изменяется (адрес добавляется или удаляется) и алгоритм перезапускается, было бы неплохо, если бы кластеры оставались настолько неизменными, насколько это возможно (т.е. это исключает простые k-средства кластеризация, которая носит случайный характер). В противном случае курьеры сойдут с ума.

Итак ... идеи?

UPDATE

График уличной сети, как описано в ответе Арахнида, недоступен.

Answer 1

Мне известен довольно новый подход к этой проблеме, который я видел в применении к биоинформатике, хотя он подходит для любой проблемы кластеризации. Это, конечно, не самое простое решение, но оно мне кажется очень интересным. Основная предпосылка заключается в том, что кластеризация включает в себя несколько целей. Для одного вы хотите минимизировать количество кластеров, тривальное решение - один кластер со всеми данными. Вторая стандартная цель состоит в том, чтобы минимизировать количество отклонений в кластере, тривиальным решением является множество кластеров, каждый из которых имеет только одну точку данных. Интересные решения появляются, когда вы пытаетесь включить обе эти цели и оптимизировать компромисс.

В основе предлагаемого подхода лежит так называемый меметический алгоритм , который немного похож на генетический алгоритм, о котором упоминал Стив, однако он не только хорошо исследует пространство решений, но и обладает способностью сосредоточиться на интересных регионах, то есть решения. По крайней мере, я рекомендую прочитать некоторые статьи на эту тему, поскольку меметические алгоритмы - необычный подход, хотя и предупреждающий; это может привести вас к прочтению «Эгоистичного гена», и я до сих пор не решил, было ли это хорошо ... Если алгоритмы вас не интересуют, то, возможно, вы можете просто попытаться выразить вашу проблему в соответствии с форматом и использовать источник код предоставляется. Соответствующие документы и код можно найти здесь: Многоцелевая кластеризация

Answer 2

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

ИБП имеет программное обеспечение, которое генерирует оптимальные маршруты для людей, которые будут их доставлять. Программное обеспечение пытается максимизировать количество правых поворотов, которые принимаются во время маршрута. Это экономит им много времени при доставке.

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

Здесь есть статья об этом: http://abcnews.go.com/wnt/story?id=3005890

Answer 3

• У вас есть набор улицы адреса, каждый из которых геокодирован.
  • Вы хотите сгруппировать адреса так, чтобы каждый кластер был назначен курьеру.
  • Количество лиц, осуществляющих доставку, или кластеров не фиксировано. Если нужно, Я всегда могу нанять больше доставки человек, или уволить их.
  • Каждый кластер должен иметь примерно одинаковое количество адресов. Тем не мение, кластер может иметь меньше адресов, если адреса кластера более распространены из. (Адрес по-другому: минимум количество кластеров, где каждый кластер содержит максимальное количество адреса, и любой адрес в пределах кластер должен быть отделен максимум расстояние.)
  • Для бонусных баллов, когда набор данных изменяется (адрес добавлен или удаляется), и алгоритм перезапускается, было бы хорошо, если кластеры остался неизменным, насколько это возможно (т.е. это исключает простые K-средства кластеризация, которая носит случайный характер). В противном случае доставщики отправятся сумасшедший.

Как уже упоминалось, проблема маршрутизации транспортных средств, вероятно, лучше подходит ... Хотя она строго не разработана с учетом кластеризации, она будет оптимизирована для назначения на основе ближайших адресов. Поэтому ваши кластеры на самом деле будут рекомендуемыми маршрутами.

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

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

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

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

На самом деле я работаю над библиотекой классов C #, чтобы достичь чего-то подобного, и думаю, что это, вероятно, лучший путь для спуска, хотя его не всегда легко реализовать.

Answer 4

Я признаю, что это не обязательно обеспечит кластеры примерно одинакового размера:

Одним из лучших современных методов кластеризации данных является накопление доказательств. (Фред и Джейн, 2005) Что вы делаете:

Учитывая набор данных с n шаблонов.

1. Используйте алгоритм типа k-средних в диапазоне k. Или используйте набор различных алгоритмов, цель - создать ансамбль разбиений.

2. Создание матрицы ассоциаций C размером n x n.

3. Для каждого раздела p в ансамбле:
   3.1 Обновите матрицу совместной ассоциации: для каждой пары шаблонов (i, j), которая принадлежит одному и тому же кластеру в p, установите C (i, j) = C (i, j) + 1 / N.

4. Используйте алгоритм кластеризации, такой как Single Link, и примените матрицу C в качестве меры близости. Одиночная ссылка дает дендрограмму, в результате которой мы выбираем кластеризацию с наибольшим временем жизни.

Я предоставлю описания SL и k-средних, если вам интересно.

Answer 5

Тривиальный ответ, который не получает никаких бонусных баллов:

Один человек на каждый адрес.

Answer 6

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

Answer 7

Я бы использовал базовый алгоритм для создания первого набора маршрутов разносчика газет в зависимости от того, где они живут, и текущего местоположения подписчиков, затем:

когда газетчики:

• Добавлено: они берут локации у одного или нескольких бумажников, работающих в той же области, где живет новый парень.
• Удалено: его местоположения предоставляются другим бумажникам, используя самые близкие места к их маршрутам.

когда местоположения:

• Добавлено: То же самое, местоположение добавлено к ближайшему маршруту.
• Удалено: только что удалено с маршрута этого мальчика.

Раз в квартал вы можете пересчитать все это и изменить все маршруты.