<p>The cumulative capacitated vehicle routing problem (CCVRP), which is widely implemented in humanitarian relief and emergency supply scenarios, aims to minimize the total cumulative customer arrival time. This paper investigates a new variant of CCVRP, namely the multi-depot cumulative capacitated vehicle routing problem with prioritized customers (MDCCVRP-Pr), where each customer has a specific priority. A mathematical model is formulated to minimize the sum of total customers arrival times and penalty costs from priority violations. A local search-based heuristic (LS-AM) with an adaptive mechanism is developed under the framework of iterated local search, adopting an adaptive parameter to dynamically determine the execution of exploitation and exploration procedures. The algorithm integrates variable neighborhood descent, dynamic perturbation and multi-depot adjustment strategies, and a parameter adaptively updating mechanism. Computational results demonstrate that the proposed adaptive mechanism is effective, and the proposed algorithm is highly competitive in obtaining high-quality solutions compared with existing approaches.</p>