Клуб Логистов | Логист.ру - Печатать страницу

Клуб Логистов | Логист.ру
https://old.logist.ru/archive/YaBB.cgi
Практика >> Все, что вы хотели знать но боялись спросить >> Задача о расстояниях.
https://old.logist.ru/archive/YaBB.cgi?num=1223753224

Сообщение написано Кузнецов Андрей 11.10.2008 :: 23:27:03

Заголовок: Задача о расстояниях.
Создано Кузнецов Андрей 11.10.2008 :: 23:27:03

Добрый вечер, уважаемые коллеги! Подскажите, пожалуйста, алгоритм решения следующей задачи. Имеется оптовый склад, порядка 500 клиентов, две транспортные единицы (грузоподъемность-20 т. каждая). Доставку груза клиентам планируем сами, т.е. работаем с остатками, а не по заявкам. У каждого клиента есть ограничение по max количеству товара (от 1 т. до 6,5 т.). Необходимо определить min пробег автотранспорта в теч. месяца, при условии, что у клиента на складе всегда джолжен находиться наш груз.

Заголовок: Re: Задача о расстояниях.
Создано Павлов Валерий 12.10.2008 :: 00:05:27

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

Заголовок: Re: Задача о расстояниях.
Создано Кузнецов Андрей 12.10.2008 :: 11:52:01

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

Заголовок: Re: Задача о расстояниях.
Создано Павлов Валерий 12.10.2008 :: 15:40:54

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

Заголовок: Re: Задача о расстояниях.
Создано Рубанов Сергей 13.10.2008 :: 22:52:40

Кузнецов Андрей wrote:

Давайте попробуем вместе подумать:

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

На дату планирования рассчитаем таблицу

"Клиент" | "Координаты XY" | "Текущий остаток" | "Требуемое пополнение" (в тоннах) | "Последня дата отгрузки" | "Осталось дней до даты"

Для первого варианта сортируем таблицу

"Осталось дней до даты" ПО ВОЗРАСТАНИЮ, "Требуемое пополнение" ПО УБЫВАНИЮ

В таблицу добавим новую колонки "Планируемая дата отгрузки" и "Пробег транспорта"

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

Для каждой рассчитываемой строки в конец таблицы рассчета добавляем планируемую строку следующего пополнения запасов с учетом выполнения текущей строки.

Разбиваем строки по рейсам (машина + конкретный рейс) и учитываем это в пробеге.

В итоге получаем некую первую последовательность, которую и начинаем оптимизировать итерационным или любым другим алгоритмом (например, генетическим) для получения минимального количества рейсов, пробега транспорта и отсутствия строк где "Планируемая дата отгрузки" не превышает "Последня дата отгрузки"