An efficient heuristic for the fixed-route vehicle-refueling problem

Trucking companies have to decide each day at which truck stops their trucks should be refueled. The underlying problem is called fixed-route vehicle-refueling problem (FRVRP). Since large trucking companies have more than 10000 trucks, small improvements in the solution quality or the required time lead to substantial cost reductions. This makes the FRVRP an important daily scheduling problem. This paper presents a fast and efficient heuristic solution approach. We introduce an exact algorithm to determine the optimal refueling policy given the selected truck stops. It has a worst case performance of O(n2) but requires linear time on average. Our computational study shows that the heuristic is able to solve instances with up to 2000 truck stops within a fraction of a second to (near) optimality. We propose two variants. The first found for 96.8% of our instances an optimal solution with an average solution gap of 0.001% while requiring 0.001 seconds of computation time on average. The second variant requires 0.1 seconds on average, but reaches an average gap of under 0.001%, and found optimal solutions in 99.0% of all instances.