To fill or not to fill: The gas station problem

Reviewer: Amrinder Arora

The traveling salesperson problem (TSP) is a well-known optimization problem; many variations of it are routinely studied. Although sometimes considered to be a theoretical rather than a practical problem, variants of the TSP appear frequently in real-world optimization problems. In this paper, the authors consider the framework in which fuel can be purchased at different prices from different gas stations. The general objective is to minimize the cost while traveling through the network. The authors consider four interesting TSP-like problems: the gas station problem-the problem of traveling between a given origin and destination in the cheapest possible way; the fixed-path gas station problem-a special case of the gas station problem in which the path is pre-specified; the uniform cost tour gas station problem-the problem of finding the shortest tour that visits a given collection of cities using a given collection of gas stations; and the tour gas station problem-a generalization of the uniform cost tour gas station problem in which the prices at different stations can vary. The authors present optimal polynomial-time algorithms for the first two problems (the gas station problems), and polynomial-time approximation schemes for the two tour problems. Some of these problems, or their special cases, are frequently discussed as example problems when studying dynamic programming or other aspects of algorithms. However, before Khuller et al.'s work, no polynomial-time optimal solution was known for the gas station problem. An attempt at a dynamic programming formulation gas station problem would falter when observing that the amount of fuel left is a parameter in the dynamic programming formulation. Since the amount of fuel is a continuous variable, dynamic programming formulation does not lead to an easy polynomial-time algorithm. Khuller et al. have improved this approach by astutely observing that, although the amount of fuel is indeed a continuous variable, it can only take O ( n 2) different values, where n is the number of locations. This is the case because we start with a known amount of fuel and can arrive at a network location only from another network location, and at each location we restock fuel entirely, restock just enough to reach the next location, or don't restock at all. The presented work has direct and obvious relevance to delivery and pickup services, such as waste collection, mail and courier, and bus tour planning. The studied problem also has significant applicability when the medium of travel is ships (and not cars or trucks) since the price of fuel along commercial freight vessel routes can vary widely. An interesting variation of the gas station problem that is not covered by this work but has wide applicability is the case in which the amount of gas contained in the vehicle changes the efficiency of the vehicle itself. This is a common problem-with significant monetary impact-when considering the movement of large repair vessels in the oil industry. Online Computing Reviews Service