Добрый день!
Вопрос связан с расчетом маршрутов.
Есть склад, N точек, в которые надо развезти товар, объемы товара на каждую точку, максимально допустимый объем на каждый маршрут, время погрузки/разгрузки, таблица времен/расстояний между точками, допустимый отрезок времени прибытия для каждой точки, формула для расчета общей стоимости доставки. Необходимо оптимизировать маршруты и их количество таким образом, чтобы минимизировать затраты на транспортировку.
В общем виде Транспортная Задача является «полиномиально неразрешимой» т.е. решается только тотальным перебором.
Вопрос. Существуют ли приложения, которые решают подобные задачи с помощю каких-либо алгоритмов приближения или полным перебором при ограниченном количестве точек?
Есть ли у кого-нибудь наработки на эту тему?
Буду признателен за любой коментарий по данному вопросу.
Спасибо.
––––––––––––-
См. также:
Програмное обеспечение транспортного отдела http://old.logist.ru/archive/YaBB.cgi?num=1145289333
Картографические сервисы, слежение, мониторинг http://old.logist.ru/archive/YaBB.cgi?num=1031291066
GPS-системы, GPRS, неGPS и т.д. http://old.logist.ru/archive/YaBB.cgi?num=1105686658
ЗП водителей, экспедиторов, мотивация и т.д. http://old.logist.ru/archive/YaBB.cgi?num=1047643752
#Практика #Информационные_технологии_в_логистике
Да сущетвуют- взять и написать — самое оптимальное на VBA for Office, можно оптимально и быстро редактировать. А в результате получиться «все оригинальное простое». Уже есть опыт в разрезе поддержания запаса по 12 представительствам. Если вышлете входящие параметры ( с описанием вариантов) и ожидаемый результат, даже постараюсь помочь.
Высылайте from.first.hands@mail.ru
С Ув. С.Романенко
Уважаемый Сергей!
Будте добры, вышлите мне на E-mail Ваш алгоритм решения этой задачи и если можно укажите ограничения, при котрых этот алгоритм работает.
С уважением,
А. Колпак
Приветствую Вас Александр!
Есть приложение к 1с расчитывающее оптимальный,по какому-то параметру, маршрут. По-моему не очень адыкватная штука. Мне интересно как Вы сейчас составляете маршруты, может необходимо просто автоматизация процесса, над которым стоит человек.
Добрый день Александр, спешу вам помочь, если конечно получется. Существует институт МАДИ(ТУ) в этом институте существует кафедра автомобильные перевозки. На этой кафедре издается литература, как раз на ту тему, которая вас интересует. «Моделирование транспортных систем», много литературы по оптимизации транспортной работы.
Институтом в свое время разрабатывались маршруты для доставки хлеба в булочные Москвы по оптимальным маршрутам, сбор почты в почтовых ящиках, сбор средств в таксофонах, вообщем там большой опыт в этом.
Так же есть на кафедре человек: доцент кафедры автомобильные перевозки Просов С.Н., который занимается вопросами оптимизации, можете обратиться к нему.
Добренького всем, уважаемые!
Начну с того, что я, практически ноль, в логистике :-( я программист (поэтому, если не затруднит, при ответах исходите из этого… «на пальцах plz…»). Почему пишу именно сюда (?)… мой boss считает, что в логистике эта задача решается «элементарно». (З.Ы. Я само слово «логистика» услышал месяц назад от своего boss`а при описании того, что мне предстоит делать… что это такое, он сам (с точки зрения программиста) толком не знает :-( поэтому не пинайте меня коли что не так или не туда).
Так что я к Вам, профессор … , и вот по какому делу. (© не мои… :-))
Дано:
1. Служба курьерской доставки.
2. Город поделён на зоны.
3. Курьеров — ровно сколько необходимо.
4. Курьер — пешеход.
5. Один курьер в день — обслуживает одну (???) зону.
6. Есть переодические (выход 1 раз в неделю) и не переодические пакеты.
7. Переодические пакеты нужно доставлять по правилу «конкретная зона — в конкретный день» (например: клиент ХХХ получает этот пакет в среду. Значит он каждую среду должен получать этот пакет).
Пояснения:
1. «Курьеров — ровно сколько необходимо». Город разбит на N участков. Количество курьеров (при пятидневке) считаем N/5 (может и не правы).
2. «Один курьер в день — обслуживает одну зону.» Практически не одну… :-) Кто-то «шустрит» и умудряется обслужить две, а то и три… При сроке доставке за 5 дней — нас это больше чем устраивает, но «не периодика» чаще всего должна быть доставлена за 2 (два) дня (требование клиента — есть закон). Для этого ввели коеффициент «delta» на который расширяем границы зон, чтоб покрыть половину города количеством курьеров (N/5)… оставшуюся половину в следующий день… и при этом не забыть про периодику.
Что нужно: (а нужно, собственно, не так и много… :-))
Отказаться от жёстко зананного коеффициента «delta» и формировать маршруты исходя из:
1-ый критерий. Расстояние. Пакет (не периодика), не входящий в зону обслуживания в этот день (считая по периодике), но доставляемый в этот день — должен принадлежать ближайшей зоне, обслуживаемой «периодикой» в этот день.
2-ой критерий. Грузоподъёмность курьера. Понятно, что за раз человек на руках 100 кг. не понесёт, поэтому: Пакет (не периодика), не входящий в зону обслуживания в этот день (считая по периодике), но доставляемый в этот день — должен принадлежать ближайшей зоне, обслуживаемой «периодикой» в этот день, в которой общий вес пакетов минимален.
3-ий критерий. Количество пакетов в день. Понятно, что человек не может за рабочий день раздать «под роспись» 1000 конвертов, даже при максимальной «кучности» адресатов (за 8-ми часовой рабочий день не успеет… принимаем минимальное время на доставку одного пакета = 1 минуте), поэтому: Пакет (не периодика), не входящий в зону обслуживания в этот день (считая по периодике), но доставляемый в этот день — должен принадлежать ближайшей зоне, обслуживаемой «периодикой» в этот день, в которой количество пакетов минимально.
Это практически текст моего задания.
Очень прошу Вас не относиться к этому, как «к бреду ребёнка»… буду рад любой помощи (документация, ссылки на аналоги, алгоритмы, примеры, обсуждению условия задачи… (может нехватает чего, а может наоборот излишнее… не профи писали :-()), но купить готовый soft не можем по «религиозным соображениям».
Если потребуется дополнительная информация, при её доступности (для меня) с удовольствием вышлю или опубликую тут.
= * = * = * = * = * = * = * = * = * = * = * = * = * =
С уважением и наилучшими пожеланиями,
Дмитрий Слуцков
Здравствуйте.
Вопрос вот какой: есть ли какой-то софт, позволяющий автоматизировать решение задачи коммивояжера? Проще говоря — оптимизировать маршрут доставки товаров по городу.
Буду признателен.
Мне кажется что задача коммивояжера и
доставка по городу — различные задачи
т.к. в первом случае точки доставки
это вершины графа , между ними дуги
длина дуг соответствует расстояниям
(если дуг и вершин очень много то резко
возрастает время расчетов)
доставка же по городу где больше 1 улицы
графовой моделью не описывается
В таком случае, есть ли какой-то софт, оптимизирующий маршруты доставки по городу? Идея вот в чём: водитель должен иметь как минимум список адресов, а желательно и карту маршрута, причём адреса доставки варьируюся ежедневно.
софта который продается в ларьке
скорее всего нет, слишком сложная и не очень
многим нужная задача
в западных изданиях и на сайтах это называется
Vehicle routing problem (VRP)
по этому и искать в интернете
подход там примерно такой
все требуемые места посещения (точки)
наносятся на карту (план)
строится несколько замкнутых линий из склада (депо)
которые перекрывают все точки
ищется оптимум ( минимальное суммарное расстояние )
с учетом загрузки транспортных средств
все алгоритмы эвристические
Простите, но прежде чем писать подобные глупости Вы хотя бы не поленились открыть учебник по мтематике. Очень рекомендую Вагнера «Основы исследования операций».
специфика внутри городской доставки заключается
в наличии знаков дорожного движения , зависимости
режима движения от времени суток , ремонте определенных
трасс, наличия пробок и т.п.
вы хотите и можете все это отслеживать ?
если все так просто, выложите ссылку
на работающую систему внутригородской доставки
или решите задачу коммивояжера в графе
с 60-70 вершинами
Для управленцев данная задача решается проще. В старом армейском высказывании она звучит примерно так: «Поставьте сюда хорошего майора или шлагбаум».
Для хорошего майора надо примерно полгода чтобы научиться интуитивно составлять маршруты для нескольких единиц транспорта с доставкой в сеть примерно в 200 магазинов ежемесячно, выполняя минимум по одной заявке в неделю при неравномерности поставки на склад товара.
Так примерно выглядит Постановка задачи по доставке (задача 1 уровня). Роль задачи о коммивояжере имеет подчиненный уровень, так как призвана решать одну из задач 1-го уровня. Уровень сложности для одного маршрута 2^n, где n — количество заявок.
Попробуйте использовать в время пробега отрезка = расстоянию между отрезками/среднюю скорость данного отрезка.
с 93-го по 98-ой год(в Новосибирске) было так «майор» садился на пару месяцев в грузовик за экспедитора и развозил по 18-25клиентов в день(а ещё очень хороший стимул -склад на 6-ом этаже,куда надо поднимать неразвезённую продукцию при отключенном лифте),после этого рука сама все маршруты рисует(на пять машин по 6-12клиентов)с учётом специфики заказа(декоративная косметика или стиральный порошёк),с уч.знаков,районов и пр.,ну а если экспедитор несколько раз неуспел,то опять переатестация(т.е 100клиентов на неделю).
Ну это так по старинке…
для СПб я делал так ( давно и на FOXe)
город разбивался на районы,
районы на сектора
каждый покупатель привязывался
к определенному сектору
выписываются условия перехода из сектор
в сектор ( возможно — невозможно )
+ особые условия для центра города
заявки от покупателей приходят случайно
( покупателей около 1000 )
заявок в день было около 80 - 120
начальник транспорта задавал
сколько заявок может обслужить один а.м. (8-10)
по схеме секторов проводился анализ
( ползла улитка )
после набора заданного числа заявок
формировался новый маршрут
в результате заявки разбивались равномерно
по городу и ни один а.м. не посещал больше 2 районов
т. к. транспорт был наемный то удалось
экономить 1500 -2000 $ в месяц по сравнению с
ручным формированием маршрутов
а FOX-это что такое?,как бы посмотреть как это выглядело?
(спасибо)
Подобные вопросы уже обсуждались.
вот ссылка:
http://old.logist.ru/archive/YaBB.cgi?board=trans;action=display;num=10…
Также в Разделе «Транспортное обеспечние логситики» рассматривался и вопрос автоматизации расчета Путевых листов и многое другое.
foxpro это субд с встроенным языком
данные хранятся в файлах dbf
был сильно распространен для DOS
foxpro в мной использовался просто потому что
вся складская система была написана на нем
несколько лет назад фирма перешла на ERP систему,
а я там больше не работаю
так что показывать особенно нечего
но принципы разбиения заявок по машинам
на основании разбивки городской территории на
сетора доставки мне кажется достаточно эффективным
и достаточно просто реализуем
Ну может «Голь на Выдумки хитра»,но я машины по районам вручную расписывал(не было ПО соответствующего).Года два после увольнения адресов триста наверное наизусть помнил.
Решение по маршрутам для автопарка по системе «улитка» можно найти в источнике — А.М. Гаджинский, Практикум по логистике, М.1999
Мое мнение — секторы ограничивают возможности парка. Необходимо искать варианты с полным покрытием заявок. Но здесь присутствует злополучный перебор вариантов. А если 100 магазинов на день и минимум 10 авто? «Улитка» спасает, но не гарантирует правильное решение.
В случае «улитки» — из набора важных решений выпадают решения позволяющие перекрыть участок «развозки». Иначе количество «реальной грузовместимости» неспособно перекрыть район «развозки» наличным транспортом.
Задача коммивояжера имеет решение для усидчивых и работающих с маршрутами в 6-8 магазинов. Источник решения задачи «методом ветвей и границ» в книге «Практикум по логистике», под руководством проф. АникинаБ.А., изд.-2, М.Инфра, 2001.
Для людей экспансивныхъ и неусидчивыхъ задача в 12 магазинов представляет проблему — личное время. Главное в этом решении вручную прийдется убирать проблемные циклы. Например, цикл 1-2-3-4, имеет проблемный цикл 4-2, который необходимо удалить. Необходимо додуматься — как это сделать. При расчете в 30 магазинов может случиться - «Crazy».
Пожалуйста, войдите или зарегистрируйтесь, чтобы комментировать.