Wednesday, October 9, 2019

The gas station problem: where to pump gas and how much

Problem

The problem (from ) is to determine where to pump gasoline (and how much) during a trip, where prices between gas stations fluctuate.

We consider some different objectives:

• Minimize Cost. This results in an LP model.
• Minimize Number of Stops. This makes the model a MIP.
• Minimize Number of Stops followed by Minimize Cost. This is essentially a multi-objective problem.
• As a bonus: Minimize Cost but always fill up the tank completely. This is a MIP model.

Data

I invented some data:

----     34 SET i  locations

start    ,    Station1 ,    Station2 ,    Station3 ,    Station4 ,    Station5 ,    Station6 ,    Station7
Station8 ,    Station9 ,    Station10,    Station11,    Station12,    Station13,    Station14,    Station15
Station16,    Station17,    Station18,    Station19,    Station20,    finish

----     34 SET g  gas stations

Station1 ,    Station2 ,    Station3 ,    Station4 ,    Station5 ,    Station6 ,    Station7 ,    Station8
Station9 ,    Station10,    Station11,    Station12,    Station13,    Station14,    Station15,    Station16
Station17,    Station18,    Station19,    Station20

----     34 PARAMETER efficiency           =       18.000  [miles/gallon]
PARAMETER capacity             =       50.000  tank-capacity [gallons]
PARAMETER initgas              =       25.000  initial amount of gasoline in tank [gallons]
PARAMETER finalgas             =       10.000  minimum final amount of gas in tank [gallons]
PARAMETER triplen              =     2000.000  length of trip [miles]

In the previous section we solved the minimize cost problem. This gave us 4 stops to refuel with total fuel cost of 219. Now, let's try to minimize the number of times we visit a gas station. Counting in general needs binary variables, and this is no exception. The model can look like: Min Number of Stops Model \begin{align} \min \> & \color{darkred}{\mathit{numstops}}\\ & \color{darkred}{\mathit{numstops}} = \sum_g \color{darkred} \delta_g \\ & \color{darkred}{\mathit{cost}} = \sum_g \color{darkred}f_{\mathit{pumped},g} \cdot \color{darkblue}{\mathit{price}}_g \\ & \color{darkred}f_{\mathit{before},i} = \color{darkred}f_{\mathit{after},i-1} - \color{darkblue}{\mathit{use}}_i && \forall i \ne \mathit{start} \\ & \color{darkred}f_{\mathit{after},g} = \color{darkred}f_{\mathit{before},g} + \color{darkred}f_{\mathit{pumped},g} && \forall g \\ & \color{darkred}f_{\mathit{after},\mathit{start}} = \color{darkblue}{\mathit{initgas}} \\ & \color{darkred}f_{\mathit{before},\mathit{finish}} \ge \color{darkblue}{\mathit{finalgas}} \\ & \color{darkred} f_{\mathit{pumped},g} \le \color{darkred} \delta_g \cdot \color{darkblue}{\mathit{capacity}} && \forall g \\ & \color{darkred}f_{k,i} \in [0,\color{darkblue}{\mathit{capacity}}] \\ & \color{darkred} \delta_g \in \{0,1\} \end{align} Because we have binary variables, this is now a MIP model. The constraint $$f_{\mathit{pumped},g} \le \delta_g \cdot \mathit{capacity}$$ implements the implication: $\delta_g=0 \Rightarrow f_{\mathit{pumped},g}=0$When we solve this we see: ---- 71 VARIABLE f.L amounts of fuel start Station1 Station2 Station3 Station4 Station5 Station6 Station7 Station8 before 20.107 10.428 10.247 1.488 1.385 41.954 32.712 pumped 6.406 46.358 after 25.000 20.107 10.428 10.247 1.488 7.791 46.358 41.954 32.712 + Station9 Station10 Station11 Station12 Station13 Station14 Station15 Station16 Station17 before 26.211 18.611 17.694 16.388 7.079 41.595 36.490 31.415 pumped 43.346 after 26.211 18.611 17.694 16.388 7.079 43.346 41.595 36.490 31.415 + Station18 Station19 Station20 finish before 27.270 19.004 17.955 10.000 after 27.270 19.004 17.955 ---- 71 VARIABLE delta.L Station5 1.000, Station6 1.000, Station14 1.000 ---- 71 VARIABLE cost.L = 314.254 VARIABLE numstops.L = 3.000 So instead of 4 stops, now we only need 3 stops. We ignored the cost in this model. This causes the fuel cost to skyrocket to314 (from $219 in the min cost model). I kept the cost constraint in the problem for two reasons. First, it functions as an accounting constraint. Such a constraint is just for informational purposes (it is not meant to change or restrict the solution). A second reason is that we use the cost variable in a second solve in order to minimize cost while keeping the number of stops optimal. This is explained in the next section. Problem 3: minimize number of stops followed by minimizing cost After solving the min number of stops problem (previous section), we can fix the number of stops variable $$\mathit{numstops}$$ to the optimal value and resolve minimizing the cost. This is essentially a lexicographic approach to solving the multi-objective problem min numstops, min cost. If we do this we get as solution: ---- 76 VARIABLE f.L amounts of fuel start Station1 Station2 Station3 Station4 Station5 Station6 Station7 Station8 before 20.107 21.238 21.058 12.298 12.196 4.404 40.758 pumped 10.811 50.000 after 25.000 30.918 21.238 21.058 12.298 12.196 4.404 50.000 40.758 + Station9 Station10 Station11 Station12 Station13 Station14 Station15 Station16 Station17 before 34.256 26.657 25.740 24.434 15.125 8.046 41.595 36.490 31.415 pumped 35.301 after 34.256 26.657 25.740 24.434 15.125 43.346 41.595 36.490 31.415 + Station18 Station19 Station20 finish before 27.270 19.004 17.955 10.000 after 27.270 19.004 17.955 ---- 76 VARIABLE delta.L Station1 1.000, Station7 1.000, Station14 1.000 ---- 76 VARIABLE cost.L = 239.188 VARIABLE numstops.L = 3.000 Now we have a solution with 3 stops and a fuel cost of$239. This is my proposal for a solution strategy for the problem stated in .

An alternative would be to create a single optimization problem with a weighted sum objective: $\min \> \mathit{numstops} + w \cdot \mathit{cost}$ with $$w$$ a small constant to make sure that $$\mathit{numstops}$$ is the most important variable. As the value of $$w$$ requires some thought, it may be better to use the lexicographic approach.

Filling up the gas tank

Suppose that when pumping gas we always fill up the tank completely. This alternative is not too difficult to handle. We need to add the implication: $\delta_g=1 \Rightarrow f_{\mathit{pumped},g}=\mathit{capacity}-f_{\mathit{before},g}$ This can be handled using the inequality: $f_{\mathit{pumped},g} \ge \delta_g \cdot \mathit{capacity}-f_{\mathit{before},g}$

If we add this constraint and solve the min cost model we see:

----     84 VARIABLE f.L  amounts of fuel

start    Station1    Station2    Station3    Station4    Station5    Station6    Station7    Station8

before                  20.107      40.321      40.140      31.381      31.278      23.487      19.082      40.758
pumped                  29.893                                                                  30.918
after       25.000      50.000      40.321      40.140      31.381      31.278      23.487      50.000      40.758

+    Station9   Station10   Station11   Station12   Station13   Station14   Station15   Station16   Station17

before      34.256      26.657      25.740      24.434      40.691      33.612      48.249      43.144      38.068
pumped                                          25.566                  16.388
after       34.256      26.657      25.740      50.000      40.691      50.000      48.249      43.144      38.068

+   Station18   Station19   Station20      finish

before      33.924      25.658      24.609      16.654
after       33.924      25.658      24.609

----     84 VARIABLE delta.L

Station1  1.000,    Station7  1.000,    Station12 1.000,    Station14 1.000

----     84 VARIABLE cost.L                =      261.709
VARIABLE numstops.L            =        4.000

In this case we have a little bit more gasoline left in the tank at the finish than strictly needed. Notice how in each case we pump gas, we end up with a full tank. This fill-up strategy is surprisingly expensive.

Conclusion

Here we see the advantages of using an optimization model compared to a tailored algorithm. We can adapt the optimization model to different situations. From the basic min cost model, we can quickly react to new questions.

References

1. Gas Station Problem - cheapest and least amount of stations, https://stackoverflow.com/questions/58289424/gas-station-problem-cheapest-and-least-amount-of-stations
2. Shamir Khuller, Azarakhsh Malekian, Julian Mestre, To Fill or not to Fill: The Gas Station Problem, ACM Transactions on Algorithms, Volume 7, Issue 3, July 2011.

1. 1. 