wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> How far can a truck go carrying it own fuel?
        
(Message started by: Feijia Zhu on Dec 22^nd, 2002, 4:49am)

Title: How far can a truck go carrying it own fuel?
Post by Feijia Zhu on Dec 22^nd, 2002, 4:49am

Please help me with this question. Urgent!

There's a truck ready to depart from a petrol station.
This truck has a gas tank, when it's full, will allow the truck to travel 100 miles. This truck can also fit a removable tank which is of the same volumn as the gas tank.
The current situation is that the gas tank is full and there are 100 removable tanks full of petrol sitting in the petrol staion.

Question, how far can this truck travel?

Assume: The truck (apart from its gas tank) can only fit one removable tank, despite whether it's full, half full or empty. Also, petrol can be transferred from the gas tank to removable tank or the other way around at any time.

The answer should be a bit more than 500 miles, but I need to know how it is done. Please help me as much as you can. Thank you very much.

//Thread title changed by Icarus

Title: Re: urgent! A really hard maths question!
Post by towr on Dec 22^nd, 2002, 7:11am

If it doesn't need to travel in a straight line, I'd say it could travel 10100 miles on the gas at the petrol station in removable tanks..
It can just travel 100 miles away on the gas tank, than put the petrol from the removable tank in the gas tank and drive back, pick up two other tanks of gas (tranfer the fuel from one to the gas tank), and repeat 50.5 times..

Title: Re: urgent! A really hard maths question!
Post by Feijia Zhu on Dec 22^nd, 2002, 4:50pm

Sorry, I didn't state the question properly.
I need to know the largest possible displacement the truck can have from the petrol station. Not the total distance this truck can travel. :)

Title: Re: urgent! A really hard maths question!
Post by towr on Dec 23^rd, 2002, 1:36am

in that case I don't see how it could get over 200 miles.
Unless it's going downhill/downmountain for an extra 300 miles.
And under the rules in the problem that wouldn't even count since a tank of gas gives 100 miles, apparantly regardless of the terrain.
Since the truck can carry a total of 2 tanks, 200 miles is the limit.
Unless it can carry more tanks than it 'fits' (fit in this interpretation being 'equip', rather than 'have place for'). But since it's not specified how much it then could carry unequipped it could be anything from 0 to 99, and three wouldn't be an obvious answer..

Oh wait..
I think I see another way..
You could carry a tank for 50 miles, drop it off, get two new tanks from the petrol station (one to fill the gas tank), repeat that a few times. That will leave 50 tanks at the drop-off point provided nobody steals them in the mean time.
Now you can repeat that for another 50 miles further up, etc..

It's like the camels and bananas riddle..

Though I think it should have been mentioned you can leave the tanks in the middle of nowhere..

Title: Re: urgent! A really hard maths question!
Post by towr on Dec 23^rd, 2002, 1:41am

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027807533;start=6

Title: Re: urgent! A really hard maths question!
Post by Kozo Morimoto on Dec 23^rd, 2002, 7:41pm

Its the same problem as the camel problem, but in the camel problem, the amount of fuel is an integer multiple of the total capacity (3000/1000)

I'm having problems here cause the total fuel is not on integer multiple (1100/200) and am not sure of how to deal with this.

I'm getting 366.55 as the total distance, but it seems like this needs a brute force approach which I'm trying to avoid...

Title: Re: urgent! A really hard maths question!
Post by Feijia Zhu on Dec 23^rd, 2002, 11:19pm

Please help me, please help me ... ...
It's a matter of life and death ... ...

Title: Re: urgent! A really hard maths question!
Post by towr on Dec 24^th, 2002, 1:25am

on 12/23/02 at 19:41:55, Kozo Morimoto wrote:

I'm having problems here cause the total fuel is not on integer multiple (1100/200) and am not sure of how to deal with this.

You don't have to use integer amounts of fuel here, I think..
You could drive f.i. half a mile, rather then 0 or 1. Fuel doesn't go bad like bananas if you don't use integer amounts ;)

Title: Re: urgent! A really hard maths question!
Post by Kozo Morimoto on Dec 24^th, 2002, 3:00am

Not integer amounts, integer multiple of max capacity.

From looking the camel/banana problem, the max cap is 1000 and after every checkpoint, you've spent 1000.

So at the first checkpoint, you have 2000 left. Then after the second checkpoint, you have 1000 left. This is so that you always start on your 'trip' with a full tank.

I was thinking of doing this with this problem.
Say checkpoint is at distance A from start.
Starting with a full load each time, so to get to A and back, you can leave 200-2A of fuel there.
If you do this five times, you'll have 1000-10A of fuel at A and 100 left at start. So when you get to A for your last trip, you are at A and have 1000-10A + 100-A = 1100-9A of fuel left. You want this to be 900 (1100-200), so A = 200/9.

But then I realized that you can't leave more than 100 at A on the first trip cause 1 spare tank can only hold 100 max. And number of spare tanks has to be integers...

OK, say you want to use up 100 fuel by each checkpoint.
So you want to transfer 1000 fuel to checkpoint A using only 100 fuel. You'll need (10-1)*2+1 trips = 19 trips so check point A is 100/19 from the start. This means that you fill up the truck but don't refill until you've got all the 10 tanks to A.

Do same to point B, which is 100/17 from A. You get to checkpoint I 113.325553 from the start and you have 200 left, which you can carry and go, so in total you can get to 313.325553 using this method.

However, this is not optimal as you drive around with near empty truck for some of the trips and I think you can utilize this.

I *believe* this is a brute force optimization problem. The complexity is higher than the camel/banana problem.

Title: Re: urgent! A really hard maths question!
Post by Feijia Zhu on Dec 24^th, 2002, 7:59pm

on 12/24/02 at 03:00:50, Kozo Morimoto wrote:

Well said Kozo. You guys can save my life by solving this maths problem. I need the full solution by the end of this year, please help me. I posted the problem here because I truly believe you guys are the best for the job.

Merry Christmas, hope I would greet again next year ...

Title: Re: urgent! A really hard maths question!
Post by Kozo Morimoto on Dec 26^th, 2002, 4:01pm

Are you sure its >500?

It may be helpful to think backwards... To get to 500 on the last gallon, you need to have 200 gallons at the 300 mile mark. (or 150gallon at 350 mile mark etc etc)

200 gallons is 1 full spare and 1 full onboard tank...

It may be helpful if YOU provided some work you've done as well 'cause you haven't given us anything!

Or start with less spare tanks: if you have 1 full truck and 1 spare tank, the best you can do is obviously 200 miles.

What happens if you have 1 full truck and 2 spares? How much can you do? 233 1/3? Can you do more?

Title: Re: urgent! A really hard maths question!
Post by Kozo Morimoto on Dec 26^th, 2002, 5:04pm

After more thought, I still think just over 313 is the best solution.

Say you want to transfer as much fuel to the 1 mile point.
You start out with 100+100, and then drop off the 100 and go back, and you use 2 gallons. You do this 8 more times, and you have 900 gallons at 1 mile point and you used up 18 gallons and you are back at start with 182 gallons. You take that to the 1 mile point and you end up with 1081 gallons at 1 mile point. So you did 9 return trips and 1 one-way trip doing the 1 mile 19 times at a cost of 19 gallons.

You can keep doing this, but at some point, you have less fuel and you reduce the number of return trips necessary to fetch the fuel. This happens at 100/19 miles when you use up the first 100 gallons. After that, you cost per mile reduces to 17 gallons instead of 19 gallons. This keeps going with 15gallons/mile, 13gallons/mile etc until you end up with 200 gallons left, whereby you just go on a one-way trip. This method nets you a total displacement of 313.3256 miles.

I'm not sure if there are any tricks you can do with filling up tanks and unfilling tanks etc etc to increase the distance.

Title: Re: urgent! A really hard maths question!
Post by towr on Dec 27^th, 2002, 6:17am

I get to 428.43 miles. That's by using 1 gastank at a time to move all the others to the next point.
Taking N to be the number of times you go back to pick up a gastank, 2N+1 is the number of times you drive the same distance between one point and the next.
so first you pick up 99 (after bringing the first tank to point 1)
on one tank of gas you can get 100/199 miles from your starting point this way. After that you've used one tank of gas, so for the next point you need to return only 98 times, and you can get 100/197 miles further..

the total distance you can drive = sum(100/(2*x+1), x, 0, 99) + 100

I'm sure it can be improved.. Seeing how you drive the same piece of road a lot at the start..
If you use 50 tanks of gas to the first checkpoint (which is thus further away) you allready gain about 16 miles I think..

Title: Re: urgent! A really hard maths question!
Post by Kozo Morimoto on Dec 28^th, 2002, 6:13pm

I misread he question initially...

If you make the checkpoints at 50 mile intervals, you get exactly 500 miles. (you'd have 200 gallons left at the 300mile mark)

So if you fiddle around with the checkpoint intervals, you should be able to get more than 500 miles.

Title: Re: urgent! A really hard maths question!
Post by Feijia Zhu on Dec 29^th, 2002, 1:31am

Thanks for the help. Here's what I got for the question, but it's not good enough, I'll be most grateful if anyone can get as far as 520 miles.

Kozo is right, if you fiddle around with the checkpoint intervals, you do get a better solution.

My answer is 510.8749 miles

There are altogether 101 tanks of petrol.

1st checkpoint: 100/199 miles from start, you can transport 100 tanks of petrol here, but 1 tankful petrol is consumed.

2nd checkpoint: 50 miles from the 1st checkpoint.
You will have 50.5 tanks of petrol left.

3rd checkpoint: 100/198 miles from the 2nd checkpoint.
That is to use the half tank of petrol to transport 50 tanks of petrol to 3rd checkpoint. So 50 tanks left.

4th checkpoint: 50 miles from the 3rd checkpoint.
You will have 25.5 tanks of petrol left.

5th checkpoint: 100/98 miles from the 4th checkpoint.
That is to use the half tank of petrol to transport 25 tanks of petrol to 5th checkpoint. So 25 tanks left.

Keep going and you'll eventually get 13 checkpoints altogether.

6th checkpoint: 100/47 miles more and 24 tanks left.
7th checkpoint: 50 miles more and 12.5 tanks left.
8th checkpoint: 100/46 miles more and 12 tanks left.
9th checkpoint: 50 miles more and 6.5 tanks left.
10th checkpoint: 100/22 miles more and 6 tanks left.
11th checkpoint: 50 miles more and 3.5 tanks left.
12th checkpoint: 50 miles more and 2 tanks left.
13th checkpoint: 200 miles more and 0 tanks left.

Add up the total and you get:
500+100/199+100/198+100/98+100/47+100/46+100/22=510.8749 miles

This is definitely NOT good enough. Please find out a way to get more than 520 miles and only then my life can be saved. I don't have much time left, 48 hours is all I've got.

Help me ...

Title: Re: urgent! A really hard maths question!
Post by Kozo Morimoto on Dec 29^th, 2002, 6:30pm

I think you can better the first leg.

Instead of 100/199, say you want the last 'trip' to the first check point to start out with 200 gallons. So excluding the last 1-way trip, you need to carry 10100-200=9900 gallons.

Since you want to reduce the number of return trips by at least one each checkpoint, you want to use up at least 100 gallons, so the total amount you want to end up at checkpoint 1 (excluding the last trip) is only 9800. Which mean you only need 196 trips (or 98 return trips) so you can set checkpoint 1 to be 100/196 miles from the start. Then you have the 200 left to get to check point 1 and end up with 200-100/196. You should try to set the trips so that you always have 200 to start the one way trip to the next checkpoint.

I don't understand why you switch between 50 mile runs and shorter runs on your answer, but your answer seems to work out higher than mine. There must be something to tell you when it is beneficial to go 50 miles or go shorter for the next checkpoint.

Hope this helps.

Title: Re: urgent! A really hard maths question!
Post by S W F on Dec 30^th, 2002, 12:25pm

It looks like you are unecessarily constraining yourself to completing each stage before moving on to the next. For example, between checkpoint 9 and 10, you progress 100/22 miles in going from 6.5 to 6 tanks. It is possible to progress 50/7 miles when going from 6.5 to 6 tanks, if you also work on checkpoint 11 before checkpoint 10 is complete. Just that one change increases your total by 2.6 miles. Changing all your non-50 mile stages this way may give you the 520 miles needed to save your life. Or maybe you need to completely rethink the problem without constraining yourself in this way.

Here are some hints for moving from your checkpoint 9 to 10 in 50/7 miles. Start with 2 full tanks and go to checkpoint 10, drop off a full tank, return to checkpoint 9. Take another full tank to checkpoint 10. Fill up the truck's tank from one of the tanks at checkpoint 10, and take a full tank to checkpoint 11, and return to checkpoint 10. At that point the truck's tank is empty. Fill the truck's tank with just enough fuel to get back to checkpoint 9, and continue. If you keep transferring fuel around between the truck's tank and the movable tanks so you are not wasting space by arriving back at checkpoint 9 with excess fuel, you will be able to have 50/7 miles between checkpoints 9 and 10.

Title: Re: urgent! A really hard maths question!
Post by James Fingas on Jan 2^nd, 2003, 1:56pm

I think you may be missing the fact that the truck is sitting at a petrol station! Don't use the tanks at all for the first 50 miles--just fill 'er up from the pump ;)

Title: Truck with Removable Gas Tanks
Post by James Fingas on Jan 3^rd, 2003, 1:40pm

I have come up with a reasonably tight upper bound on the distance that the truck can travel. It is based on the following considerations:

How can we get the truck to travel the maximum distance? By taking the smallest number of trips possible to go back and get more gas. Consider that, to start with, you have 10100 miles worth of gas at the petrol station. You can remove up to 200 miles worth at a time, so you must leave from the petrol station at least 51 times in order to carry all the gas away. There is obviously no point in leaving gas behind.

If you leave from the gas station 51 times, you must return to the gas station 50 times. Therefore, the first section of road going away from the gas station will be driven over a minimum of 101 times. How long is this first section of road? Well, long enough that we no longer have 10100 miles worth of gas to carry. After merely 100/101 miles, we have used up 100 miles worth of gas in making these 101 one-way trips. If 10000 miles worth of gas were located there, we would need to leave there only 50 times to get all the gas, and return 49 times. We would then use up 200 more miles worth in 200/99 miles, getting us down to 9800 miles worth of gas. This creates the following sum as an upper limit for the problem:

100/101 + 200/99 + 200/97 + 200/95 + ... + 200/3 + 200/1 = 588.5 miles

This, as I have said, is an upper limit. The complicating factors are that you can never drop off more than 100 miles worth of gas, you can never have more than 100 miles worth of gas after you drop some off, etc.

For example, if you travel 100/101 miles, you can only drop off 100 miles worth of gas, and you will return with an almost-full tank, meaning that you cannot pick up 200 miles worth of gas. Because you don't pick up 200 miles worth, you increase the number of trips you must take. I'm going to try to compute an upper bound that takes this into account.

That being said, here are near-optimal solutions for a few cases where you start with fewer than 100 removable tanks. Here is the format I present my answers in:

number of tanks: (theoretical upper bound) best solution so far: directions to implement best solution

The directions to implement the best solution are just a sequence of actions. I'll use these actions:

fXXX - go forward XXX miles
rXXX - go backward XXX miles
pXXX - pick up XXX miles worth of gas
dXXX - drop off XXX miles worth of gas

tanks: (bound) distance: solution
0: (100) 100: f100
1: (200) 200: p100, f200
2: (233) 233: p100, f33.3, d100, r33.3, p100, f33.3, p100, f200
3: (266) 266: p100, f66.6, d66.6, r66.6, p200, f66.6, p66.6, f200
4: (286) 286: p100, f20, d60, r20, p200, f20, p20, f66.6, d66.6, r66.6, p20, r20, p200, f20, p20, f66.6, p66.6, f200
5: (306) 300: p100, f50, d100, r50, p200, f50, p50, f50, d50, r100, p200, f50, p50, f50, p50, f200
6: (320) 319: p100, f19, d61.3, r19, p100, f19, p4.6, f33.3, d100, r52.3, p200, f19, p19, f33.3, p33.3, f66.6, d66.6, r66.6, p33.3, r33.3, p19, r19, p200, f19, p19, f33.3, p33.3, f66.6, p66.6, f200
7: (335) 326: p100, f50, d100, r50, p200, f50, p20, f10, d100, r60, f60, p60, f66.6, d66.6, r66.6, p30, r10, p30, r50, p200, f50, p50, f10, p10, f66.6, p66.6, f200
8: (346) 342: p100, f16, d80, r16, p100, f42.6, d100, r42.6, p200, f16, p16, f26.6, p20, f33.3, d100, r60, p16, r16, p200, f16, p16, f26.6, p26.6, f33.3, p33.3, f66.6, d66.6, r66.6, p33.3, r33.3, p26.6, r26,6, p16, r16, p200, f16, p16, f26.6, p26.6, f33.3, p33.3, f66.6, p66.6, f200

Some of these numbers are rounded off for simplicity's sake, so they might not work out perfectly the way they're shown here (eg. there's a little gas left somewhere, or there isn't quite have enough to do one step). You can see that in all these cases, I manage to come pretty close to the theoretical bound. I believe that it gets harder as we get more gas tanks, but this is a start anways. I have also found out how to go exactly 519 miles, but it's a hybrid of this and a binary method.

Title: Re: urgent! A really hard maths question!
Post by James Fingas on Jan 6^th, 2003, 12:08pm

After doing some serious spreadsheeting, I have come up with a method for moving 560.754 miles from the beginning. I worked backwards from the end, and ended up with 57 waypoints (including the end but not the beginning).

It takes 56.5 round trips (one going to each waypoint from the beginning) to complete the solution. Coincidentally (or is it?), this takes 10099.88 miles worth of gas.

Each round trip has five stages:

1) In the first stage, you drive out from the beginning, topping up at every waypoint you get to (this stage may have zero length).

2) In the second stage, you drive out towards the destination waypoint, without topping up at every waypoint.

3) The third stage is dropping off the gas tank at the destination waypoint.

4) In the fourth stage, you head back towards the petrol station without picking up any gas.

5) In the fifth stage, you keep going back towards the petrol station, picking up just enough gas at every waypoint to make it to the next waypoint.

The transition between stages 1 and 2 occurs at the same point as the transition between stages 4 and 5, and may involve partially topping up the tank at some waypoint.

This may be the optimal solution given the constraints on the truck, but I'm still trying to find some optimization...

Title: Re: How far can a truck go carrying it own fuel?
Post by Kugar on Nov 19^th, 2003, 4:18am

i am only 14 but here is the way i see it. i would think that you would drive out 50 miles drop off a tank then drive back another 50 to pick a tank up. seeing you have used 100 miles you would need to fill up your tank and pick up another one. Then drive out and drop it off. i will work this out and how far you will have to drive out but i like the problem thanks.

I would see it you slowly work your way out

maybe building your way up

so you would have 40 full tanks 100 miles out and 20 200 miles out and 10 300 miles out then you would start moveing out furthur basicly moveing the pertol station in a way.

you probably wont make any sence of this but i just wrote it to help

Title: Re: How far can a truck go carrying it own fuel?
Post by LZJ on Nov 25^th, 2003, 7:32am

To Kugar:

Well...I think you should take a closer look at the question...in this manner, one can only move half the oil tanks left a distance of 50 miles, and not 100 miles. Furthermore, there would be half a tank extra:
For example, if you start off with 40 tanks, if you move it 50 miles away, you will end up with 20.5 tanks worth of petrol.

Title: Re: How far can a truck go carrying it own fuel?
Post by Margit Schubert-While on Dec 18^th, 2003, 7:36am

James, in reply 18 for 4 tanks, you begin :
4: (286) 286: p100, f20, d60

Ermm, where do you put the 40 ?

Title: Re: How far can a truck go carrying it own fuel?
Post by James Fingas on Dec 18^th, 2003, 12:52pm

on 12/18/03 at 07:36:47, Margit Schubert-While wrote:

James, in reply 18 for 4 tanks, you begin :
4: (286) 286: p100, f20, d60

Ermm, where do you put the 40 ?

Hmm ... good point. I think I screwed up, although you'll notice that there are only 20 of the 40 left when you get there. The same problem applies to the 6 tank and 8 tank solutions I gave. Maybe I should check my full solution ... nope, it uses a different waypoint method (always dropping off 100 except for the last waypoint). And there's another error too. You can't pick up 200 unless you're empty (and you won't be after driving only 40 miles). Try the following instead:

4: (286) 286: p100, f20, d100, r20, p140, f20, p20, f66.6, d66.6, r66.6, p20, r20, p160, f20, p60, f66.6, p66.6, f200

A fix like this should also be applicable to the 6 and 8 tank solutions too.

Title: Re: How far can a truck go carrying it own fuel?
Post by Margit on Dec 18^th, 2003, 2:13pm

That looks as though it works James.
Tell me, how did you arrive at these waypoint distances versus # of tanks ?
Why is (apparently) 20 and 66 2/3 optimal ? (and the splits for 5,6,7,8 tanks)
Seems extremely weird to me.

Title: Re: How far can a truck go carrying it own fuel?
Post by James Fingas on Dec 22^nd, 2003, 11:21am

Margit,

I guess what I should have done all along was to give my method for finding the solution instead of giving my solution!

My first insight was that the efficiency of a solution is determined by the total distance that the truck travels (not very insightful, but it gets better). As you drive forward, you have less gas to move, so you don't have to make as many trips. Over the first stretch of road, you have 10100 miles of gas to move, and you can depart with a maximum of 200 miles at a time, so you must depart at least 51 times. However, as soon as you have gone 2 miles forward these 51 times, you have burned up 102 miles worth of gas, leaving you with 9998 miles of gas. If 2 miles were your first "waypoint", then you could leave the first waypoint only 50 times and carry all the gas.

This is the basis for all the solutions. When you look at the solution on a position-time graph, you get graphs like the ones attached. As you get farther and farther from the starting point, you take fewer trips back and forth.

The first realization I had was that the very last waypoint was 66 2/3 miles from the waypoint before it. This is easy to figure out: you want the last leg of the journey (driving off into the sunset so to speak) to start out with 200 miles of gas. The journey to the last waypoint starts twice, with 200 miles of gas each time. You want to exactly burn up those 200 miles of gas when you make the trip three times, so you need to travel 66 2/3 miles, drop off 66 2/3 miles worth of gas, travel back, pick up 200 miles of gas, then drive to the last waypoint, fill up, and head off into the sunset. This is a perfectly optimal solution (especially if you start with 3 tanks of gas).

After trying many methods, I realized that working backwards from the end was the only way I had ever gotten success. The same way I found the distance to the last waypoint could be used to find the distance to the second-last waypoint as well. We set out for the second-last waypoint 5 times, and we use up 200 miles of gas, so it should be 40 miles from the third-last waypoint. We should use up 40 miles of gas, drop off 120, then use up 40 miles more going back. This raised the problem that you cannot drop off 120 miles of gas. The most you can drop off is 100 miles worth. As shown in the diagram below, there are three times that you must fill up from the second-last waypoint. Since you can drop off at most 100 miles of gas, you can fill up with at most 33 1/3 miles of gas each time, making the second-last waypoint 33 1/3 miles from the third-last.

The third-last waypoint calculation shows the final complication. Using the same calculation as for the second-last waypoint, we would get a distance of 20 miles. However, we do not actually need to fill up fully 5 times. Noticed that when we get back from the second-last waypoint the first time, we have an extra 33 1/3 miles of gas. Therefore, we don't have to fully fill up after the first two trips, because 33 1/3 miles worth are available. So the equation we solve is 5x = 133 1/3 (the 1 tank of gas we can drop off plus the 33 1/3 available). This gives us x = 26 2/3. All the other waypoints can also be calculated in this manner.

Title: Re: How far can a truck go carrying it own fuel?
Post by Margit on Dec 22^nd, 2003, 1:12pm

Ah, thanks James, neatly explained.
I shall now get out the pencil and paper :D
Without having worked it out, shouldn't this mean we get 326 2/3 with 6 tanks ?

Title: Re: How far can a truck go carrying it own fuel?
Post by Nigel_Parsons on Jul 17^th, 2005, 1:31pm

Going for a maximised distance, shouldn't the initial waypoint be at 50 miles, with a fuel dump of 100 spare tanks?

There's a truck ready to depart from a petrol station.
This truck has a gas tank, when it's full, will allow the truck to travel 100 miles. This truck can also fit a removable tank which is of the same volumn as the gas tank.
The current situation is that the gas tank is full and there are 100 removable tanks full of petrol sitting in the petrol staion.

Question, how far can this truck travel?

The truck picks up a spare tank, takes it to dump#1 and returns to the station using up its own tankful. It then refills from the petrol station and takes the next spare out.

This adds almost fifty miles to any other answer given, as the truck starts at the fifty mile point with half a tank of its own, plus 100 spares

Nigel

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Mar 19^th, 2007, 2:52pm

There are two possible formulations: One with no more gas in the gas stattion. The other with infinite amount of gas. Let n be the number of removable tanks.

This seems to me that the 2nd formulation allows us to go nearly n.50 miles. ... left a halffull tank each 50 miles to allow way back for next tank. This creates n.50 miles long starting chain. Now starts the task how far you can go starting with such chain ... I let it open for others ;)

This puzzle was concerned on the first formulation.
It was almost solved by James ... sorry I should reread it. ... As the amount of gas is limited, you must minimize the distance traveled by car.
It's easier for me to think about it in "projections" of the car positions onto the "distance from origin axes".
If you don't use all the gas, the solution can be improved.

----------
Suppose you left some gas on position x in the best solution.
Let x is maximum such position in a best solution.
We should prove that you can move some gas to position x+d for d>0. This would lead to contradiction. (Let v be the fulltank ratio of the left gas ... On last way through cordinate x you can modify the solution ... change removeble tanks, move 100v/3 forward, refil car tank with as much of v/3 as possible and left rest of the v here. Than return back for the removable tank. At cordinate x+100v/3 fill what does not fit to car previous try.
This will left v/3 at coordinate x+100v/3 ... the contradiction.)
-----------
Therefore you should return for each gas tank whenewer it is not empty.
This defines coordinates x_k,x_k-1 ... such that you must go at least k times from x_k to x_k-1 and k-1 times back. As you can use 2 tanks for each return you must return to starting position upper part of (n+1)/2 times.
So the initial portion of way was traversed n+1 times for n even and n times for n odd.

Suppose at first you can leave gas at any place (no tank needed to left the gas there) ... we will think about the constrain later.

So the initial portion traversed (n+1) resp. n times can be chosen such a way you consumed exactly one tank of gas. This reduces problem size from n to (n-1) and we can continue (actually two consecutive portions of path obtained by this approach can be glued together as they represent the same number of traversals).

This leads to 100(1+1+1/3+1/3+1/5+1/5+1/7+1/7+...) upper bound.
Think now about the restrictions for leaving gas anywhere. ... I will continue on the next post.

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Mar 19^th, 2007, 3:18pm

BTW: the argument you use all the gas in some of the best solutions can be simplified ... just run 100v/2 forward and backward ... so you can waste the gas ... sorry :-[
... so the constraints in the next post ;)

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Mar 20^th, 2007, 7:00am

Wow it seemed to be easier at the first look ... James made good job so far. Discrete simulation using something like f,b,d,t used by him will be required ... there may be local changes ... may be it is important where the empty used tanks remain ... so it should be distinguished if you take the tank or not ... (I am not sure it realy helps to take empty tank back). The simulation should not use exact distances but rather "distance intervals".
You can add some constrains ... you neednot leave halfempty tank on the maximal distance so far; comute the ways if halpful; return with nonempty car only for n even ... such tricks can bound the computation space a bit.
The actual distances should be computed at the end solving corresponding equations.
These tricks were used by James so I am reinventing wheel :( ...

I hope the empty tank tricks are helpful especialy for big n. ...

Title: Re: How far can a truck go carrying it own fuel?
Post by tiber13 on Mar 23^rd, 2007, 3:52pm

what if you carry the max, drive the 1 mile, drop off all but 1, drive back, repeat, i am to lazy to calculate but it does sound good..... hmmm

Title: Re: How far can a truck go carrying it own fuel?
Post by hypocryt on Mar 30^th, 2007, 6:35am

Although James has advanced the debate on this topic quite far, I think his final number (I believe it was 560 or so) is too high. Indeed, with 128 tanks of gas or less (including the initial tank in your truck), the most one could go is 529.94 miles. Now why is that?

I like James's idea of checkpoints, so let's use'em. If you want to move x tanks forward to the next checkpoint, it will take at least 2x-1 trips to do so (the first tank moved only takes one trip, where as each additional tank moved takes two trips). It is obvious that an Efficient Pickup will add a full 2 tanks (200 miles) to the car's fuel supply. In other words, the car should depart from its checkpoint with only the minimum amount of fuel necessary to get back to the previous checkpoint. As long as a method uses the least number of trips possible and always uses an Efficient Pickup, it should be the best solution for that leg of the trip.

My hypothesis is that the most efficient way to move x tanks of gas is to use up an additional x tanks of gas to move those x tanks (100 * x/(2^x - 1)) miles. So working inductively (and working backwards):

On your last full tank you drive 100 miles.
Use 1 tank to move this 1 tank 100 miles.
Use 2 tanks to move these 2 tanks 66.67 miles.
Use 4 tanks to move these 4 tanks 57.14 miles.
Use 8 tanks to move these 8 tanks 53.33 miles.
Use 16 tanks to move these 16 tanks 51.61 miles.
Use 32 tanks to move these 32 tanks 50.79 miles.
Use 64 tanks to move these 64 tanks 50.39 miles.

This uses 128 tanks in total, to go about 529.94 miles. Since each pickup here is Efficient, one cannot go *more* than 529.94 miles on 128 tanks, and one should certainly go less far with fewer tanks. I know I can get the car 508.68 miles on 101 tanks (i.e. the problem), and optimization can probably push it a little further, but not much.

P.S. To give an example of how this works using a modified version of James's parlance---(1/7) represents the amount of a tank dropped off or picked up or used up in driving. If I want to move 4 tanks the maximum distance, I would: p(2), f(4/7) (i.e. 57.14 miles), d(6/7), r(4/7), p(2), f(4/7), d(6/7), r(4/7), p(2), f(4/7), d(6/7), r(4/7), p(2), f(4/7). At that point you'll have 3 cans 6/7 full, 1 can (onboard) that is 7/7 full, and one gas tank that is 3/7 full. ( 3*6 + 7 + 3 = 28 )/7 = 4 full tanks left.

Title: Re: How far can a truck go carrying it own fuel?
Post by towr on Mar 30^th, 2007, 7:49am

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

Title: Re: How far can a truck go carrying it own fuel?
Post by hypocryt on Mar 30^th, 2007, 8:08am

Although the Jeep Problem is interesting, it's distinguishable. In the Jeep Problem, the Jeep can carry only 1 tank at a time. Moreover, the Jeep has no restrictions on what it can drop off once it gets to a checkpoint.

Dividing the size of the Truck's tanks by 2 (for equivalence with the Jeep), I'd suggest that the Jeep will beat the Truck everytime---the Jeep is able to drop off more than half its fuel at any given checkpoint, whereas the Truck cannot do so (since it can only leave one container behind).

Title: Re: How far can a truck go carrying it own fuel?
Post by towr on Mar 30^th, 2007, 8:19am

Hmm, yes, I seem not to have looked closely enough at both problems to notice they are not in fact equivalent.

Title: Re: How far can a truck go carrying it own fuel?
Post by rmsgrey on Mar 30^th, 2007, 8:45am

I notice you use a hypothesis to get your figure. The fact James provided figures that contradict your conclusion suggests that at least one of the following hold:

1) His working is in error (in which case it should be possible to find his mistake)
2) Your working is in error (in which case it should be possible to find your mistake)
3) Your hypothesis is wrong (in which case there may be no mistakes to find)

I suspect you do better having an even number of tanks at each checkpoint than having a power of two at each checkpoint, but I don't have the time to work it out at the moment...

[edit]James' figure for 7 extra tanks is 2 miles higher than your "optimum" figure[/edit]

Title: Re: How far can a truck go carrying it own fuel?
Post by hypocryt on Apr 1^st, 2007, 2:15am

rmsgrey, you're totally right. My figures are definitely too low and James's total of 560 may be correct. So let me change my hypothesis from before. An Efficient Pickup is a *necessary* condition of the most efficient trip, but it's not a *sufficient* condition.

Let me think about this a while.

Title: Re: How far can a truck go carrying it own fuel?
Post by rmsgrey on Apr 1^st, 2007, 11:09am

on 04/01/07 at 02:15:01, hypocryt wrote:

It's not clear that an efficient pick-up is always optimal when you have constraints on how much fuel you can leave where. James' upper bounds reflect the optimum when you can leave arbitrary amounts of fuel at any drop-point, and his "best" figures work from that by adding a few extra trips to build up fuel storage capacity at the checkpoints...

Title: Re: How far can a truck go carrying it own fuel?
Post by Nigel_Parsons on Aug 26^th, 2007, 12:00pm

I like James' method on working backward, but I'm not too happy with the method working from the start point.
Quote:

. As you drive forward, you have less gas to move, so you don't have to make as many trips. Over the first stretch of road, you have 10100 miles of gas to move, and you can depart with a maximum of 200 miles at a time, so you must depart at least 51 times. However, as soon as you have gone 2 miles forward these 51 times, you have burned up 102 miles worth of gas, leaving you with 9998 miles of gas. If 2 miles were your first "waypoint", then you could leave the first waypoint only 50 times and carry all the gas.

In covering that first 2 miles to the waypoint, you do not burn up 102 miles worth of gas, but 202 miles worth (another full tank!) as there are also the 50 return journeys (of 2 miles each) to the depot to be considered.

Title: Re: Truck with Removable Gas Tanks
Post by Hippo on Sep 19^th, 2008, 4:16pm

on 01/03/03 at 13:40:48, James Fingas wrote:

The directions to implement the best solution are just a sequence of actions. I'll use these actions:

fXXX - go forward XXX miles
rXXX - go backward XXX miles
pXXX - pick up XXX miles worth of gas
dXXX - drop off XXX miles worth of gas

tanks: (bound) distance: solution
0: (100) 100: f100
1: (200) 200: p100, f200
2: (233) 233: p100, f33.3, d100, r33.3, p100, f33.3, p100, f200
3: (266) 266: p100, f66.6, d66.6, r66.6, p200, f66.6, p66.6, f200
4: (286) 286: p100, f20, d60, r20, p200, f20, p20, f66.6, d66.6, r66.6, p20, r20, p200, f20, p20, f66.6, p66.6, f200
5: (306) 300: p100, f50, d100, r50, p200, f50, p50, f50, d50, r100, p200, f50, p50, f50, p50, f200
6: (320) 319: p100, f19, d61.3, r19, p100, f19, p4.6, f33.3, d100, r52.3, p200, f19, p19, f33.3, p33.3, f66.6, d66.6, r66.6, p33.3, r33.3, p19, r19, p200, f19, p19, f33.3, p33.3, f66.6, p66.6, f200
7: (335) 326: p100, f50, d100, r50, p200, f50, p20, f10, d100, r60, f60, p60, f66.6, d66.6, r66.6, p30, r10, p30, r50, p200, f50, p50, f10, p10, f66.6, p66.6, f200
8: (346) 342: p100, f16, d80, r16, p100, f42.6, d100, r42.6, p200, f16, p16, f26.6, p20, f33.3, d100, r60, p16, r16, p200, f16, p16, f26.6, p26.6, f33.3, p33.3, f66.6, d66.6, r66.6, p33.3, r33.3, p26.6, r26,6, p16, r16, p200, f16, p16, f26.6, p26.6, f33.3, p33.3, f66.6, p66.6, f200

The missprints were mentioned in the discussion, I don't want to talk about them ...
At least the case 7 is not optimal: I use fractions instead of percents (or 100 miles): and adding notation
txxx - take the amount form the tank (p means take the tank, d means drop the tank)
bxxx - return to the tank from the truck (not needed here, but simplifies description ... you can tank less instead)
7: 644/195 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/thickapprox.gif3.30
1) repeat 6 times[p1, f7/195,d1,r7/195];p1,f7/195,
2) f4/15,d1,r4/15,
3) t1,p1,f4/15,t4/15,f1/3,d1,r1/3,t4/15,t(-1/3),r4/15,
4) t1,p1,f4/15,t4/15,f1/3,t1/3,f2/3,d2/3,r2/3,t1/3,r1/3,t4/15,r4/15,
5) t1,p1,f4/15,t4/15,f1/3,t1/3,f2/3,t2/3,f1,d1,t1,f1

1) moves all 7 tanks to distance 7/(13*15) using 7/15 of tank
2) creates base 0 at distance 4/(3*5) using 8/15 of tank so one tank emptied so far
3) creates base 1 at distance 1/3 from base 0
4) creates base 2 at distance 2/3 from base 1, leaving 2/3 there
5) final trip to distance 2 form base 2.
base 0 ... initialised with d1, t4/(3*5) used 5 times, but t(-1/3) after the 2nd, so 4/3 in and out.
base 1 ... initialised with d1, t1/3 used 3 times, so 1 in and out.
base 2 ... initialised with d2/3, t2/3 used once, so 2/3 in and out.

I am not sure this is the optimal solution for 7(+1) tanks.

This can be improved to
7/(9*15)+4/15+1/3+2/3+2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/thickapprox.gif3.32

Title: Re: How far can a truck go carrying it own fuel?
Post by ThudanBlunder on Sep 21^st, 2008, 4:57pm

While we are on the subject:

An explorer and his crew want to explore a desert. There are 6 drivers and 6 jeeps with GPS. Each jeep carries a tank of fuel and 6 jerry cans that can contain exactly one tank's worth. Every driver and jeep must make it back to base, but they can transfer fuel before doing so.

If a tank of fuel is worth 80 miles what is the furthest the explorer can drive into the desert and still get back to base camp safely?

Title: Re: How far can a truck go carrying it own fuel?
Post by Grimbal on Sep 22^nd, 2008, 4:34am

[hide] 686? [/hide]

Title: Re: How far can a truck go carrying it own fuel?
Post by ThudanBlunder on Sep 22^nd, 2008, 8:56am

on 09/22/08 at 04:34:39, Grimbal wrote:

[hide] 686? [/hide]

I have about 30% less than that. ???

Title: Re: How far can a truck go carrying it own fuel?
Post by Grimbal on Sep 22^nd, 2008, 12:44pm

I convert them to hybrid cars ;D

Or maybe because I assume you can drive 7/12 of 80 miles and refill all cars with 3.5 jerrycans, leaving one half-empty.

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Sep 24^th, 2008, 7:40am

Return to the original thread ...

I have planned to code search with dynamic constraints to solve the problem since I have found this thread. Dynamic maintanance of the linear constraints would not be problem, but I have needed good heuristic to eliminate nonperspective branches fast. So I have reread the thread ... especialy James Fingas notes ...

on 12/22/03 at 11:21:23, James Fingas wrote:

After trying many methods, I realized that working backwards from the end was the only way I had ever gotten success. The same way I found the distance to the last waypoint could be used to find the distance to the second-last waypoint as well. We set out for the second-last waypoint 5 times, and we use up 200 miles of gas, so it should be 40 miles from the third-last waypoint. We should use up 40 miles of gas, drop off 120, then use up 40 miles more going back. This raised the problem that you cannot drop off 120 miles of gas. The most you can drop off is 100 miles worth. As shown in the diagram below, there are three times that you must fill up from the second-last waypoint. Since you can drop off at most 100 miles of gas, you can fill up with at most 33 1/3 miles of gas each time, making the second-last waypoint 33 1/3 miles from the third-last.

The third-last waypoint calculation shows the final complication. Using the same calculation as for the second-last waypoint, we would get a distance of 20 miles. However, we do not actually need to fill up fully 5 times. Noticed that when we get back from the second-last waypoint the first time, we have an extra 33 1/3 miles of gas. Therefore, we don't have to fully fill up after the first two trips, because 33 1/3 miles worth are available. So the equation we solve is 5x = 133 1/3 (the 1 tank of gas we can drop off plus the 33 1/3 available). This gives us x = 26 2/3. All the other waypoints can also be calculated in this manner.

This seems almost solves the problem. The method: Incrementaly bound the distances with at most i returns first and than return to solution with given number of tanks works perfect. Actually there is a complication mentioned at most implicitly. When the total distance of several bases is less than 1/2 of tank distance, there is fuel excess so you must "carefully plan tanking/leaving fuel in middle bases". This is generalization of the 1/5->1/3 example above. Even when the optimal "base" distances are computed, the order of their visits is the crucial point of planning.

I have made table upto 8 returns by hands ... I am lazy to implement rational arrithmetics ...
e ... denoting fuel excess reusable in "recurence interface" it's recurrence enter at the same time ;)
[0]: 2 (p1 f1 d1 t1 f1)
[1]: 2/3 (p1 f2/3 d1 t1/3 r2/3 e0 p1 t1 f2/3 t2/3 d1 [0])
[2]: 1/3 (p1 f1/3 d1 r1/3 e1/3 p1 t1 f1/3 t1/3 d1 [1](0) t1/3 r1/3 e0 p1 t1 f1/3 t1/3 d1 [1])
[3]: 4/15 (p1 f4/15 d1 r4/15 e7/15 p1 t1 f4/15 t4/15 d1 [2](1/3) t4/15 t(-1/3) r4/15 e0 p1 t1 f4/15 t4/15 d1 [2] ...

... I must make more compact notation ... I will continue editting the post after a while ... the interesting cases are [4] and [5] ;)

[2]: x=1/3 (p1 fx d1 rx e1/3 p1 t1 fx tx d1 [1](0) tx rx e0 p1 t1 fx tx d1 [1])
[3]: x=4/15 (p1 fx d1 rx e7/15 p1 t1 fx tx d1 [2](1/3) tx t(-1/3) rx e0 p1 t1 fx tx d1 [2](0) tx rx e0 p1 t1 fx tx d1 [2])
[4]: x=1/5 (p1 fx d1 [3](7/15) rx e1/15 p1 t1 fx d1 rx e3/5 {p1 t1 fx tx d1 [3](0) tx rx e0}₂ p1 t1 fx tx d1 [3])
Now we use {}_k to denote repetition k-times.
Let us denote by Tⁱ_k the pattern {p1 t1 fx tx d1 [i](0) tx rx e0}_k p1 t1 fx tx d1 [i].
So [4]: x=1/5 (p1 fx d1 [3](7/15) rx e1/15 p1 t1 fx d1 rx e3/5 T³₂)

[5]: x=5/27 (p1 fx d1 rx e17/27 p1 t1 fx tx [4](1/15) tx t(-1/15) rx e0 p1 t1 fx tx [4](3/5) tx t(-3/5) rx e0 T⁴₂)
Note that the order in [4] was crucial ... the excess 3/5 is higher than 2x (of 5), but total excess 2/3 is less than 4x.
[6]: x=1/9 (p1 fx d1 [5](17/27) rx e11/27 p1 t1 fx d1 rx e7/9 T⁵₄)
[7]: x=1/9 (p1 fx d1 [6](11/27) rx e5/27 p1 t1 fx d1 [6](7/9) rx e5/9 p1 t1 fx d1 rx e7/9 T⁶₄)

For the next recurence we will see we should reorder the 3 initial calls (this is possible as they all had excess)
So rewrite the results in better form (at least for [6] this is the final one ... may be some commutative notation would be preferable ... [6]^4,5 noting the original one and [6]^5,4 noting the following one, some notation for yet nondetermined order ... OK let {x|y|...|z} denotes x,y,...,z in unknown order):
[6]: x=1/9 (p1 fx d1 rx e7/9 p1 t1 fx d1 [5](17/27) rx e11/27 T⁵₄)
[7]: x=1/9 ({p1 fx d1 [6](7/9) rx e5/9|p1 t1 fx d1 rx e7/9} p1 t1 fx d1 [6](11/27) rx e5/27 T⁶₄)
[8]: x=32/297 ({p1 fx d1 [7](5/9) rx e103/297|p1 t1 fx d1 [7](7/9) rx e169/297|p1 t1 fx d1 rx e233/297} p1 t1 fx tx d1 [7](5/27) tx t(-5/27) rx e0 T⁷₄)

What is common for the paths [i]: Once the number of trips to bases having excess is known to be n_i than x=1+excess of all trips to further bases/(2i+1-2n_i). The order of the trips that loose excess in this step can be choosen such that the further bases are visited first. This allows us to empty the tank on the base such that following higher excesses fit well. The condition for the k-th trip to loose the excess is that average distance of first k such trips is bigger than 1/2. We are looking for minimal n_i having compatible x_ni (xhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifn can be easily computed). The correct ordering of trips having excess so far is delayed to the time they loose the excess. Trips with excess goes first, then trips loosing excess now from furthest. The order of the rest was determined in previous steps.
Trips having excess so far ignore the newly created base, the trips loosing excess now tank to full whenever going through the new base, this allows them to leave the excess in the new base on return. Remaining trips tank to full whenever going through the new base, too.

(n₂=0 leads to 1/5 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifn₂>0, so n₂=1 leading to compatible x₂=1/3.
n₃=1 leads to compatible x₃=4/15 (n_i(>2)=0 obviously fails, ...)

In the next post, I will show some first results using [i].

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Sep 24^th, 2008, 10:22am

Let i: denotes problem starting with filled car and i additional full tanks.

0: http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif=1 (f1)
1: http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif=2 ([0])
2: y=1/3 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif=7/3http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif2.33(p1 fy d1 ry p1 fy d1 t1 [0])
3: http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif=8/3http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif2.67 ([1](0) t1 [1])
4: y=1/5 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif=43/15http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif2.87 (p1 fy d1 ry t(2y-1) t1 p1 fy ty d1 [1](0) ty ry t(1-2y) p1 fy ty t(2y) [0])
5: y=1/21 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif=64/21http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif3.05 ({p1 fy d1 [2](1/3) ry t(2y-1/3) t1|p1 fy d1 ry t(2y-1) t1} p1 fy ty d1 [2](0) ty ry t(1/3-4y) p1 fy ty t(4y) d1 [2]) ... 7y=1/3
6: y=4/21 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif=67/21http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif3.19 (p1 fy d1 ry t(2y-1) t1 p1 fy ty d1 [2](1/3) ty t(-1/3) ry t1 p1 fy ty [2](0) ty ry t(1-2y) p1 fy ty t(2y) d1 [2]) ... 7y=4/3
7: y=7/135 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif=448/135http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif3.32 ({p1 fy d1 [3](7/15) ry t(2y-7/15) t1|p1 fy d1 ry t(2y-1)} p1 fy ty d1 [3](0) ty ry t1 p1 fy ty d1 [3](0) ty ry t(7/15-4y) p1 fy ty t(4y) d1 [3]) ... 9y=7/15
8: y=22/135 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif=463/135http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif3.42 ... 9y=22/15 ... uff it's time to write a program ... but the pattern can be seen

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Sep 30^th, 2008, 1:07pm

Finaly I have generated a spreadsheet upto [50], just n_i's are important.
Here is the code:

Sub Truck()
' Truck Makro 1.10.2008, Hippo
Dim i
Cells(1, 1) = "i" 'cells(i+3,1)=i
Cells(1, 2) = "n_i" 'cells(i+3,2)=n_i number of trips with excess for [i]
Cells(1, 3) = "excess_end" 'cells(i+3,3)=total excess from stage n_i-1 of trips having no excess on n_i stage
Cells(1, 4) = "dx_i" 'cells(i+3,4)=distance of bases i and i+1
Cells(1, 5) = "x_i" 'cells(i+3,5)=coordinate of the i+1 base (measured from base 0)
Cells(1, 6) = "sum x_i" 'cells(i+3,6)=sum of coordinates of bases 0 to i+1
Cells(1, 7) = "tot end len" 'cells(i+3,7)=total length of trips ending in this stage
Cells(1, 8 ) = "tot len" 'cells(i+3,7)=total length of the journey
Cells(2, 5) = 0
Cells(2, 6) = 0
' i<=2 are precomputed special cases
Cells(3, 4) = 2
Cells(4, 4) = 2 / 3
For i = 0 To 1
Cells(i + 3, 1) = i
Cells(i + 3, 2) = 0
Cells(i + 3, 5) = Cells(i + 3, 4) + Cells(i + 2, 5)
Cells(i + 3, 6) = Cells(i + 3, 5) + Cells(i + 2, 6)
Cells(i + 3, 8 ) = (3 + 2 * Cells(i + 3, 1)) * Cells(i + 3, 5) - 2 * Cells(i + 3, 6)
Next i
i = 1
While Cells(2, 1) > Cells(i + 3, 8 )
i = i + 1
Cells(i + 3, 1) = i
Cells(i + 3, 2) = 0
Cells(i + 3, 7) = 0
While Cells(i + 3, 7) < 1 + Cells(i + 2, 2) - Cells(i + 3, 2) ' number of ending trips < total ending len
Cells(i + 3, 2) = Cells(i + 3, 2) + 1
Cells(i + 3, 3) = (1 + Cells(i + 2, 2) - Cells(i + 3, 2)) * (1 - 2 * Cells(i + 2, 5)) + 2 * (Cells(i + 2 - Cells(i + 3, 2), 6) - Cells(i + 1 - Cells(i + 2, 2), 6))
' = (1+n-n')(1 - 2x(i)) + 2 * (sum x(i - n') - sum x(i - n - 1))=
' = (1-2(x(i)-x(i-n))+...+(1-2(x(i)-x(i-n'))
Cells(i + 3, 4) = (1 + Cells(i + 3, 3)) / (2 * i + 1 - 2 * Cells(i + 3, 2))
Cells(i + 3, 5) = Cells(i + 3, 4) + Cells(i + 2, 5)
Cells(i + 3, 7) = 2 * ((1 + Cells(i + 2, 2) - Cells(i + 3, 2)) * Cells(i + 3, 5) - (Cells(i + 2 - Cells(i + 3, 2), 6) - Cells(i + 1 - Cells(i + 2, 2), 6)))
' = (1+n-n')(2x(i+1)) - 2 * (sum x(i - n') - sum x(i - n - 1))=
' = (2(x(i+1)-x(i-n))+...+(2(x(i+1)-x(i-n'))
Wend
Cells(i + 3, 6) = Cells(i + 3, 5) + Cells(i + 2, 6)
Cells(i + 3, 8 ) = (3 + 2 * Cells(i + 3, 1)) * Cells(i + 3, 5) - 2 * Cells(i + 3, 6)
'x(i)+2((i+1)*x(i)-sum x(i))=x(i)+2(x(i)-x(0))+2(x(i)-x(1))+2(x(i)-x(2))+...+2(x(i)-x(i-1))+2(x(i)-x(i))
Wend
End Sub

I hope ... there is no bug there ;)

on 01/06/03 at 12:08:13, James Fingas wrote:

Surprisingly ... I have got for 50 returns value only http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif5,51. What the 100: value be ...
BTW: I didn't check the fractions shown by excell are exact values. May be they are approximations.
Yes, they are approximations ... dx₁₀=(47+297)/297*13=344/3861http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif67/752.

[edit]I have replaced the code by the version not ending on 50 returns but on wasting all 101 tanks.[/edit]
Using only http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif100.995 tanks we can travel http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif5.611. The http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif5/1000 of tank will increase result to value rounded to the same http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif5.611.

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Oct 1^st, 2008, 1:31pm

I am planning to close this by creating a picture discribing the jurney so I allocate this post for the purpose.
It may take a day, but may be delayed much much longer ... OK here is *.ps.zip file

[edit]Replaced by .pdf[/edit]

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Oct 12^th, 2008, 3:59pm

So here it is, unfortunately at least for the choosen paths the METAPOST capacity exceeded for 100 tanks. The paths can be optimised not to tank on a trip at a base and later on return leave the fuel at the same base. For such paths the capacity will not exceed probably.

There are two paths on each page. One from top letf to bottom right (returning to left repeatedly) and the other from bottom right to top left (returning to right repeatedly). Each path is scaled to fit on the page. Page "number" correspond to the number of tanks at the start.

The x coordinate corresponds to distance from the start in both cases, the y coordinate corresponds to fuel at the car plus fuel on start in downward path and to fuel at start plus twice fuel at start in upward path. Tanking at bases can be seen by vertical lines in both cases, but tanking at the start can be seen only on upward path. I am not sure which method better describes the situation.

Oops ... file is too long ... I should make just some screen shots.

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Oct 16^th, 2008, 2:00pm

Finaly I have looked for ps -> pdf conversion (actualy inherited in gsview) ... I usually generate PDF files using PDFTeX, but I have had problems now ... this much smaller attachment contains optimalised paths ... nonnecessary tanking reduced.

Actually METAPOST main memory is not sufficient even for optimised paths for 100 additional tanks (now having only 4082 vertices improving the original 6753). So the last path I have included is for 80 additional tanks (capacity does not allow to draw both paths on one picture).

... Actually even when the order of first trips can be choosen arbitrary for given fixed number of tanks, it was choosen such that this can be extended for higher number of tanks.

Here is the code ... not very nice, but works :)
------ TeX ------
\nopagenumbers
\input epsf
\def\truck#1{
\count0=#1\vbox to 0pt{\kern 11cm\hbox to 0pt{\kern 7cm \hbox to 0cm{\hss\bf #1\hss}\hss}\vss}\epsfbox{truck.#1}\vfil\eject}
------- METAPOST --------
def truck(expr tanks)=
%tanks > 3
begingroup
save e,ii,i,et,el,ee,f,dx,xx,sx,eb,n,tl,p,fb;
xx[0]=sx[0]=eb[0]=0;
dx[1]=2MAG;dx[2]=2MAG/3;
for i=1,2:
fb[i]:=-MAG;xx[i]=xx[i-1]+dx[i];sx[i]=sx[i-1]+xx[i];eb[i]=i;n[i]=0;tl[i]=(1+2i)*xx[i]-2*sx[i];
endfor;
i:=2;e=2;show(MAG*(tanks+1));
forever:
if (MAG*(tanks+1)>=tl[i]): ii:=i+1; fi
exitif (e>=ii);i:=i+1;fb[i]:=-MAG;
n[i]=0;
forever:
n[i]:=n[i]+1;et:=1+(n[i-1]-n[i]);ee:=et*(MAG-2xx[i-1])+2(sx[i-1-n[i]-sx[i-2-n[i-1]);
dx[i]:=(MAG+ee)/(2i-1-2n[i]);xx[i]:=xx[i-1]+dx[i];el:=2(et*xx[i]-(sx[i-1-n[i]-sx[i-2-n[i-1]));
exitif (el>=MAG*et);
endfor
sx[i]=sx[i-1]+xx[i];tl[i]=(1+2i)*xx[i]-2sx[i];
forever:exitif(e+n[i]>=i);
e:=e+1;eb[e]:=i;
endfor
endfor
ee:=(tanks+1)*MAG-tl[ii-1];
dx[ii]:=ee/(2ii-1);xx[ii]:=xx[ii-1]+dx[ii];sx[ii]:=sx[ii-1]+xx[ii];tl[ii]:=(1+2ii)*xx[ii]-2sx[ii];
show('F');show(ee);show(ii);show(e);show(dx[ii]);show(xx[ii]);show(sx[ii]);show(tl[ii]);
i:=-INCR;f:=MAG*(tanks+1); %global addressing in trip!
e:=ii-1;
forever:exitif(e=0);
ee:=e; forever:exitif(eb[ee]<eb[ee+1]);ee:=ee-1;endfor
et:=ee; forever:exitif(ee>e);trip(ee);ee:=ee+1;endfor
e:=et-1;
endfor
lasttrip;
len:=i;
endgroup
enddef;

def trip(expr b)=
show('Trip[b]');
begingroup
save c,t,pb,bb,si,sf;
si:=i;sf:=f;c:=0;
pb:=t:=ii;
trace;
c:=2MAG;f:=f-c;
if (f<eps): show('fuel problems at the base'); fi
trace;
forever:
t:=t-1;
exitif (t=b);
bb[t]:=0;
if (fb[t]>-MAG): %base exists already
c:=c-(xx[pb]-xx[t]);trace;
bb[t]:=bb[t]+c-2MAG;
fb[pb]:=fb[pb]+c-2MAG;c:=2MAG;trace;
if (fb[pb]<-eps) or (fb[pb]>MAG+eps): show('problems at base'+pb);show(fb[pb]);fi
fi
endfor
c:=c-(xx[pb]-xx[t]);trace;
bb[pb]:=MAG;
fb[pb]:=MAG;c:=c-MAG;trace;
if (2dx[pb+1]>MAG):
c:=c+2dx[pb+1]-MAG;
bb[pb]:=bb[pb]+MAG-2dx[pb+1];
fb[pb]:=fb[pb]+MAG-2dx[pb+1];trace;
fi
forever:
t:=t+1;
exitif (t=ii);
if (fb[t]>-MAG):
c:=c-(xx[t]-xx[pb]);trace;
if (c<dx[pb+1]):
bb[pb]:=bb[pb]+c-dx[pb+1];
fb[pb]:=fb[pb]+c-dx[pb+1];c:=dx[pb+1];trace;
else:
if (c>dx[pb+1]):
if (fb[pb]+c-dx[pb+1]>MAG):
bb[pb]:=bb[pb]+MAG-fb[pb];
c:=c+fb[pb]-MAG;fb[pb]:=MAG;trace;
else:
bb[pb]:=bb[pb]+c-dx[pb+1];
fb[pb]:=fb[pb]+c-dx[pb+1];c:=dx[pb+1];trace;
fi
fi
fi
fi
endfor
c:=c-(xx[t]-xx[pb]);trace;
f:=f+c;c:=0;trace;
i:=si;f:=sf;c:=0;
pb:=t:=ii;trace;
c:=2MAG;f:=f-c;trace;
forever:
t:=t-1;
exitif (t=b);
if (abs(bb[t])>eps): % filling necessary at the base
fb[t]:=fb[t]-bb[t]; % original amount
if (bb[t]<0): % base -> car
c:=c-(xx[pb]-xx[t]);trace;
if (c-bb[pb] < 2MAG):
fb[pb]:=fb[pb]+bb[pb];c:=c-bb[pb];bb[pb]:=0;trace;
else:
fb[pb]:=fb[pb]+c-2MAG;bb[pb]:=bb[pb]-c+2MAG;c:=2MAG;trace;
fi
if (fb[pb]<-eps) or (fb[pb]>MAG+eps): show('problems at base'+pb);show(fb[pb]);fi
fi
fi
endfor
c:=c-(xx[pb]-xx[t]);trace;
fb[pb]:=MAG;c:=c-MAG;trace;
if (2dx[pb+1]>MAG):
c:=c+2dx[pb+1]-MAG;
fb[pb]:=fb[pb]+MAG-2dx[pb+1];trace;
fi
forever:
t:=t+1;
exitif (t=ii);
if (abs(bb[t])>eps): % remaining change
c:=c-(xx[t]-xx[pb]);trace;
fb[pb]:=fb[pb]+bb[pb];c:=c-bb[pb];bb[pb]:=0;trace;
fi
endfor
c:=c-(xx[t]-xx[pb]);trace;
f:=f+c;c:=0;trace;
endgroup
enddef;

def lasttrip=
show('L');
begingroup
save t,pb;
c:=f;f:=0;
pb=t=ii;
trace;
forever:
t:=t-1;
c:=c-(xx[pb]-xx[t]);trace;
exitif (t=0);
c:=c+fb[pb];trace;
endfor
if (abs(c)>eps): show('final fuel problems'+abs(c)); fi
endgroup
enddef;

def trace=
pb:=t;x[INC]t:=xx[pb];y[i]t:=f+c;x[i]b:=xx[pb];y[i]b:=2f+c;
if (abs(c-MAG)>MAG+eps):show('fuel problems'+c); fi
enddef;

vardef INC=
i:=i+INCR;i
enddef;

INCR:=1/256*1/256;MAG:=100;

beginfig(4)
truck(4);
pickup pencircle scaled 0.4pt;
transform t;
z[0]t transformed t = (0,22cm);
z[len]t transformed t = (14cm,0);
(x[0]t,y[len]t) transformed t = (0,0);
i:=0;draw (z[i]b forever: --z[INC]b exitif(i>=len); endfor) transformed t;
transform t;
z[0]b transformed t = (14cm,0);
z[len]b transformed t = (0,22cm);
(x[len]b,y[0]b) transformed t = (0,0);
i:=0;draw (z[i]b forever: --z[INC]b exitif(i>=len); endfor) transformed t;
endfig;
% same for other number of tanks, but changing MAG as the sx exceeds 4098 ... smaller pen for higher tanks
bye.

Title: Re: How far can a truck go carrying it own fuel?
Post by Vashist on Nov 20^th, 2008, 8:07pm

According to Physics, Gases occupy 10% more place than the same volume of water, So it there is a full tank of Petrol, it will become 10% more Gas. And the Lorry, would travel more than 500 miles.

Title: Re: How far can a truck go carrying it own fuel?
Post by towr on Nov 20^th, 2008, 11:52pm

on 11/20/08 at 20:07:27, Vashist wrote:

According to Physics, Gases occupy 10% more place than the same volume of water, So it there is a full tank of Petrol, it will become 10% more Gas.

That sentence makes no sense. The volume is the amount of space it occupies. So you're saying gases occupy 10% more space than they occupy; which implies they either don't take any space, or all space.

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Apr 9^th, 2009, 2:29pm

The original problem is Dewdney's jeep problem, except that the jeep has initial fuel in its tank, but that can be solved by using 101 drums. The extra drum is not needed for depots, because about half of the drums does not leave the starting point in the solution of Dewdney's jeep problem in the link below. Actually, it is solved with drums of five tankloads instead of one, but the solution with drums of another amount of fuel is similar. Furthermore, you cannot get further if you have smaller drums and you can carry one (or five) tankloads by way of drums.

The problem with n empty drums and infinitely much fuel is Maddex' jeep problem, and the solution for that problem is that you can get exactly as far as a jeep that can carry n full drums. You have to set up full drums in the desert instead of riding out from the fuel station with all of them.

A solution to Dewdney's jeep problem (1995)
by B Jackson, J Mitchem, E Schmeichel
in: Graph Theory, Combinatorics, and Applications: Proc. 7th Quadrenn. Int. Conf. Theory Appl. Graphs, Kalamazoo

PS: I believe the answer is 560.755540. At least, that is what the following program outputs. 58 of the 100 drums are moved.

Code:

#include <stdio.h>

double jeep[100], jeepload[100][100], jeepdist[100], jeepdist2[100], jeepdrum[100];
double load;
double fuel = 101;
double drum = 1;
double distunit = 100;

main ()
{
double distance = distunit * (drum + 1);
int count = 1;
double remain = fuel;
fuel -= drum + 1;
jeepdist[0] = -distunit;
jeepdist[1] = -distance;
while (fuel > 0.0000000001) {
load = drum;
jeep[count] = 1;
count++;
int i;
for (i=1; i<count; i++) {
if (load / (2*i-1) < jeep[i] / 2) break;
load += jeep[i];
jeep[i] = 0;
}
load /= 2*i-1;
distance += load * distunit;
jeepdist[count] = -distance;
fuel -= load * (2*count-1);
for (; i<count; i++) {
jeep[i] -= 2 * load;
}
}
distance += distunit * fuel / (2*count-1);
fuel = 0;

int i, j, k;
jeepdist[count] = 0;
jeepdrum[count] = remain - count*drum;
for (i=count-1; i>=1; i--) {
jeepdist[i] += distance;
jeepdist2[i] = jeepdist[i];
jeepdrum[i] = drum;
double tank = 0.5 - (jeepdist[i] - jeepdist[i+1]) / distunit;
if (tank < -0.0000000001) {
tank = 0;
jeepdist2[i] = jeepdist[i+1] + 0.5 * distunit;
}
for (j=i+1; j<count; j++) {
tank -= (jeepdist[j] - jeepdist[j+1]) / distunit;
if (tank < 0) {
jeepload[i][j] = -tank;
jeepdrum[j] += 2*tank;
tank = 0;
}
}
jeepload[i][j] = 1-2*tank;
jeepdrum[j] -= 1-2*tank;
}
jeepload[i][i] = 1;
jeepdist[i] += distance;
jeepdist2[i] = jeepdist[i];
for (j=i+1; j<=count; j++) {
jeepload[i][j] = jeepdrum[j];
}

printf ("Leave %d drums closed. ", count);
printf ("Open the other drums on position 0.\n");
jeepdrum[count] = remain - count*drum;
printf ("So we start with %f tankloads of opened drums on position 0.\n\n", jeepdrum[count]);
for (i=count-1; i>=0; i--) {
jeepdrum[i] = drum;
for (j=i+1; j<count; j++) {
if (jeepload[i][j] > 0) break;
}
printf ("Pick one drum on position %d.\n", 0.0);
double tank = 0;
for (k=count; k>=j; k--) {
tank += jeepload[i][k];
if (tank > 1.0000000001) {
printf (" %f tankloads of tank fuel remains.\n", tank-jeepload[i][k]);
printf ("Dump drum and ride back to %f\n", jeepdist2[k]);
printf ("Take drum with %f tankloads and ride to %f\n", jeepload[i][k], jeepdist[k]);
tank -= 2*(jeepdist[k]-jeepdist2[k]) / distunit;
}
printf (" Take %f tankloads from position %f.\n", jeepload[i][k], jeepdist[k]);
printf ("Increase tank fuel from %f to %f tankloads.\n", tank-jeepload[i][k], tank);
jeepdrum[k] -= jeepload[i][k];
printf ("%f tankloads remain on position %f.\n", jeepdrum[k], jeepdist[k]);
if (k == j) {
printf ("Ride to position %f and dump drum.\n", jeepdist2[i]);
tank -= (jeepdist2[i]-jeepdist[k]) / distunit;
} else {
printf ("Ride to position %f.\n", jeepdist[k-1]);
tank -= (jeepdist[k-1]-jeepdist[k]) / distunit;
}
}
if (i == 0) {
printf (" Take %f tankloads from position %f.\n", jeepload[i][i], jeepdist[i]);
printf ("Increase tank fuel from %f to %f tankloads.\n", tank, tank+jeepload[i][i]);
jeepdrum[i] -= jeepload[i][i];
printf ("%f tankloads remain on position %f.\n", jeepdrum[i], jeepdist[k]);
printf ("Ride to %f.\n", distance);
break;
}
for (k=j; k<count; k++) {
printf (" Ride to position %f.\n", jeepdist[k]);
if (k == j) {
tank -= (jeepdist2[i]-jeepdist[k]) / distunit;
} else {
tank -= (jeepdist[k-1]-jeepdist[k]) / distunit;
}
printf ("Take %f tankloads from position %f.\n", jeepload[i][k], jeepdist[k]);
printf ("Increase tank fuel from %f to %f tankloads.\n", tank, tank+jeepload[i][k]);
tank += jeepload[i][k];
jeepdrum[k] -= jeepload[i][k];
printf ("%f tankloads remain on position %f.\n", jeepdrum[k], jeepdist[k]);
}
printf (" Ride to position %f.\n\n", jeepdist[k]);
}
}

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Apr 10^th, 2009, 7:44am

on 04/09/09 at 14:29:51, brac37 wrote:

I have find this link, page 23 (http://page.mi.fu-berlin.de/rote/Papers/pdf/Optimal+logistics+for+expeditions+-+the+jeep+problem+with+complete+refilling.pdf), I should compare it with my results (at least the path is different).
There seems to be nonoptimality in the link. In my solution I went distance from start to base 1 23 times to base 2 21 times to base 3 19 times, but in the link they went to base 2 23 times, ... they got 5417/1344http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif4.030506. I should check my resulting distance.... by the metapost code given above http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif4.6435532. May be I have to write some article about it (or if there is a volunteer, I can share ... to be coautor would be sufficient).

I should install ghostview to convert the .ps file for 22 tanks to .pdf ...

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Apr 10^th, 2009, 10:39am

on 04/10/09 at 07:44:58, Hippo wrote:

There is non-optimality in that link, because it solves the camel-banana-problem. With the camel-banana-problem, you must empty each opened can immediately entirely in the jeep's fuel tank. This restriction has a price. 515.5598958 miles is the optimum instead of 560.755540.

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Apr 10^th, 2009, 12:00pm

on 04/10/09 at 10:39:20, brac37 wrote:

Oh, I see now, they have the 4th constrain ... they can fill the truck only when it is out of gas.

on 04/09/09 at 14:29:51, brac37 wrote:

PS: I believe the answer is 560.755540. At least, that is what the following program outputs. 58 of the 100 drums are moved.

on 01/06/03 at 12:08:13, James Fingas wrote:

After doing some serious spreadsheeting, I have come up with a method for moving 560.754 miles from the beginning.

So you have beaten James bound.

I have got 561.1 see this post (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1040561389;start=25#47) and immediately preceeding ones.

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Apr 10^th, 2009, 2:36pm

The solution in the link is optimal, so I must have misremembered the solution. It is a while ago that I studied the problem. I will try to remember the right solution another time.

Now I remember that not moving drums any more after opening them has a prize. It that is true, then that is a reason that my solution is not optimal. My solution might be the optimal solution for not moving drums any more after opening them.

It's long ago. I might be wrong about that this problem is Dewdney's jeep problem: I do not remember any more if transferring tank fuel into drums is allowed. That can also be the reason for non-optimality, although not remembering it can also be a sign for that is does not matter.

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Apr 11^th, 2009, 12:59am

on 04/10/09 at 14:36:13, brac37 wrote:

Now I remember that not moving drums any more after opening them has a prize. It that is true, then that is a reason that my solution is not optimal. My solution might be the optimal solution for not moving drums any more after opening them.

It seems to me this constrain is not important ... I always move full tanks
(but I can tank any exact portion from a tank in "an arbitrary" situation, I hope as well as you).

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Apr 16^th, 2009, 3:59pm

On easter holidays, I have though about my algorithm. I convinced myself it is optimal when you do not allow returning tank fuel to drums, and that Hippo returns tank fuel to drums in his algorithm.

But it does not seem that Hippo returns tank fuel to drums in his algorithm. But I still think doing so in the right way will lead to a better algorithm.

So I have compared my table and Hippo's table. They start to get different at the exact position that the denominator does not fit any more in three digits. So my guess is that James, Hippo and I all have the same algorithm. Prove me I am wrong!

This is my table after getting a library for exact rational computation here (http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=9735&lngWId=3):

Fuel = 101+0/1
2+0/1 + 0+2/3 = 2+2/3
2+2/3 + 0+1/3 = 3+0/1
3+0/1 + 0+4/15 = 3+4/15
3+4/15 + 0+1/5 = 3+7/15
3+7/15 + 0+16/105 = 3+13/21
3+13/21 + 0+1/7 = 3+16/21
3+16/21 + 0+106/945 = 3+118/135
3+118/135 + 0+32/297 = 3+54/55
3+54/55 + 0+1/11 = 4+4/55
4+4/55 + 0+1262/15015 = 4+214/1365
4+214/1365 + 0+1/13 = 4+319/1365
4+319/1365 + 0+206/2925 = 4+479/1575
4+479/1575 + 0+1/15 = 4+584/1575
4+584/1575 + 0+4756/80325 = 4+6908/16065
4+6908/16065 + 0+195028/3357585 = 4+19280/39501
4+19280/39501 + 0+1/19 = 4+21359/39501
4+21359/39501 + 0+210148/4147605 = 4+129097/218295
4+129097/218295 + 0+1/21 = 4+139492/218295
4+139492/218295 + 0+587738/13054041 = 4+2126038/3108105
4+2126038/3108105 + 0+1/23 = 4+2261173/3108105
4+2261173/3108105 + 0+629318/15540525 = 4+39917/51975
4+39917/51975 + 0+11146/280665 = 4+161927/200475
4+161927/200475 + 0+1/27 = 4+169352/200475
4+169352/200475 + 0+295282/8139285 = 4+1327958/1507275
4+1327958/1507275 + 0+1/29 = 4+1379933/1507275
4+1379933/1507275 + 0+976524/29419775 = 4+25985891/27390825
4+25985891/27390825 + 0+1/31 = 4+26869466/27390825
4+26869466/27390825 + 0+47985422/1561277025 = 5+589289/50363775
5+589289/50363775 + 0+53286872/1762732125 = 5+2737481/65286375
5+2737481/65286375 + 0+1/35 = 5+4602806/65286375
5+4602806/65286375 + 0+1836365026/65221088625 = 5+1286913644/13044217725
5+1286913644/13044217725 + 0+1/37 = 5+1639460069/13044217725
5+1639460069/13044217725 + 0+1913109826/72674927325 = 5+2090019229/13749310575
5+2090019229/13749310575 + 0+1/39 = 5+2442565654/13749310575
5+2442565654/13749310575 + 0+29115404776/1178690897475 = 5+874536288086/4321866624075
5+874536288086/4321866624075 + 0+1/41 = 5+979947669161/4321866624075
5+979947669161/4321866624075 + 0+30269193076/1299582271575 = 5+1133323033751/4532689386225
5+1133323033751/4532689386225 + 0+4695599713352/203971022380125 = 5+1295235726329/4743512148375
5+1295235726329/4743512148375 + 0+1/45 = 5+1400647107404/4743512148375
5+1400647107404/4743512148375 + 0+4861533485902/222945070973625 = 5+14138389506778/44589014194725
5+14138389506778/44589014194725 + 0+1/47 = 5+15087091936453/44589014194725
5+15087091936453/44589014194725 + 0+5017698494902/242762410615725 = 5+3337986346129/9297283810815
5+3337986346129/9297283810815 + 0+1/49 = 5+3527726832064/9297283810815
5+3527726832064/9297283810815 + 0+1352409418767292/68753413780976925 = 5+559998966160828/1403130893489325
5+559998966160828/1403130893489325 + 0+1449177066594142/74365937354934225 = 5+610374946531726/1458155634410475
5+610374946531726/1458155634410475 + 0+1/53 = 5+637887316992301/1458155634410475
5+637887316992301/1458155634410475 + 0+46219536558573544/2486155356669859875 = 5+21392781359065033/46908591635280375
5+21392781359065033/46908591635280375 + 0+1/55 = 5+22245664843342858/46908591635280375
5+22245664843342858/46908591635280375 + 0+47540130340681144/2673789723210981375 = 5+4783792823313542/9722871720767205
5+4783792823313542/9722871720767205 + 0+1/57 = 5+4954369520169107/9722871720767205
5+4954369520169107/9722871720767205 + 0+2871921257729234/168720421036842675 = 5+1394609113417621/2648427661704825
5+1394609113417621/2648427661704825 + 0+37046418912178022/2192519757082780125 = 5+141374317705768811/260129462704736625
5+141374317705768811/260129462704736625 + 0+1/61 = 5+145638735127157936/260129462704736625
5+145638735127157936/260129462704736625 + 0+37951519752636122/2341165164342629625 = 5+22109838293394386/38379756792502125
5+22109838293394386/38379756792502125 + 0+1/63 = 5+22719040782164261/38379756792502125
5+22719040782164261/38379756792502125 + 0+1439091161045885576/92303315085967610625 = 5+6230931582461214809/10255923898440845625
5+6230931582461214809/10255923898440845625 + 0+1/65 = 5+6388715027052612434/10255923898440845625
5+6388715027052612434/10255923898440845625 - 0+449052542624931547357037189551336682/29208840246683310357102124103841028125 = 5+17745988533599676346381190694635102128/29208840246683310357102124103841028125

With 100 digits accuracy (moved the point two spots to the right): 560.7555397055340087981800092587688093618090864090505387490128868221531903614211532617991533191874618

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Apr 16^th, 2009, 11:12pm

I have noted that table contains fractions that are approximations to the correct values ... it's how excell writes them. But the difference is too big to be rounding problems. Did you optimise the order the trips?

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Apr 17^th, 2009, 4:42am

on 04/16/09 at 23:12:31, Hippo wrote:

No, but I do not return tank fuel to the drums either. I see how out of order transportation of drums can be useful, but only if you allow returning tank fuel to the drums. See my previous post. If you do not refill drums with tank fuel, then your algorithm is a counterexample to what I believe. But your pictures show that you do refill drums.

Title: Re: Truck with Removable Gas Tanks
Post by Hippo on Apr 17^th, 2009, 6:18am

I had no time to edit the previous post after thinking about it ...

on 09/19/08 at 16:16:44, Hippo wrote:

3) t1,p1,f4/15,t4/15,f1/3,d1,r1/3,t4/15,t(-1/3),r4/15

base 0 ... initialised with d1, t4/(3*5) used 5 times, but t(-1/3) after the 2nd, so 4/3 in and out.

Yes, I am taking fuel from the truck (I am not sure James does this as well).
And this is why optimisation of order of trips is important in my solution.

Oops, not realy, see the PDF in the first link on this page, this t(-1/3) was only for easines of describtion.
I can as well tank less during the trip ...
3) t1,p1,f4/15,t3/15,f1/3,d1,r1/3,r4/15

Oops, Oops ... see "pages" 9,10 ... there it is required.

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Apr 17^th, 2009, 7:39am

Cool that that out of order transportation leads to a better algorithm. But refilling makes proving optimality much harder. One way to prove optimality is to prove that some program finds the optimal algorithm and to run that program. 8)

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Apr 21^st, 2009, 3:21pm

It seems hard to find an optimal algorithm. I got as far as

5 110210046720786239934976/168036215348370240246375 = 5.655871

thus far by reusing drum depots. The second time a drum depot is used, the jeep can "vomit" its tankfuel into the already used drum. If the first drum is not empty yet, then the jeep can use all its fuel for riding if the "vomit" trip is chosen on the right moment.

I have tested the algorithm with a simulation. Hippo seems to use a different approach, and I think that combining both approaches might lead to an even better algorithm.

Here are the drum depot positions in arbitrary order.

4.655871 3.655871 2.989204 2.655871 2.389204
1.583144 2.189204 2.036823 1.378967 1.893966
1.226856 1.781797 1.102632 1.102632 1.674053
0.940084 0.940084 1.583144 0.801645 0.801645
1.378967 0.681888 0.681888 0.681888 1.226856
0.541525 0.541525 0.541525 0.541525 1.102632
0.390658 0.390658 0.390658 0.390658 0.940084
0.261390 0.261390 0.261390 0.261390 0.801645
0.148316 0.148316 0.148316 0.067856 0.681888
0.034310 0.541525 0.390658 0.261390 0.148316
0.067856 0.034310 0.002052

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Apr 22^nd, 2009, 6:24am

An improvement of the above is the following. Assume the jeep has dumped his full drum and is about to vomit its tankload. Before doing so, ride back a little with the empty drum. The dumped drum will be emptied during the last outward trip, so only small amounts of fuel can be taken from the dumped drum. But it gives some room to ride back with the empty drum.

After riding back a little, dump the empty drum and vomit. It seems somewhat illogical to vomit on a smaller position than you reach in a trip. But it does not cost anything and even saves fuel in case of multiple vomit positions: the drum to vomit into will be closer. The third time a drum is used to vomit into, the drum will be even more closer, etc. In the above algorithm, the multiplicities of the vomits are: 5 x 1, 3 x 2, 2 x 3, 3 x 4.

I currently do not have time any more to make further computations, so here are my files.
http://host-a.net/brac37/jeep.zip/link.png (http://host-a.net/brac37/jeep.zip)

EDIT: Wait, it can be done better. The above algorithm does not only seem illogical, but is illogical: vomiting must be done on the same position as dumping. The drum is not carried backward on the vomit trip, but on the last trip that its fuel is used. This way, the fuel of dumped drums can be saved for a while, giving more room to carry back empty drums.

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Apr 22^nd, 2009, 2:17pm

I didn't checked the results ... can you find minimal number of drums for which your algorithm gives better results than mine.

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Apr 23^rd, 2009, 12:55pm

on 04/22/09 at 14:17:24, Hippo wrote:

I didn't checked the results ... can you find minimal number of drums for which your algorithm gives better results than mine.

My algorithm starts deviating from the Dewdney jeep algorithm at 24 tankloads (23 drums). But your algorithm is better at that point. So you have a better start, but I overtake you later. The conclusion is that our ideas should be combined. But haven't I said that already? So there is a lot of room for improvement, see also my previous post.

The precise deviation point is 23.810. It does not take very long before I overtake you:

23 116/271:
Me 4.305052 :(
You 4.308641 :)

25 210/937:
Me 4.372006 :(
You 4.375163 :)

26 93/100
Me 4.431824 :(
You 4.433987 :)

28 577/804
Me 4.491351 :P
You 4.491654 :o

30 5/11
Me 4.545729 :)
You 4.544286 :(

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Apr 24^th, 2009, 10:24pm

on 04/23/09 at 12:55:48, brac37 wrote:

Can you write describtion of you jurney with 30 drums (preferable format is with distances to the target rather from the start).
Thanks

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Apr 25^th, 2009, 8:25am

The below solution is with 29 drums and a full tank. So its target is lower than that of 30 5/11 tankloads. The drum positions are:

3.531780 2.531780 1.865113 1.531780 1.265113
0.549962 1.065113 0.331664 0.912732 0.167265
0.769875 0.657706 0.549962 0.331664 0.167265
0.037116

The journey is in the same format as you use, so no distances form start or target.

p1 f0.037116 d1 r0.037116
p1 f0.167265 d1 r0.167265
p1 t0.240428 f0.331664 d1 r0.331664 t0.331664
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.012845 f0.382696 d1 r0.382696 t0.012845 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.120589 f0.490440 d1 r0.490440 t0.120589 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.102610 f0.438211 d1 r0.438211 t0.102610 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.081068 f0.362771 d1 r0.362771 t0.081068 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 d1 t(-0.739702) r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.015152 f0.407407 d1 r0.407407 t0.015152 r0.107744 t0.218297 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 d1 t(-0.671202) r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 d1 t(-0.563405) r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.107744 f0.112169 t0.107407 f0.495238 d1 r0.495238 t0.107407 r0.112169 t0.107744 r0.107744 t0.218297 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.107744 f0.112169 t0.112169 f0.142857 t0.142857 f0.152381 t0.119048 f0.466667 d1 r0.466667 t0.119048 r0.152381 t0.142857 r0.142857 t0.112169 r0.112169 t0.107744 r0.107744 t0.218297 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.107744 f0.112169 t0.112169 f0.142857 t0.142857 f0.152381 t0.152381 f0.200000 t0.200000 f0.266667 t0.100000 f0.333333 d1 r0.333333 t0.100000 r0.266667 t0.200000 r0.200000 t0.152381 r0.152381 t0.142857 r0.142857 t0.112169 r0.112169 t0.107744 r0.107744 t0.218297 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.107744 f0.112169 t0.112169 f0.142857 t0.142857 f0.152381 t0.152381 f0.200000 t0.200000 f0.266667 t0.266667 f0.333333 t0.333333 f0.666667 d1 t0.333333 r0.666667 t0.333333 r0.333333 t0.266667 r0.266667 t0.200000 r0.200000 t0.152381 r0.152381 t0.142857 r0.142857 t0.112169 r0.112169 t0.107744 r0.107744 t0.218297 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.107744 f0.112169 t0.112169 f0.142857 t0.142857 f0.152381 t0.152381 f0.200000 t0.200000 f0.266667 t0.266667 f0.333333 t0.333333 f0.666667 t0.666667 f1.000000 d1 t1.000000 f1.000000
4 45220886/85036875 = 4.531780

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Apr 25^th, 2009, 11:50pm

Seems, I get the diference ... you better use truck for transporting fuel inside it's tank. Good job.
I will think later about the problem again ...

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Feb 1^st, 2010, 6:25am

A solution to Dewdneys jeep problem that is easier to get is the following article in the Mathematical Gazette.

http://www.jstor.org/stable/3618853

But it is harder to find since it is not indexed in the MathSciNet database.

Title: Re: How far can a truck go carrying it own fuel?
Post by Hippo on Feb 4^th, 2010, 1:49am

I still have this problem on to think about later list :) :(

Title: Re: How far can a truck go carrying it own fuel?
Post by brac37 on Apr 19^th, 2010, 8:03am

Jeep problems are interesting on its own, especially when they are unsolved, like this one. But does anyone know real life applications of such problems?

I think about (ant)arctic expeditions, cage diving and spatial traveling. But there might be applications that did not cross my mind.