Branch-and-cut algorithms for the vehicle routing problem with trailers and transshipments

This article studies the vehicle routing problem with trailers and transshipments (VRPTT), a practically relevant, but challenging, generalization of the classical vehicle routing problem. The article makes three contributions: (i) Building on a nontrivial network representation, two mixed-integer programming formulations for the VRPTT are proposed. (ii) Based on these formulations, five different branch-and-cut algorithms are developed and implemented. (iii) The computational behavior of the algorithms is analyzed in an extensive computational study, using a large number of test instances designed to resemble real-world VRPTTs.