Вычисление длин по дорожному графу, градусы - метры

[bim2010]

По поводу моей первой ссылки ключевым словом в ней является Pgrouting
http://en.giswiki.net/wiki/PostLBS
http://pgrouting.postlbs.org/wiki/Works ... G2008/ch02
А вот это оставлю без перевода:
http://74.125.43.113/search?q=cache:iQ2 ... clnk&cd=28

Rob said...
I recently put together a demo for the local 911 dispatch centre. It was a custom QGIS application using pgRouting on top of PostGIS. This was an entire open source sandwich. The 911 boys had a little trouble getting their heads around the idea that the software was free, considering that it worked better than any proprietary demo they had seen.

Еще одно решение
QGIS + PostGIS + PostGraph
http://www.keittlab.org/node/160

Продолжение вашей ссылки:
http://www.parallel.ru/ftp/chg2000/Chepovsky.zip
Цитата:

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

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

Вывод: кризис математики продолжается !

[stopa85]

Bim2010, я не понимаю, что Вы хотите этим сказать?

[bim2010]

Построение расписания можно разбить на три этапа:
1) распределение клиентов между агентами (разбиение множества C на m непересекающихся подмножеств);
2) выбор порядка обслуживания клиентов для каждого агента;
3) оптимизация маршрута каждого агента при фиксированном порядке обслуживания клиентов.
Таким образом, суммарные ограничения по характеристикам для каждого агента
проверяются на первом этапе, ограничения на вершины—на первых двух, а на третьем этапе проверяются временные ограничения.

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

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

Ну и какой результат? Задумайтесь! Необходимо доставить клиенту товар в срок, только метод рассчитывает несколько тысяч секунд при полном использовании ресурсов компьютера под эту задачу.
Реально ведь никто Вам не даст полностью ресурсы сервера только под эту задачу. Т.е. о том, как вам надо ехать сегодня Вы узнаете только завтра.
Вообще говоря в иностранной литературе уже есть наработки по переопределению класса NP через другие классы.

[stopa85]

о том, как вам надо ехать сегодня Вы узнаете только завтра.

Это да. Это очень серьезная проблема... потому и применяют эвристические и псевдо эвристические методы...
О том что "все хреново" я тоже знаю

Я собираюсь применить генетический алгоритм в своей программе. ИМХО это более или менее реальный выход из сложившейся ситуации.

[bim2010]

The Genetic Algorithm Utility Library
http://gaul.sourceforge.net/

[stopa85]

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

На OSM-карте Берлина вычисления занимают меньше 3-х секунд (есть поле для оптимизации), это не считая времени потраченного на построение матрицы смежности.

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

Установка
Я компилировал свой плагин вместе с qgis, поэтому инструкция по установке проста:
Скопируйте содержимое архива vrp-plugin-0.01.tar.gz в папку qgis-1.0.x/src/plugins/
В файл qgis-1.0.x/src/plugins/CMakeLists.txt добавьте строчку:

Код: Выделить всё

SUBDIRS (vrp)

далее следуйте инструкции по установке qgis.

ShortestPath mini Howto
Запустите qgis, активируйте плагин vrp.
В новый проект вставьте слой roads.shp из архива roads.shp.
Укажите настройки плагина. Команда меню "Модули-vrp-Vrp settings".
Road layer: roads
direction field: oneway
speed field: maxspeed
(остальное можно оставить по умолчанию)

Теперь:
1) у вас активировалась кнопочка показа направления движения, и
2) Если слой дорог в режиме редактирования, то Вы можете в режиме Vising редактировать направление движения по дорогам.
3) Боковая панель ShortestPath - в работоспособном состоянии.

Укажите начальные и конечные точки движения и нажмите на кнопку "calculate". Будет построен и отображен кратчайший маршрут - как на рис2.png

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

P.S. Все таки цель проекта - интеграция ГА для решения транспортной задачи в QGIS. Не ругайте меня за мое высокомерное название плагина:-)

[rimbo]

Stopa85 можно ли данный плагин поставить в КуГис на виндоз? С С++ абсолютно не знаком. При установке в папку с плагинами пишет ошибку - не найден модуль vpr.

[Максим Дубинин]

rimbo, надо компилировать под новую версию QGIS в Win
боюсь что если с C++ абсолютно не знакомы, будет сложновато

[Voltron]

Может имеет смысл положить код в репозиторий и время от времени собирать библиотеку для актуальной версии? А там глядишь кто-то заинтересуется дальнейшим развитием

[Максим Дубинин]

сказано-сделано
http://svn.gis-lab.info/road-graph/

[stopa85]

Отредактировал свой плагин. Из изменений:
1. Устранена проблема, когда слой дорог имеет другую, отличную от проекта, систему координат. Правда все работает только если включить преобразование на лету.
2. Работает с QGis 1.5. Где-то начиная с версии 1.2 работоспособность была нарушена.
3. Теперь плагин - полноценный проект. Для его компиляции больше не нужно ковырять исходники QGis и устанавливать его вместе с ним. Достаточно:

Код: Выделить всё

mkdir build 
cd build
make 
make install

Из планов на будущее:
1. Экспорт кратчайшего пути в линейный слой.
2. Использование http://gis-lab.info/projects/osm-export.html для полноценной маршрутизации. Правда для этого придется пилить последние.

Что касается проблемы маршрутизации, то процитирую мой ответ на личное сообщение:

"Мой" алгоритм дает хорошие результаты только для 50-70 точек на 3-4 агента. Мне требовалось решить задачу для 150-200 клиентов и 10-15 машин. К сожалению, ничего универсального не вышло. Хотя были и реальные задачи и люди готовые заплатить реальные деньги.

Возможно, в будущем, я вернусь к этой задаче.