Solving the truck and trailer routing problem based on a simulated annealing heuristic

Shih Wei Lin, Vincent F. Yu*, Shuo Yan Chou

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

152 Scopus citations

Abstract

In this study, we consider the application of a simulated annealing (SA) heuristic to the truck and trailer routing problem (TTRP), a variant of the vehicle routing problem (VRP). In the TTRP, some customers can be serviced by either a complete vehicle (that is, a truck pulling a trailer) or a single truck, while others can only be serviced by a single truck for various reasons. SA has seen widespread applications to various combinatorial optimization problems, including the VRP. However, to our best knowledge, it has not been applied to the TTRP. So far, all the best known results for benchmark TTRP instances were obtained using tabu search (TS). We applied SA to the TTRP and obtained 17 best solutions to the 21 benchmark TTRP benchmark problems, including 11 new best solutions. Moreover, the computational time required by the proposed SA heuristic is less than those reported in prior studies. The results suggest that SA is competitive with TS on solving the TTRP.

Original languageEnglish
Pages (from-to)1683-1692
Number of pages10
JournalComputers and Operations Research
Volume36
Issue number5
DOIs
StatePublished - 05 2009
Externally publishedYes

Keywords

  • Heuristic
  • Simulated annealing
  • Truck and trailer routing problem
  • Vehicle routing problem

Fingerprint

Dive into the research topics of 'Solving the truck and trailer routing problem based on a simulated annealing heuristic'. Together they form a unique fingerprint.

Cite this