What is the name for this special case of the Travelling Salesman involving dynamic edge costs?

Question

This is a modeling / taxonomy question. Is there a name for this type of problem?

I came up with the following graph problem for a pizza delivery truck, which starts with zero dollars and enough fuel to drive N miles. They want to deliver pizza to C customers. Each customer will immediately pay them some number of dollars.

Edge weights in this graph are the number of miles between destinations.

Vertices in the graph aren't just customers. They also include "gas station" nodes -- places at which the delivery truck can refuel, converting money on hand to "miles able to drive".

The problem is, given a starting location, how much money on hand and/or gas in the tank does the truck need to delivery pizza to every customer, and still return home?

This isn't the classic Travelling Salesman problem because there are two types of resources in play here, $ and fuel. And there's a resource constraint -- the problem isn't just about finding the minimum cost. It's about finding the minimum starting resources necessary to be able to complete a circuit.

Answer 1

Not sure if there is a name for this, but there's a straightforward NP-hardness reduction from TSP: Given a TSP instance and length L, create a Pizza instance with the same graph, L starting fuel and no gas stations.