Problem
The problem (from [1]) 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]
---- 34 PARAMETER price [$/gallon]
Station1 3.002, Station2 3.630, Station3 3.616, Station4 3.126, Station5 3.167, Station6 3.603
Station7 2.067, Station8 3.281, Station9 3.748, Station10 3.783, Station11 3.065, Station12 2.349
Station13 3.135, Station14 2.928, Station15 3.527, Station16 3.585, Station17 3.305, Station18 3.460
Station19 3.320, Station20 2.375
---- 34 PARAMETER distance [miles]
Station1 Station2 Station3 Station4 Station5 Station6 Station7 Station8 Station9
incr 88.074 174.227 3.250 157.671 1.847 140.247 79.275 166.355 117.030
cumul 88.074 262.301 265.550 423.221 425.068 565.315 644.590 810.945 927.975
+ Station10 Station11 Station12 Station13 Station14 Station15 Station16 Station17 Station18
incr 136.787 16.517 23.499 167.570 127.418 31.520 91.885 91.363 74.604
cumul 1064.762 1081.279 1104.778 1272.348 1399.767 1431.286 1523.172 1614.535 1689.139
+ Station19 Station20 finish
incr 148.788 18.876 143.198
cumul 1837.926 1856.802 2000.000
Prices and distances were produced using a random number generator.
Note that I added the constraint that we need a little bit left over gas in the tank when arriving at the finish. That requirement was not in the original problem [1]. We can drop this constraint by just setting the parameter \(\mathit{finalgas}=0\).
We also have some derived data: the amount of gas we use for each leg of the trip. This is just the length of the leg divided by the efficiency of the car:
---- 34 PARAMETER use gas usage from previous location [gallons]
Station1 4.893, Station2 9.679, Station3 0.181, Station4 8.760, Station5 0.103, Station6 7.791
Station7 4.404, Station8 9.242, Station9 6.502, Station10 7.599, Station11 0.918, Station12 1.305
Station13 9.309, Station14 7.079, Station15 1.751, Station16 5.105, Station17 5.076, Station18 4.145
Station19 8.266, Station20 1.049, finish 7.955
Problem 1: minimize cost
The first problem is to minimize fuel cost. I have modeled this by observing three stages at each way point:
- First is the amount of gas in the tank when arriving at point \(i\). This amount should be non-negative: we cannot drive when the tank is empty. This variable is denoted by \(f_{\mathit{before},i}\ge 0\).
- The amount we pump is the second stage. This amount is bounded by \([0,\mathrm{capacity}]\). This variable is denoted by \(f_{\mathit{pumped},g}\).
- The amount in the tank after pumping. This amount cannot exceed the capacity of the tank. This is \(f_{\mathit{after},i} \in [0,\mathrm{capacity}]\).
This problem is a little bit like modeling inventory: keep track of what is going out and what is added. The LP model can look like:
| Min Cost Model |
|---|
| \[\begin{align} \min \> & \color{darkred}{\mathit{cost}}\\
& \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_{k,i} \in [0,\color{darkblue}{\mathit{capacity}}]
\end{align}\]
|
Note that the set \(g\) is a subset of set \(i\): \(g\) indicates the locations with gas stations between \(\mathit{start}\) and \(\mathit{finish}\). Also note that we cannot just substitute out the variable \(f_{\mathit{before},i}\): we need to make sure this quantity is non-negative. Similarly, we cannot substitute out the variable \(f_{\mathit{after},i}\): this must obey the tank capacity bound.
The results look like:
---- 66 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 40.691 33.612 31.861 26.756 21.680
pumped 25.566
after 34.256 26.657 25.740 50.000 40.691 33.612 31.861 26.756 21.680
+ Station18 Station19 Station20 finish
before 17.535 9.270 8.221 10.000
pumped 9.735
after 17.535 9.270 17.955
---- 66 VARIABLE cost.L = 218.998
We see we pump the most at station 7. Looking at the prices this makes sense: gasoline is cheapest at that gas station.
The number of stops where we pump gas is 4, and the total gas bill is $219.
Problem 2: minimize number of stops
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 to $314 (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 [1].
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
