As already stated, the LRP with uncapacitated depots and capacitated
vehicles, studied for instance by Tuzun and Burke (1999), is
seldom studied at this time. The exception is a paper by Hashemi
Doulabi and Seifi (2013), which addresses the location-arc routing
problem on a mixed network where up to L uncapacitated depots
can be selected out of m. They present mixed integer programs
for L ¼ 1 and L > 1 and relax some constraints to obtain lower
bounds for the total cost. They then develop a simulated annealing
(SA) framework, working on partial solutions composed of small
tours over customers. A partial solution is completed using a savings
heuristic that merges small tours, followed by an assignment
of each tour to the closest depot and by an improvement procedure
that randomly changes the set of open depots. The moves considered
by the SA consist in breaking small tours, randomly selected
in the incumbent partial solution