We proposed models and metaheuristic search methods to solve complex real-world problems in the domain of computational logistics. In particular we focused on routing and loading problems, which have several practical applications in transportation, cutting, packing, and scheduling. We extended the problem formulations available in the literature to include several practical constraints, and we designed effective metaheuristic approaches based on large composite neighborhood structures. In addition, we made available to the community a set of challenging real-world instances provided by industrial partners.