Location-Routing and Location-Arc Routing - Location Science - page 383

the links of the network. In both cases, the need to design vehicle routes to evaluate
the cost of a set of facilities adds an extra level of difficulty to these problems which
are, in general, -hard.

The first works addressing LRPs date back to the 1960s (e.g. Von Boventer 1961
and Maranzana 1964 ). However, it was not until the end of the 1980s, when a solid
knowledge on both pure location and routing problems was achieved, that location-
routing became a really active field of research. The most common approach in the
first references addressing this type of problems was to make locational and routing
decisions in two separate steps, although it is well-known that this is most likely
to yield suboptimal solutions, as shown in Salhi and Rand ( 1989 ). For this reason,
more recent references address both decisions simultaneously.
LRPs arise as a natural extension of both, location and vehicle routing problems.
Moreover, there are several settings where LRPs appear naturally. For example,
Schittekat and Sörensen ( 2009 ) study the optimization problem arising in some
automotive companies that use third-party logistics partners for the distribution of
spare parts and model it as a large scale LRP. Other examples of real applications
where extensions of the LRP need to be solved are given in Ahn et al. ( 2012 ), where
the authors present a LRP with profits faced by NASA while planning planetary
surface exploration, or in Samanlioglu ( 2013 ) where hazardous waste management
of a Turkish region is dealt with by solving a multiobjective LRP.
Although there exist papers dealing with planar LRPs (see, for instance,
Manzour-al-Ajdad et al. 2012 or Salhi and Nagy 2009 ), most of the studies
concerning LRPs deal with discrete location problems. As a consequence, this
chapter will only consider this type of LRPs. Moreover, it does not pretend to be a
complete survey of all works in the literature addressing discrete LRPs, and only
presents the state of the art methods and the tools that have proven to be the most
suitable ones to tackle LRPs. For a complete recent survey on works concerned
with LRPs the reader is referred to Prodhon and Prins ( 2014 ). The reader can also
find a taxonomy of location-routing models and the related literature in Borges
Lopes et al. ( 2013 ). Earlier works are surveyed in Nagy and Salhi ( 2007 ). Given the
little attention that LARPs have received, this chapter is also mostly concentrated
on LRPs with node routing, and the most relevant issues concerning LARPs are
gathered in a single section.
The remainder of this chapter is organized as follows. Section 15.2 provides a
formal definition of the considered problems, together with the notation that will
be used throughout the chapter. The next two sections describe the main scientific
contributions on LRPs; Sect. 15.3 explores the different types of LRP formulations,
together with the most relevant valid inequalities used in exact methods, whereas
Sect. 15.4 is concerned with heuristic algorithms. The main findings regarding
LARPs are outlined in Sect. 15.5 ,and 15.6 concludes the chapter.

NP