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

Arne Schulz and Yoshinori Suzuki

Transportation Research Part E: Logistics and Transportation Review, 2023, vol. 169, issue C

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(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.

Keywords: Transportation; Truck scheduling; Local search; Lower bound; Exact solution procedure (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554522003404
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:169:y:2023:i:c:s1366554522003404

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2022.102963

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().