A metaheuristic for a time-dependent vehicle routing problem with time windows, two vehicle fleets and synchronization on a road network

In this work, the authors extend the time-dependent vehicle routing problem with time windows on a road network by considering two types of vehicles, large and small, to serve customers. Motivated from city logistics applications, large vehicles are forbidden from the downtown area. Accordingly, goods must be transferred from large to small vehicles to serve downtown customers. This leads to synchronization issues at transfer points, which are special locations without storage capacity. The problem is not a pure two-echelon vehicle routing problem, since customers outside of the downtown area can be served directly by large vehicles. The problem is further compounded by the presence of time-dependent travel times that are defined on the arcs of the road network and are used to model congestion periods. To solve this difficult problem, we propose an adaptation of the Slack Induction by String Removals metaheuristic, which is state-of-the-art for the classical capacitated vehicle routing problem. Computational results on a set of test instances with different characteristics empirically demonstrate the optimization capabilities of this new metaheuristic on a problem which is much more complicated than the capacitated vehicle routing problem.

• Record URL:
  • https://doi.org/10.1016/j.ejtl.2024.100143
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S2192437624000189
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/21924376
• Supplemental Notes:
  • © 2024 The Authors. Published by Elsevier B.V. on behalf of Association of European Operational Research Societies (EURO). Abstract reprinted with permission of Elsevier.
• Authors:
  • Guillen Reyes, Fernando O
  • Gendreau, Michel
  • 0000-0002-9262-3648
  • Potvin, Jean-Yves
  • 0000-0003-0210-4033
• Publication Date: 2024

Language

• English

Media Info

• Media Type: Web
• Features: Appendices; Figures; References; Tables;
• Pagination: 100143
• Serial:
  • EURO Journal on Transportation and Logistics
  • Volume: 13
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 2192-4376
  • Serial URL: https://www.journals.elsevier.com/euro-journal-on-transportation-and-logistics/
• Publication flags:

  Open Access (libre)

Subject/Index Terms

• TRT Terms: Delivery vehicles; Heuristic methods; Routing; Time dependence; Time windows; Vehicle fleets
• Identifier Terms: Vehicle Routing Problem
• Subject Areas: Freight Transportation; Operations and Traffic Management; Planning and Forecasting;

Filing Info

• Accession Number: 01935503
• Record Type: Publication
• Files: TRIS
• Created Date: Oct 30 2024 11:08AM