The variable-route vehicle-refueling problem (VRVRP) is a variant of the network-flow
problem which seeks, for a vehicle traveling from origin s to destination d, both the
route and the refueling policy (sequence of fuel stations to use between s and d) that
jointly minimize the fuel cost of operating the vehicle. Commercial-grade decision
support systems that solve the VRVRP are widely used by motor carriers, but they
provide heuristic solutions only. Exact methods are available from the academic side,
but because they focus on minimizing costs, they tend to cut fuel costs in exchange for
increased vehicle miles (which can increase fuel consumptions and pollutants emission).
We propose a new approach to the VRVRP that allows carriers to jointly seek the two
possibly conflicting goals; minimizing fuel cost and vehicle miles. Computational testing
shows that our approach (i) outperforms the commercial software products in both goals,
and (ii) finds solutions that require significantly less vehicle miles than those given by
the exact method proposed in the academic literature, without incurring unacceptable
increases in fuel cost. [Submitted: November 28, 2011. Revised: January 30, 2013.
Accepted: February 8, 2013.]