Метод Кларка-Райта. Оптимальное планирование маршрутов грузоперевозок

0. Дмитрий Павлов (mi1man) 169 13.01.16 11:40 Сейчас в теме
Одной из наиболее важных задач каждого предприятия, осуществляющего доставку грузов в крупных населенных пунктах, является сокращение издержек. Возможное решение данной проблемы заключается в сокращении пробега автотранспорта и, как следствие, уменьшении расхода ГСМ. Появляются такие вопросы ... - СКОЛЬКО НУЖНО МАШИН ДЛЯ РАЗВОЗКИ КОНКРЕТНОГО ОБЪЕМА ГРУЗА ПО АДРЕСАМ ДОСТАВКИ ? - КАК РАЗБИТЬ ТОЧКИ ДОСТАВКИ НА ОПТИМАЛЬНЫЕ ПО ПРОБЕГУ И ЗАГРУЗКЕ МАШИН МАРШРУТЫ ? ... В этой статье Вы найдете один из многих способов получить ответ на эти вопросы.

Перейти к публикации

Комментарии
1. Игорь Иванов (paybaseme) 4 11.02.16 13:14 Сейчас в теме
Спасибо за статью! Информация полезная.

P.s.: оформление так вообще супер :)
2. Юрий Бунаков (Lostar) 11.02.16 13:25 Сейчас в теме
Этот редкостный упырь переписал нам всю. логистику и теперь мы вообще не представляем, где наши машины))

На самом деле шучу. При помощи механизмов автоматизации Дмитрия наша корпорация сократила расходы на логистику на 17%.

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

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

Спасибо, Дмитрию, за проделанный труд!
3. Дмитрий Павлов (mi1man) 169 11.02.16 22:59 Сейчас в теме
(2) Lostar, Не каждый день от начальства о себе столько "хорошего" услышишь)) Благодарю Вас Юрий за столь "лестный" отзыв))
4. Артём Андриянов (CSiER) 12.02.16 08:20 Сейчас в теме
Спасибо за статью - хорошо, что подобные темы затрагиваются на ресурсе.
5. Антон Володченко (Euroset1) 4 13.02.16 02:01 Сейчас в теме
Алгоритм хороший, в целом. Хотя он требует эволюции в какой-то мере:
1) Бывают случаи, когда добить машину под завязку в конечном счете дешевле, чем отдать ту же точку соседней машине из-за ее большей близости. Например, в результате можно сэкономить на количестве машин и как следствие, на ФОТ и на дорогах между складом и первой\последней точками. Намек на апгрейд - учитывать дорогу домой при каждой итерации. Но и этого будет мало, тут надо думать глубже. Возможно даже в ущерб быстродействию комбинировать с перебором, начиная с какой-то стадии.
2) Нагрузка влияет на затраты ГСМ, поэтому можно учитывать некий коэффициент в зависимости от массы между точками. То есть анализировать не голый километраж, а с учетом нагрузки. Иногда полезно сначала сбросить пол кузова, чем сэкономить километр доставляя более легкий груз первым.
3) Тут не учитывается возможность каждой точки выдавать грузы. Возможно, данной фирме это и не нужно. Но в общем случае грузы могут располагаться на любой точке. Иногда предварительная переброска на другой распределительный склад обходится дешевле, чем везти груз сразу до конечной точки. А это уже взаимодействие транспорта и требует подстраивать еще и время в пути...

Но в целом, даже такой алгоритм должен хорошо проявить себя в качестве экономки.
6. Дмитрий Павлов (mi1man) 169 13.02.16 18:39 Сейчас в теме
(5) Euroset1, Спасибо за такой развернутый отзыв, чувствуется что Вы "глубоко" в этой теме. Что качается реализации пунктов 1 и 2 то это все правильно, но мне кажется что и транспортному логисту все таки нужно поработать головой, а не полагаться целиком на рассчитанные варианты. К тому же существует большая проблема, которая все эти расчеты просто обнуляет. Это запрет движения грузового транспорта по некоторым дорогам (особенно актуально для Москвы), а есть даже ограничения до 2,5 тонн (в спальных районах) и есть утвержденные дороги по которым должен двигаться грузовой транспорт .. а по п.3 - как раз сейчас работаю над реализацией "кросс-докинга" (нужно учитывать и планировать перемещение товаров со склада в конечную точку с разгрузкой в промежуточной точке)
7. Антон Володченко (Euroset1) 4 13.02.16 21:16 Сейчас в теме
(6) mi1man, так я же не говорил, что расчет расстояния по координатам является правильным. Если деятельность сильно завязана на логистике и это приносит деньги, то стоит задуматься о ведении расстояний между пунктами с учетом реальных возможностей транспорта. Изначально координаты являются заплаткой в силу того, что дороги не соединяют точки напрямую. Поэтому для полноценной эволюции придется затеять нагруженный граф расстояний между каждой парой точек. А чтобы не выполнять лишних действий по администрированию этого графа, требования к его пополнению алгоритм должен выдавать сам непосредственно при нехватки данных. То есть он должен вычислить все непроставленные пары, запросить под каждую из них расстояния в обе стороны (одностороннее движение может существенно влиять) и лишь тогда провести работу по подбору маршрутов. При этом со временем вопросов о расстоянии будет все меньше и меньше.
Помимо расстояния можно также ввести градацию загрузки дорог между точками, ака пробки. То есть коэффициент, который помножает расход ГСМ за счет простоя.

Либо можно пойти другим путем. Научиться тырить карты с гугла или яндекса и рассчитывать расстояния и загруженность по ним. Возможно там даже есть АПИ, о котором я просто не в курсе. Это более оптимально, но вселяет существенную зависимость от чужих сервисов (накрылся гугл - ваши машини стоят). А вот если сделать гибрид между этими двумя методами, то система будет аварийно устойчива.

Признаюсь честно в своих сомнениях по поводу "логист должен сам принимать решения". Алгоритмы подобного рода довольно сложны для корректировки. Пытаясь скорректировать предложенные маршруты можно одним неверным действием перечеркнуть всю выгоду. Здесь пройдена та грань, где можно комбинировать человека с программой. На этой стадии остается только улучшать программу. Коробка-автомат =)
8. Дмитрий Павлов (mi1man) 169 13.02.16 23:02 Сейчас в теме
(7) Euroset1, Вы коснулись очень важной темы. Считать геометрическое расстояние между точками на карте и на его основе строить маршрут, в реальной жизни может получится совсем плохой результат, если например точки разделяет река(каналы). Поэтому матрицу расстояний лучше всего заполнять реальным пробегом по дороге между точками, а еще лучше - временем прохождения (так будут учитываться пробки). Возможно я ошибаюсь, но предложенный Вами граф(ы) расстояний это по сути - матрица расстояний и километровых выигрышей (описанная в этом алгоритме).
Матрицу расстояний с указанием длительности и расстояния для всех пар из точек маршрута можно получить используя api Google (для Yandex такого аналога я не нашел), только за это нужно будет им платить.
Насчет Ваших сомнений о логисте, это зря .. людям надо доверять)) до тех пор пока они не подведут. Эта статья была написана для рекламы обработки (она в конце статьи указана), которая позволяет логисту достаточно просто корректировать рассчитанный маршрут, используя его знания (в том числе и для ситуаций, описанных Вами в пп.1,2 предыдущего поста) и как раз реализует комбинирование человека и программы, то что Вы "отрицаете" как оптимальный вариант))
9. Сергей Рубанов (rsergio) 71 17.02.16 10:58 Сейчас в теме
Давно использую данный метод, но не как конечный вариант решения задачи, а как первый приближенный т.к. по времени расчет производится почти мгновенно.
Получив первый вариант решение дальше оптимизация производится другими алгоритмами перебора, которые более точнее находят оптимальное решение с учетом всех факторов (время доставки, стоимость километра и часа пути и т.д.)

Касаемо вопроса расстояний между точками - я использую три метода:
1) Через API Яндекса
2) Через API Openstreetmap
3) Расчет прямого расстояния по GPS координатам

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

Пока только не удалось прикрутить актуальные пробки на нужный час т.к. Яндекс позволяет учитывать только пробки на текущий момент.
10. Дмитрий Павлов (mi1man) 169 17.02.16 11:58 Сейчас в теме
(9) rsergio, похоже что и мне предстоит также действовать)
11. Alik Datsko (DAlik) 26.02.16 18:50 Сейчас в теме
Спасибо за статью.
Тоже сделал недавно на 1С своего Кларка-Райта.
Сейчас научился учитывать временные окна, плюс сделал модификацию целевой функции. Целесообразно увеличивать выигрыш для заказов с весом выше среднего. Т.е. алгоритму тем ценнее взяться за заказ, чем выше его вес среди прочих. Такую же поправку сделал и для окон. Т.е. тем ценнее взяться за заказ первым, чем уже его временное окно доставки. В жизни логист так и рассуждает, часто в ущерб километрового выигрыша. Т.е. строит рейсы в первую очередь к клиентам с наиболее узкими окнами и с наибольшим весом на выгрузке.
Сейчас остановился на подборе оптимального транспортного средства среди имеющегося в парке. Как вы справляетесь с этим? Если например в компании узким местом является парк. В процессе работы Кларка-Райта нужно уметь учитывать различные ограничения по машинам: совместимость груза с типом транспортных средств (рефы, изотермы), время доступности машины (актуально для кругорейсов), признак собственный\наемный и.т.д.
Соглашусь с rsergio, возможно мне тоже стоит перейти к двухфазным методам т.е. оптимизировать рейсы после приближенного решения Кларком-Райта.
12. Дмитрий Павлов (mi1man) 169 02.03.16 18:01 Сейчас в теме
(11) DAlik, Спасибо за отзыв. Сразу не увидел заданного вопроса). В нашей компании нет проблемы с различной грузоподъемностью (только фуры), поэтому и не было ранее задачи учитывать таковую. Однако многие мои клиенты выразили пожелание, чтобы программа умела работать с временными окнами доставки и транспортом различной грузоподъемности. Сейчас как раз работаю над реализацией такого функционала .. будет использоваться усовершенствованный эвристическими методами генетический алгоритм с модифицированными проблемно-ориентированными операторами .. о какое крутое название получилось)) .. возможно потом напишу статью об этом методе.
13. saksaul (saksaul) 01.12.16 04:47 Сейчас в теме
афтар вы хоть укажите что не сами писали, сделайте ссылку на первоисточник, как сделали люди на этом сайте http://jurisprudent.site/ekonomicheskaya-teoriya/312-metod-klarka-52262.html
14. Дмитрий Павлов (mi1man) 169 01.12.16 11:03 Сейчас в теме
(13) чудак (не стану ошибаться в этом слове) .. в каком месте ты увидел, что это я придумал этот метод .. прочитай еще раз его название .. эта статья написана только для того чтобы показать (в деталях) как этот метод работает в программе "Простые маршруты" (http://infostart.ru/public/452803/)
15. rjhev korum (корум) 307 01.12.16 11:06 Сейчас в теме
(14)
в каком месте ты увидел, что это я придумал этот метод

он про то, что описание метода и картинки типа с учебника скопипастили.
16. Дмитрий Павлов (mi1man) 169 01.12.16 11:29 Сейчас в теме
(15) тогда чудак выглядит еще глупее, с чего он решил что по его ссылке находится правильное описание, он даже не вникал в его суть, т.к в статье по его ссылке приведен ход и описание алгоритма с грубыми опечатками .. это видно хотя бы по приведенным результатам.
17. Лев Бирев (user736465) 18.04.17 13:22 Сейчас в теме
(16)
Нет ли у вас JAVA кода решения методом Метод Кларка-Райта.
А именно код, который бы генерил матрицу километровых выигрышей и определял максимально удобный путь
18. Дмитрий Павлов (mi1man) 169 18.04.17 13:36 Сейчас в теме
Оставьте свое сообщение