The efficient solving of the vehicle routing problem (VRP), derived from many optimization problems in the real-world, is of great economic and ecological importance. This work extends an adaptive large neighbourhood search framework (ALNS framework) for calculating VRP with profits modelled as team orienteering problems. An algorithm is proposed to solve appearing problems caused by introducing a relaxation step to the ALNS framework. For large and complex instances the proposed algorithm can be combined with graph sparsification to reduce the computation time without significant loss of the solution quality. The experiments on benchmark instances from literature and the comparison with the original ALNS framework prove that the extended ALNS framework results in solution improvements. Consequently the deviations of the ALNS framework compared to the best known solutions are reduced. Compared with other state-of-the-art algorithms, the proposed algorithm shows an advantage in computation time.