Cross the desert.

[Guv]

Years ago I remember problems about crossing a desert or or desolate area. I do not remember if the problems were solved by trial and error or some sort of analysis. The following is the general idea.

Say you had a vehicle which could carry enough fuel to travel 600 units (miles or kilometers). You want to cross a desolate area which is say 1500 units (miles or kilometers). How do you do this using a minimum amount of fuel?

It seems obvious that this could be solved by trial and error. Certainly you could write a program to assist the trial and error process.

Is there some analytical approach or successive approximations method which would be certain of obtaining an optimum solution?

[noble]

All this involves is a knowledge of serperable ordinary
differential equations and variable mass momentum.

[Guv]

Noble, interesting analysis.

All this involves is a knowledge of serperable ordinary
differential equations and variable mass momentum.

I might have suspected that differential equations were pertinent, but it never occurred to me that momentum analysis would help solve this problem.

Might it also be necessary to consider the use of worm holes or other time warps?

[Balder]

Most problems "What is the shortest/most efficent/... way/method/.. of something" has the same sort of solution.
Set up an expression which depends of the factor wer'e looking for.
Then...urg...don't know the english word for this, but if our expression is f(t) for example, we figure out the f'(t). Hope you got it
Then set f'(t)=0 and find out where the function has it's roots. The value (t) has when you've found the root is the max/min point. If there's more than one root you must check towards the f(t) and check which t wer'e looking for.

Hm, I would really need to learn some more math-terms in english. Sorry.

I doubt you'll need diff. eq.'s in most of theese cases, althuough I might have misunderstood what Guv explained.

[Balder]

"variable mass momentum"...is that nuclear physics?
I've solved many problems similar to Guv's but none of them had any of that in their solution.

[Guv]

I do not think this type of problem is amenable to calculus methods, which are applicable to continuous functions. This seems to involve discrete methods.

The problem involves establishing fuel depots to enable you to travel the entire distance. You can carry enough fuel for a 600 unit trip and you are trying to travel across a 1500 unit desert.

A guess at a start to the solution is to travel 200 units and leave enough fuel at the first depot for a 200 unit trip & return to the starting point. Do this again and you have 400 units of fuel at the first depot. Now you can go to the first depot, fill up and go another 200 units of distance, leave 200 units at the second depot, return to the first depot, and use the 200 units there to return to the starting point. You now have 200 units of fuel at the second depot and none at the first. You can repeat this process to build up the supply at the second depot, and then get some fuel to a third depot.

Do you see the approach to a solution? It takes a lot of bookkeeping to keep track of how much fuel you use and how much is at each depot. The above suggests establishing 7 depots at 200 unit intervals, with the last depot 100 units from the destination. I am sure you can find a solution using this distance between depots. You could also establish 14 depots at 100 unit intervals and find a solution. Now the question is, what is the solution which requires the minimum amount of fuel?

It does not seem difficult to write a VB program to solve any particular example of this problem, and tinker with the number and spacing of depots to find an optimum solution. The real problem is to determine a general algorithm for solving this type of problem.

I first encountered this problem 40-50 years ago in a magazine. The magazine asked for the solution to a particular problem, but did not bring up the question of a general solution to any such problem.

I have no idea if there is an algorithm usable for the general problem, and I do not know the optimum solution to the above special case. Intuitively, it seems as though the intervals between depots should be equal, except perhaps for the last one. It also seems correct to establish depots at an interval such as the above: Use 1/3 to get to the next depot, leave 1/3, and use 1/3 to return to the starting point. While this seems like the right idea for a general purpose algorithm, I have no idea if it is the correct approach in all cases.

It might be correct to try to analyze how much fuel should be at each depot for the last trip. If you assume depots at 100 unit intervals for the above problem, it seems correct to start the final trip with no fuel at the first 5 depots and 100 units of fuel at each of the others.

It might be very difficult to decide and/or prove that a particular solution is optimal. Note that for depots at 100 unit intervals, there are many itineraries possible for the above problem. For 50 unit intervals, there are even more itineraries possible.

Does anybody have any ideas? Right now, I am too busy with higher priority activities to spend time on this. It looks like a time consuming problem.

[Balder]

Hm...I guess I did misunderstand you Guv. Don´t think I wanna dig into this either

[noble]

var mass momentum...nuclear physics? I thought you
guys were smarter than this. I did, however, misinterpret what exactly you wanted to do in your problem. btw, guru != comedian

[Balder]

Well, I must blaim my english math-term knowledge again...I´m really curious what "var mass momentum" really is...please explain...perhaps I know without being aware of it.

[noble]

variable mass momentum can be applied to an object whose mass changes while in motion, such as a rocket who burns fuel or drops rockets while traveling

[crutchlb]

err, have 8 vehicles. and a few friends to help.

All travel 300 units and then dump four of the vehicles.

syphen the remaining out of the tanks and fill up the remaining 4 vehicles, then travel another 300 units before dumping another two vehicles and doing the same again with the fule.

Travel another 300 units and dump one of the vehilcles, syphen and then travel the last 600 units with all your friends who probably stink now from having traveled so far in desolate conditions.

would that count as an answer?

[Guv]

Crutchlb, you have come up with a novel approach. I did not check your arithmetic, but assume it is correct. I have seen this type of problem many times with different numbers. Nobody ever proposed your solution.

Your method should be declared allowable on the basis of originality.

[Guv]

Crutchlb, BTW: Your solution seems to waste a lot of vehicles, but is undoubtedly the most efficient with respect to fuel.

[Starman]

Hi Guv,

Have you seen this?

http://mathworld.wolfram.com/JeepProblem.html

I've been twiddling on-and-off with a program that should have given results that would have led to this formula, but seeing the amount of Greek it contains I am now sure that I wouldn't have recognised a pattern anyway.
(My vehicle kept going to base 1, dumping some fuel, returning, refuelling and then repeating the above and I never spent enough time fixing the code).

[thinktank2]

Originally posted by Guv
Noble, interesting analysis.I might have suspected that differential equations were pertinent, but it never occurred to me that momentum analysis would help solve this problem.

Might it also be necessary to consider the use of worm holes or other time warps?

[DavidHooper]

I've just caught up with this thread and it's quite interesting! That Mathworld link seems to have a (the?) solution. But, "seeing the amount of Greek it contains" I won't build my own program.

[beachbum]

Yeah David I agree... i started thinking about it before Starman posted that link then thought hell this is gonna get into the gazillions... so i guess the answer is that sometime during the journey either mankind became extinct, oil companies finally stopped hijacking alternative power sources or the guys holidays were up and he had to go back.