Транспортная задача у Google Maps, G E и Openstreetmap

[stopa85]

Здравствуйте еще раз.

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

В центре экрана "черным квадратиком" обозначен склад.
Маленькими кружочками нарисованы клиенты. Сверху кружочка номер клиента и в скобках сколько товара ему нужно. Под кружочком частично нарисовано "окно клиента" время когда клиент должен быть обслужен.

В правой части окна "Vrp View":
Указывается "общее время" доставки в часах, количество и грузоподъемность каждого "агента" (ну то есть машины).

Задачи генерируются случайным образом.

Сейчас думаю с какой бы ГИС и как бы интегрировать.

[KolesovDmitry]

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

[stopa85]

1) В большинстве случаев из жизни, достаточно найти не оптимальное решение, а близкое к оптимальному.

А на сколько близкое решение Вас устроит? 5% 10% или 50%? Эвристика тем и плоха, что не позволяет показать степень близости к оптимальному.

2) Методы решения, нацеленные на поиск оптимального решения очень часто бывают и сложнее, и затратнее, чем эвристические.

Это точно. Однако именно они способны показать, на сколько "текущее полученное решение" близко к оптимальному.

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

Я тоже не уверен, тут никто не может быть уверенным.

[nodemind]

Привет всем!

по поводу транспортной задачи попробуйте NodeMind

Описание 1

Описание 2

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

[Дмитрий Барышников]

С учетом скриншотов - может быть плагин к QGIS?

[bim2010]

С учетом скриншотов - может быть плагин к QGIS?

Для QGIS они уже есть:
Quantum Navigator плагин на Python для QGIS автор Martin Dobias
QGIS + PostGIS + PostGraph
http://bazaar.launchpad.net/~tkeitt/pos ... runk/files
Вычисление длин по дорожному графу, градусы – метры
stopa85 написал плагин на С++ для QGIS


Кроме того можно воспользоваться
pgRouting

Boost Graph Library
Библиотека различных алгоритмов на C++ содержит в т.ч. алгоритмы решения транспортной задачи.

Еще один интересный плагин для гис с открытым кодом на java OpenJUMP
MULTI-DEPOT VEHICLE ROUTING
Плагин работает на shp файлах.