Open AccessSTORN: Solution to Traversal of Road Networks/ RCTI: izbraucama ceļu tīkla risinājums/ РПДС: Решение дорожных сетей для проезда
Author(s) -
Jānis Kampars,
Elina Shmite
Publication year - 2014
Publication title -
information technology and management science
Language(s) - Russian
Resource type - Journals
eISSN - 2255-9094
pISSN - 2255-9086
DOI - 10.1515/itms-2014-0011
Subject(s) - tree traversal , plan (archaeology) , computer science , field (mathematics) , mashup , web application , web service , database , transport engineering , world wide web , computer network , engineering , geography , web 2.0 , mathematics , algorithm , archaeology , pure mathematics
Цель плана оптимального проезда (ПОП) - обнаружить маршрут, который обеспечил бы проезд по всем улицам на заранее определённом участке. Решая проблему ПОП, особое внимание следует обратить на минимизацию времени проезда по всему маршруту. Ещё один важный фактор - время разработки маршрута, которое быстро возрастает вместе с увеличением соответствующего географического участка. Разрабатывая маршрут, нужно принимать во внимание, что некоторые повороты могут быть запрещены, и что на двусторонних улицах движение идёт в двух направлениях. Возможные области применения ПОП: чистка улиц, доставка посылок, планирование эвакуации, планирование маршрута полицейского патруля и другие. Для определения ПОП с OpenStreetMaps собираются пространственные данные, которые превращаются в графу (сегмент улицы соответствует дуге графы, а пересечение - вершине). Для полного обхода такой графы необходимо посетить все его стороны, по крайней мере, один раз. В статье рассмотрены и экспериментально оценены два разных алгоритма получения плана проезда ПОП. Основываясь на этих алгоритмах, определяетс