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

[bim2010]

Кто нибудь разбирался как решается транспортная задача у Google Maps, Google Earth и Openstreetmap

http://groups.google.com.sb/group/Google-Maps-API

http://wiki.openstreetmap.org/index.php/FAQ
http://apps.sourceforge.net/mediawiki/t ... g_Salesman

http://www.foss4g2007.org/presentations ... ent_id=83.

http://ask.slashdot.org/article.pl?sid=08/01/09/2311215

http://sourceforge.net/projects/travelingsales/

http://www.ogleearth.com/2006/08/traveling_sales.html
A Travelling Salesman Problem Solver for Google Earth

Смотрим на тексты решения (php,java)
Похоже, всюду используется метод ветвей и границ. Кто нибудь проверял как они объезжают территорию? Как это работает? У меня это происходит не всегда оптимально. Проверял на 30 точках. Иногда при создании маршрута, если точки расположены достаточно близко (ларьки на оптовом рынке) происходит так - метод оставляет часть их на обратный путь ( петля), хотя точки расположены буквально в 30 м друг от друга. Конечно, можно было бы объединить их в одну точку доставки, суммируя их объем, но не всегда это удобно. Работает метод достаточно шустро на 30 точках – 0.5 сек. Да и то основное время тратится на выгрузку из базы транспортного графа в массив.
Проверял, как оптимизирует маршрут ИНГИТ. Там другая проблема. Он действительно создает оптимальный маршрут с точки зрения расстояния, но воспользоваться им нельзя. Ездит не по главным дорогам и трассам, а по второстепенным, без покрытия, дворами - “Тропой Хошемина”, где не всегда и проедешь. Не учитывает дорожное покрытие, полосность и т.д…
Одна из задач стоящих передо мной, заключается в отыскании такого плана перевозок продукции с m складов к n который потребовал бы минимальных затрат. Есть около 100 единиц автотранспорта. Часть заявок принимается заранее, большая часть в этот же день. Лозунг компании – 2 часа на доставку по городу с момента приема заявки.

Похоже, мне надо использовать не ветви и границы, а метод потенциалов или северо-западного угла. Подскажите пожалуйста хотя бы название метода.
Я не нахожу в интернете реально работающих решений оптимизирующих одновременно несколько маршрутов.
Кормен, Вентцель, Таха, Харари, Кристофидес, Грешилов, Окулов, Новиков,
Аникин, Гаджинский, Неруш и т.д… дают решения упрощенных задач (для студенчества).
Любимая книжка - Кормен.

Забавно, что в части литературы метод ветвей и границ называют точным, в другой приближенным, а Новиков дописался до того, что решений нет вообще. Смешно. Смешно.
Спрашиваю у доцента – зав.кафедрой высшей математики университета. Его ответ – метод ветвей и границ – точный. Прикольно ! Конечно, проверяют по матрице 6 на 6.
На самом деле входные условия задачи (требование заказчика) приводят к необходимости решать матрицу переменных четвертого порядка т.е. 1000x1000x1000x1000
Народ откликнись пожалуйста !!!
Чуствую, что профи промолчат, а начинающие освоение GIS и задач основанных на их использовании не знают еще, что Travelling Salesman Problem - действительно проблема!!!

Уважаемый администратор форума не знаю, в какой из уже существующих разделов отправить свой вопрос. Переместите на Ваше усмотрение.

[gis]

у даты+ есть решение для логистики, вроде бы неплохое. Но стоит относительно дорого. Может вам стоит подумать приобрести его а не изобретать велосипед
www.dataplus.ru ((вроде)

[Mitrich]

только Дата+ говорит, что АркЛогистик хорошо справляется с 50 машинами - не больше, потом глохнет. Надо обязательно поинтересоваться перед покупкой.

[bim2010]

Около 11 лет назад готовое полнофункциональное решение уже было приобретено у фирмы с название подобным тому, о чем Вы говорите (50% совпадение). Слава богу, у них хватило ума, оставить тексты и последующие 4 года я дописывал и переписывал функционал. Конечно же, при покупке решения было клятвенно заявлено, что транспортная задача решена. Лёлик не сумлевайся усе будет у порядке! Что же там внутри оказалось за те немалые деньги, которые были заплачены. Сначала строят кратчайшую связывающую сеть (“минимальное дерево”), затем по каждой ветви сети, начиная с пункта, наиболее удаленного от начального пункта, считая по кратчайшей связывающей сети, группируют в маршрут. Напоминает откусывание веток у елки. Затем внутри каждого маршрута - ветви и границы. Эту комбинацию из двух методов нельзя назвать точной.
Хочу отметить, что до внедрения проекта диспетчер по логистике, не используя компьютер, легко “разруливал” в одиночку больше 1000 заявок в день...

То, что переделал я - также приближенные методики, не имеющие математического обоснования. Что касается оптимизации одного маршрута, использую идеи Кормена, Неруш, и Аверченкова о свойствах выпуклого многоугольника. (В оригинальной английской версии у Кормен сноска о том, что и эти свойства еще не доказаны).
Так что внутри одного маршрута оптимизация работает приемлемо - не хватает математического обоснования методик.
Что же касается оптимизации одновременно нескольких маршрутов относительно хороший результат дали “статистические” методики в связке с идеями Вирта о топологической сортировке (имеется в виду сортировка элементов, для которых определено отношение частичного порядка). Вся территория делится на зоны - у меня их около 90. Происходит закрепление клиентов по зонам. Снижаем размерность матрицы.
Внутри зон разные подходы и методы по их обходу. Для микрорынков своя методика (допустимые шаблоны обхода), для других зон временной график доставки,
А еще понятие VIP –клиент, а еще диапазон допустимой доставки, а еще разная грузоподъемность автотранспорта, а еще обеденный перерыв + еще десяток взаимоисключающих требований.
Когда же мне в руки попалась Mapinfo 6.0 я перестал дописывать этот проект, так как GIS функционал серьезно уступал Mapinfo на тот момент. Единственным преимуществом была высокая скорость GIS движка по отображению вектора – она до сих пор превосходит Mapinfo.
Так что вопрос о покупке не стоит. Речь идет о том, что хотелось бы перейти на WEB GIS OPEN SOURCE, хотя бы частично. Мой вопрос не кто решает транспортную задачу (Почти все декларируют что она давно решена), а как она решена – используемые алгоритмы и методы?
Смотрим что в API у Google Maps, Google Earth и Openstreetmap – а там просто “отмазка” - ветви и границы. Что изменилось за 11 лет ?

Меня интересует - существуют ли WEB GIS топологические (кстати Mapinfo не топологическая GIS).
Есть ли GIS (или API) у которых, вектор на клиенте работает быстрее, чем у Flex(flash)?

[gis]

Ну за алгоритмами наверно надо к математикам на форум
Это вроде чисто математический вопрос из области теории графов наверно...

Про зоны - это правильно сделано. Зоны для Москвы должны быть на пересечении секторных и круговых. Это при расположении точки выезда и возврата близком к центральному. Если точек выезда или возврата несколько, и если они не центральные, тогда зональная политика усложняется.
В принципе при правильном использовании зонирования вся задача сводится к поиску оптимального маршрута для одного средства по известным точкам.

Вам надо посмотреть QGIS, KOSMO, gvSIG - вроде у кого-то был модуль для решения логических задач. Если Вы хотите использовать OS c доступом к хранилищу через интернет. То на базе Mapserver вы можете сделать картографический веб-сервис а в качестве клиента использовать любую из вышеперечисленных OS GIS.

Кстати гугловские сервисы с OS вроде ниче общего пока не имеют.

Я так понимаю что речь идет об инкассаторской деятельности? Вам стоит подумать насчёт рисков использования OS... Может все таки чем самому писать или использовать OS продукты, лучше приобрести коммерческий - его по крайней мере официально тестируют. Связку подобную вышеизложенной можно реализовать и на базе ArcGIS.
Вы не обижайтесь, но как-то с трудом верится, что один человек сможет сделать то что делают сотни...
Но если выйдет что дельное и Вы выложите это для любой из OS GIS - я думаю все порадуются

[bim2010]

Вы не обижайтесь, но как-то с трудом верится, что один человек сможет сделать то что делают сотни...
Возьмите в правую руку мышь и запустите Microsoft Office Excel 2007
Не спеша наберите в любой ячейке
=77,1*850
Нажмите Enter

Если Вы получите результат 100,000 то значит у Вас не установлен патч
http://download.microsoft.com/download/ ... 86-glb.exe

Проверьте результат на калькуляторе который должен быть 65,535
...
Неудивительно что потом ракеты куда попало попадают, спутники не...
Вы тоже не обижайтесь ...
По поводу Mapserver - полностью с Вами согласен. На клиенте пробую Openlayers. Вектор на клиенте не очень быстро работает, а народ уже привык к интерактиву и преобразовывать его(вектор) в растр не хотелось бы.
Может из перечисленного Вами кто- то смог бы побыстрее с вектором на клиенте справится.
Еще вопрос про Mapserver - одно дело я его локально тестирую, другое когда машин 50-60 одновременно начнут преобразовывать вектор (у меня на входе всюду вектор) в растр и что мне об этом скажет хостер.
Если будет все плохо может сразу часть вектора преобразовать в битмап без Mapserver (c этим никаких проблем нет). Адресный план у меня не меняется каждую минуту. Ну если изменится - только этот фрагмент и менять.
А пробовали Вы битмап в базу заливать, я пробовал - побыстрее работает. Только вот не под всеми ОС правильно отображает.
По поводу "Вы выложите ... все порадуются" речи нет - это внутрикорпоративное решение.
Зачем web? - Наличие филиалов и желание руководства увидеть что происходит не приходя в офис.

Что вы имели в виду говоря про "коммерческий... " не это WebMap и WebMap Route и http://www.resident.ru/

[gis]

Сервер-клиент структура

Сервер - mapserver, на котором создается WFS http://en.wikipedia.org/wiki/Web_Feature_Service
Клиент - удобней реализовать на QGIS или KOSMO, при необходимости дописать то что необходимо.

То же самое можно сделать на коммерческом софте ESRI или MapInfo или Autodesk..... цены примерно одинаковы, функционально в лидерах ESRI.

Карту Москвы с подробным дорожным графом и периодически обновляемую продает таже дата+, но фирма другая какая-то делает.


Из любого правила бывают исключения Эйнштейн тому пример
Но все таки MS Of гораздо лучше OF

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

[Каминский Вадим]

Свежий велосипед http://resources.esri.com/geoprocessing ... ptID=16044

Очень хочется потестить, но при инстале http://pulp-or.googlecode.com/files/PuLP-1.21.04.zip
попадаю на ошибку:
error: package directory 'pulp-or\src' does not exist
Мож, кто-нить из девелоперов сможет разобраться как заинсталить pulp.

[Vladimir Morozov]

Вадим !
А попробуйте ещё вот это
http://www.new-techniq.org/alma/routing.html
Здесь как раз флэш, о котором Вы упоминаете...
С уважением,
Владимир Морозов
PS
И посмотрите здесь
http://www.new-techniq.org/alma/prob.html
Скоро мы эти две технологии совместим... Будет один движок..
Да, чтобы маршрутизаторы работали как надо (через дорогу объекты, а хожу
через Африку или по плохой дороге), надо иметь ПОЛНУЮ базу знаний....
И алгоритмы обработки (с элементами Искуственного интеллекта....)
Тогда это будет работать как надо....
Пока эта вся "Маршрутизация" (OpenStreet и прочие...) может использоваться ЧИСТО ДЛЯ КАКИХ ЛИБО ПРИКИДОЧНЫХ, ОЦЕНОЧНЫХ РЕШЕНИЙ....

[andreichernov]

Здравствуйте!

Вы не там ищете. Для транспортной задачи ГИС почти не при чем. Поясню.
Ваша транспортная задача решается в 2 действия.

1) Сначала вычисляются кратчайшие пути между всеми возможными точками развоза.
Это действительно делается по ГИС. При этом Вы можете ограничить набор сегментов уличной сети, которые
участвуют в задаче или поставить главным магистралям бОльшие веса.
Получаются маршруты со значением времени.
2) Строится полный граф с вершинами - точками развоза и ребрами-маршрутами, в которые записываются веса - найденные значения кратчайших путей.
Это уже не гисовская структура и это стандартный вход для решения транспортных задач. Там даже координаты не нужны. Его Вы подаете на вход алгоритма решения транспортной задачи. Это стандартный вход для подобных алгоритмов. Попробуйте матлаб или подобные пакеты, в том числе специализированные. Вам нужно там рыть.

Допустим вы в пакете решили транспортную задачу, то бишь получили список маршрутов.
Его Вы уже отображаете в ГИС , используя связь маршрут<-> сегменты уличной сети.

С уважением , Андрей Чернов.

[Vladimir Morozov]

Уважаемый Андрей !
Вы взяли и до минимума сузили задачу...
Да, так как Вы пишите, народ помиру и делает... Узнал (как то ?!) характерсти уличной сети (те самые "веса"), составил граф, "немножко" ГИСА и всё - задача комивяжера, как между лавками оптимально развести товар, решена !
Есть ведь и более серьёзные задачи, которые я имел ввиду!
Например, наши фирмы транспортной логистики просят решить, такие.. .
Расчитайте и нарисуйте нам маршрут "хороший" ! (то бишь близкий к оптимальному).
Маршрут такой, как из г.Алматы (улица Абая д.36) перевезти товар, например, баранов, в г.Франкфурт на Майне, улица Либенштрасе 48)
Это мне (клиенту) надо, чтоб я сосчитал, какой счет я обосную и предъявлю клиенту ?
И где ж я эти самые "веса" возьму, и скока надо бензину купить и прочее, чтобы я решил клиенту его транспортную задачу задачу и он довез этих самых баранов (живыми !) ?
Поэтому я писал, что нужно, чтобы транспортные задачи решались в полный рост и без достаточно полной характеристики транспортной сети (ГИС) не обойтись !
А на сегодня этого нет...
И, наверное вряд ли когда будет...
И дело совсем не в инструменте, какой взять за основу или сваять самому...
С уважением,
Владимир Морозов
PS
Поэтому и "ишем" именно там...

[andreichernov]

Здравствуйте!

Изначально вопрос был про алгоритмы. Какие точные, какие приближенные.
Я на него и отвечал, что надо абстрагироваться от ГИС.

В любом случае, какую бы Вы задачу не решали и как, есть следующие этапы.
1 этап - составляется "геометрическая сеть" в терминах ArcGIS (слои ГИС),
2 этап геометрическая сеть преобразуется в логическую сеть (граф с весами), при этом возможно распутываются все Т-образные примыкания, дорожные знаки и пр.
3 этап - запускается алгоритм решения задач на графе.
4 этап - результат отрисовывается на ГИС

Это верно и про Вашу задачу "поставки баранов во Франкфурт".

С уважением, Андрей Чернов.

[stopa85]

Хочу свои пять копеек вставить:)

В англоязычной части интернета эта задача называется Vechicle Routing Problem.
И для большой размерности она решается исключительно эвристически. Т.е. не точно.
У меня есть данные, что на 2002 год не было точных решений для этих задач с числом клиентов более 100. А минимальное число клиентов в задаче, для которой не удалось найти точного решения - 50. Такова природа задачи.

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

Поэтому я бы не надеялся на "хорошее" решение чисто практических задач из "коробки".
В любом случае понадобиться доработка напильником.

[Vladimir Morozov]

Здравствуйте Все!
Я про четыре, пункта (этапа), которые декларирует Андрей, выполнение которых гарантирует успех.
А также эфективное решение моей задачи по "баранам" ....
К сожалению (4 пункта), этого крайне мало и работать эффективно такая схема, к сожаленю, не будет...
Без актуальных, постоянно поддерживаемых БАЗ ЗНАНИЙ, огромного количества факторов, которые надо учесть в режиме построения маршрута, а также ВО ВРЕМЯ ЕГО РЕАЛИЗАЦИИ (когда я по нему передвигаюсь) - ничего путевого пока получить нельзя....
Может быть (как пишется в предыдущем посте) - на 100 -200 транспортных единиц и можно исхитриться, да и то с применением "эвристических способов" (то бишь экспертных оценок и систем....).
Без нормальной базы ЗНАНИЙ, постояно актуализируемой и тех самых элементах систем искуственного интеллекта (экспертные системы, эвристических методов и проч.) ничего путевого не будет !
Вспомните тех трех парней на перепутье, которые стояли перед камнем, на котором было написано :налево пойдешь......., направо подёш... и т.д.
Так вот, тогда, то чего они читали, и было НАЧАЛОМ БАЗ ЗНАНИЙ, необходимых для начала каких то движений...
А просто знание маршрута, даже самого короткого - ещё не успех !
Надо ж чтоб сработало ограничение - "бараны должны приехать во Франкфурт ЖИВЫМИ !" (с учетом минимума израсходованной солярки.... )
А это немаловажное условие, Андрей, в четырёх пункта Вы упустили....
С уважением,
Владимир Морозов
PS
Наверное было бы правильным в постановку Танспортной задачи включить:
5. Создание, актуализация Баз данных (знаний) и интерфейсов взаимодействия с транспортными ситемами.
Это, например, позволяет реализовывать функции “пространственного анализа”, которых сейчас великое множество !
В том числе и в России
http://blogs.mail.ru:80/community/maps. ... 86AB3.html
Просто Человек в начале своей рубрике просил: "Народ откликнись пожалуйста !!!"
Вот я "откликаюсь", чтобы он подошел к решению этой задачи СИСТЕМНО !
И не потратил впустую время , решая частные задачки, которые успеха не дадут...

[bim2010]

Спасибо "stopa85". Похоже что Вы в теме.
По поводу многочасовых расчетов - это не так. Новые заявки поступают не одним махом. а постепенно.
Поэтому оптимизация маршрутов происходит последовательно. Речь идет о параллелизации процесса ввода и расчета.
Аналогичный пример - расчет и печать на принтере. Ну и еще не забывайте что есть ночь для расчетов.
Кроме того сами данные должны быть хорошо структурированы. Естественно это базы. Я делаю принудительно индексы по тем полям (кроме id), которые отвечают за оперативное построение транспортного графа.
Пока я тоже не нахожу точных методик оптимизации.
Статистические методики которые использую сейчас (см. выше) хотя и дают результат но мне это зонирование
напоминает ручную работу диспетчера. Все разговоры о том, что был когда то "шелковый путь", и он прошел именно там где он прошел и никак иначе. Что исторически сложились эти зоны, а мы их только зафиксировали.
Что то как ехать - знает только тот кто едет, и прочие сентенции ... Все это ... как то... от лукавого.

Думаю что приближенные методики построенные на комбинации алгоритмов теории графов могли бы дать неплохой результат. Я уже почти созрел для их написания.
Я думаю о нескольких алгоритмах которые будут работать на разных этапах расчета. Сначала получаем группу решений при этом часть параметров будет упрощена (через коэфф. приведения). На заключительной части алгоритма разворачиваем влияние всех параметров. Поскольку заключительная часть метода обладает не высокой сходимостью необходимо в первой части алгоритма серьезно постараться.