You are not logged in.

#26 2012-10-02 14:24:06

Monochrome
Member
Registered: 2012-10-02
Posts: 15

Re: Нужен граф дорог России - что делать/с чего начать?

map.PNG

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

Offline

#27 2012-10-02 14:27:24

Monochrome
Member
Registered: 2012-10-02
Posts: 15

Re: Нужен граф дорог России - что делать/с чего начать?

Граф направленный или ненаправленный? Ограничения поворотов, запреты проездов как задавать планируете?

Ну, если граф в структуре будет направленным - то просто супер.

Если нет, то не так страшно - мы это зададим позже сами.



Мой граф используется главным образом для:

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

Offline

#28 2012-10-02 14:32:33

Zkir
Member
From: Хрустальная Москва
Registered: 2009-02-21
Posts: 6,110

Re: Нужен граф дорог России - что делать/с чего начать?

Самый простой способ получить граф - это преобразовать osm в польский формат (mp). Там граф представлен очень разумно. Для этого есть скрипт - osm2mp.pl.

Написал в форумную почту.

Last edited by Zkir (2012-10-02 14:37:14)


Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.

Offline

#29 2012-10-02 14:43:43

Sergey Astakhov
Member
From: St.Petersburg, Russia
Registered: 2009-11-13
Posts: 5,779

Re: Нужен граф дорог России - что делать/с чего начать?

Monochrome wrote:

Ну, если граф в структуре будет направленным - то просто супер.

Ну вот для подготовки подобного графа я и сделал свой плугин, про который упоминал выше.

Устанавливаете osmosis, затем устанавливаете плугин osmrouting версии 1.2 (например в подкаталог plugins в текущем каталоге), качаете нужный регион с gis-lab и запускаете подобную строку:

osmosis --read-pbf RU-LEN.osm.pbf --lp --build-routing-graph graphLevel=secondary minorGraphsAction=drop --split-routing-graph --directed-graph-lines --write-xml RU-LEN_graph.osm.bz2

В данном пример выполняется фильтрация дорожного графа Ленобласти уровня secondary (с выкидыванием изолятов), далее этот граф разбивается по перекрёсткам и создаются двунаправленные линии. Результат можно открыть в JOSM и посмотреть. Если удовлетворяет - делаете процедуру конвертации полученного графа в вашу БД.

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

Offline

#30 2012-10-02 14:45:10

Monochrome
Member
Registered: 2012-10-02
Posts: 15

Re: Нужен граф дорог России - что делать/с чего начать?

Парни, а может я бы дал структуру своей БД, а вы бы её заполнили?
Я заплачУ.

Offline

#31 2012-10-02 16:23:42

moresquitch
Member
From: Ульяновск
Registered: 2012-06-07
Posts: 134

Re: Нужен граф дорог России - что делать/с чего начать?

BushmanK wrote:

А "чистить" - http://www.gpsbabel.org/htmldoc-develop … scard.html как минимум, sat=4

Ко всей базе треков osm бы такое

Offline

#32 2012-10-02 16:54:36

BushmanK
Member
Registered: 2011-05-03
Posts: 5,106

Re: Нужен граф дорог России - что делать/с чего начать?

moresquitch wrote:
BushmanK wrote:

А "чистить" - http://www.gpsbabel.org/htmldoc-develop … scard.html как минимум, sat=4

Ко всей базе треков osm бы такое

Там бы еще максимальная скорость и высота (над GTOPO30 хотя бы) не помешали бы, как ограничение. Вот нафига там авиатреки?


"Не умею" не значит "невозможно", "не видел" не значит "не бывает". "Нет проблемы", вероятнее всего, значит, что "нет мозгов".

Offline

#33 2012-10-02 17:48:51

Sergey Astakhov
Member
From: St.Petersburg, Russia
Registered: 2009-11-13
Posts: 5,779

Re: Нужен граф дорог России - что делать/с чего начать?

Monochrome wrote:

Парни, а может я бы дал структуру своей БД, а вы бы её заполнили?
Я заплачУ.

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

Offline

#34 2012-10-02 18:40:39

moresquitch
Member
From: Ульяновск
Registered: 2012-06-07
Posts: 134

Re: Нужен граф дорог России - что делать/с чего начать?

BushmanK wrote:

Вот нафига там авиатреки?

[irony]рисовать авиамаршруты[/irony]

Offline

#35 2012-10-02 19:08:42

Hind
Member
From: Moscow
Registered: 2009-05-25
Posts: 3,950

Re: Нужен граф дорог России - что делать/с чего начать?

Где-то была тема для предложений о работе...

Offline

#36 2012-10-02 22:24:55

Santacloud
Member
Registered: 2012-03-15
Posts: 331

Re: Нужен граф дорог России - что делать/с чего начать?

Sergey Astakhov wrote:
Monochrome wrote:

Парни, а может я бы дал структуру своей БД, а вы бы её заполнили?
Я заплачУ.

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

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

Hind wrote:

Где-то была тема для предложений о работе...

Эта?

Offline

#37 2012-10-03 07:18:45

Monochrome
Member
Registered: 2012-10-02
Posts: 15

Re: Нужен граф дорог России - что делать/с чего начать?

Ну, с базами данных я и сам разберусь, но мне просто нужна понятная структура с данными.

Offline

#38 2012-10-03 07:23:45

liosha
Member
From: Moscow
Registered: 2008-03-04
Posts: 8,447
Website

Re: Нужен граф дорог России - что делать/с чего начать?

Monochrome, давай структуру базы, посмотрю.
Можно на почту, xliosha@gmail.com

Offline

#39 2012-10-03 07:47:04

Monochrome
Member
Registered: 2012-10-02
Posts: 15

Re: Нужен граф дорог России - что делать/с чего начать?

https://dl.dropbox.com/u/11083106/DATA.rar

Файл с базой. Там создано три узла и три ребра. Свойства узлов и ребер там задаются заморочено, поэтому для пробега можно просто создать отдельную таблицу, я бы её потом преобразовал.

Offline

#40 2012-10-03 07:57:41

liosha
Member
From: Moscow
Registered: 2008-03-04
Posts: 8,447
Website

Re: Нужен граф дорог России - что делать/с чего начать?

Хм... А нельзя ли в каком-нть переносимом формате?
MSSQL под рукой нет.

Offline

#41 2012-10-03 08:06:12

Monochrome
Member
Registered: 2012-10-02
Posts: 15

Re: Нужен граф дорог России - что делать/с чего начать?

А что есть?

Offline

#42 2012-10-03 08:12:08

liosha
Member
From: Moscow
Registered: 2008-03-04
Posts: 8,447
Website

Re: Нужен граф дорог России - что делать/с чего начать?

Чтобы структуру посмотреть, dbf или даже csv достаточно

Offline

#43 2012-12-18 13:36:57

Aclz
Member
Registered: 2012-08-01
Posts: 34

Re: Нужен граф дорог России - что делать/с чего начать?

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

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

P.S. Если нет на базе OSM, то может есть на базе еще чего (2gis, Я.карты и т.п.), но чтобы считался и межгород, и внутригородские маршруты по РФ.

Last edited by Aclz (2012-12-18 13:38:49)

Offline

#44 2012-12-18 13:51:50

Hind
Member
From: Moscow
Registered: 2009-05-25
Posts: 3,950

Re: Нужен граф дорог России - что делать/с чего начать?

Задача коммивояжера, штоле?

Offline

#45 2012-12-18 13:52:59

Aclz
Member
Registered: 2012-08-01
Posts: 34

Re: Нужен граф дорог России - что делать/с чего начать?

Да, типа того.

Offline

#46 2012-12-18 17:06:33

andriano
Member
Registered: 2009-06-15
Posts: 1,667

Re: Нужен граф дорог России - что делать/с чего начать?

Это NP-полная задача.

Offline

#47 2012-12-18 19:40:48

Aclz
Member
Registered: 2012-08-01
Posts: 34

Re: Нужен граф дорог России - что делать/с чего начать?

Да знаю я ее как решать каноничным способом и при каноничных условиях. Но зачем?
Дело в том, что я не вижу большого смысла изобретать велосипед, и уж тем более, как топикстартер, выкачивать гиги данных дорожного графа, обновлять всё это хозяйство регулярно, писать и отлаживать алгоритмы прокладки маршрута, вникать в форматы, при условии, что я сам не создаю новый суперпуперплатныйкоммерческий сервис. В остальных случаях зачем тратить такую гору ресурсов? Всё уже украдено написано до нас, вопрос лишь в том, чтобы найти подходящую, пусть даже платную, реализацию.
И, к слову, даже если у меня точек всего штук 20, нужно будет построить матрицу расстояний 20х20, сгенерить кучу запросов и обработать их. В том же OSRM построение "таблиц расстояний" запрещено, за что следует бан.

Конкретно для Свердловской области в стародавние времена существовала программа "СвО на блюдечке", решавшая эту задачу и предоставлявшая платный API. Всё устраивало, но фирма-производитель загнулась и творение перестало отвечать реалиям.
Гугль имеет подобную бесплатную реализацию "Дирекшенс", но дорожный граф для РФ убог до безобразия, праймари почти нет, нет даже некоторых транков.
ОСМ из того, что видел, справляется с задачей отлично и имеет самую актуальную базу, но все виденные реализации строят маршрут между точками, уже выстроенными в правильном порядке.

Offline

#48 2012-12-18 20:13:26

Sergey Astakhov
Member
From: St.Petersburg, Russia
Registered: 2009-11-13
Posts: 5,779

Re: Нужен граф дорог России - что делать/с чего начать?

Aclz wrote:

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

Проблема в том, что

Wikipedia wrote:

Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.

А на малом числе точек она практически никому не интересна. Поэтому большинство юзают приблизительные алгоритмы, которые могут выдавать неидеальные (но приемлемые для юзера) варианты. А приемлемость определяется на базе компромиссов, которые у каждой реализиции свои и заточены под конкретную предметную область. И эти алгоритмы зачастую являются предметом know-how.

Aclz wrote:

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

Скорей всего эти реализации надо среди всяких пакетов логистики искать.

Offline

#49 2012-12-18 21:17:23

Aclz
Member
Registered: 2012-08-01
Posts: 34

Re: Нужен граф дорог России - что делать/с чего начать?

А на малом числе точек она практически никому не интересна.

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

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

Скорей всего эти реализации надо среди всяких пакетов логистики искать.

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

Offline

#50 2012-12-18 21:31:35

Sergey Astakhov
Member
From: St.Petersburg, Russia
Registered: 2009-11-13
Posts: 5,779

Re: Нужен граф дорог России - что делать/с чего начать?

Aclz wrote:

Обработать матрицу уже проблем нет, т.к. размерность матрицы в данном конкретном случае лежит в пределах 10-20 точек.

Вы плохо представляете себе сложность задачи.

Wikipedia wrote:

Для простого варианта, симметричной задачи с  городами, существует 65154f862c4ac04ef32e538ded254474.png возможных маршрутов, то есть для 15 городов существует 43 миллиарда маршрутов и для 18 городов уже 177 биллионов.

Это именно обработка матрицы.

Last edited by Sergey Astakhov (2012-12-18 21:32:34)

Offline

Board footer

Powered by FluxBB