A walk into the desert and back - have some hard-won answers but can't see the pattern

Question

Mission: To find a minimum-length walk from "base" to a point g distance units away and back for 1 person alone, given:

1. An unlimited supply of rations provided at base, to be consumed continuously while walking.
2. The ability to walk up to 1 distance unit per unit of rations consumed.
3. The ability to carry no more than 2 total units of rations at a time, including those about to be consumed.
4. The ability to walk away from and return to sealed rations only, i.e. rations in full 1-unit packages kept sealed since leaving base. Of course each such package has to be unsealed for any of its contents to be consumed.

Let us assume we have a rule that no more than 1 unit of rations is available (ready to be consumed without an unsealing) at any given time and that an increase in available rations always implies an unsealing. (Such a rule is not really required, but explaining why requires some wordy lemmas and would distract from what I am trying to ask.)

Using a long-running simplex algorithm computer program, I think I have found minimum walks for g between 1 and 195/64 (= 3.046875) distance units, and I would like to do the same for even greater values of g.

But first, I would really like to find a way to cut down on the computation time, if possible, by eliminating a bifurcation of my objective function.

Total walk length, to be minimized, equals twice the amount of walking toward g (because we end where we begin); and the amount of walking toward g has to include the sum of distances from base of all unsealings (because all sealed packages begin at base and no more than 1 can move at a time), plus the distance to g from the nearest unsealing (because the person has to get to g even if no unsealing occurs there).

It is that nearest unsealing that causes the bifurcation. My constraints have to distinguish unsealings before reaching g from unsealings after reaching g because the contents of the packages unsealed after reaching g cannot be used to move any packages unsealed before reaching g.

So I have been having to run the dual simplex algorithm twice for each value of g, once with an objective that assumes the closest unsealing to g happens no later than the arrival at g, and once with an objective that assumes the closest unsealing to g happens no earlier than the arrival at g. Then the result with the smaller minimum walk is my answer.

I find it interesting that none of the results I have gotten so far put the 2 closest unsealings to g equal to each other.

Question 1: Is it impossible to minimize walking with the 2 closest unsealings to g > 1 equal?

Question 2: Is there a clue here as to how to eliminate the bifurcation?

Answer 1

We shall assume the artificial rule already mentioned, so the amount of walking between consecutive unsealings will always be at least zero and at most 1 unit, and we shall follow the convention of using the same names for locations as for their respective distances from base, and answer Questions 1 and 2 assuming g > 1.

Let g′ = g − ½, and let I be any valid itinerary that fulfills the mission, i.e. in which the person reaches g and then returns to base. Since g′ > ½, there must be at least one location between base and g′ where in I the person changes direction, unseals a package, or walks away from stationary rations. Let g″ be the closest such location to g′.

Lemma 1: For any valid itinerary I that fulfills the round-trip-to-g mission, there exists an itinerary I′ fulfilling the same mission in which the person takes the same actions between base and g″ and does only 2(g − g″) units of walking between g″ and g.

Proof of Lemma 1:

Let m_b be the moment in I of the person’s last departure from g″ before reaching g and m_a the moment of their next arrival at g″, after reaching g. Between m_b and m_a, the person must walk from g″ to g, a distance of g − g″ units, and then from g back to g″, a further g − g″ units, and may change direction multiple times and may unseal multiple packages. Since the person has to cover more than 1 unit of distance in that interval, at least one unsealing must occur between m_b and m_a. Let m_y be the moment of the first such unsealing.

Altering I by replacing all walking beyond g″ with just consuming the same rations without walking anywhere would give us a valid itinerary for a round trip to g″ with some wasting of rations at g″. But the unsealing at m_y is unnecessary in such an itinerary because the amount of walking between m_x, the moment of the latest unsealing before m_y (the beginning of the mission if none), and m_z, the moment of the first unsealing after m_y (the end of the mission if none), which is no more than 2 units in I, invariably gets reduced to 1 unit or less by the alteration: If m_y is the only unsealing between m_b and m_a, then the whole interval from m_b to m_a, in which walking gets reduced from greater than 1 unit to zero, is contained within the interval from m_x to m_z, and otherwise m_z occurs before m_a so that walking between m_y and m_z gets reduced to zero, leaving only the walking between m_x and m_y, 1 unit or less, between m_x and m_z.

Since all rations begin at base and only 1 sealed package can be carried at a time, the person must have, at some point prior to m_y, departed from g″ carrying a sealed package toward g′ when there were no rations at or beyond g′. Let m_i be the latest such time before m_y, and let m_j be the moment of the person’s next arrival back at g″ after m_i.

Altering I by eliminating both all walking beyond g″ and the unnecessary unsealing at m_y gives us a valid itinerary for a round trip to g″ in which there is at least 1 sealed package at g″ at all times after m_i. Call this altered itinerary J. Assuring that the sealed package being carried at m_i is never unsealed or even carried back toward base after m_i in J is not a real restriction. Since all sealed packages are the same, the person can always, whenever an unsealing or removal is required after m_i, choose a different package to unseal or carry away and leave that particular package undisturbed.

If m_i = m_b, then in I the person has to be carrying at least 2(g − g″) units more rations at m_i = m_b than at m_j = m_a, including a sealed package, in order to walk to g and return to g″. Otherwise, between m_i and m_j in I, the person takes a sealed package to g′ or beyond and returns to g″, so in this case too the person has to be carrying at least 2(g − g″) more rations at m_i than at m_j, 1 sealed package plus 2(g′ − g″).

If the difference in rations being carried between m_i and m_j is greater than 2(g − g″), the excess can be discarded or consumed without walking at the corresponding point in I′. Then in I′ the person can simply walk directly to g and back, consuming exactly 2(g − g″) units of rations, and the part of I′ beginning at the point corresponding to m_j will suffice to return the person to base. The sealed package being carried at m_i will of course need to be unsealed at the exact moment when the other rations inevitably get used up. If the unsealing will happen after the person reaches g, the person can even leave the package at its unsealing location when on the way to g. Q.E.D.

Answer to Question 1: At least 1 unsealing must occur between m_b and m_a, when the person is beyond g″, so if the 2 closest unsealing positions to g are equal in some valid itinerary I, they must both occur beyond g″, and this requires more than 2(g − g″) units of walking beyond g″ in I. But by Lemma 1 there exists an itinerary J with less walking, so yes, it is impossible to minimize walking with the 2 closest unsealing positions to g > 1 equal.

Answer to Question 2:

Let M₁ be the original mission, a round trip to g, and let M₂ be the alternative mission of a round trip to g′ in which a sealed package remains at g′ at the end.

There are at least 2 clues in the answer to Question 1: (1) that the mininum rations required for a round-trip between g″ and g is less than the maximum load of 2 units and is equal to the minimum rations required for a round trip between g″ and g′ that leaves 1 sealed pack at g′, and (2) that an optimal itinerary for M₁ always includes a minimum-length round-trip between g″ and g.

From the clues and the method used for Lemma 1, we can prove that any itinerary for M₂ can be converted into an itinerary for M₁ by adding exactly 1 more unit of walking, and that any optimal itinerary for M₁ can be converted into an itinerary for M₂ with exactly 1 unit less walking. This implies that any optimal itinerary for M₂ can be converted into an optimal itinerary for M₁. An optimal itinerary for M₂ can be calculated without the variable that causes the bifurcation, the position of the unsealing at m_y in any itinerary for M₁, and that position can be calculated as part of the conversion to an optimal itinerary for M₁.