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

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

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

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

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

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

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

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

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

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

городские пробки уравнивают логистов и пофигистов.

(1) Не всегда все идет по плану. Бывает.

Это не значит, что план придумывать не надо.

Кроме того, для каждого ребра графа можно задать скорость продвижения.

При желании на разные моменты времени скорость продвижения.

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

срубишь свой первый миллион...

(2)
> Кроме того, для каждого ребра графа можно задать скорость продвижения. При желании на разные моменты времени скорость продвижения.

Ты сам-то веришь в это фуфло? Встанет МКАД и сиди соси ноги, никакая мат. модель не поможет.

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

(4) То что цена доставки увеличится, вовсе не сделает её больше, чем если загружать машины без плана.

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

(5) Да вроде классическая задача. На решении таких задач программирование и росло, а не на учете документооборота.

Опять мир затрат. Забил газель под завязку, начал развозить 50 клиентам сразу, а машинка встала, зато забита по самые помидоры.
Вопрос, сколько сэкономил ТС на стоимости доставки?
Или при разгрузке на все точки, водила с экспедитором не успели разгрузить в этот день и привезли назад.

Забивай в общую сумму расходов стоимость доставки и не парься. Лучше, обеспечьте доставку в срок(не раньше и не позже оговоренного) и наличие ассортимента на складе на уровне 98%.

З.Ы. Не люблю когда умничают чересчур и фигней страдают.

(7) зачем тогда вопросы задаешь, сделай сам быстренько, две формулы всего.

в крупных городах все эти логистические штуки не работают. Иногда быстрее и экономнее объехать полгорода, чем по прямой в пробке стоять

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

Прикрути GPS мониторинг чтоб левых рейсов не делали, сейчас это дешево.

(7) ага...

ну так в принципе ничего сложного..

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

затем заполни по каждому авто объем багажника и его габариты
по каждому грузу соответственно тоже габариты упаковки

далее тебе остается заполнить коробки из ранее созданных массивов в багажник по схеме заполнения.

то что осталось - на пересчет..


все же просто...

и надо все это на SAP писать, она быстрее одинэса считает

Во главе угла, на первом месте должна стоять доставка клиенту в срок! На втором наличие товара на складе. А потом уже на 95-м месте стоимость доставки.
ТС, вам что наценки на товары мало?

(11) главное незабыть реализовать алгоритмы расчета оптимального заполнения багажника... чтобы пустое место не возить по оптимальному маршруту

(8)

>Опять мир затрат.

Ну экономисты они такие. Только о затратах и думают

>Забил газель под завязку,

Никто не мешает указать половину объема от реального.

>начал развозить 50 клиентам сразу, а машинка встала, зато забита по самые помидоры.

Херня случается.

>Или при разгрузке на все точки, водила с экспедитором не успели разгрузить в этот день и привезли назад.

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

>Забивай в общую сумму расходов стоимость доставки и не парься.

Эфрика!!! Задача решена.

>Лучше, обеспечьте доставку в срок(не раньше и не позже оговоренного) и наличие ассортимента на складе на уровне 98%.

А потом без штанов ходить.

>З.Ы. Не люблю когда умничают чересчур и фигней страдают.

Это да.

(9) Меня интересует конфа где это реализовано.

(16) нигде

(15) Ну если такой комерс, то ходи без штанов.

ЭТО ГЕНИАЛЬНО!!!!!


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

(13) Там не клиенты, а свои же торговые точки, на которых есть запас, а эти запасы пополняются.

(13)

> Во главе угла, на первом месте должна стоять доставка клиенту в срок! На втором наличие товара на складе. А потом уже на 95-м месте стоимость доставки.
ТС, вам что наценки на товары мало?

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

> А потом уже на 95-м месте стоимость доставки.

доставка презервативов вертолетами

Можно доставлять и 80% от потребности клиента, исходя из собственной выгоды.

(22) доставка пиццы

Вот про то чего нет это и есть 20%.

(19) Маршруты уже знают водители, и кривая дорога просто забивается в виде ребра графа.

Для каждого ребра можно задать характеристики. По скорости прохождения и затратам топлива.

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

(21) ыыыыы

нанять авто с мигалкой и номером серии АМР... кортеж полиционеров....

(26) реализуй - заработаешь свой первый миллион

(23)

> Можно доставлять и 80% от потребности клиента, исходя из собственной выгоды.

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

(24) Доставку пиццы разумеется так не автоматизируешь. Тут заранее известны точки, заранее известны маршруты.

Такая есть конфа, по названию подходит

Управление транспортной логистикой ред.3.6 (3.6.9.22) (www.nova-it.ru)
БИТ
(www.1cbit.ru)

(30)

> Доставку пиццы разумеется так не автоматизируешь. Тут заранее известны точки, заранее известны маршруты.

а пиццу возят не зная адреса?

(23) + Но клиент уйдет к тому кто может доставлять 95-98 %%.

а вообще - я бы воспользовался вебсервисом типа http://www.integprog.ru/route2/
или гуглевским...

отправляешь массив адресов.. получаешь схему проезда..

но опять же - ни один расчет тебе не покажет что прямо сейчас вот этот перекресток имеет 10 баллов пробок ибо там авария или там асфальт с утра кладут...

а постоянно вносить в свой алоритм параметры типа "обледенела трасса с 3 по 4ый километр" или "авариия на 20ом километре" или "сломался светофор на таком то перекрестке" - никто не будет

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

далее ей никто верить не будет

(31) Вроде не то. Там скорее следят кто где ездит.

пиццу еще желательно теплой привезти

все зависит от товара. Если возишь покойников - логистика дело десятое.

Ситуация.
Затраты на доставку 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) Развозите по ночам.
Очень удобно.