Способы и устройства построения точной траектории перемещений объектов

Изобретение относится к способам построения точной траектории перемещений объекта на основе разреженных источников геолокационных данных с низкой точностью географических привязок за счёт выделения поездок по регулярным маршрутам. Способ построения траектории перемещений объекта содержит этапы, на которых разбивают поток данных геолокационных событий объекта на данные о стояниях и данные о поездках, определяют координаты локации стояния и строят траектории поездки. При этом этап построения траектории поездки содержит этапы, где выбирают из транспортного графа узлы в радиусе неопределённости плюс некоторый буфер от координат локации стояния, предшествующего поездке, из выбранных узлов с помощью алгоритма поиска A* строят варианты траекторий на графе внутрь следующей геолокационной зоны или максимально близко к ней, при этом этот этап повторяют, последовательно для каждой зоны, до локации следующего стояния, расставляют для узлов на траектории временные метки и осуществляют поиск оптимальной траектории путем выбора лучших кандидатов на основании функции стоимости из пула из нескольких лучших кандидатов. Технический результат заключается в повышении точности при построении траектории объекта за счёт выделения поездок по регулярным маршрутам. 6 н. и 26 з.п. ф-лы, 2 ил.

 

Область техники

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

Уровень техники

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

Задача построения непрерывных траекторий пользователей на разреженных геолокационных данных решалась многократно:

Michelle Fillekes. Reconstructing Trajectories from Sparse Call Detail Records, Master's thesis, 30.06.2014, 101 стр., найдено в Интернете по ссылке: https://lean-gate.geo.uzh.ch/prod/typo3conf/ext/qfq/qfq/api/download.php?s=5d3ef2708de59 ;

Ning Yang, Philip S. Yu. Efficient Hidden Trajectory Reconstruction from Sparse Data, Conference: the 25th ACM International Conference on Information and Knowledge Management (CIKM 2016), At Indianapolis, United States, найдено в Интернете по ссылке: https://www.researchgate.net/publication/305996333_Efficient_Hidden_Trajectory_Reconstruction_From_Sparse_Data ;

Guangshuo Chen, Aline Carneiro Viana, Marco Fiore, Carlos Sarraute. Individual Trajectory Reconstruction from Mobile Network Data. [Technical Report] RT-0495, INRIA Saclay - Ile-de-France. 2018, стр.1-23, найдено в Интернете по ссылке: https://hal.inria.fr/hal-01675570v2/ .

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

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

Сущность изобретения

Настоящее изобретение представляет собой способы и устройства обработки данных, направленных на повышение точности при построении траектории объекта.

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

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

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

Согласно варианту осуществления на этапе разбиения потока данных геолокационных событий объекта на стояния и поездки: выделяют стояние на основе последовательности регистраций объекта в трёх и более взаимно пересекающихся геолокационных зонах на протяжении более заданного порогового отрезка времени и/или если интервал времени между двумя последовательными регистрациями в геолокационных зонах больше заданного порога, а верхняя оценка скорости, с которой расстояние между зонами могло быть преодолено по прямой, меньше заданного порога, при этом этот этап повторяют до выделения всех возможных стояний; и маркируют интервалы между выделенными стояниями как движения.

Согласно еще одному варианту осуществления на этапе определения координат локации: строят взвешенную сумму полигонов геолокационных зон, в которых объект регистрировался во время стояния, с весами, пропорциональными времени, проведённому в зонах; и выбирают пересечение полигонов с максимальным суммарным весом, при этом центр и радиус выбранного пересечения задают координаты локации и радиус неопределённости этих координат.

Согласно другому варианту осуществления на этапе построения траектории поездки: выбирают из транспортного графа узлы в радиусе неопределённости плюс некоторый буфер от координат локации стояния, предшествующего поездке; из выбранных узлов с помощью алгоритма поиска A*, строят варианты траекторий на графе внутрь следующей геолокационной зоны или максимально близко к ней, при этом этот этап повторяют, последовательно для каждой зоны, до локации следующего стояния; расставляют для узлов на траектории временные метки; и осуществляют поиск оптимальной траектории путем выбора лучших кандидатов на основании функции стоимости из пула из нескольких лучших кандидатов.

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

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

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

При этом база данных геолокационных зон содержит по меньшей мере одно из следующего: идентификатор (ID) зоны и полигон зоны. Поток геолокационных событий содержит по меньшей мере одно из следующего: ID объекта, ID зоны и метку времени.

Согласно еще одному варианту осуществления на этапе построения траектории объекта получают данные о траектории объекта, включающие в себя по меньшей мере одно из следующего: ID объекта, координата, метка времени, флаг стояния/движения, ID геолокационной зоны.

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

Согласно варианту осуществления на этапе разбиения потока данных геолокационных событий объекта на стояния и поездки: выделяют стояние на основе последовательности регистраций объекта в трёх и более взаимно пересекающихся геолокационных зонах на протяжении более заданного порогового отрезка времени и/или если интервал времени между двумя последовательными регистрациями в геолокационных зонах больше заданного порога, а верхняя оценка скорости, с которой расстояние между зонами могло быть преодолено по прямой, меньше заданного порога, при этом этот этап повторяют до выделения всех возможных стояний; и маркируют интервалы между выделенными стояниями как движения.

Согласно еще одному варианту осуществления на этапе формирования регулярных локаций объекта: осуществляют кластеризацию всех стояний объекта; сравнивают полученные кластеры с базой данных регулярных локаций объекта и объединяют совпавшие локации; определяют координаты локации для каждого выделенного кластера; и формируют справочную базу данных регулярных локаций объекта на основании полученных координат локации.

При этом кластеризацию регулярных локаций объекта осуществляют за фиксированное временное окно. Справочная база данных регулярных локаций объекта содержит по меньшей мере одно из следующего: идентификатор (ID) объекта, ID локации, координаты локации, радиус неопределённости координат, ID геолокационных зон в локации и количество регистраций в них, и история посещений локации.

Согласно другому варианту осуществления на этапе формирования регулярных маршрутов объекта: выделяют среди всех поездок объекта поездки между парами регулярных локаций объекта; осуществляют кластеризацию каждой пары регулярных локаций объекта; строят объединённую последовательность регистраций в геолокационных зонах для каждого выделенного кластера поездок; строят траекторию поездки на основании объединённой последовательности геолокационных событий; и формируют справочную базу данных регулярных маршрутов объекта на основании полученной траектории поездки.

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

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

В другом варианте осуществления на этапе определения координат локации: строят взвешенную сумму полигонов геолокационных зон, в которых объект регистрировался во время стояния, с весами, пропорциональными времени, проведённому в зонах; и выбирают пересечение полигонов с максимальным суммарным весом, при этом центр и радиус выбранного пересечения задают координаты локации и радиус неопределённости этих координат.

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

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

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

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

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

Согласно варианту осуществления на этапе построения траектории объекта получают данные о траектории объекта, включающие в себя по меньшей мере одно из следующего: ID объекта, координата, метка времени, флаг стояния/движения, ID геолокационной зоны, ID регулярной локации, и ID регулярного маршрута.

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

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

Краткое описание чертежей

Подробное описание изобретения ведется со ссылками на фигуры чертежей, на которых:

фиг. 1 - блок-схема способа повышения точности траектории перемещения объектов согласно первому варианту осуществления.

фиг. 2 - блок-схема способа повышения точности траектории перемещения объектов согласно второму варианту осуществления.

Подробное описание изобретения

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

В настоящем описании используется следующая терминология:

Объект — уникально идентифицируемое устройство, датчик или электронный платежный инструмент, перемещающееся в пространстве (например, мобильный телефон с привязкой к международному идентификатору мобильного оборудования (International Mobile Equipment Identity, IMEI), международному идентификатору мобильного абонента (International Mobile Subscriber Identity, IMSI) или номеру мобильного абонента цифровой сети с интеграцией служб (Mobile Subscriber Integrated Services Digital Number, MSISDN));

Геолокационная зона — уникально идентифицируемая территория, на которой возможна регистрация объекта в момент его там нахождения (например, сота сети мобильной связи или зона точки доступа Wi-Fi);

Поток геолокационных событий объекта — факты регистрации объекта в геолокационных зонах в привязке к конкретным моментам времени (например, данные подробной записи о вызове (Call Detail Record, CDR) оператора мобильной связи);

Траектория объекта — история перемещений объекта с указанием конкретных координат и моментов времени;

Стояние и поездка — фрагменты траектории объекта, соответствующие пребыванию в ограниченной локации и перемещению между локациями, соответственно;

Регулярная локация объекта — уникально идентифицируемая локация, регулярно посещаемая объектом, с сопоставленными ей координатами и радиусом неопределённости координат (оценочная точность координат);

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

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

Варианты осуществления изобретения

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

Общая схема первого варианта осуществления способа повышения точности траектории перемещения объектов представлена на фиг. 1.

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

На втором этапе поток данных геолокационных событий объекта разбивается на данные о стояниях и данные о поездках.

На следующем этапе осуществляют построение траектории. В результате построения получают данные о траектории объекта, включающие в себя по меньшей мере одно из следующего: ID объекта, координата, метка времени, флаг стояния/движения и ID геолокационной зоны.

Согласно настоящему изобретению на этапе разбиения потока геолокационных событий объекта на стояния и поездки последовательность регистраций объекта в трёх и более взаимно пересекающихся геолокационных зонах на протяжении заданного порогового отрезка времени (например, 15 минут) образует стояние. Также фиксируют стояние, если интервал времени между двумя последовательными регистрациями в геолокационных зонах больше заданного порога (например, 1 часа), а верхняя оценка скорости, с которой расстояние между зонами могло быть преодолено по прямой, меньше заданного порога (например, 5 км/ч). После выделения всех возможных стояний интервалы между ними маркируются как движения (движение может не содержать промежуточных регистраций в локационных зонах).

На этапе построения траектории к стояниям применяется этап определения координат локации, а к поездкам применяется этап определения траектории поездки.

На этапе определения координат локации и радиуса их неопределённости строится взвешенная сумма полигонов геолокационных зон, в которых объект регистрировался во время стояния, с весами, пропорциональными времени, проведённому в зонах. Затем выбирается пересечение полигонов с максимальным суммарным весом. При этом центр и радиус выбранного пересечения задают координаты локации и радиус неопределённости этих координат.

Далее будет пояснен этап построения траектории поездки. На первом этапе из транспортного графа выбираются узлы в радиусе неопределённости плюс некоторый буфер (например, 100 метров) от координат локации стояния, предшествующего поездке. Из выбранных узлов с помощью алгоритма A*, представляющего собой алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), строятся варианты траекторий на графе внутрь следующей геолокационной зоны (или максимально близко к ней) и далее, последовательно двигаясь от одной зоны к другой, до локации следующего стояния. Затем для узлов на траектории расставляются временные метки путём решения задачи оптимизации со следующими ограничениями: временные метки вдоль траектории монотонно увеличиваются; временная метка регистрации в геолокационной зоне попадает внутрь отрезка, проходящего через эту геолокационную зону (или максимально близкого к ней, если траектория не проходит через эту зону); минимизируется суммарное отклонение средних скоростей на каждом участке траектории, соответствующем одному типу транспорта или категории дороги, от типичной скорости для данного типа транспорта или категории дороги; минимизируется суммарный разброс скоростей на каждом участке траектории, соответствующем одному типу транспорта или категории дороги.

На следующем этапе в ходе поиска оптимальной траектории поддерживается пул из нескольких лучших кандидатов (например, 100), из которых в итоге происходит выбор на основании функции стоимости, что соответствует применению алгоритма beam search. Функция стоимости для алгоритма A* и для финального выбора оптимальной траектории является взвешенной суммой штрафов за: пройденное расстояние для каждого типа транспорта и категории дороги, смену типа транспорта или категории дороги с разными весами для разных вариантов смен, смену направления движения, разброс скоростей и отклонения от типичных скоростей, рассчитанные при расстановке временных меток.

Веса для функции стоимости подбираются исходя из оптимизации метрик точности относительно эталонных данных.

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

Общая схема второго варианта осуществления способа повышения точности траектории перемещения объектов представлена на фиг. 2.

Способ повышения точности траекторий за счёт выделения поездок по регулярным маршрутам заключается в том, что на первом этапе осуществляют ввод входных данных, включающих историю геолокационных событий за продолжительный период времени, данные справочной базы данных геолокационных зон и данные транспортного графа. При этом в одном варианте осуществления изобретения справочная базы данных геолокационных зон может содержать по меньшей мере одно из следующего: идентификатор (ID) зоны и полигон зоны. Поток геолокационных событий в одном варианте осуществления может содержать по меньшей мере одно из следующего: ID объекта, ID зоны и метку времени

На втором этапе поток данных геолокационных событий объекта разбивается на данные о стояниях и данные о поездках на основании времени между регистрациями в зонах и расстояниями между ними.

Затем к данным о стояниях применяется этап формирования регулярных локаций объекта, а к данным о поездках между регулярными локациями объекта применяется этап формирования регулярных маршрутов объекта.

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

Способ может применяться в одном из двух режимов:

однократный - осуществление всего способа построения траекторий в отношении всей истории событий, если не требуется обрабатывать постоянно поступающий поток;

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

Согласно настоящему изобретению на этапе разбиения потока геолокационных событий объекта на стояния и поездки последовательность регистраций объекта в трёх и более взаимно пересекающихся геолокационных зонах на протяжении заданного порогового отрезка времени (например, 15 минут) образует стояние. Также фиксируют стояние, если интервал времени между двумя последовательными регистрациями в геолокационных зонах больше заданного порога (например, 1 часа), а верхняя оценка скорости, с которой расстояние между зонами могло быть преодолено по прямой, меньше заданного порога (например, 5 км/ч). После выделения всех возможных стояний интервалы между ними маркируются как движения (движение может не содержать промежуточных регистраций в локационных зонах).

Для формирования регулярных локаций объекта на первом этапе в режиме периодического запуска в качестве основы используется справочная база данных регулярных локаций, сформированная при предыдущем запуске (при первом запуске база данных пустая). Затем ко всем стояниям объекта (при периодическом запуске — за фиксированное временное окно, например, 1 год) применяется алгоритм кластеризации стояний. Далее при периодическом запуске полученные кластеры сопоставляются с предыдущей версией базы данных регулярных локаций и совпавшие локации объединяются. На следующем этапе к каждому выделенному кластеру стояний применяется этап определения координат локации и радиуса их неопределённости, который был подробно описан выше. Полученный набор локаций с координатами центра, радиусом неопределённости, историей посещений локации, списком геолокационных зон и количеством регистраций объекта в них формируют новую версию справочной базы данных регулярных локаций объекта. В одном из вариантов осуществления изобретения справочная база данных регулярных локаций содержит, по меньшей мере, одно из следующего: идентификатор (ID) объекта, ID локации, координаты локации, радиус неопределённости координат, ID геолокационных зон в локации и количество регистраций в них, и история посещений локации.

Для формирования регулярных маршрутов объекта среди всех поездок объекта (при периодическом запуске — за фиксированное временное окно, например, 16 недель) выделяются поездки между парами регулярных локаций объекта. Затем для каждой пары регулярных локаций объекта применяется алгоритм кластеризации поездок. Для каждого выделенного кластера поездок строится объединённая последовательность регистраций в геолокационных зонах. На следующем этапе к объединённой последовательности геолокационных событий применяется этап построения траектории поездки, который был подробно описан выше. Полученный набор маршрутов с траекториями и объединённой последовательностью геолокационных зон формируют справочную базу данных регулярных маршрутов объекта. В одном из вариантов осуществления изобретения справочная база данных регулярных маршрутов содержит, по меньшей мере, одно из следующего: идентификатор (ID) объекта, ID маршрута, ID регулярных локаций, соответствующих началу и концу маршрута траектория маршрута с относительными метками времени, ID геолокационных зон в порядке появления на маршруте с относительными метками времени.

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

В одном из вариантов осуществления изобретения данные о траектории, полученной на предыдущем этапе, могут содержать, по меньшей мере, одно из следующего: ID объекта, координаты, метки времени, флаг стояния/движения, ID геолокационной зоны, ID регулярной локации и ID регулярного маршрута.

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

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

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

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

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

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

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

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

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

Компьютерные носители хранения являются физическими аппаратными носителями хранения, которые хранят машиноисполняемые инструкции и/или структуры данных. Физические аппаратные носители хранения включают в себя компьютерные аппаратные средства, такие как RAM, ROM, EEPROM, твердотельные накопители ("SSD"), флэш-память, память на фазовых переходах ("PCM"), устройство хранения на оптических дисках, устройство хранения на магнитных дисках или другие магнитные устройства хранения, или любое другое аппаратное устройство(-а) хранения, которое может быть использовано, чтобы хранить программный код в форме машиноисполняемых инструкций или структур данных, к которым может быть осуществлен доступ и которые выполняются посредством компьютерной системы общего назначения или специализированной компьютерной системы, чтобы реализовывать раскрытую функциональность изобретения.

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

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

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

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

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

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

1. Способ построения траектории перемещений объекта, содержащий следующие этапы:

разбивают поток данных геолокационных событий объекта на данные о стояниях и данные о поездках;

определяют координаты локации стояния и

строят траектории поездки, отличающийся тем, что этап построения траектории поездки содержит:

выбирают из транспортного графа узлы в радиусе неопределённости плюс некоторый буфер от координат локации стояния, предшествующего поездке;

из выбранных узлов с помощью алгоритма поиска A* строят варианты траекторий на графе внутрь следующей геолокационной зоны или максимально близко к ней, при этом этот этап повторяют, последовательно для каждой зоны, до локации следующего стояния;

расставляют для узлов на траектории временные метки и

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

2. Способ по п. 1, отличающийся тем, что этап разбиения потока данных геолокационных событий объекта на стояния и поездки содержит:

выделяют стояние на основе последовательности регистраций объекта в трёх и более взаимно пересекающихся геолокационных зонах на протяжении более заданного порогового отрезка времени и/или если интервал времени между двумя последовательными регистрациями в геолокационных зонах больше заданного порога, а верхняя оценка скорости, с которой расстояние между зонами могло быть преодолено по прямой, меньше заданного порога, при этом этот этап повторяют до выделения всех возможных стояний; и

маркируют интервалы между выделенными стояниями как движения.

3. Способ по п. 1, отличающийся тем, что этап определения координат локации содержит:

строят взвешенную сумму полигонов геолокационных зон, в которых объект регистрировался во время стояния, с весами, пропорциональными времени, проведённому в зонах; и

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

4. Способ по п. 1, отличающийся тем, что функция стоимости для алгоритма A* и для финального выбора оптимальной траектории является взвешенной суммой штрафов за: пройденное расстояние для каждого типа транспорта и категории дороги, смену типа транспорта или категории дороги с разными весами для разных вариантов смен, смену направления движения, разброс скоростей и отклонения от типичных скоростей, рассчитанные при расстановке временных меток.

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

6. Способ по п. 1, дополнительно содержащий этап ввода входных данных, включающих по меньшей мере одно из следующего: данные справочной базы данных геолокационных зон и данные транспортного графа.

7. Способ по п. 6, отличающийся тем, что база данных геолокационных зон содержит по меньшей мере одно из следующего: идентификатор (ID) зоны и полигон зоны.

8. Способ по п. 1, отличающийся тем, что поток геолокационных событий содержит по меньшей мере одно из следующего: ID объекта, ID зоны и метку времени.

9. Способ по п. 1, отличающийся тем, что на этапе построения траектории объекта получают данные о траектории объекта, включающие в себя по меньшей мере одно из следующего: ID объекта, координата, метка времени, флаг стояния/движения, ID геолокационной зоны.

10. Способ построения траектории перемещений объекта, содержащий следующие этапы:

разбивают поток данных геолокационных событий объекта на данные о стоянии и данные о поездках;

формируют регулярные локации объекта на основании данных о стоянии;

формируют регулярные маршруты объекта на основании данных о поездках между регулярными локациями объекта и

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

выбирают из транспортного графа узлы в радиусе неопределённости плюс некоторый буфер от координат локации стояния, предшествующего поездке;

из выбранных узлов с помощью алгоритма поиска A* строят варианты траекторий на графе внутрь следующей геолокационной зоны или максимально близко к ней, при этом этот этап повторяют, последовательно для каждой зоны, до локации следующего стояния;

расставляют для узлов на траектории временные метки и

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

11. Способ по п. 10, отличающийся тем, что этап разбиения потока данных геолокационных событий объекта на стояния и поездки содержит:

выделяют стояние на основе последовательности регистраций объекта в трёх и более взаимно пересекающихся геолокационных зонах на протяжении более заданного порогового отрезка времени и/или если интервал времени между двумя последовательными регистрациями в геолокационных зонах больше заданного порога, а верхняя оценка скорости, с которой расстояние между зонами могло быть преодолено по прямой, меньше заданного порога, при этом этот этап повторяют до выделения всех возможных стояний; и

маркируют интервалы между выделенными стояниями как движения.

12. Способ по п. 10, отличающийся тем, что этап формирования регулярных локаций объекта содержит:

осуществляют кластеризацию всех стояний объекта;

сравнивают полученные кластеры с базой данных регулярных локаций объекта и объединяют совпавшие локации;

определяют координаты локации для каждого выделенного кластера и

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

13. Способ по п. 10, отличающийся тем, что кластеризацию регулярных локаций объекта осуществляют за фиксированное временное окно.

14. Способ по п. 10, отличающийся тем, что справочная база данных регулярных локаций объекта содержит по меньшей мере одно из следующего: идентификатор (ID) объекта, ID локации, координаты локации, радиус неопределённости координат, ID геолокационных зон в локации и количество регистраций в них, и история посещений локации.

15. Способ по п. 10, отличающийся тем, что этап формирования регулярных маршрутов объекта дополнительно содержит:

выделяют среди всех поездок объекта поездки между парами регулярных локаций объекта;

осуществляют кластеризацию каждой пары регулярных локаций объекта;

строят объединённую последовательность регистраций в геолокационных зонах для каждого выделенного кластера поездок и

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

16. Способ по п. 15, отличающийся тем, что поездки между парами регулярных локаций объекта выделяют за фиксированное временное окно.

17. Способ по п. 15, отличающийся тем, что справочная база данных регулярных маршрутов объекта содержит по меньшей мере одно из следующего: ID объекта, ID маршрута, ID регулярных локаций, соответствующих началу и концу маршрута, траектория маршрута с относительными метками времени, ID геолокационных зон в порядке появления на маршруте с относительными метками времени.

18. Способ по п. 10, отличающийся тем, что этап построения траектории объекта содержит:

сравнивают каждое стояние объекта со справочной базой данных регулярных локаций объекта, при этом если находится соответствие, то в траекторию подставляется координата из справочной базы данных регулярных локаций объекта, к прочим стояниям применяется этап определения координат локации; и

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

19. Способ по любому из пп. 12 или 18, отличающийся тем, что этап определения координат локации содержит:

строят взвешенную сумму полигонов геолокационных зон, в которых объект регистрировался во время стояния, с весами, пропорциональными времени, проведённому в зонах; и

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

20. Способ по п. 10, отличающийся тем, что функция стоимости для алгоритма A* и для финального выбора оптимальной траектории является взвешенной суммой штрафов за: пройденное расстояние для каждого типа транспорта и категории дороги, смену типа транспорта или категории дороги с разными весами для разных вариантов смен, смену направления движения, разброс скоростей и отклонения от типичных скоростей, рассчитанные при расстановке временных меток.

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

22. Способ по любому из пп. 1-18, отличающийся тем, что все этапы способа выполняют однократно.

23. Способ по п. 22, отличающийся тем, что при однократном выполнении этапов способа данные о стояниях и данные о поездках, отнесённые к регулярным локациям и регулярным маршрутам, заменяются соответствующими уточнёнными координатами и отрезками траектории.

24. Способ по любому из пп. 1-18, отличающийся тем, что все этапы способа выполняют периодически.

25. Способ по п. 10, дополнительно содержащий этап ввода входных данных, включающих по меньшей мере одно из следующего: данные справочной базы данных геолокационных зон и данные транспортного графа.

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

27. Способ по п. 10, отличающийся тем, что поток геолокационных событий содержит по меньшей мере одно из следующего: ID объекта, ID зоны и метку времени.

28. Способ по п. 10, отличающийся тем, что на этапе построения траектории объекта получают данные о траектории объекта, включающие в себя по меньшей мере одно из следующего: ID объекта, координата, метка времени, флаг стояния/движения, ID геолокационной зоны, ID регулярной локации и ID регулярного маршрута.

29. Устройство построения траектории перемещений объекта, содержащее:

один или более процессоров;

системную память;

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

30. Устройство построения траектории перемещений объекта, содержащее:

один или более процессоров;

системную память;

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

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

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