Abstract: As e-commerce platforms continue to evolve, user demands become more personalized, and expectations for delivery speed increase, compounding the complexity of urban logistics. Therefore, the urban logistics delivery issue, such as the large-scale rich vehicle routing problem (LS-RVRP), faces increasingly severe challenges. Existing studies have used both exact solution algorithms and heuristic algorithms to solve VRP problems. However, as an NP-hard problem, the solution time of the VRP increases exponentially with the problem size. Therefore, exact solution algorithms are less efficient in solving LS-RVRPs. In addition, heuristic algorithms may fall into local optima, complicating the provision of efficient and satisfactory solutions. This paper proposes a novel approach: an adaptive large neighborhood search with continuous removal operator (CALNS) to find a balance between efficiency and performance in solving the LS-RVRP. The experiments conducted on two VRP datasets with time windows and five VRP datasets with time windows for heterogeneous fleets demonstrate the superiority of the proposed algorithm in solving the efficiency of LS-RVRPs. In detail, during testing on large-scale VRPTW datasets, the average computational time of CALNS was 0.42 s. Comparisons with best-known solutions revealed an average reduction in travel distance of 2.14%. For large-scale VRPTW datasets with heterogeneous fleets, CALNS has an average computational time of 2.41s, outperforming current mainstream algorithms and indicating the high computational efficiency of the proposed algorithm. This study offers logistics companies a practical, efficient solution for complex routing in densely populated urban areas.