Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

The task I'm struggling with for the last three or four days looks like this: there is a depot. We load some goods in a truck, and this truck delivers goods to the clients. There is a route, which means that this truck has to deliver goods in some predefined order, and we know distances between "adjacent" customers (vertexes on the following picture).
enter image description here
So, what I need to find is some kind of metric or heuristic to find which client is the most profitless for us - which means that it costs too much to deliver the goods for him, or he is too far from us and our truck spends too much time to get to him. On the previous picture point G looks like very profitless - distances g and h are relatively long, but if we move point G to be near the F, and make the distance g relatively small, this point become profitable - because it costs very little to get to G from F, if g is small.
I've read an article about Savings algorithm, but understood that it doesn't fit here, because I don't have distances from Depot to every point, all I have are distances between adjacent points.
Does anybody have any ideas about possible ways to solve this issue? I don't need anybody to solve it for me - if you know a link to an article, or some good algorithm - just put it here, it'll be just perfect.

share|improve this question
3  
If you only have the distance of the lines, then this question isn't possible to answer. If it can be the case that the lines form the unique road (one-way) to reach all points, then it costs nothing to visit them all. – Pål GD Jan 11 at 10:20
If you could make the problem a bit clearer, that would be nice. You could associate with each edge a weight, which would be the cost (which could be negative, i.e. you have a profit) for traversing this edge (e.g. money you need for gas - money you gain from delivering to vertex). Then, you would be asking for the shortest simple cycle that contains the vertex Depot. – chazisop Jan 11 at 11:11
Given three consecutive points A->B->C, do you also know the distance from A to C ? – Marzio De Biasi Jan 11 at 15:14
@MarzioDeBiasi no, all I know are distances between adjacent vertices - A and B, B and C. – aga Jan 14 at 5:20

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.