A variable-reduction technique for the fixed-route vehicle-refueling problem

The fixed-route vehicle-refueling problem (FRVRP) is a difficult combinatorial problem that is used extensively in the US truckload industry to manage fuel costs. This paper proposes a preprocessing technique for the FRVRP that cuts the problem size noticeably without eliminating the optimal solution(s), which allows users to enlarge the size of solvable instances or save the CPU time of solving the problem dramatically. Empirical testing with real-world instances shows that our method: (i) reduces the problem size by 54.8% and (ii) solves the FRVRPs to optimality in roughly 1/4 of the time it is currently taking.