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. The authors 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. Their 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. They propose two variants. The first found for 96.8% of their 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.

• Record URL:
  https://doi.org/10.1016/j.tre.2022.102963
• Record URL:
  http://www.sciencedirect.com/science/article/pii/S1366554522003404
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/13665545
• Supplemental Notes:
  • © 2022 Elsevier Ltd. All rights reserved. Abstract reprinted with permission of Elsevier.
• Authors:
  • Schulz, Arne
  • 0000-0002-3088-2820
  • Suzuki, Yoshinori
• Publication Date: 2023-1

Language

• English

Media Info

• Media Type: Web
• Features: Appendices; Figures; References; Tables;
• Pagination: 102963
• Serial:
  • Transportation Research Part E: Logistics and Transportation Review
  • Volume: 169
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 1366-5545
  • Serial URL: http://www.sciencedirect.com/science/journal/13665545

Subject/Index Terms

• TRT Terms: Fixed routes; Heuristic methods; Refueling; Routing; Scheduling; Trucking
• Subject Areas: Highways; Motor Carriers; Planning and Forecasting;

Filing Info

• Accession Number: 01874805
• Record Type: Publication
• Files: TRIS
• Created Date: Feb 27 2023 8:51AM