Это вопрос моделирования / таксономии. Есть ли название для этого типа проблемы?
Я придумал следующую графическую задачу для грузовика по доставке пиццы, который начинается с нуля долларов и достаточного количества топлива, чтобы проехать N миль. Они хотят доставить пиццу клиентам C. Каждый покупатель немедленно заплатит им определенное количество долларов.
Веса ребер на этом графике - это количество миль между пунктами назначения.
Вершины в графе - это не просто клиенты. Они также включают в себя узлы «заправочные станции» - места, в которых грузовик может заправиться топливом, конвертируя наличные деньги в «километры, которые можно проехать».
Проблема в том, с учетом исходного местоположения, сколько наличных денег и / или бензина в баке нужно грузовику, чтобы доставить пиццу каждому покупателю и все равно вернуться домой?
Это не классическая проблема коммивояжера, потому что здесь задействованы два типа ресурсов: $ и топливо. И есть ограничение на ресурсы - проблема не только в том, чтобы найти минимальную стоимость. Речь идет о поиске минимальных стартовых ресурсов, необходимых для прохождения круга.
