In transportation, the multi-depot heterogeneous fleet vehicle routing problem with time windows (MDHFVRPTW) is one of the hard-to-solve real-life problems. In the study, a new node-based MDHFVRPTW has been developed. Unlike other studies in the literature, heterogeneous fleets including both airline and roadway vehicles are used for routing. In the model, real-life data of the airline and roadway are taken into consideration. In particular, important aviation constraints such as the range of the aircraft, landing and take-off cycle (LTO) cost according to the engine type, and the penalty cost are presented in the model. The problem is analysed by using narrow and wide time windows, which is the realization of fast and normal demand. A new hybrid genetic algorithm with variable neighborhood search (HGA-VNS) has been proposed for the solution of the MDHFVRPTW model. In the solution of the model, remarkable results have been obtained with the HGA-VNS algorithm compared to the genetic algorithm and off-the-shelf solvers. Also, the HGA-VNS algorithm has been tested with small and large-scale instances and compared with other studies in the literature. It is thought that the proposed MDHFVRPTW model and the developed HGA-VNS algorithm will bring a different perspective to transportation.