How to identify mathematical model of "Fuel Problem"?

Question

Fuel problem

• My vehicle's tank has unlimited capacity of some units (galons or liters) , but it is broken and the gasoline evaporates from it if. So, if I don't consume the gasoline I have bought during the next 50km of travel, it is going to disappear all instantly at kilometer number 51. I.e., I can't hoard gasoline for the entire trip, I must use each unit of gas before any 50km of traveling, and the Gas Stations are there so I could refill my tank. I am consuming the gasoline using (FIFO) schedule, so each purchase has its own evaporation time and , i.e. aquired gasoline isn't mixed.
• As I drive down the road, there are Gas Station at any discrete periods of distance, for example, at kilometer 10 there might be one Gas Station , at km 15 there could be two Gas Stations (different simulations will have different environment data).
• Each Gas Station has different price, one Gas Station might be selling gasoline at 10 coins per unit, the other might have a lower price , say of 5 coins per unit.
• Each Gas Station has a purchasing limit per customer, so I can't buy unlimited amount, but only the maximum amount according to the policy of that station.
• I have an unlimited amount of coins, but I must minimize the cost of the trip. (arrive at the finish line with an empty tank)
• The road is just a single path (straight line), with gas stations on it , where I could stop and reload fuel
• I am starting this journey with 10 units of gasoline. (initial params)

Goal:

• I need to travel 500 km down the road, with minimal cost, and avoid losing purchased gasoline due to evaporation. The input will be the vector of gas stations on the road, the output - the minimal cost of the trip for this particular simulation

Analysis:

• Does this problem has a generalized matemathical model already? It seems like the traveling salesman problem, but with the paths being the "gasoline purchases". Kind of like "if I buy X amount of gas, I could only travel the distance Y, but at that distance I might not find any Gas Station, so this path is not good, i.e a dead end". So, this variation of traveling salesman problem, would have many different paths depending on the cost of purchased gasoline. And instead of minimizing the distance like in classic traveling salesman problem, I must minimize the accumulated cost of gasoline used. I am correct in this analysis? (I mean, is this really some variation of traveling salesman problem?)

• The solution to this problem seems like requires handling a state, for example my State could be something like:

      gasoline_in_the_tank:            35 liters
      kilometers_traveled:            351 km
      kilometers_remaining:           149 km  // i.e summing up to 500km
      kilomters_to_next_gas_station:    9 km
      accumulated_cost:               140 coins
  

• We also have environment:

      vector_of_gas_stations: {
          { 
              km:                     51, // point where the Gas station is located (km)
              gas_price:              20, // coins
              max_purchasing_amount:  10  // liters
          },
          { 
              km:                     87, 
              gas_price:              30, 
              max_purchasing_amount:  20 
          },
          ... and so on ...
  
  
      }
  

• So, would be the best approach to solve this problem using Decision Trees ? Each Node in the tree would have the State variables , so I would build a tree of all possible actions (gasoline purchases), and once I have build the entire tree, I would search for Leaf that contains the minimum value in accumulated_cost field. After finding that Leaf, I would just build the entire path from the Root of the tree down to the Leaf and that would be the solution.

• Also, what would be the state of the art algorithm for solving this kind of problem?

Answer 1

It does not sound like a variant of the traveling salesman problem. Instead, I would recommend thinking of it in terms of an inventory optimization problem, where the reorder decisions occur at the time periods associated with the gas station locations. The decisions are how much fuel to purchase (restock) at each time period. The demand is the consumption of gasoline and is deterministic. You have an initial inventory of 10 units and must have nonnegative inventory at all times (no backordering). The objective is to minimize the total cost over the finite time horizon. You can solve this problem via linear programming.

Answer 2

A simple strategy is to think about where the gas for the last km came from. It clearly comes from the cheapest station within 50 km of the end. You should stop at that station and buy just enough to complete your journey. The km just after that station can be traveled with gas from that station or one within the past 50 km. If there is a cheaper station within 50 km you should leave it with 50 km of fuel, then just top up where you are now. Keep working backward