Geoscience Reference
In-Depth Information
and the cost of reaching the arcs. Using a branch-and-cut algorithm, the authors can
solve to optimality instances involving up to 140 nodes and 190 required arcs.
15.6
Conclusions
This chapter has summarised some the most relevant research contributions on LRPs
and LARPs. As it has been shown, the different research directions followed in the
study of formulations and exact algorithms for LRPs have finally converged to one
single proposal, which has been able to incorporate most of the relevant contribu-
tions in the field so far. In the case of heuristic algorithms, the research activity has
recently been reactivated, giving raise to several competitive algorithms in the last
years. The most successful approaches involve one or several metaheuristics, and the
current activity in this area gives the impression that relevant further improvements
can be expected in the near future.
In contrast, research on LARPs is still in its early stages. Exact algorithms have
only been proposed for very particular cases, and even in the case of heuristics the
literature is rather scarce. Keeping in mind the evolution followed by the research on
LRPs, especially in what concerns exact algorithms, further research is still required
on arc routing problems with multiple depots before it is possible to devise efficient
algorithms for solving LARPs.
References
Ahn J, de Weck O, Geng Y, Klabjan D (2012) Column generation based heuristics for a generalized
location routing problem with profits arising in space exploration. Eur J Oper Res 223:47-59
Akca Z, Berger RT, Ralphs TK (2009) A branch-and-price algorithm for combined location
and routing problems under capacity restrictions. In: Proceedings of the eleventh INFORMS
computing society meeting, Charleston, pp 309-330
Albareda-Sambola M, Díaz JA, Fernández E (2005) A compact model and tight bounds for a
combined location-routing problem. Comput Oper Res 32:407-428
Amaya A, Langevin A, Trépanier M (2007) The capacitated arc routing problem with refill points.
Oper Res Lett 35:45-53
Amberg A, Domschke W, Voß S (2000) Multiple center capacitated arc routing problems: a tabu
search algorithm using capacitated trees. Eur J Oper Res 2000:360-376
Arbib C, Servilio M, Archetti C, Speranza MG (2014) The directed profitable location rural
postman problem. Eur J Oper Res 236:811-819
Baldacci R, Maniezzo B (2006) Exact methods based on node-routing formulations for undirected
arc-routing problems. Networks 47:52-60
Baldacci R, Mingozzi A, Wolfler Calvo R (2011) An exact method for the capacitated location-
routing problem. Oper Res 59:1284-1296
Barreto S, Ferreira C, Paixão J, Souza Santos B (2007) Using clustering analysis in a capacitated
location-routing problem. Eur J Oper Res 179:968-977
Bartolini E, Cordeau J-F, Laporte G (2013) Improved lower bounds and exact algorithm for the
capacitated arc routing problem. Math Program 137:409-452
