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.

Caespitose

It resembles a bit the knapsack problem, I think. Let's see what the others say. – Stephenstephenie

May I suggest you change your title to "Travelling Salesman Variation" or something. The current title is somewhat nondescript. – Waggery

It's neither a knapsack problem nor the travelling salesman problem: he wants to go from A to B, not everywhere. It's a specific graph problem, which doesn't have a name afaik. – Tympany

I think it is actually a combination of a variation of both problems. Each problem influences the other in some way. – Jubilate

agree with niomaster and dough, still, this title less specific than it could be – Waggery

source problem @ s3-eu-west-1.amazonaws.com/marathon24-public/… – Mulloy

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.

Polyclitus

clever - I like this! Although it does make the graph a lot bigger if you have a big tank! – Caespitose

Answer 2

I think you can solve this with dynamic programming. For each node, you save an array of tuples of petrol cost and the length of the path where you use that petrol, containing the optimal solution. Every step you loop trough all nodes and if there is a node you can go, which already has a solution, you loop trough all the nodes you can go to with a solution. You select the minimum cost, but note: you have to account for the petrol cost in the current node. All costs in the array that are higher than the cost in the current node, can instead be bought at the current node. Note that nodes which already have a solution should be recalculated, as the nodes you can go to from there could change. You start with the end node, setting the solution to an empty array (or one entry with cost and length 0). The final solution is to take the solution at the beginning and sum up every cost * length.

Berthaberthe

I can't quite see how this works but I'll have another look tomorrow when I'm less tired! – Caespitose

Answer 3

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.

Waggery

agree with @niomaster in fact, further away from a travelling salesman problem than I first thought – Waggery

But in general the traveling salesman problem is trivially reduced to this one by setting all the petrol prices to the same value and making the petrol tank of the car large enough to complete the whole journey without additional tanking, therefore the problem is NP-hard in general. – Peta

+1 for using the tank size to reduce computational complexity :) however, the additional difference is that he doesn't want to visit all cities – Waggery

My apologies, looks like I have misread the problem statement. – Peta

Answer 4

I'd try this:

1. Find the shortest route from start to destination. Dijkstra's algorithm is appropriate for this.
2. Find the minimum cost of petrol to travel this route. I'm not aware of any off-the-shelf algorithm for this, but unless there are many cities along the route even an exhaustive search shouldn't be computationally infeasible.
3. Find the next shortest route ...

Defining precise stopping criteria is a bit of a challenge, it might be best just to stop once the minimum cost found for a newly-tested route is greater than the minimum cost for a route already tested.

So, use 2 algorithms, one for each part of the problem.

Petuntse

This is a valid solution as well, but, unfortunately, very slow. – Tympany

I don't think you can stop once the minimum cost starts to increase again, its possible for the cheapest route to be the longest and the second cheapest to be the shortest for example... in order to be sure of having the cheapest you would have to examine every route :/ – Caespitose

Answer 5

This might be optimized suitably well using a Genetic Algorithm. Genetic Algorithms beat humans at some complex problems: http://en.wikipedia.org/wiki/Genetic_algorithm

The gist of a Genetic Algorithm is:

1. Come up with a ranking function for candidate solutions
2. Come up with a pool of unique candidate solutions. Initialize it with some randomly-generated possibilities. Maybe 10 or 100 or 1000...
3. Copy a candidate solution from the pool and perturb it in some way - add a town, remove a town, add two towns, etc. This might improve or worsen matters - your ranking function will help you tell. Which one do you pick? Usually, you pick the best, but once in a while, you intentionally pick one that's not to avoid getting stuck on a local optimum.
4. Has the new solution already been ranked? If yes, junk it and go to
   1. If no, continue...
5. Add the perturbed candidate back to the pool under its newly-calculated rank
6. Keep going at this (repeat from #3) until you feel you've done it long enough
7. Finally, select the answer with the best rank. It may not be optimal, but it should be pretty good.

Jeremiahjeremias

Answer 6

You could also formulate that as an integer linear programming (ILP) problem. The advantage is that there is a number of off-the-shelf solvers for this task and the complexity won't grow so fast as in the case of Peters solution with the size of the tank.

The variables in this particular problem will be the amounts of petrol purchased in any one town, the amount in the cars tank in any town on the way and actual roads taken. The constraints will have to guarantee that the car spends the necessary fuel on every road and does not have less that 0 or more than MAX units of fuel in any town and that the roads constitute a path from A to B. The objective will be the total cost of the fuel purchased.

The whole thing may look monstrous (ILP formulations often do), but it does not mean it cannot be solved in a reasonable time.

Peta