Каково название этого особого случая для путешествующего коммивояжера с динамическими издержками?

Question

Это вопрос моделирования/таксономии. Есть ли название для такого типа проблем?

Я придумал следующую проблему с графиком для грузовика для доставки пиццы, который начинается с нулевых долларов и достаточного количества топлива, чтобы проехать N миль. Они хотят доставить пиццу клиентам C. Каждый клиент сразу выплачивает им некоторое количество долларов.

Грубые грузы в этом графе - это количество миль между пунктами назначения.

Вершины на графике - это не только клиенты. Они также включают в себя узлы «бензоколонки» - места, в которых грузовик может заправлять топливо, конвертируя денежные средства в руки «миль, способных управлять».

Проблема заключается в том, что с учетом начального местоположения, сколько денег на руках и/или в газе в баке нужно грузовику для доставки пиццы каждому клиенту, и все же вернуться домой?

Это не классическая проблема с Traveling Salesman, потому что здесь есть два типа ресурсов: $ и топливо. И есть ограничение ресурсов - проблема заключается не только в поиске минимальной стоимости. Речь идет о поиске минимальных исходных ресурсов, необходимых для завершения схемы.

Answer 1

Не уверен, что есть имя для этого, но есть прямое сокращение NP-твердости от TSP: учитывая экземпляр TSP и длину L, создайте экземпляр Pizza с тем же графиком, L, запускающим топливо, и никакие заправочные станции.