Multi-objective constrained vehicle refueling planning: Complexity and polynomial-time approximation schemes

For point-to-point direct delivery over the transportation network, timely delivery of commodity and reduction of total fuel cost are both important objectives to consider. Since fuel prices can vary significantly over a broad region, often there is a tradeoff between fuel cost and travel time. A short path may not be economical in terms of fuel cost while routing through regions with lower fuel prices may take more time. In this paper, we consider multi-objective constrained vehicle refueling planning in two settings: (i) minimizing the fuel cost given an upper bound on travel time or (ii) minimizing travel time given an upper bound on the fuel cost. We prove that the computational task is NP-Complete even when the fuel price is fixed or when the amount of fuel consumption and the travel time are linearly dependent. We then show fully polynomial-time approximation schemes for refueling planning in these two situations.