Какой программой решить задачу по планированию перевозок?

Question

[Нерон Лордов]

Есть вот такая задача:
https://cloud.mail.ru/public/Kt7n/sfk4duPpv
(pdf ~5mb)

Вкратце: дается 30 магазинов на карте с координатами. У каждого магазина есть потребности в трёх товарах. Потребности меняются в зависимости от дня недели. Задача - найти оптимальные пути поставок, учитывая грузоподъемность машин, зарплату водителя (и переработки), время на разгрузку, необходимость найма дополнительных машин и т.п. и т.д. (переменных тьма).

Понятно, что вручную это делать нельзя, а 4 часа гугления ничего путного не дало (либо какие-то исходники кода С/С++, либо демки, в которых ничего не настраивается, либо статьи без ссылок на программы).

Я не программист... Подскажите пожалуйста программу для такой задачи. Или может где можно скачать модельку в формате Эксель. Или если сами можете решить - давайте обсудим цену.

PS: еще одна сложность - карта магазинов дана в виде сетки, и машины могут двигаться по ней ТОЛЬКО "ступеньками" - либо вертикально, либо горизонтально, по диагонали - нельзя.

Comments

[ivkol]

какие сроки?

[Нерон Лордов]

ivkol: до 12 января

[ivkol]

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

[ivkol]

Nekto_Habr: и отпишитесь, если нетрудно, когда узнаете как решать надо было и когда решите - поделитесь, что и как.

[Нерон Лордов]

ivkol: 20к? мне тут за тыщу предлагают сделать (а в основном 2500-2600), вот думаю как быть)

Answer 1

[Константин Цветков]

Это называется линейное программирование (к текущему понятию не имеет отношение). Есть сайты, которые помогают решать такие задачи.

Comments

[Нерон Лордов]

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

Answer 2

[Philipp]

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

Comments

[Нерон Лордов]

Я так и подумал, после дня изучения материалов по теме... Проблема в том, что эта задача дана обычным студентам-логистам, которые с программированием не знакомы. И не понятно, какими инструментами пользоваться - в решении скорее всего используется несколько алгоритмов, и как ни странно - во всей великой сети нет специального ПО с человеческим интерфейсом.

[Philipp]

Nekto_Habr: так в этом-то и ответ кроется. Их же учат тому, какие методы применяются, как это все считается. В обучении рассматриваются эмпирические методы ручного расчета. Им студентов учат. Вы пришли на сайт программистов, которые в принципе привыкли решать задачи в общем виде, но в данном случае задача такого класса, которая в общем виде не решается вообще. Т.е. в идеале там нужен полный перебор, но увы столько процессорного времени нет ни у кого. Поэтому применяются разного рода специфичные к области методы. Честного говоря, вам тут больше нужен специалист по логистике, нежели программист.
Честно говоря, попахивает тем, что ваши студенты народ бездарный. Я никогда не сталкивался с неподъемными задачами для уровня студента, такими, к которым их не готовили. Если студент не может решить задачу, значит он не готовился все время, не ходил на лекции и не читал учебников.

[Нерон Лордов]

Артём Петренков: и сколько времени уйдет на ручной перебор для 30 с гиком магазинов помноженные на все заложенные переменные? Сомневаюсь, что жизни хватит...

Philipp: для обучению методов и ручных подсчетов дают задачи с гораздо меньшим объемом данных (в учебниках - не более 10 магазинов и не более 1 вида товаров, ну и еще какая-то одна переменная, всё), а тут вон какие таблицы с исходными данными и ограничения дурацкие, вроде того что нельзя двигаться между магазинами напрямую, а только ступеньками (см. посткриптум в исходном вопросе, апдейтнул его)

[malbaron]

Такими вещами занимаются программисты, работающие в логистических компаниях.

Мы, программисты, работавшие в логистических компаниях, решали совсем-совсем другие задачи
;))))

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

А в подавляющем большинстве случаев - это делается вручную.

[malbaron]

Nekto_Habr:

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

;)
Типичная задача нашего типичного экспедитора.
Решается им каждый день в перерывах между погрузкой коробок.

Самая большая проблема лежит вовсе не так, где вы думаете.
Если окажется, что коробок слишком много и они не влазят в нашу собственную машину - ему нужно срочно найти подменную машину большего объема (нанять на стороне).

А все это "перебор" и "планирование маршрута" на фоне проблемы из предыдущего абзаца - ерунда полнейшая и не стоит даже выеденного яйца.

[Philipp]

malbaron: вы абсолютно правы, я в этой области теоретик, т.к. это не то, в чем я специализируюсь.

[malbaron]

Philipp:
Это так называемая "профессиональная деформация". Это не оскорбление.
Человек смотрит на все вещи, сквозь призму своего опыта.

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

Я тоже когда-то думал, что это все нужно, что это можно автоматизировать и т.д. и т.п.
На деле учитывается столько индивидуальных факторов:

1.поломка машины - нужна замена;
2.заболел водитель - нужна замена или водителя или и водителя и автомобиля одновременно, зависит от того, какой именно водитель заболел;
3.температура на улице - у нас часть товара чувствительна к переморозке, а часть товара - нет;
4.ремонт определенных улиц, чтобы не потерять время и вообще успеть - нужно перепланировать всю доставку, вплоть до переноса части товара на другой день, что нужно с клиентами согласовать;
5.время работы клиентов - кто-то допоздна, а кто-то нет. иногда имеет смысл сначала отвести товар дальнему клиенту, несмотря на то, что какой-то клиент по пути, но пропускаем его, едем мимо, потом позже вернемся к нему;
6.забыли подвести в прошлый раз или нужно поменять брак - нужно подъехать вне плана;
7.нужно подъехать забрать деньги - товар вести не нужно, но используется та же машина и тот же экспедитор
8.слишком много товара в этот день - нужна совсем другая машина.

И это только то что сразу в голову пришло.

[malbaron]

Причем, поломка машины или водитель заболел - это не исключение.
А вполне штатно решаемая задача.

[malbaron]

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

[Нерон Лордов]

malbaron: что делать-то в итоге? понятно, что задача решаема, но как ее решать - всё равно не ясно. раз экспедиторы решают такие задачи ежедневно в перерывах - сомневаюсь, что они делают это вручную, там всё-таки данных вагон с телегой

[malbaron]

Nekto_Habr: не только в перерывах. более того - даже в уме.

[malbaron]

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

2. все остальное решает человек-курьер-экспедитор.
легко и непринужденно.
динамически учитывая пробки, рабочее время клиентов и пр. и пр. и пр.

совершенно непонятно зачем вам это на 30 клиентах хоть как-то программным путем автоматизировать.

[Нерон Лордов]

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

[malbaron]

Nekto_Habr:

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

5??????????
Не 50? Не 500? А 5?
Это задача для решения в уме.

[malbaron]

Артём Петренков:

Ведь ни человек, ни компьютер не перебирают все варианты, однако играют же как-то.

Компьютер - перебирает.

Answer 3

[kadibiget]

Точное решение ищется математическим программированием.
Приближенное человеком.