posted 15 years ago
I think it may be a good deal simpler than the traveling salesman, if my guesses about the intent here are correct.
[mani]: But you know that the sum of liters of petrol in all the bunks is equal to the distance to be covered.
What distance to be covered? It seems like there are many possible distances that we might travel, depending on our objectives - and the problem hasn't even given us a goal. Perhaps we are supposed to visit each fuel station once? Perhaps the "distance to be covered" is the total d1 + d2 + d3 + ... + dn? In this case, we could simply travel the circle (or polygon as the case may be), visiting each station in order, never reversing direction. The only important choices would be (a) where to start, and (b) which direction to travel in, so as not to ever run out of fuel. There's a reasonably simple algorithm that can be used here, and there will always be at least two solutions - one in each direction. Maybe more.