The Gas Station Problem

Optimization problems to find the shortest path between locations are pervasive in computer science and operations research. This problem considers both the distance traveled and the cost of gas along with a myriad of other factors including gas station quality or if we are willing to stop for gas only one time for a given trip. An additional constraint to this problem we must consider is limited or costly information about local gas prices – this obstacle may be the most challenging for drivers to overcome. With large variance in gas price on the same day in any given city (as much as 20% in Washington, D.C.!), this is an important economics problem that we all encounter in our daily lives.

I personally encountered the gas station problem last week on my way home from the gym pulling into an Exxon. I recoiled at the exorbitant $$$$$!, not even knowing if there would be a cheaper gas station around the corner. While I could have used GasBuddy, Waze or a similar service to locate inexpensive gas on my route ahead of time, I chose to skip on optimizing the route – adding ten plus minutes to my route to find affordable gas. This example clearly shows that the cost of the most convenient gas station can either be paid at the pump or in additional drive time to a less convenient gas station. The gas station problem can be easily optimized under any number of constraints, shown HERE, however the price-finding cost throws in an additional wrinkle that is not considered.

Many drivers rely on past experience to solve this problem. Having once identified a particular gas station as “cheap”, they might cease price comparison on future drives – saving these drivers both the price-finding cost (using the service to find the cheapest gas) and the cost of non-optimization (like I encountered). This method spreads the one-time optimization cost over future trips and brings the per-trip optimization cost close to zero – and holds up for as long as stations are consistent in their pricing strategy. In other words, if gas stations flip between overcharging and undercharging, these customers may find themselves on the wrong end of the bargain.

Another strategy for minimizing the price paid at the pump along with a variety of time variables mentioned above (driving time, number of times you stop to get gas, and time spent finding cheap gas stations) could be to start searching for cheap gas earlier. In the example above, I had a limited time horizon with my tank approaching empty and was unable to postpone getting gas to a later drive. However if I had searched for gas with more gas in my tank, I would be able to search for gas on many different routes across multiple days and therefore have a greater chance of finding cheap gas without excess price-finding cost.

The optimal solution considering drivers’ budget and time constraints, ability to use technology in price-finding, the consistency of pricing for local gas stations, not to mention preferences (who doesn’t love a Sheetz or QuikTrip?) may vary wildly for anyone who spends their dollars at the pump. We may not even explicitly think about this problem in the ways I describe above. However, this problem outlines many of the implicit tradeoffs we encounter every day.