Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) , нужен графовый алгоритм, не пойму какой

Всем хай! Сходу к делу!
Есть задача, примерно такого содержания: есть сеть магазинов, в которые грузовик доставляет товары. Грузоподъемность грузовика 6тонн (прим.маловато будет). Средние величины заказов из отрезка [0.8 ... 3.2]тонн. Все магазины снабжаются из одного хаба (распределительный центр). Т е из этого хаба начинает движение грузовик. Также известны расстояния между магазинами (не между всеми магазинами есть связь), а также расстояние от магазинов до склада/хаба. Нужно получить ОПТИМАЛЬНЫЙ МАРШРУТ движения грузовика с целью доставки товаров по всем магазинам.

1. Вот 100пудово это НА ГРАФЫ (неор.графы)!
2. Под оптимальностью, что понимать? Ну, мне кажется, что минимизация пройденного пути грузовиком. (не факт, что я прав)
3. Как понимаю, грузовик не факт, что управится за 1 рейс. Может быть и 2 и 3 и 23 рейса...
4. Все товары на складе, т е грузовик стартует с хаба и "дозаправляется" товаром также со склада
*5. Из условия вроде не гарантируется, что есть ПРЯМОЙ путь от склада до любого магазина (не уверен)

Это вообще, в сторону чего копать графы нужно?

Подскажите как быть-то?
спс за внимание!

Цитата

Есть задача, примерно такого содержания

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

Сообщение отредактировано: AVA12 - 23.12.19, 17:00

Если предположить, что обеспечение всех заказов является обязательным условием, возможны два критерия. Первый - минимизация времени. Второй - минимизация тонно-километров (в первом приближении - расстояния).

В принципе обе версии фактически сводятся к одной - к задаче о рюкзаке. Где на первом шаге определяется количество рейсов, которое получится roundup(общий вес / грузоподъёмность), возможно ещё плюс один, если расстояние сильно варьирует. А на втором выполняется деление на рюкзаки (загрузки), для загрузок в несколько точек - минимизация расстояния/времени.

В общем, по большому счёту, NP или очень близко, так что да, динамика на базе графа.

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

на рис. один из вариантов такой сети дороги-магазины-хаб

Прикреплённая картинка

Т е программа запрашивает кол-во магазинов, затем их названия, затем расстояние между магазинами или хабом и магазином (инициализация) - тут все понятно!

Сразу оговорка: товар однотипный, т е это НЕЧТО, имеющее какой-то вес и все)

Затем в программе вводится для магазинов, кол-во необходимого им товара, например:
1 1.1
3 0.85
4 3.3
5 1.7
...
Если кол-во товара для какого-то магазина НЕ ЗАДАЕТСЯ, значит оно равно 0 (логично)

Грузовик (6тонн) начинает движение с ХАБА (всегда) и заканчивает движение в ХАБЕ (всегда). Его цель: доставить товар во все магазины в нужном кол-ве. Остатка в кузове быть НЕ ДОЛЖНО, т е приезжает на ХАБ пустым. В процессе доставки товаров может многократно проезжать через ХАБ, т е нет цели посещать магазины (вершины графа) ровно по 1 разу.
Поскольку кол-во магазинов может быть очень большим и большинство из них хотят заполучить этот товар, то обычно за 1 рейс грузовик не управится. Кол-во рейсов НЕ имеет значения (столько, сколько нужно).

Цель грузовика: намотать мин.километраж (кол-во рейсов НЕ важнО), обслужив все магазины.
Кол-во товара на складе неограниченно.


AVA12, не знаю, ответил ли я этим на твои вопросы...

Цитата Akina @ 23.12.19, 17:02

В общем, по большому счёту, NP или очень близко,

т е даже НЕ нужно считать кратчайшие расстояние от ХАБА до каждого магазина (алг.Дейкстры)?

Добавлено 23.12.19, 17:52
также давайте считать, что товар НЕ МОЖЕТ разгружаться частично, т е грузовик приехал в магазинN и отгрузил ВЕСЬ товар, который нужен этому магазину при условии, что в кузове есть необходимое кол-во товара (а если нет необходимого кол-ва товара, тогда спрашивается, зачем он туда приехал) )
может это важно)

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

Цитата FasterHarder @ 23.12.19, 17:35

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

Граф - кольцо из хаба и 3 магазинов. Потребность каждого 2, грузоподъёмность 3.

Добавлено 23.12.19, 18:49

Цитата AVA12 @ 23.12.19, 17:59

Разве что принцип "один магазин - одна доставка" слегка утешает.

Причём на порядки. Фактически сводя задачу к линейному раскрою (или получится совсем нереальный граф).

Сообщение отредактировано: Akina - 23.12.19, 18:50

Цитата Akina @ 23.12.19, 18:45

Граф - кольцо из хаба и 3 магазинов. Потребность каждого 2, грузоподъёмность 3.

понимаю, что имеешь ввиду этим примером
тут просто лексически я подразумевал разность слов "приехал" и "проехал(мимо/через)", т е грузовик приехал в городN и отгрузил товар (стоянка какая-то), а если он едет в др.город транзитом через N, то грузовик ПРОЕХАЛ не останавливаясь, как бы)
тут все понятно и спорных моментов нет никаких!

в общем быстро прочитал/вспомнил задачи о рюкзаке и коммивояжера. Как-то все слишком сложно получается применительно к моей задаче, т к грузовику нужно возвращаться на дозаправку товаром (например, в коммивояжера лишь 1 рейс делается через все города)

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

еще: наверняка потребуется применить алгоритм Флойда-Уоршелла для построения матриц кратчайших расстояний между вершинами графа

не уверен, еще какой-нибудь мин.остов нужен и пр. пр.
и при этом нужны всякие NP-переборы.

СЛИШКОМ СЛОЖНО ВСЕ! Слишком большая концентрация графовых алгоритмов в одной задаче (прим.ТС, знать бы еще их хорошо) Надо упрощать, причем значительно!

ВОПРОС: как можно значительно упростить данную задачу, введя какие-то допущения, ограничения, но не нарушая базовых требований задачи??

т е на данный момент задача имеет сложность 8 из 10, надо ее превратить в сложность 3/4 из 10, т е не максимально упростить до сложности 1 из 10, а до 3/4 из 10.
сделать граф полностью связным? да никак это вроде не поможет.
вот за счет чего можно упростить?

Хотите упростить? Тогда сделайте размер заказа фиксированным 1 или 3 тонны.

Гм. А какие тут базовые требования? Что именно нельзя нарушать?

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

Цитата AVA12 @ 24.12.19, 12:50

Гм. А какие тут базовые требования? Что именно нельзя нарушать?

ну, например, грузоподъемность грузовичка (хотя на грузовик не тянет) ) в 6тонн и т.п.

Цитата AVA12 @ 24.12.19, 12:50

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

ясно, ну, тогда на этом и остановимся, может что-то и получится.

всем спс. за участие!

г

Скрытый текст

рафы - опаснейшие химеры, обладающие какой-то бесконечной лютой сложностью на определенном этапе)) а ведь существует миллион графовых задач в разы сложнее, как их решают, хз)...
и вообще, мне кажется (возможно, что именно КАЖЕТСЯ), что графы - апофеоз сложности в Computer Science...те же деревья - частный случай графа вроде

Цитата AVA12 @ 23.12.19, 17:59

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

Типичная транспортная задача, решается методом симплекса

Сообщение отредактировано: Gonarh - 25.12.19, 03:31

Я почитал про транспортную задачу в Википедии - там нет ничего про транспортную сеть. Есть только стоимости доставки из пункта производства a[i] в пункт потребления b[j]. Но у нас другой случай: если имеется плотный кластер магазинов, к которому от хаба ведет длинная дорога, то минимальная стоимость доставки товаров ко всем магазинам кластера будет меньше, чем сумма стоимостей доставки к каждому из них. Свести имеющуюся задачу к транспортной (назначить некоторые магазины временными "пунктами производства") так просто не получается.

Я бы предложил следующий алгоритм:
1. Составить все варианты сочетания магазинов (маршрутов), для 8ми магазинов из #5 получится 2^8-1 = 255 маршрутов
2. Решить задачу коммивояжера для каждого маршрута (наименьший путь)
3. Исходя из требуемых заказов составить все варианты упаковки груза не превышающий грузоподъемность машины
4. Составить линейную модель где требуется минимизировать пробег, выполнив все заказы используя варианты упаковки из п.3 с учетом весов полученных в п.2. для каждого маршрута и решить ее целочисленным линейным программированием

Ну тут сразу надо отказаться от попыток найти оптимальное решение точным алгоритмом.
Что-то эвристическое на здравом смысле.
А насколько непредсказуемо магазины делают заказы? Заказывают каждый день? раз в неделю? раз в месяц?

Если заказывают более-менее равномерно по времени.
Это всё на плоскости происходит, можно сказать, на карте.
Разделить карту на квадранты, сгруппировать магазины по квадрантам.
Средняя суммарная потребность одной группы не должна превосходить 6 тонн.
В идеальной ситуации грузовик объезжает группу - возвращается, загружается и едет в следующую группу.
Если что-то пошло не так.
В каких-то группах сегодня недогруз, в каких-то - перегруз.
Берём список групп-"ближайших соседей" группы с недогрузом, ищем группу с максимальным "перегрузом" и в заключении маршрута из одной группы с недогрузом переезжаем в группу с перегрузом.
Если во всех группах одновременно недогруз или перегруз, значит группы неправильно сформированы.

Как внутри группы объезжать магазины - водила сам догадается.
Остаётся только задача набора заданного веса из заданных слагаемых.
Если слагаемых меньше 20, то алгоритмом с возвратом. Больше - динамикой. Сверхбольшой размерности тут, видимо, нет.

swf,
Предложенный мной алгоритм не исключает упрощения и эвристики
Если "магазинов" много, и значение 2^n (где n - количество магазинов) большое, становится не рационально генерировать все комбинации маршрутов
На этапе 1-2 исключаем варианты, в которых расстояние больше определенного, либо, как предложили Вы группируем магазины, в качестве группировки можно использовать алгоритм k-means
Этап 1-2 делается один раз для заданной логистической схемы, поэтому на него можно потрать определенное время

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

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

Есть вот какое предложение ...

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

1) Матрицу NxN разделить на крупные области, ну как в картографии - "квадраты"
2) Если квадраты получаются тоже большого размера, каждый квадрат так же разделить на "под-квадраты"
3) Итерация п.2 до разумных размеров полученных "под-квадратов"
4) Построить матрицы стоимостей путей между квадратами, под-квадратами, под-под- квадратами, но только на своих уровнях

И теперь получается следующее. Пусть грузовик находится в квадрате A1, и есть варианты куда доставить груз - это квадраты M122, N3, Z14. По предварительно рассчитанным данным мы сразу выбираем нужный квадрат, в нем подквадрат и т.д.

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

to m-ch
Приветствуем нового рыцаря участника Алгоритмов!
Давно уже к нам специалисты не заглядывали.

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

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

Сообщение отредактировано: swf - 18.06.20, 16:12

Цитата JoeUser @ 18.06.20, 07:32

стопицот миллионов

Один грузовик не осилит

Есть "главный" вопрос: это теоретическая задача или это будет практическое применение?

На практике. За достоверность не ручаюсь.
Заказы надо получать утром, это если это продуктовые магазины. Хозяйственные, строительные и т.д. в течении дня или недели.
Один грузовик не будет возить продукты и не продукты (даже по очереди), сан.нормы.
Продукты развозятся или с местных заводов или с центрального склада. В первом случае получается узко специализированная поездка, например, развозка из теплицы огурцов и помидоров, что одним грузовиком можно охватить много магазинов. Хлебобулочные сразу же с пекарни отгружаются в магазины, молочка тоже. У каждого может быть свой грузовик, а возможно общий.
Не продукты так же возможно отгрузка не с центрального склада, а с фабрики/завода и так же будет тематической.

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

Добавлено 19.06.20, 03:36
Если чисто теоретически, что за товар не известно, т.е. не делим продукты и не продуты и один склад.

На вскидку вижу два стартовых шага/направления с повторением цикла:
1) Берем тот продукт, масса которого самая большая, строим для него оптимальный маршрут(ы), может быть с несколькими поездками, в последнем случае с не полной загрузкой, докидываем потребность этих же магазинов другим товаром.
2) Берем такой товар, для которого самый длинный маршрут по длине пути или по количеству магазинов. В случае недогруза, докидываем товарами из объезжаемых магазинов.

Если рассуждать логически из физического смысла задачи, грузовик имеет грузоподъемность (это не почтальон который может носить 100 писем)
поэтому число посещаемых магазинов будет варьироваться от 1 до 7 (6/3.2)...(6/0.8).
Теперь можно составить списки (цепочки) посещений магазинов которые удовлетворяют условию: Сумма отвозимых товаров не более грузоподъемности.
пример
вариант 1
A(3.0) - B(2.5) - C(0.5)
D(2.5) - E(1.5) - F(1.0) - G(0.5)
H(1.0) - I(1.0) - J(1.0)
вариант 2
A(3.0) - D(2.5) - C(0.5)
B(2.5) - E(1.5) - F(1.0) - G(0.5)
H(1.0) - I(1.0) - J(1.0)
и т.д.
Простой перебор (вариантов цепочек + перебор внутри цепочек) решает задачу. Критерий для сравнения вариантов суммарный путь грузовика.

Что такое оперативное планирование производства при горизонте планирования сутки.
Утром появляется суточный портфель заказов.
Эти данные загружаются в программу, нажимают кнопку, через 5(пять) минут должен выйти план.
Поэтому линейное программирование сразу идёт в топку.

Далее, предположим, мы написали программу для 20 магазинов. А 20 магазинов ещё можно перебрать.
А через некоторое время появляются ещё 5 магазинов, уже программа идёт в топку.
Магазины, конечно, надо агрегировать и для понижения размерности задачи, и на случай увеличения размерности входных данных.
Новые магазины добавляются в группы. а там можно увеличивать количество "ходок" при увеличении объёма товара.

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

Цитата

Эти данные загружаются в программу, нажимают кнопку, через 5(пять) минут должен выйти план.
Поэтому линейное программирование сразу идёт в топку

А можно пояснить что значит через 5 минут должен выйти план.
Компьютер считает исключительно быстро, (при малом числе вариантов например менее 1000 магазинов) слабым звеном здесь является оператор(диспетчер) который вводит данные тут и 5 и 30 мин может быть ... но при удобном интерфейсе программы и при правильном планировании рабочего времени проблем не вижу.

Цитата

Далее, предположим, мы написали программу для 20 магазинов

Цитата

Далее, фирма прикупила ещё два транспортных средства, разной ёмкости

Могу написать программу для N магазинов и K грузовиков, каждый из которых M(K) грузоподъемности, руководствуясь вышеизложенным принципом построения цепочек по грузоподъемности. Но оставлю этот алгоритм для автора, дабы не лишать его удовольствия от создания интересной и полезной программы.

5 минут прописывается в техзадании, это требование заказчика.
Если задача включает в себя коммивояжера и размерность задачи 250 (с точки зрения заказчика, это совсем немного), то размерность пространства решений равна 250!, это больше чем число атомов в видимой нами части вселенной.
Впрочем, заказчика атомы в видимой нами части вселенной не волнуют, он точно знает, что он нажал кнопку и не более чем через 5 минут должен выйти суточный план.

Цитата

Могу написать программу для N магазинов и K грузовиков, каждый из которых M(K) грузоподъемности

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

Цитата swf @ 19.06.20, 09:44

Если задача включает в себя коммивояжера и размерность задачи 250 (с точки зрения заказчика, это совсем немного), то размерность пространства решений равна 250!, это больше чем число атомов в видимой нами части вселенной.

Ну это именно теоретический подход с прицелом "на статью".

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

Цитата Маршал @ 19.06.20, 08:37

число посещаемых магазинов будет варьироваться от 1 до 7

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

Цитата Akina @ 19.06.20, 10:53

Цитата swf @ 19.06.20, 09:44

Если задача включает в себя коммивояжера и размерность задачи 250 (с точки зрения заказчика, это совсем немного), то размерность пространства решений равна 250!, это больше чем число атомов в видимой нами части вселенной.

Ну это именно теоретический подход с прицелом "на статью".

С этого начинается работа математика-постановщика. Вначале определяется класс задачи.
Затем у заказчика запрашивается максимальный размер входных данных и определяется размерность пространства решений.
И после этого сразу отбрасываются те методы, которые не укладываются в 5 минут в оперативное планирование.