In this paper, we present two multi-start heuristic approaches to solve the clustered traveling salesman problem with d-relaxed priority rule (CTSP-d). In this problem, the nodes (except the starting node or depot) are partitioned into different clusters according to their urgency levels and higher urgency nodes must be visited prior to visiting lower urgency ones, but this could lead to severe inefficiency in travel costs. A rule, called d-relaxed priority rule, provides a trade-off between travel cost and urgency level by relaxing this urgency-oriented restriction to certain extent. This problem is NP-hard as it contains the very well-known traveling salesman problem as a special case. Our first approach is a hyper-heuristic approach that makes multiple starts and utilizes three levels of heuristics. At the top level, this hyper-heuristic approach makes use of two hyper-heuristic approaches as low level heuristics. These two hyper-heuristic approaches in turn use five elementary problem-specific heuristics as low level heuristics to generate a new solution from the current solution. Our second approach is a multi-start iterated local search approach where variable neighborhood descent (VND) is used as local search. VND uses five neighborhoods to improve the solution. Performance of the proposed approaches are experimentally analyzed on 148 standard benchmark instances available in the literature. Computational results on these benchmark instances show the effectiveness of the proposed approaches as they generate high-quality solutions in low computational times compared to the state-of-the-art approaches available in the literature. Our approaches improve the best-known solution values on 20 instances.