Чуть-чуть графов. Алгоритм

Добрый день, буду рад любым наводкам

Есть такая задача.
Желтые круги – это стоянки.
Зеленые квадраты – это склады(Цифра внутри квадрата – это кол-во товара, которое есть на складе).
Синие круги – это магазины.
Стрелочки – это дороги(Цифра в стрелочках – длина/вес)

Допустим есть заявка от магазина привезти ему 20шт. товара.

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

Какой алгоритм или совокупность алгоритмов лучше использовать в случаях(когда данный граф ориентированный(у дорог есть направление и стоимость может отличаться) или же когда граф неориентированный(т.е. точки связаны каким-то среднеарифметическим весом)?


Пока была идея взять магазины и только склады. Методом потенциалов(вроде классическая транспортная задача) найти сперва какие склады удовлетворяют потребностям магазина(т.е. на них есть кол-во нужного товара и путь от склада оптимальный). Затем найти с какой стоянки кратчайший путь до магазина через данные выбранные склады(последовательность заездов на склады не оговорена), правда не совсем понятно какой алгоритм лучше для этой части. Но думал либо использовать А* только искать до тех пор пока в маршруте не будут содержаться нужные склады, либо Дейкстру только k! перестановок(задание очереди посещений складов).

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

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

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

INFINITs,

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

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

Согласен, рассматривается как учебная задача.
В части Дейкстра не будет ли слишком долго, ведь при про счете для трех заявок при 4 стоянках это уже 12 раз минимум надо прогнать алгоритм, а так даже больше.
Ведь выбрав для какой-то заявки стоянку и набор складов, то для другой заявки уже может измениться набор складов, т.к. на прежнем не будет хватать товара.

Поэтому если смысл рассмотреть какие-либо другие алгоритмы или каким-либо образом разбить задачу на под задачи.

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

Задача коммивояжера. В гугль.

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

Dimitry Sibiryakov
Задача коммивояжера. В гугль.

Мне казалось данная задача немного про другое. Или Вы видите смысл обходить все вершины графа?

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

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

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

exp98
У меня лежит целая книга про "транспортного типа" (намёк как бы). Если надо посетить неизвестное кол-во узлов, то это ни классический комивояжер, ни классич-я трансп-я. Если получится представить в виде выпуклой задачи оптимизации, то был симплекс-метод. Был ещё "метод динамического программирования".

Если книга очень хорошая, то не могли так сказать автора и название )

Спасибо за наводку почитаю про эти два метода.

INFINITs
Если книга очень хорошая, то не могли так сказать автора и название )

Кому очень, кому нет. Сколько помню, посвящена различным постановкам задач, больше теоретическая, прошлый век. Да так и называлась "Задачи трансп-го типа", в Ленинке можно поискать (очно). А лучше в инете на эту тему, что-нить ещё - намёк на это был.

Вот эта
"Задачи линейного программирования транспортного типа" Гольдштейн, Юдин
Изд. Наука, М. 1969, тир.9650 экз, цена 1р 42 коп.

Ещё раз проглядел - годится.