A hybrid metaheuristic for single truck and trailer routing problems

Luca Accorsi, Daniele Vigo

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

In this paper, we propose a general solution approach for a broad class of vehicle routing problems that all use a single vehicle, composed of a truck and a detachable trailer, to serve a set of customers with known demand and accessibility constraints. A more general problem, called the extended single truck and trailer routing problem (XSTTRP), is used as a common baseline to describe and model this class of problems. In particular, the XSTTRP contains, all together, a variety of vertex types previously considered only separately: Truck customers, vehicle customers with and without parking facilities, and parking-only locations. To solve the XSTTRP, we developed a fast and effective hybrid metaheuristic, consisting of an iterative core part, in which routes that define high-quality solutions are stored in a pool. Eventually, a set-partitioning-based postoptimization selects the best combination of routes that forms a feasible solution from the pool. The algorithm is tested on extensively studied problems from the literature, such as the multiple depot vehicle routing problem, the location routing problem, the single truck and trailer routing problem with satellite depots, and the single truck and trailer routing problem. Finally, computational results and a thorough analysis of the main algorithm's components on newly designed XSTTRP instances are provided. The obtained results show that the proposed hybrid metaheuristic is highly competitive with previous approaches designed to solve specific specialized problems, both in terms of computing time and solution quality.

Original languageEnglish
Pages (from-to)1351-1371
Number of pages21
JournalTransportation Science
Volume54
Issue number5
DOIs
Publication statusPublished - May 2020

Keywords

  • Metaheuristics
  • Truck and trailer
  • Vehicle routing

Fingerprint

Dive into the research topics of 'A hybrid metaheuristic for single truck and trailer routing problems'. Together they form a unique fingerprint.

Cite this