Найдите почтовые индексы Великобритании, наиболее близкие к другим почтовым индексам Великобритании, сопоставив строку почтового индекса.

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

У меня есть сценарий в моем приложении, где у меня есть пара заданий (от 1 до 50). У задания есть адрес, и у меня есть следующие свойства адреса: почтовый индекс, широта и долгота.

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

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

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

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

Теперь вот головная боль: у меня более 1500 рабочих. У меня есть служебная функция, которая использует Json Convert от Newtonsoft для десериализации потока ответов от Google Maps. Мне нужно ввести почтовый индекс A и B.

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

Я не могу использовать простую формулу Хаверсина, так как путь вороньей мухи здесь не является моим требованием. Боль в этом заключается в том, что для расчета требуется много времени. Некоторые работники могут проехать более 10 миль, а некоторые — от 15 до 80. Я должен взять первое задание из списка и выполнить его со всеми подходящими рабочими в системе! Мне было интересно, что почтовый индекс Великобритании имеет шаблон. Если мы отсортируем список почтовых индексов Великобритании, сможем ли мы приблизительно оценить по буквенно-цифровому шаблону, где мы достигнем отметки в 100 миль, отметки в 200 миль и так далее?

Если кому-то интересен код, напишите, я вставлю.


person Hassan Gulzar    schedule 11.04.2011    source источник
comment
Хорошо, у меня есть этот SQL-запрос. Чтобы искать поблизости, я добавляю и вычитаю 0,100000 из широты и долготы:   -  person Hassan Gulzar    schedule 12.04.2011


Ответы (2)


(Я работаю в Google, но я не говорю от имени Google. Я не имею никакого отношения к API карт.)

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

Когда я занимался чем-то подобным на предыдущей работе, мы купили локальный API карт, но даже этого было недостаточно для такой работы. В итоге мы предварительно вычислили время, необходимое для путешествия из центра тяжести каждой «области» почтового индекса (вероятно, это неправильное название, но первая часть почтового индекса, за которой следует первая цифра остатка, например, «SW1W 9» для «SW1W 9TQ ") в любую другую область, сохраняя результат в гигантской таблице. Я думаю, мы сделали это только для почтовых индексов, которые были в пределах 100 миль или что-то подобное, чтобы сократить объем предварительной обработки.

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

  • Работа с областями почтовых индексов (работа с подстроками)
  • Найдите индекс каждой области почтового индекса в последовательности
  • Проверьте, загрузили ли мы эту часть файла (мы лениво загружали для скорости запуска)
  • Загрузите строку, если необходимо, и просто получите к ней доступ в противном случае

Байты были на скользящей шкале точности, поэтому первые 60 минут они были поминутными, затем каждое дополнительное значение означало дополнительные 2 минуты, затем 5 и т. д. (это не точные значения, но они было что-то такое)

Когда вы подберете «хороших кандидатов», вы, конечно, можете запросить более точные указания для ваших точных почтовых индексов у местного API или Google Maps API.

person Jon Skeet    schedule 11.04.2011
comment
Я понимаю беспокойство. Вот почему я хотел провести исследования и разработки, прежде чем делать какие-либо звонки в Google. Думаю, я буду чесать голову немного больше. - person Hassan Gulzar; 12.04.2011

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

person Gigamegs    schedule 11.04.2011
comment
Рекомендуем изучить алгоритм. Спасибо. - person Hassan Gulzar; 12.04.2011
comment
Спасибо за ваш голос. Я написал реализацию quadtree для поиска почтового индекса в php на phpclasses.org (hilbert-curve). Он использует строковый индекс для каждого почтового индекса. - person Gigamegs; 12.04.2011