This study addresses the initial phase of a multi-modal air cargo transport network, where trucks collect shipments from multiple origins and deliver them to the hub airport of an airline. Efficient coordination between ground transport and outbound flights is crucial for optimising truck load factors, reducing operational costs, and ensuring on-time cargo transfers at the hub. Poor synchronisation can cause delays and increased expenses, reducing the efficiency of the entire transport network. This paper presents a novel Mixed Integer Linear Programming (MILP) formulation and an Adaptive Large Neighbourhood Search (ALNS) framework for an integrated vehicle routing and dock-door scheduling problem that includes split delivery, incompatible products, time windows, and open routes, with the objective of minimising operational costs. The ALNS framework uses a dock-door-based route representation along with multiple insertion and removal operators to improve the solution to the problem at hand. A comparative analysis between the MILP and ALNS model shows that the ALNS model consistently outperforms the MILP model in computational efficiency and solution quality for larger and more complex instances. The ALNS model efficiently finds feasible solutions within significantly reduced computational times, making it practical for real-world applications. Moreover, using a case study of an airline, the ALNS-generated network demonstrates improvements in cost efficiency, fleet utilisation, and truck load factors compared to the airline’s historical routing data. Despite differences between the actual network data and the model-generated data, stemming from assumptions that create an idealised scenario that does not fully capture the complexities of real-world operations, the ALNS model offers significant enhancements in efficiency for the airline’s trucking network.