  The Clustered Traveling Salesman Problem with a Prespecified Order on the
Clusters, a variant of the well-known traveling salesman problem is studied in
literature. In this problem, delivery locations are divided into clusters with
different urgency levels and more urgent locations must be visited before less
urgent ones. However, this could lead to an inefficient route in terms of
traveling cost. This priority-oriented constraint can be relaxed by a rule
called d-relaxed priority that provides a trade-off between transportation cost
and emergency level. Our research proposes two approaches to solve the problem
with d-relaxed priority rule. We improve the mathematical formulation proposed
in the literature to construct an exact solution method. A meta-heuristic
method based on the framework of Iterated Local Search with problem-tailored
operators is also introduced to find approximate solutions. Experimental
results show the effectiveness of our methods.
