Кластеризация алгоритма для разносчиков газет

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

, когда разносчики газет:

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

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

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

Однажды четверть, Вы могли повторно вычислить все это и изменить все маршруты.

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

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

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

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

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

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

2. Создают матрицу co-ассоциации C размера n x n.

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

4. Использование кластеризация algorihm, такая как Единственная Ссылка и применяют матрицу C как мера по близости. Единственная Ссылка дает древовидную схему как результат, в котором мы выбираем кластеризацию с самым долгим временем жизни.

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

Это - классический пример проблемы, которая заслуживает оптимизированное решение вместо того, чтобы пытаться решить для "ОПТИМУМА". Это подобно до некоторой степени" проблема Коммивояжера ", но также необходимо сегментировать местоположения во время оптимизации.

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

1. Моделируемый Отжиг
2. Замечательный Алгоритм Наводнения
3. Генетический Algoritms

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

1. географическая область для каждого разносчика газет должна быть минимизирована.
2. число подписчиков, обслуживаемых каждым, должно быть приблизительно равным.
3. расстояние переместилось каждым, должен быть о равном.
4. (И один Вы не заявили, но могли бы иметь значение), маршрут должен закончиться, где он начался.

Hope это запустило Вас!

* Редактирование *

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

алгоритм работает над списком, если (x, y) провода ps, которые определяются как int с. Требуется три других параметра также:

1. радиус (r): учитывая точку, что является радиусом для сканирования для соседних точек
2. макс. адреса (maxA): каково максимальное количество адресов (точки) на кластер?
3. минимальные адреса (minA): минимальные адреса на кластер

Набор limitA=maxA. Основное повторение: Инициализируют пустой список possibleSolutions. Внешнее повторение: для каждой точки p в ps. Инициализируйте пустой список pclusters. worklist точек wps=copy(ps) определяется. Workpoint wp=p. Внутреннее повторение: , в то время как wps не пусто. Удалите точку wp в [1 115]. Определите все точки wpsInRadius в [1 117], которые являются на расстоянии < r от [1 119]. Вид wpsInRadius ascendingly согласно расстоянию от [1 121]. Сохраните первое min(limitA, sizeOf(wpsInRadius)) точки в [1 123]. Эти точки формируют новый кластер (список точек) pcluster. Добавьте pcluster к [1 126]. Удалите точки в [1 127] от [1 128]. Если wps не пусто, wp=wps[0], и продолжите внутреннее повторение. Конец внутреннее повторение. список А кластеров pclusters получен. Добавьте это к [1 132]. Конец внешнее повторение.

Мы имеем для каждого p в [1 134] список кластеров pclusters в [1 136]. Каждый pclusters тогда взвешивается. Если avgPC среднее число очков на кластер в [1 139] (глобальный), и avgCSize среднее количество кластеров на [1 141] (глобальный), то это - функция, которая использует обе этих переменные для определения веса:

  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 с наименьшим количеством веса. Мы повторяем основное повторение, пока мы можем найти лучшее решение (меньше веса), чем предыдущее лучше всего один с [1 143]. Конец основное повторение.

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

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

Затем, если мы сокращаем минимальное число адресов на кластер установкой minA=12, мы находим 3 кластера точек 12.12.08.

И продемонстрировать, что алгоритм совсем не прекрасен, вот вывод с [1 146], все же мы получаем 6 кластеров, некоторые из них маленький. Таким образом, все еще необходимо предположить слишком много при определении параметров. Обратите внимание, что r вот только 5.

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

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