Geoscience Reference
In-Depth Information
one for the general case, and a second one for the particular case where one single
depot has to be located. Another formulation is also presented in Borges Lopes
et al. (
2014
). However, these papers do not explore the possibility of solving these
formulations exactly, possibly because they all use flow variables, with up to four
indices in some cases, and therefore, they are rather large.
Bearing in mind the evolution of the formulations for the capacitated arc routing
problem (CARP), one might expect set partitioning formulations to allow for more
efficient solution methods. Indeed, the most successful algorithms for the CARP
so far, proposed by Bode and Irnich (
2012
) and Bartolini et al. (
2013
), both rely
on set partitioning formulations for this problem. In any case, further research is
still needed before reaching efficient exact methods for solving general LARPs.
Although it is true that research on the CARP has been very fruitful in the past
years, the subproblem obtained from a LARP when the set of facilities to open is
fixed is a CARP with multiple depots, which has hardly been studied, and for which
only heuristic algorithms exist (see, for instance, Amberg et al.
2000
).
In the case of heuristic methods, the original approaches relying on the sequential
solution of the different subproblems of a LARP have evolved with a recent
focus on the use of metaheuristics. Doulabi and Seifi (
2013
) propose a simulated
annealing heuristic which, at each iteration, proceeds following an allocation-
routing-location scheme: it first builds a routing solution then tries to improve
the depot locations. More recently, Borges Lopes et al. (
2014
) have proposed and
compared several heuristics combining tabu search, variable neighborhood search,
and GRASP for which they also test different constructive heuristics. According
to their computational experiments, the combination of tabu search and GRASP
provides the best results. With this combination, they find optimal or near optimal
solutions in less than a minute, for instances with up to 140 nodes and 190 required
edges. They also propose a set of benchmark instances for future comparisons.
In contrast to the scarce literature available on the LARP, a relatively large
variety of related problems have been studied. This is the case, for instance, of
the capacitated arc routing problem with intermediate facilities presented in Ghiani
et al. (
2001
). In this case, no location decisions need to be made, and a single depot
is considered, like in the CARP, but several facilities are available in the network
where a vehicle can unload the demand collected at the required edges before the
loaded demand exceeds the vehicle capacity.
Other examples are the capacitated arc routing problem with refill points or the
synchronized arc and node routing problem, presented in Amaya et al. (
2007
)and
Salazar-Aguilar et al. (
2013
), respectively. In these cases, an additional fleet of
vehicles is available to refill the main fleet, and the locations where these vehicles
meet each other need to be determined when designing their respective routes. These
problems differ in the types of routes performed by the vehicles used to replenish
the service vehicles.
A recent paper on the directed profitable location rural postman problem (Arbib
et al.
2014
) also deserves a mention. This is an uncapacitated LARP where required
arcs have associated profits and the decision maker can choose whether or not to
serve any of them, taking into account the differences between the profit generated
