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

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

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

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

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


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

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

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

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

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

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

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


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

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

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

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

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