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

<p>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.</p>

<p>Edge weights in this graph are the number of miles between destinations.</p>

<p>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".</p>

<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2014-06-25T18:56:59.403Z
"dynamic"? usually called "online algorithms" in comparison to "batch" algorithms where graphs can change over time....? are you saying the graph & weights continuously change over time or they are static? its something like a scheduling/resource conservation/optimization problem... suggest you formalize it some/further
vzn
CC BY-SA 3.0
2014-06-25T20:36:37.283Z
do different gas stations have different rates? does each customer pay the same amount of money per pizza? do different customers have different demands for pizza (i.e. how many pies they want)? and, as vzn asked, is all this information available up front?
Sasho Nikolov
CC BY-SA 3.0
2014-06-25T22:16:59.673Z
You can find a similar problem (that takes into account the fuel and the gas stations) in [S. KHuller et al. To Fill or not to Fill: the Gas Station Problem](http://sydney.edu.au/engineering/it/~mestre/papers/gas-station.pdf); in particular the third variant in the introduction: The uniform cost tour gas station problem.
Marzio De Biasi
<graph-theory><graph-algorithms>
What is the name for this special case of the Travelling Salesman involving dynamic edge costs?
Aaron Fi
# What is the name for this special case of the Travelling Salesman involving dynamic edge costs?

(Asked by: username_0 on 2014-06-25)

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.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: "dynamic"? usually called "online algorithms" in comparison to "batch" algorithms where graphs can change over time....? are you saying the graph & weights continuously change over time or they are static? its something like a scheduling/resource conservation/optimization problem... suggest you formalize it some/further  
> **username_2**: do different gas stations have different rates? does each customer pay the same amount of money per pizza? do different customers have different demands for pizza (i.e. how many pies they want)? and, as vzn asked, is all this information available up front?  
> **username_3**: You can find a similar problem (that takes into account the fuel and the gas stations) in [S. KHuller et al. To Fill or not to Fill: the Gas Station Problem](http://sydney.edu.au/engineering/it/~mestre/papers/gas-station.pdf); in particular the third variant in the introduction: The uniform cost tour gas station problem.  

---

## 0 answers

