by S. Khuller, A. Malekian, and J. Mestre
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:
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?
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.
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.
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.
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.
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.
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:
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.