An efficient heuristic for the fixed-route vehicle-refueling problem
Publication date
2022-11-30
Document type
Forschungsartikel
Author
Suzuki, Yoshinori
Organisational unit
Institute of Operations Management, Universität Hamburg
Scopus ID
Publisher
Elsevier
Series or journal
Transportation Research Part E: Logistics and Transportation Review
ISSN
Periodical volume
169
Article ID
102963
Peer-reviewed
✅
Part of the university bibliography
Nein
Language
English
Keyword
Exact solution procedure
Local search
Lower bound
Transportation
Truck scheduling
Abstract
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(n<sup>2</sup>) 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.
Version
Published version
Access right on openHSU
Metadata only access