The Gas Station Problem

In the Gas Station project we studied several routing problems that generalize shortest paths and the Traveling Salesman Problem. Our generalizations use a new cost model based on gas prices rather than distance traveled. The project largely grew out of the following natural question:

Question: Suppose you are planning a road trip across the Unites States, and you want to go from Washington DC to Boston. With sky rocketing gas prices, how would you plan your trip to spend as little money as possible?

Needless to say, gas does not cost the same everywhere. Indeed, due to differences in demand, legislation and affluence, gas prices can vary as much as 30% between nearby locations. Luckily, information about gas prices in a given area is readily-available from web sites such as AAA.com, GasPriceWatch.com and GasBuddy.com. How can we use this information to plan the cheapest route?

The Gas Station Problem: Assume you have a road map, given as a graph with edge lengths, and the price of gas at each location. Our car has a given tank capacity U. The objective is to find a route from a starting point S to a target destination T that minimizes gas costs.

Notice that an optimal solution need not use the shortest path between S and T, since the gas stations along that path may be more expensive that stations slightly off the shortest path -- precisely what happens along major highways. In addition to the path and the set of gas stations where to stop, a solution must also specify how much to fill at each station; this is because an optimal solution need not fill up the tank completely at each stop. The following toy instance exemplifies these two issues.

Below each edge, on black, is the amount of gas needed to traverse the edge; below each gas station, on red, is the cost of gas per gallon; above each gas station, on purple, is the amount filled by the optimal solution.

In an optimal solution the amount of gas filled at each refill stop, however, is not arbitrary. Indeed, the following easy-to-verify observation is the cornerstone of our algorithms.

Key Observation: If the next refill stop is more expensive then fill up, otherwise just fill enough to reach the next stop with an empty tank.

This seemingly innocuous observation can lead to strange solutions like the one depicted in the following cartoon where the driver asks the gas station employee for "Just enough to get me across the street to the cheaper station". (Parade, 12 Nov 2005.)

Now imagine the kind of optimal solution we would get if there was a long sequence of stations each one slightly cheaper than the previous! In order to avoid such degenerate solutions our algorithm can set a bound on the number of stops we are willing to make. Subject to this additional constraint, it finds the the optimal path minimizing the total cost of gas.

Theorem: In a graph with n locations, the Gas Station problem with at most D stops can be solved in O(n² D log n) time and O(n²) space.

For some applications, the path may be specified in advance. In this case we only need to choose the refill stops along the way; we call this the Fixed Path Gas Station problem.

Theorem: In a path with n gas stations, the Fixed Path Gas Station problem can be solved in O(n log n) time.

Finally, we studied the Tour Gas Station problem, a generalization of the Traveling Salesman problem that uses our cost model based on gas expenses. Here we are given a set of cities and we are to find a minimum cost tour that visits the cities in any order. Unlike the previous problem, the Tour Gas Station problem is NP-hard; thus, we designed approximation algorithms.

Theorem: Assuming that every city has a gas station at distance U (1-a) / 2, there is a 3 (1+a) / 2 (1-a) approximation algorithm for the Tour Gas Station problem with uniform gas prices.

For a complete description of the algorithms behind these theorems, and for further results on the Gas Station and Tour Gas Station problems, the interested reader is referred to our paper:

"To fill or not to fill: The Gas Station Problem" by S. Khuller, A. Malekian and J. Mestre, to appear in the 15th Annual European Symposium on Algorithms (ESA). [ ps | pdf | slides ]

This research was supported by NSF grant CCF-0430650.

About the researchers: Samir Khuller is a Professor at the Computer Science Department in the University of Maryland. This project was done while Azarakhsh Malekian and Julian Mestre were Ph.D. students working under the supervision of Prof. Khuller.

Photo (from left to right) : Julian, Azarakhsh, and Samir.