Уважаемые форумчане! Нужен Ваш опыт и совет!
Есть задача, как мне кажется тривиальна, хотя решения я не нашел.
Существуют пункты с жидкими веществами. Необходимо объехать все пункты и собрать жидкости.
Каждый пункт имеет жидкость определенного веса и типа.
Есть сеть дорог в виде неориентированного нагруженного графа.
Есть транспортные цистерны (грузовики) с ограниченным тоннажем, находятся в гаражах. Они должны объехать все пункты и собрать жидкости.
Смешивать жидкости, понятное дело, нельзя.
Пример такой схемы на скрине:
Цель задачи - построить маршруты сбора жидкостей для каждого грузовика (маршрут возврата в гараж цистерны после заполнения - не актуален), так чтоб грузовик был заполнен по максимуму и при этом суммарный пробег всех машин был минимален.
Если бы не ограничения по тоннажу цистерны данная задача решается с помощью нахождения покрытия вершин подграфа (где подграф - это множество пунктов, сбор в которых будет произведен н-тым грузовиком). Но проблема в том, что я не знаю на перед сколько пунктов объедет цистерна перед тем как заполнится.
Получается, что сначала необходимо определится с тоннажем, т.е. распределить цистерны по пунктам согласно весу. Но таких вариантов может быть не один. Т.е. надо следить за тоннажем во время построения минимальных маршрутов. Как это сделать я пока не догоняю. Усложняется еще тем, что цистерна может быть заполнена под завязку и при этом не собрав все жидкости данного типа. Поэтому жидкость одного типа могут собирать несколько цистерн.
Очень иллюстративный пример на скрине. Конечные точки концентрируются больше у второго (нижнего гаража). Но тоннаж его цистерн не достаточно, чтобы все собрать.
Подскажите куда копать! Разброс по цистернам напоминает задачу про камни или ранец. Но эти алгоритмы должны быть синтезом выбора цистерн для пунктов и построения минимальной карты маршрутов одновременно.
