  This paper presents a new branch-and-cut algorithm based on infeasible path
elimination for the three-dimensional loading capacitated vehicle routing
problem (3L-CVRP) with different loading problem variants. We show that a
previously infeasible route can become feasible by adding a new customer if
support constraints are enabled in the loading subproblem and call this the
incremental feasibility property. Consequently, different infeasible path
definitions apply to different 3L-CVRP variants and we introduce several
variant-depending lifting steps to strengthen infeasible path inequalities. The
loading subproblem is solved exactly using a flexible constraint programming
model to determine the feasibility or infeasibility of a route. An extreme
point-based packing heuristic is implemented to reduce time-consuming calls to
the exact loading algorithm. Furthermore, we integrate a start solution
procedure and periodically combine memoized feasible routes in a
set-partitioning-based heuristic to generate new upper bounds. A comprehensive
computational study, employing well-known benchmark instances, showcases the
significant performance improvements achieved through the algorithmic
enhancements. Consequently, we not only prove the optimality of many best-known
heuristic solutions for the first time but also introduce new optimal and best
solutions for a large number of instances.
