QGIS и логистика

[Geo-U-Piter]

Всем привет,
Очень нужен совет для решения следующей задачи.
На большой территории есть несколько сотен свалок и несколько оборудованных полигонов ТБО. Необходимо найти инструменты (желательно в рамках QGIS) которые помогут рассчитать оптимальный маршрут вывоза свалок на Полигоны, с учётом имеющихся дорог, объёма свалок (есть данные) и возможности загрузки полигонов (есть данные).

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

[trir]

python

[bim2010]

Венгерский алгоритм
QGIS + R: https://cran.r-project.org/web/packages/clue/clue.pdf (solve_LSAP стр 58)
http://www.inside-r.org/packages/cran/c ... solve_LSAP
minimum-cost flow problems
https://sites.google.com/site/eospansite/introqgis_r
Integrating QGIS and R: A stratified sampling example
Интеграция QGIS с другим программным обеспечением: R & PostGIS
GIS for Transport Applications
http://robinlovelace.net/r/2015/04/20/r ... sport.html
Introduction to R and QGIS for transport applications
QGIS + python: AequilibraE
https://www.youtube.com/watch?v=VsgyBil ... Jv7d80mg5y
http://www.aequilibrae.com/
http://software.clapper.org/munkres/
https://github.com/tdedecko/hungarian-algorithm
Аникин Б.А. Практикум по логистике (стр 203)

[Boris]

Задача не сводится к задаче "коммивояжера", если объемы являются ограничивающим факторов, по общему объему или локальному = предельный объем в единицу времени или период.
В такой постановке имеют место две задачи: "задача о рюкзаке" (имеет алгоритмическое решение) или задача о "N-рюкзаках" (имеет решение только полным перебором вариантов) и задачей "коммивояжера". В зависимости от того, что назначается "оптимумом" - расстояния, время, равномерность загрузки "полигонов", число "коммивояжеров", будет построена разная сеть и оптимум будет разный.
Какие то из параметров придется фиксировать заранее, поскольку решение задачи находится в объединении алгоритмов полного перебора и перебора с возвратом. Если еще и число "коммивояжеров" переменно, то скорее всего алгоритм будет экспоненциальным.

[bim2010]

Boris:

Задача не сводится к задаче "коммивояжера", если объемы являются ограничивающим факторов, по общему объему или локальному = предельный объем в единицу времени или период.
В такой постановке имеют место две задачи: "задача о рюкзаке" (имеет алгоритмическое решение) или задача о "N-рюкзаках" (имеет решение только полным перебором вариантов) и задачей "коммивояжера". В зависимости от того, что назначается "оптимумом" - расстояния, время, равномерность загрузки "полигонов", число "коммивояжеров", будет построена разная сеть и оптимум будет разный.
Какие то из параметров придется фиксировать заранее, поскольку решение задачи находится в объединении алгоритмов полного перебора и перебора с возвратом. Если еще и число "коммивояжеров" переменно, то скорее всего алгоритм будет экспоненциальным.

В приведенных ссылках нет задачи "коммивояжера" и "задача о рюкзаке". Мной даны ссылки на два метода решения задачи о назначениях. Обобщенная задача о назначениях.
Посмотрите внимательно ссылку на Аникина начиная с стр 201 и далее. Есть несколько методик решения. Я реализовал две, еще в прошлом веке.

[Boris]

Посмотрите внимательно ссылку на Аникина начиная с стр 201 и далее.

Спасибо. Я умею внимательно смотреть, может быть даже слишком. Предыдущая, до того как вы ее исправили ссылка, была указана на страницу 220.
И еще раз прочитайте условие задачи данное автором вопроса, и постановку задачи на стр. 201. Автор не спрашивал как ему оптимально "забить" все полигоны мусором со всех свалок. Он спрашивал как ему оптимально, не дав определение оптимальности, переместить мусор со свалок на неизвестные заранее полигоны. Автор указал, что у полигонов есть ограничения, но опять же не упомянул какие именно. Кроме расстояния самые очевидные - это вид полигона, в жизни не все полигоны принимают любой мусор; и объем, который полигон может принять в день или всего. Автор ничего не упомянул о том должна ли машина обслуживать путь свалка-полигон или путь "свалка-свалка-...-полигон". На задачу коммивояжера указали вы своей начальной ссылкой.
Если автору не надо посещать несколько свалок одной машиной, а его интересует оптимум "свалка-полигон", число машин - не ограничение, а ограничение только объемы вывозимого и объем принимаемого, то имеет место быть классическая "Транспортная задача"

ранспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.[1][2] Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача по теории сложности вычислений входит в класс сложности P. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

[bim2010]

Автор не спрашивал как ему оптимально "забить" все полигоны мусором со всех свалок. Он спрашивал как ему оптимально, не дав определение оптимальности, переместить мусор со свалок на неизвестные заранее полигоны. Автор указал, что у полигонов есть ограничения, но опять же не упомянул какие именно. Кроме расстояния самые очевидные - это вид полигона, в жизни не все полигоны принимают любой мусор; и объем, который полигон может принять в день или всего. Автор ничего не упомянул о том должна ли машина обслуживать путь свалка-полигон или путь "свалка-свалка-...-полигон". На задачу коммивояжера указали вы своей начальной ссылкой.

Boris все не так! Оптимизировать нужно затраты. Деньги. Себестоимость. Расстояние важный, но не единственный параметр. Другой параметр - вес/ объем перевозимого мусора. Ограничения: грузоподъемность единицы транспорта; количество рейсов в смену; режим работы источника, приемника ТБО и транспорта; транспорт не одинаков по параметрам и характеристикам, разный тип топлива: дизель/бензин, маршрут не может быть бесконечен - необходимы заправки (вкл. заправок в маршрут), качество, скоростной режим дорог, пробки, и т. д.
Читать Неруш. Задача сводится к минимизации затрат по перевозке всего мусора, имеющимся разнообразным транспортом. Необходимо назначить транспорт для перевозки от источника к приемнику с ограничениями, при которых общая себестоимость будет минимальной.

Предыдущая, до того как вы ее исправили ссылка, была указана на страницу 220.

- нет, это неправда.

[bim2010]

Транспортная задача решена в QGIS.
Библиотека сетевого анализа QGIS: описание и примеры.Результаты решения транспортной задачи есть входная информация для "венгерского метода", т.е. транспортная задача является подзадачей (одним из этапов) при реализации методики.

[Александр Мурый]

Библиотека сетевого анализа QGIS: описание и примеры.Результаты решения транспортной задачи есть входная информация для "венгерского метода", т.е. транспортная задача является подзадачей (одним из этапов) при реализации методики.

http://gis-lab.info/qa/qgis-network-analysis-lib.html
Просьба давать ссылки на сами опубликованные статьи, а не на вики.