Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832813 Fri, 19 Jun 2020 11:04:23 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832813 Цитата Akina @
Цитата swf @
Если задача включает в себя коммивояжера и размерность задачи 250 (с точки зрения заказчика, это совсем немного), то размерность пространства решений равна 250!, это больше чем число атомов в видимой нами части вселенной.

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

С этого начинается работа математика-постановщика. Вначале определяется класс задачи.
Затем у заказчика запрашивается максимальный размер входных данных и определяется размерность пространства решений.
И после этого сразу отбрасываются те методы, которые не укладываются в 5 минут в оперативное планирование.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832811 Fri, 19 Jun 2020 10:53:47 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832811 Цитата swf @
Если задача включает в себя коммивояжера и размерность задачи 250 (с точки зрения заказчика, это совсем немного), то размерность пространства решений равна 250!, это больше чем число атомов в видимой нами части вселенной.

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

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

То есть программно практически без итераций формируется 99% плана разъездов. И лишь остаток закрывается с использованием всех существующих связей - да и его проще закрыть "ближними перетасовками", чем одним покрывающим маршрутом. Даже жадный алгоритм, начинающий с дальних узлов, я думаю, отлично справится с задачей - нам же нужно получить план развоза, а не доказательство, что он оптимален...]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832809 Fri, 19 Jun 2020 09:56:27 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832809 Цитата
Могу написать программу для N магазинов и K грузовиков, каждый из которых M(K) грузоподъемности

Но пока занят другим проектом, и кроме того коммерческого предложения на разработку этой программы у меня нет. В области реального количества вариантов которые останутся если сначала отбраковать все невозможные, решение не будет занимать много компьютерного времени. В этом я и вижу смысл "не искать лучший математический алгоритм" а "отбраковать все нереальные на ранней стадии"]]> Маршал Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832805 Fri, 19 Jun 2020 09:44:30 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832805 Если задача включает в себя коммивояжера и размерность задачи 250 (с точки зрения заказчика, это совсем немного), то размерность пространства решений равна 250!, это больше чем число атомов в видимой нами части вселенной.
Впрочем, заказчика атомы в видимой нами части вселенной не волнуют, он точно знает, что он нажал кнопку и не более чем через 5 минут должен выйти суточный план.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832803 Fri, 19 Jun 2020 09:25:20 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832803 Цитата
Эти данные загружаются в программу, нажимают кнопку, через 5(пять) минут должен выйти план.
Поэтому линейное программирование сразу идёт в топку

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

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

Могу написать программу для N магазинов и K грузовиков, каждый из которых M(K) грузоподъемности, руководствуясь вышеизложенным принципом построения цепочек по грузоподъемности. Но оставлю этот алгоритм для автора, дабы не лишать его удовольствия от создания интересной и полезной программы.]]> Маршал Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832802 Fri, 19 Jun 2020 08:58:12 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832802 Утром появляется суточный портфель заказов.
Эти данные загружаются в программу, нажимают кнопку, через 5(пять) минут должен выйти план.
Поэтому линейное программирование сразу идёт в топку.

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

Далее, фирма прикупила ещё два транспортных средства, разной ёмкости.
Программа для одного грузовика идёт в топку.
С другой стороны, для разработчика это хорошо, без дела не сидит :D]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832801 Fri, 19 Jun 2020 08:37:07 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832801 поэтому число посещаемых магазинов будет варьироваться от 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)
и т.д.
Простой перебор (вариантов цепочек + перебор внутри цепочек) решает задачу. Критерий для сравнения вариантов суммарный путь грузовика.]]> Маршал Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832777 Fri, 19 Jun 2020 03:19:14 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832777 Цитата JoeUser @
стопицот миллионов

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

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

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

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

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

На вскидку вижу два стартовых шага/направления с повторением цикла:
1) Берем тот продукт, масса которого самая большая, строим для него оптимальный маршрут(ы), может быть с несколькими поездками, в последнем случае с не полной загрузкой, докидываем потребность этих же магазинов другим товаром.
2) Берем такой товар, для которого самый длинный маршрут по длине пути или по количеству магазинов. В случае недогруза, докидываем товарами из объезжаемых магазинов.]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832766 Thu, 18 Jun 2020 16:10:17 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832766 m-ch
Приветствуем нового рыцаря участника Алгоритмов!
Давно уже к нам специалисты не заглядывали.

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

Но могу сказать одно, по опыту решения других задач.
Если для подобной, весьма сложной реальной задачи с элементами коммивояжера, для большой размерности сделать эвристический алгоритм, который будет прекрасно (и быстро!) работать, то работать он будет не по науке и статью про это не напишешь.
А вот если делать чем-то модным (неважно чем, лишь бы мейнстрим), например, генетическими алгоритмами, то работать оно будет плохо, зато с публикациями будет полный порядок.
Либо шашечки, либо ехать. Вот такая моя т.н.т.з. :D]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832732 Thu, 18 Jun 2020 07:32:51 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832732
Допустим у нас не 10 магазинов, а стопицот миллионов (пусть это размер N). Полный перебор сразу можно делегировать правнукам. Но задачу же все равно нужно решать. А что если произвести предварительную "подготовку"?

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

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

Предложение мое конечно "сыровато", но оно призвано уменьшить объемы пересчетов путем отсечения ненужных областей для пересчетов.]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832730 Thu, 18 Jun 2020 05:57:36 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832730 swf,
Предложенный мной алгоритм не исключает упрощения и эвристики
Если "магазинов" много, и значение 2^n (где n - количество магазинов) большое, становится не рационально генерировать все комбинации маршрутов
На этапе 1-2 исключаем варианты, в которых расстояние больше определенного, либо, как предложили Вы группируем магазины, в качестве группировки можно использовать алгоритм k-means
Этап 1-2 делается один раз для заданной логистической схемы, поэтому на него можно потрать определенное время

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

Думаю, что для небольшой сетки (пару десятков магазинов) можно найти оптимальное решение через линейное программирование, для большего количества, используя эвристики, достаточно близкое к оптимальному за разумное время.]]> m-ch Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832725 Wed, 17 Jun 2020 20:22:38 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832725 Что-то эвристическое на здравом смысле.
А насколько непредсказуемо магазины делают заказы? Заказывают каждый день? раз в неделю? раз в месяц?

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

Как внутри группы объезжать магазины - водила сам догадается.
Остаётся только задача набора заданного веса из заданных слагаемых.
Если слагаемых меньше 20, то алгоритмом с возвратом. Больше - динамикой. Сверхбольшой размерности тут, видимо, нет.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832712 Wed, 17 Jun 2020 13:48:26 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3832712 1. Составить все варианты сочетания магазинов (маршрутов), для 8ми магазинов из #5 получится 2^8-1 = 255 маршрутов
2. Решить задачу коммивояжера для каждого маршрута (наименьший путь)
3. Исходя из требуемых заказов составить все варианты упаковки груза не превышающий грузоподъемность машины
4. Составить линейную модель где требуется минимизировать пробег, выполнив все заказы используя варианты упаковки из п.3 с учетом весов полученных в п.2. для каждого маршрута и решить ее целочисленным линейным программированием]]> m-ch Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817346 Wed, 25 Dec 2019 13:44:31 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817346 AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817325 Wed, 25 Dec 2019 03:30:22 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817325 Цитата AVA12 @
Ну, вроде, ясно. Получается самый сложный случай, задача коммивояжера плюс задача о рюкзаке. Разве что принцип "один магазин - одна доставка" слегка утешает. Надо думать.

Типичная транспортная задача, решается методом симплекса]]> Gonarh Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817323 Wed, 25 Dec 2019 03:14:00 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817323 Цитата AVA12 @
Гм. А какие тут базовые требования? Что именно нельзя нарушать?

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

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

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

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

г
Скрытый текст
рафы - опаснейшие химеры, обладающие какой-то бесконечной лютой сложностью на определенном этапе)) а ведь существует миллион графовых задач в разы сложнее, как их решают, хз)...
и вообще, мне кажется (возможно, что именно КАЖЕТСЯ), что графы - апофеоз сложности в Computer Science...те же деревья - частный случай графа вроде
]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817305 Tue, 24 Dec 2019 12:50:00 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817305
Я уже упоминал вариант радикального упрощения задачи: вместо неупорядоченного набора заказов использовать очередь, и грузить заказы в машину строго в порядке их поступления. Тогда действительно сложной проблемой будет только выбор, грузить очередной заказ "прям щас" или оптимальнее будет отложить его для следующей доставки.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817304 Tue, 24 Dec 2019 11:28:59 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817304 Pavia Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817295 Tue, 24 Dec 2019 05:02:26 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817295 Цитата Akina @
Граф - кольцо из хаба и 3 магазинов. Потребность каждого 2, грузоподъёмность 3.

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

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

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

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

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

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

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

т е на данный момент задача имеет сложность 8 из 10, надо ее превратить в сложность 3/4 из 10, т е не максимально упростить до сложности 1 из 10, а до 3/4 из 10.
сделать граф полностью связным? да никак это вроде не поможет.
вот за счет чего можно упростить?]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817290 Mon, 23 Dec 2019 18:45:49 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817290 Цитата FasterHarder @
а если нет необходимого кол-ва товара, тогда спрашивается, зачем он туда приехал

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

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

Причём на порядки. Фактически сводя задачу к линейному раскрою (или получится совсем нереальный граф).]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817286 Mon, 23 Dec 2019 17:59:28 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817286 AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817284 Mon, 23 Dec 2019 17:35:20 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817284
______.png (, : 2222)

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

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

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

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

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


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

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

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

Добавлено
также давайте считать, что товар НЕ МОЖЕТ разгружаться частично, т е грузовик приехал в магазинN и отгрузил ВЕСЬ товар, который нужен этому магазину при условии, что в кузове есть необходимое кол-во товара (а если нет необходимого кол-ва товара, тогда спрашивается, зачем он туда приехал) )
может это важно)]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817283 Mon, 23 Dec 2019 17:32:05 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817283 AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817281 Mon, 23 Dec 2019 17:02:55 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817281
В принципе обе версии фактически сводятся к одной - к задаче о рюкзаке. Где на первом шаге определяется количество рейсов, которое получится roundup(общий вес / грузоподъёмность), возможно ещё плюс один, если расстояние сильно варьирует. А на втором выполняется деление на рюкзаки (загрузки), для загрузок в несколько точек - минимизация расстояния/времени.

В общем, по большому счёту, NP или очень близко, так что да, динамика на базе графа.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817280 Mon, 23 Dec 2019 16:55:32 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817280 Цитата
Есть задача, примерно такого содержания

Все-таки надо уточнить - что на входе, что должно получиться на выходе. Если на входе конкретный список заказов для конкретной поездки (без "дозаправки"), то решение тривиально (тупой перебор небольшого количества вариантов). Если есть очередь заказов, не влезающих в грузовик, тогда все уже сложнее. Если и очереди нет, а есть неупорядоченный набор заказов, и нужно минимизировать общее время доставки, то это уже две сложные задачи.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817278 Mon, 23 Dec 2019 16:26:45 +0000 Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) https://forum.sources.ru/index.php?showtopic=416459&view=findpost&p=3817278 Есть задача, примерно такого содержания: есть сеть магазинов, в которые грузовик доставляет товары. Грузоподъемность грузовика 6тонн (прим.маловато будет). Средние величины заказов из отрезка [0.8 ... 3.2]тонн. Все магазины снабжаются из одного хаба (распределительный центр). Т е из этого хаба начинает движение грузовик. Также известны расстояния между магазинами (не между всеми магазинами есть связь), а также расстояние от магазинов до склада/хаба. Нужно получить ОПТИМАЛЬНЫЙ МАРШРУТ движения грузовика с целью доставки товаров по всем магазинам.

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

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

Подскажите как быть-то?
спс за внимание!]]> FasterHarder Алгоритмы