4.1.2 Прокладка оптимального маршрута

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

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

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

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

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

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

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

Операционная система Android разработана компанией Google. Поэтому логично выделить первого кандидата ­– картографический сервис Google Maps. Действительно, в настоящее время он очень бурно развивается. Кроме того, существуют готовые и очень удобные инструменты для создания приложений под Android с использованием Google Maps. Однако детальное изучение системы показало, что подробно сеть дорог проложена только в пределах США и стран Евросоюза. В России же в векторном формате представлены карты лишь наиболее крупных городов. Свободное редактирование так же не представляется возможным.

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

После выделения недостатков двух представленных выше картографических сервисов, выбор пал в сторону использования OpenStreetMap (дословно «открытая карта улиц»), сокращённо OSM – некоммерческий веб-картографический проект по созданию силами сообщества участников-пользователей Интернета подробной свободной и бесплатной географической карты мира.

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