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.

  • $\begingroup$ "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 $\endgroup$ – vzn Jun 25 '14 at 18:56
  • $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Jun 25 '14 at 20:36
  • $\begingroup$ 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; in particular the third variant in the introduction: The uniform cost tour gas station problem. $\endgroup$ – Marzio De Biasi Jun 25 '14 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.