Vehicle Routing Problem (VRP) is one of the most studied topics in Operations Research. Among the numerous variants of the VRP, this research addresses the Clustered Heterogeneous Vehicle Routing Problem with relaxed priority rules in which customers are assigned to several priority groups and customers with the highest priorities typically need to be visited before lower priority ones. Some rules are additionally imposed to control the trade-off between priority and efficiency (traveling cost). The problem has important applications in the context of logistics of commercial products as well as humanitarian relief operations. We propose a Mixed Integer Linear Programming (MILP) model to formulate the problem and solve small-size instances. An adaptive large neighborhood search (ALNS) algorithm with problem-tailored components is then designed to handle the problem at larger scale. The results obtained on a set of instances with different priority assignment appoaches that simulate natural disasters and commercial logistics show the robusness of the problem model and the performance of the proposed methods.