Geoscience Reference
In-Depth Information
15.5
Location Arc Routing
LARPs are typically defined on graphs G
D
.V;E/ that can be either directed,
undirected or, in the most general case, mixed. In G,asetI
V of selected
nodes where facilities may be established is given, together with a selected subset
of links R
E, known as required arcs or edges, which must be traversed to
receive some service. Common applications of LARPs include garbage collection,
road maintenance and postal delivery. For details on these applications, the reader
is referred to Ghiani and Laporte (
2001
).
In contrast to the volume of the literature on LRPs with node routing, LARPs
have been addressed only in a few references. This is due in part, to the difficulty
of these problems, but also to the fact that several strategies have been devised to
transform arc routing problems into node routing problems by suitably modifying
the underlying graph (see, for instance Pearn et al.
1987
; Baldacci and Maniezzo
2006
; Longo et al.
2006
). However, significant differences exist between the
structures of the routes depending on whether service is provided at the nodes or
on the links. These differences suggest that, as happens with pure routing problems,
specific approaches for either type of problem may yield more efficient algorithms.
The most relevant difference between routes in node and arc routing is that in
node routing problems one can assume, without loss of generality, that no node
will be visited more than once, and the only links that may be traversed twice are
those connecting one facility with one customer, allowing thus for routes visiting
one single customer. In contrast, in arc routing problems, even required links may
be traversed more than once in optimal solutions. Also, the set of required arcs
induces a family of connected components of G which, as happens in pure arc
routing problems, play an important role in determining which links are susceptible
of being used more than once.
The first paper addressing a LARP is probably that of Levy and Bodin (
1989
)
in which a problem with uncapacitated vehicles arising in the USA postal services
was solved. To this end, the authors split the problem into its components and solve
them sequentially, following the scheme (1) location of facilities, (2) allocation of
required edges to facilities, and (3) route design.
Uncapacitated LARPs were also studied in Ghiani and Laporte (
1998
). One of
the first consequences of having uncapacitated vehicles is that, when the triangle
inequality holds, only one route needs to be built for each open facility. Moreover,
the authors show that, in this case, optimal solutions exist where all the required
edges belonging to the same connected component are served in the same route,
which allows to transform this particular LARP into different arc routing problems,
depending on whether the number of depots to locate is bounded or not. Applying a
branch-and-cut algorithm to these problems, the authors solve uncapacitated LARP
instances on graphs with up to 200 nodes. Since then, no exact algorithm for
any LARP variant has been proposed, and only heuristic algorithms for different
variants can be found in the literature. Actually, two mixed integer programming
formulations for capacitated LARPs were proposed by Doulabi and Seifi (
2013
):
