A formulation and a metaheuristic approach for the clustered vehicle routing problem with <i>d</i> ‐relaxed priority rule

Abstract This paper investigates an extension of the vehicle routing problem in which, in addition to minimizing the distance traveled, the sequencing of customer visits is subject to precedence constraints that impose visiting priorities among customers. This problem has practical applications in various real‐world contexts, including humanitarian logistics and internet service provision. In this paper, we extend the literature by considering the clustered vehicle routing problem with ‐relaxed priority rule, a version of the problem where all vertices must be visited exactly once, the vehicles have capacity limitations, and the vertices must be visited considering the ‐relaxed priority rule. A new mathematical formulation considering the local timing case is presented, and a metaheuristic approach is proposed to tackle bigger instances. Finally, computational experiments using a general‐purpose mixed‐integer linear programming solver are compared with the results obtained by the metaheuristic. The results indicate that the mathematical model can find feasible solutions for small instances—although without proving optimality—while the proposed metaheuristic is able to find feasible solutions for larger instances in significantly less computational time.