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

Ответ 1

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

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

Я предполагаю, что ваша настоящая проблема не имеет ничего общего с доставкой газет...

Ответ 2

Я написал неэффективный, но простой алгоритм в Java, чтобы увидеть, насколько близко я могу получить базовую кластеризацию на множестве точек, более или менее, как описано в вопросе.

Алгоритм работает над списком, если (x, y) согласованы ps, которые указаны как int s. Он принимает еще три параметра:

• radius (r): при заданной точке, каков радиус для сканирования ближайших точек
• max addresses (maxA): каково максимальное количество адресов (точек) на кластер?
• минимальные адреса (minA): минимальные адреса для кластера

Установите limitA=maxA. Основная итерация: Инициализировать пустой список possibleSolutions. Внешняя итерация: для каждой точки p в ps. Инициализировать пустой список pclusters. Определен рабочий список точек wps=copy(ps). Рабочая точка wp=p. Внутренняя итерация, а wps не пуста. Удалите точку wp в wps. Определите все точки wpsInRadius в wps, которые находятся на расстоянии < r из wp. Сортировка wpsInRadius по возрастанию в соответствии с расстоянием от wp. Сохраните первые min(limitA, sizeOf(wpsInRadius)) точки в wpsInRadius. Эти точки образуют новый кластер (список точек) pcluster. Добавьте pcluster в pclusters. Удалите точки в pcluster с wps. Если wps не пусто, wp=wps[0] и продолжить внутреннюю итерацию. Завершить внутреннюю итерацию. Получен список кластеров pclusters. Добавьте это к possibleSolutions. Завершить внешнюю итерацию.

Мы имеем для каждого p в ps список кластеров pclusters в possibleSolutions. Затем каждый pclusters взвешивается. Если avgPC - среднее число точек на кластер в possibleSolutions (global), а avgCSize - среднее число кластеров на pclusters (глобальное), то это функция, которая использует обе эти переменные для определения вес:

  private static WeightedPClusters weigh(List<Cluster> pclusters, double avgPC, double avgCSize)
  {
    double weight = 0;
    for (Cluster cluster : pclusters)
    {
      int ps = cluster.getPoints().size();
      double psAvgPC = ps - avgPC;
      weight += psAvgPC * psAvgPC / avgCSize;
      weight += cluster.getSurface() / ps;
    }
    return new WeightedPClusters(pclusters, weight);
  }

Лучшим решением является pclusters с наименьшим весом. Повторяем основную итерацию, пока мы можем найти лучшее решение (меньше веса), чем предыдущее лучшее с limitA=max(minA,(int)avgPC). Завершить основную итерацию.

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

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

Далее, если мы уменьшим минимальное количество адресов на кластер, установив minA=12, мы найдем 3 кластера по 12/12/8 баллов.

И чтобы продемонстрировать, что алгоритм далек от совершенства, вот результат с maxA=7, но мы получаем 6 кластеров, некоторые из них небольшие. Поэтому при определении параметров вам все равно придется угадывать слишком много. Заметим, что r здесь всего 5.

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

Вывод? Это заняло у меня полдня, это неэффективно, код выглядит уродливым, и он относительно медленный. Но это показывает, что можно произвести некоторый результат за короткий промежуток времени. Конечно, это было просто для удовольствия; превращение этого во что-то, что действительно полезно, - это трудная часть.

Ответ 3

То, что вы описываете, является проблемой (Multi) -Vehicle-Routing-Problem (VRP). Там очень много академической литературы по различным вариантам этой проблемы, используя большое разнообразие методов (эвристика, готовые решения и т.д.). Обычно авторы пытаются найти хорошие или оптимальные решения для конкретного примера, что также предполагает кластеризацию сайтов (все сайты на маршруте одного транспортного средства).

Однако кластеры могут подвергаться серьезным изменениям только в немногих разных случаях, чего вы хотите избежать. Тем не менее, что-то в VRP-Papers может вдохновить вас...

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

Для оценки кластеров с использованием графического представления уличной сетки, вероятно, будут получены более реалистичные результаты, чем подключение точек на белой карте (хотя оба варианта TSP). Если модель графа недоступна, вы можете использовать таксономическую метрику (| x_1 - x_2 | + | y_1 - y_2 |) в качестве приближения для расстояний.

Ответ 4

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

Назначьте функцию стоимости каждой точке, сколько она добавляет к графику, и дайте каждой дополнительной точке экономическое значение.

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

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

Ответ 5

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

Ответ 6

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

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

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

Теперь вы можете работать на этой сетке так же, как с программным обеспечением для обработки фотографий. Вы можете обнаружить края кластеров, найдя блоки, в которых у некоторых соседних блоков нет точек доставки.

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

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

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

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

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

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

Ответ 7

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

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

• Имитированное отжиг
• Алгоритм Великого Потопа
• Генетические алгоритмы

Используя алгоритм оптимизации, я думаю, вы описали следующие "цели":

• Географическая область для каждой бумаги мальчик должен быть сведен к минимуму.
• Число подписчиков, обслуживаемых каждый должен быть приблизительно равным.
• Расстояние, пройденное каждым должен быть примерно равным.
• (И тот, который вы не указали, но можете вопрос) Маршрут должен заканчиваться там, где это началось.

Надеюсь, вам это поможет!

* Изменить *

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

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

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

Ответ 8

Вместо модели кластеризации я думаю, что вам действительно нужен какой-то вариант модели местоположения Set Covering, с дополнительным ограничением для покрытия количества адресов, охватываемых каждым объектом. Я не могу найти хорошее объяснение этого онлайн. Вы можете взглянуть на на этой странице, но они решают его с использованием единиц измерения, и вы, вероятно, захотите решить его в евклидовой или сетевой пространство. Если вы готовы выкопать что-то в формате мертвого дерева, ознакомьтесь с главой 4 "Сетевое и дискретное местоположение" Даскина.

Ответ 9

Хороший обзор простых кластерных альго. Еще есть: http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/index.html

Ответ 10

Возможно, минимальное остовное дерево клиентов, разбитое на множество, основанное на местности, на бумажного мальчика. Prims или Kruskal, чтобы получить MST с расстояние между домами для веса.

Ответ 11

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

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

Ответ 12

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

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

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

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

Ответ 13

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

Ответ 14

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

Один человек доставки для каждого адреса.

Ответ 15

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

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

Учитывая набор данных с n образцами.

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

• Создайте матрицу совпадений C размера n x n.

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

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

Я расскажу описания SL и k-средств, если вы заинтересованы.

Ответ 16

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

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

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

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

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

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

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

Ответ 17

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

когда бумажные:

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

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

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

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