Suggest an algorithm (graph - possibly NP-Complete)

Question

There is a network of towns, connected by roads of various integer lengths.

A traveler wishes to travel in his car from one town to another. However, he does not want to minimize distance traveled; instead he wishes to minimize the petrol cost of the journey. Petrol can be bought in any city, however each city supplies petrol at various (integer) prices (hence why the shortest route is not necessarily the cheapest). 1 unit of petrol enables him to drive for 1 unit of distance. His car can only hold so much petrol in the tank, and he can choose how many units of petrol to purchase at each city he travels through. Find the minimum petrol cost.

Does anyone know an efficient algorithm that could be used to solve this problem? Even the name of this type of problem would be useful so that I can research it myself! Obviously it's not quite the same as a shortest path problem. Any other tips appreciated!

EDIT - the actual problem I have states that there will be <1000 cities; <10000 roads; and the petrol tank capacity will be somewhere between 1 and 100.

Answer 1

You could solve this directly using Djikstra's algorithm if you are happy to increase the size of the graph.

Suppose your petrol tank could hold from 0 to 9 units of petrol.

The idea would be to split each town into 10 nodes, with node x for town t representing being at town t with x units of petrol in the tank.

You can then construct zero-cost edges on this expanded graph to represent travelling between different towns (using up petrol in the process so you would go from a level 8 node to a level 5 node if the distance was 3), and more edges to represent filling up the tank at each town with one unit of petrol (with cost depending on the town).

Then applying Djikstra should give the lowest cost path from the start to the end.

Answer 2

I think the question is: Is there a chance the petrol stuff makes the underlying traveling salesman problem computationally more feasible? If not, there is no efficient non-approximating algorithm.

Of course, you can find efficient solutions for edge cases, and there might be more edge cases with the petrol condition, as in, always take this city first because the petrol is so cheap.