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

Стоит классическая задача по программированию.

Для каждой накладной(набор товаров для точки на сегодня) известен вес и объем.

Известна грузоподъемность автомобиля.

Известно расстояние между точками.

Известна цена часа работы автомобиля.

Известная цена бензина автомобиля и расход на километраж.

Как распределить товар по машинам, чтобы стоимость доставки была минимальна?

Может где такое уже решено?

Ситуация.
Затраты на доставку 100 рублей. Если даже их сократить до 50 рублей, 50 рублей - это 0.00001 % прибыли.

Нафига раздувать штат- директор по логистке, целый отдел ... Вы хоть посчитали - оно того стоит ?

(38) у автора задача автоматизировать процесс, а не сэкономить деньги конторы

(38) Этот штат уже есть. Задачи кого куда с каким грузом отправить уже решаются. Надо это автоматизировать.

(40) у тебя динамическая система - она постоянно меняется, кто будет вносить изменения в параметры расчетов?

автоматизация ради автоматизации

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

(41) Ну 100% точность не нужна. Достаточно указать, что весной эта дорога такая то, скорость снижается, расход бензина увеличивается.

Собственно это то самое простое.

Важнее алгоритм обхода графа. Машинами и распределение грузов между машинами.

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

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

(45) Город уже разбит на районы доставки.

> Важнее алгоритм обхода графа

достал ты со своими графами, математик

(46) ой лоло.

(44) ыыыы и в итоге будет так:

1. ты выдаешь с утра из базы маршруты "какая машина куда едет" и схему распределения грузов
2. водятел тебе говорит что его машина по твоим двум адресам ну никак не успеет ибо вот именно сегодня там на дороге провал и вообще трындец
3. ты берешь свои расчеты и идешь пересчитывать
4. пока ты пересчитываешь те кто уже загрузился бодро разгружаются обратно



точно - логистический отдел можно разгонять...

(47) тогда впиши стоимость доставки и задача решена

(48) больше важных слов - и никто не подумает что ты дурач0к :)

(46) Вот и я о чем.

Другое дело если оптимальный вариант будет на не хилом компьютере 18 лет рассчитываться.

Хорошее сегодня утро. Под водочку и эту тему.

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

(52)

+1

м.б. сегодня день теоретика? у кого есть отрывной календарь?

Здесь уже прозвучала мысль.

Во первых есть время доставки, во вторых стоимость доставки.

(50) Это отклонение от плана ну и что? Бывает.

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

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

(53) это если точек будет 10000 и машин столько же. Вообще в экселе расчет элементарно делается

(58) открываем яндекс пробки
включаем отображение аварий

есть вероятность близкая к 100% что эти отклонения будут каждый день

(58) У тебя скорее будет бывать попадание в план. Иногда.

(62) ага.. попадание.. с ноги..
типа "опять из за вашей программы мы не привезли груз вовремя и вообще не успели за сегодня ничего развести"

до тыщи дотянем?

(64) не... слишком очевидна тупизна темы...

Логистика вообще сложная штука.

Вот у нас: торговых точек 2300(клиентов) * разные виды продукции = 10000

Таже фигня - загрузка машин, пиковые дни. Вип клиенты...

Маршруты сейчас фиксированные, но тоже ... пришел новый директор и хочет динамические маршруты ...(

(65) если будут реально буйные (Базванов) - дотянем. Главное чтобы Рома не пришел.

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

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

далее эти параметры просто закладываются в систему "по районам доставки"  и вперед развозить по "стандартным" маршрутам...

(48)(52)

А я кроме графов и не знаю как это решать.

Да и уже доводилось нечто похожее делать.

Организация липовые путевые листы выписывает.

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

И ничего работает.

(70) непонял - задача была нагенерить липовых путевых листов?

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

(70)

> А я кроме графов и не знаю как это решать.

не надо это решать вообще.

> Да и уже доводилось нечто похожее делать

работает? деньги экономит? окупилось?

(72) шикарно....

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

(73)

Работает. Бухгалтеру не нужно сидеть и сочинять путевые листы.

(75) ну так если разбить по зонам весь город и отправлять одну машину в одну зону - чем не решение ?

приехал, посетил пять точек, разгрузился и уехал.. не ?

(75)
> И естественно, не мотался на одну и ту же точку пять раз, а роде как объезжал несколько точек.

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

(76)ыыыы
то есть  у тебя фактический расход бензина в путевых листах и пробег не по факту заполняются а программно?

(76) LOL!
Программа факт. расх. бенз. сама пишет?

(78) Там не планировались реальные маршруты. Там надо было списать бензин на затраты. для этого написать красивую документацию. Вот программа эту документацию  и составляла.

(81) 5 баллов!

(81) можно уточнить, адреса доставки ты из кладра генеришь?
содержимое груза из яндекс маркета случайным образом подбираешь?
имена водителей из реестра "1000 имен мальчиков"?

(77) Уже разбит. Но в зону надо не одну машину. Или наоборот, сегодня в ту зону только одну, а завтра две. От объемов зависит.

(84) то есть задача классическая

имеем набор грузов по этой зоне
рассчитываем что нужно 2 машины
заполняем и отправляем


причем тут тогда расчет оптимальных маршрутов?

(83) Нет. У организации есть несколько контрагентов по которым они ездят. И длина маршрута между ними по всякому. Создается обычный граф. И перебираются разные маршруты с длинами путей. Если какой маршрут более менее подходит, тот  и вписывается в путевой лист.

(86) а если водятел поехал фактически по другому маршруту?

(83)
>имена водителей из реестра "1000 имен мальчиков"?

Водитель заполняет ексель, сколько за каждый день наездил.

В конце месяца загружаются данные в конфу и на каждый день составляется путевой лист.

Листы распечатываются, и используются как обоснование затрат.

(87) Они и ездят по другим маршрутам. А документацию надо составить что ездили по маршрутам связанным с работой.

(85) Какие товары и для каких точек?

Машин может не две быть на район.

(89) ааааааа
ну тогда какие нафиг вопросы в оптимальности?

генери просто самые короткие маршруты методом ближайших точек и все...

(91) Длина маршрута должна соответствовать фактическим данным. Чтобы не было на спидометре 500км, а в путевом листе по маршрутам 100км.

(92) ы
а расход должен соответствовать фактическому расходу..

может тогда не генерить ничего а просто заполнять маршрутные листы по факту ?

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

(93) По факту они машины и в личной жизни используют. Да и по факту много писанины. Есть разница между тем что просто написать пробег за день и расписывать куда ездил и какой там длина пути.

(94) Ага. Вот что то типа http://www.ingit.ru/articles/index.php?id=4 и нужно.

(95) можно уточню

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


а ты хочешь чтобы программа мои 1000 км. и расход в 100 литров подогнала под развоз между тремя точками у коорых максимальное расстояние между ними всеми 15 км?

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

(94) Можно спросить накуя?

(97) хз, но работает. И точек не 3 шт.

(98) у нас куплены их карты, и есть задачи оптимизации траснспортной логистики для диспетчерской

(100) моя первая сотко))

(99) бгыыыы

шикарно...

то есть ты офсис находится на моховой
нужно отвезти на воздвиженку

по спидометру 150 км и 15 литров бензина

можно уточнить - как твоя программа маршрут рассчитает ?

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

(10) Давно это было, но насколько помню:
Два справочника. Первый точки, другой длина маршрутов между точками.

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

(104) это к (102)

(103) Путевые листы нужны для проверяющих. Они не идиоты.

(104) чисто на вскидку

http://maps.yandex.ru/-/CNH3jNOi

как ты сюда 150 км впишешь?

(107) В путевом листе не один маршрут. там из А в Б, из Б в В, из В в Г.

Так набирается приблизительно 150 км.

(108) давай рассмотрим плохой день.. когда у тебя всего один маршрут а водятел по личным делам 150 км намотал..

(109) Маршруты с фактом вообще никак не соотносятся.

может не быть ни одного рабочего, маршрута в реальности

Они просто выдумываются.

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

(111) Маршрут имеется ввиду просто от точки А к точке Б, по каким улицам это уже дело водителя.

Но согласитесь, скорее всего такой оптимальный маршрут в рамках района один.

(112) не факт. Ты же из Пензы. Например я часто езжу из района 8 корпуса политеха в арбеково. Самый короткий маршрут это по улице Володарского, пушкина Суворова. А вот в часы пик до арбеково проще добраться через западную поляну.
Или теновку возьми. Да и у нас улиц параллельных полно. На улицу Киров, Володарского лучше не соваться лучше проехать по параллельным улицам, например по Урицкого.

(113) Я же сказал: "в рамках района"

(113) Да и в рамках района могут быть варианты, но погрешность не значительная.

(114) (115) Что понимать под районом? И почему ты рассматриваешь только в рамках этого района?

Попкорн доставать?

(117) Рано еще. Я через 20 минут уеду на работу.

(116) Район это административная единица.

Для точек в одном районе можно указать некоторую виртуальную точку маршрут через которую будет проходить. Например склад находится у 8 корпуса, и сделать общую точку для маршрута 8 марта/Куприна. До нее можно добраться по разному а от нее до любой точки Арбекова вариант практически один, если специально не петлять. Да бывают исключения, но не часто.

(31) смотри внимательнее, прокладка маршрутов, распределение по машинам, там всё есть

(120) Наверное просмотрел. Там как то не очень понятно прописано.

(119) Если ты решаешь задачу для конторы торгующей продуктами питания, то это вариант не пойдет. Т.к. во первых посмотри размеры первомайского района, например. Оцени какая у тебя будет погрешность. И второе учти что магазины находятся часто внутри кварталов, во дворах и к ним можно подъехать с двух сторон. Если не с 4. Мелких магазинов очень много.

(122) Да такую задачу не решить. Правда http://www.ingit.ru/articles/index.php?id=4 говорят что решили: "При расчетах учитываются грузоподъемность и вместимость транспорта, требования срочности заказов и времени исполнения, оптимизация движения с учетом дорожных знаков, ограничения на время или протяженность маршрутов, с тем, чтобы например, доставить хлеб в торговые точки горячим и пр."(С)

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

У большинства крупных фирм нет таких заморочек, потому что машины свои развозят, а водителям платят по весу увезенного, числу заявок и прочим характеристикам.
И если честно никогда не видел подобного бреда, есть маршрут и есть точки доставки, что мешает заявки разбить на маршруты и грузить каждую машину только нужным весом и по нужному пути.
А проблемы с бензином и часом работы дело маркетологов, которые схему оплаты придумают или бухгалтера, а не логиста :)

Смешались в кучу кони, люди,
И залпы тысячи орудий,
И все на наш редут...

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

Да есть куча программ, расписаний, MES, составление графиков доставки. Только это мимооооо.... О чем и пишут ТС.

тут уже предлагали решения http://nova-it.ru/ ? в УТЛ есть всё, что в (1) внедрял лично :)

(127) Куча народа просто пытаюстя открыть глаза ТС в реальный мир. Задача быть может интересная. Но  все понимают что она не разрешима или разрешима при боле точной параметризации входных данных до которого мы просто не созрели.
У меня в компании свои машины есть маршруты. Руководсво тоже думало что внедрение gps все решится. Мы им объяснили что система дает только факт но не может прогнозиовать моделировать или решать человеческие задачи по планированию.

(0)Это из серии. Кафе - какие установить оптимальные цены, чтобы увеличить посещаемость и при этом иметь максимальную прибыль. Эта задача решаема, но далека от реальности.

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

(130) хех.. в своем время и мне куча народа открывала глаза на тему автоматического формирования расписания вуза.. благо, не открыла..

(133) Что вуз съехал)))

(0) Сколько точек? Если меньше тысячи - то просто возьми на работу грамотного логиста.
Решают такую задачу (правда хуже чем человек) многие решения. Например БиТ (Нова) Транспортная логистика.

А если больше тысячи - то найми двух логистов.

(0) Развозите по ночам.
Очень удобно.