# Exact algorithms and heuristics for capacitated covering salesman problems

Lucas Porto Maziero, Fábio Luiz Usberti, Celso Cavellucci
Institute of Computing
Universidade Estadual de Campinas
Campinas
{lucas.maziero, fusberti<EMAIL_ADDRESS>

###### Abstract

This paper introduces the Capacitated Covering Salesman Problem (CCSP),
approaching the notion of service by coverage in capacitated vehicle routing
problems. In CCSP, locations where vehicles can transit are provided, some of
which have customers with demands. The objective is to service customers
through a fleet of vehicles based in a depot, minimizing the total distance
traversed by the vehicles. CCSP is unique in the sense that customers, to be
serviced, do not need to be visited by a vehicle. Instead, they can be
serviced if they are within a coverage area of the vehicle. This assumption is
motivated by applications in which some customers are unreachable (e.g.,
forbidden access to vehicles) or visiting every customer is impractical. In
this work, optimization methodologies are proposed for the CCSP based on ILP
(Integer Linear Programming) and BRKGA (Biased Random-Key Genetic Algorithm)
metaheuristic. Computational experiments conducted on a benchmark of instances
for the CCSP evaluate the performance of the methodologies with respect to
primal bounds. Furthermore, our ILP formulation is extended in order to create
a novel MILP (Mixed Integer Linear Programming) for the Multi-Depot Covering
Tour Vehicle Routing Problem (MDCTVRP). Computational experiments show that
the extended MILP formulation outperformed the previous state-of-the-art exact
approach with respect to optimality gaps. In particular, optimal solutions
were obtained for several previously unsolved instances.

_K_ eywords Covering routing problems $\cdot$ Integer linear programming
$\cdot$ Metaheuristic $\cdot$ Matheuristic

##  1 Introduction

The Capacitated Vehicle Routing Problem (CVRP), initially proposed by Dantzig
and Ramser [1], is one of the most well-known problems in combinatorial
optimization. The goal of CVRP is to service the demands of a set of customers
through a set of vehicles located in a depot, minimizing the total distance
travelled. Each vehicle must depart and return to the depot, and cannot
service more than its capacity [2].

The CVRP encompasses many variants with restrictions of time constraints,
resources availability, and even customers accessibility, for example, regions
of difficult means of entry to vehicles [3, 4]. The latter can be addressed by
considering service by covering. A notion by which a customer can be serviced
remotely as long as the customer is in the covering range of the vehicle. For
example, in Figure 1 customers $b$ and $d$ are within the covering range of
customer $a$. Also, customers $a$ and $e$ can be remotely serviced by vertex
$c$, if there is enough remaining capacity in the corresponding vehicle.

Figure 1: Example of covering ranges.

The first problem using the concept of servicing by coverage is the Covering
Salesman Problem (CSP), by Current and Schilling [5], stated as follows. Given
an undirected graph with cost attributed to the edges, the objective is to
determine a minimum cost cycle such that every vertex out of the cycle is
covered by at least one vertex in the cycle. The CSP generalizes the
Travelling Salesman Problem (TSP) [6] in the case where each vertex only
covers itself, from which follows that CSP is NP-hard.

Generalizations of the CSP were investigated in literature. Golden et al. [7]
proposed a generalization of the CSP in which each vertex has a covering
demand referring to the number of times it must be covered by the tour. Also,
each vertex has a fixed cost that incurs from visiting it. The authors
developed a heuristic with local search that explores exchange, removal, and
insertion neighborhoods.

Gendreau et al. [8] investigated the Covering Tour Problem (CTP), a problem
where the vertices are categorized by those that can be visited $V$, must be
visited $T\subseteq V$, and cannot be visited $W$. The goal of the CTP is to
obtain a minimum cost Hamiltonian cycle over a set of vertices $S\subseteq V$
containing all vertices in $T$ and no vertices in $W$, and each vertex of $W$
is covered by at least one vertex in $S$. Exact and heuristic methodologies
were proposed to solve the problem.

Hachicha et al. [9] introduced the Multi-Vehicle Covering Routing Problem
($m$-CTP). It generalizes the CTP in the sense that there are multiple
vehicles, and each route cannot exceed predefined length and number of
vertices. The $m$-CTP was used as the basis to formulate a problem of locating
distribution centers for humanitarian aid in disaster areas [10].
Methodologies to solve the $m$-CTP include branch-and-cut [11], column
generation [12], branch-and-price [13], constructive heuristics [9],
evolutionary metaheuristic [11], variable neighborhood descent[14].

Allahyari et al. [4] proposed the the Multi-Depot Covering Tour Vehicle
Routing Problem (MDCTVRP). The MDCTVRP is a combination of the Multi-Depot
Vehicle Routing Problem (MDVRP) [15] and CSP. In the MDCTVRP, the demand of
each customer can be served either by visiting the customer directly or by
covering, i.e, the customer location is within a covering range of at least
one visited customer. The authors developed two mixed integer programming
formulations and a hybrid metaheuristic, combining Greedy Randomized Adaptive
Search Procedure (GRASP), Iterated Local Search (ILS) and Simulated Annealing
(SA).

It is worth noticing that the CSP does not have a multi-vehicle variant, as
does the CTP. This work fills this gaps by proposing the Capacitated Covering
Salesman Problem (CCSP), a NP-hard problem generalizing both the CVRP and the
CSP. Vertices with non-negative demands must be covered by a set of
capacitated vehicles, based at the depot. The goal is to find a minimum cost
set of vehicle routes servicing all the demands. The CCSP represents a
straightforward extension of the CSP where the service employed by the
vehicles comes at a limited supply. At the same time, the CCSP generalizes the
CVRP since covering provides an additional way to service each demand. It is
worth pointing out the differences between $m$-CTP and CCSP:

  * •

CCSP considers demands on the vertices;

  * •

$m$-CTP forces some vertices to be visited ($T\subseteq V$);

  * •

$m$-CTP constrains the routes by their lengths and number of vertices, while
in CCSP the vehicle is capacitated by the amount of serviced demand.

  * •

CCSP is a natural generalization of the CSP and the $m$-CTP generalizes the
CTP.

##### Our contributions

Two combinatorial optimization problems, the CSP and the VRP, are combined
into a general framework to address routing problems with multiple vehicles
and limited capacity in the context of service by covering. Mathematical
formulations, using integer linear programming, are provided to represent
these problems as a CCSP. The complexity of solving these problems optimally
asks for heuristic methodologies to tackle large instances that arise from
real applications. This work answers this demand by proposing a biased random-
keys genetic algorithm to solve the CCSP, and a matheuristic to intensify the
search. Furthermore, we extended our ILP to solve the MDCTVRP and conducted
computational experiments on a benchmark of instances, comparing our
formulation with the state-of-the-art exact methodology from literature. The
proposed formulation outperformed the previous approach with respect to
optimality gaps. Moreover, optimal solutions were proven for several
previously unsolved instances.

The CCSP and MDCTVRP share common concepts of covering and vehicle capacity.
Consequently, both can be modeled in a similar manner concerning serving
remotely customers and demands served by the vehicle. Nevertheless, notable
distinctions exist between these problems. In CCSP, a vehicle is not obligated
to serve a customer during its visit, unlike in MDCTVRP, where the vehicle is
required to serve a customer during each visit. Additionally, in CCSP there
are customers with no specified demand, providing an opportunity for vehicles
to use them to serve other customers remotely which have demand. In contrast,
in MDCTVRP every customer is associated with a specific demand.

This paper is organized as follows. Section 2 formally defines the CCSP and
MDCTVRP, presenting ILP formulations for the CCSP and a MILP formulation for
the MDCTVRP. Section 3 describes the BRKGA, and the intra-route and inter-
route intensification procedures. In Section 4, computational experiments are
conducted on a representative set of instances, and results are analyzed and
discussed. Section 5 gives the concluding remarks.

##  2 Mathematical Formulations

###  2.1 Models for the CCSP

Consider a complete undirected graph $G(V,E)$, where each vertex $v\in V$ has
a demand $d_{v}$, each edge $e\in E$ has a metric cost $c_{e}$, and a depot
vertex is denoted by $v_{0}$. Let $V_{0}=V\setminus\\{v_{0}\\}$ and
$V_{d}=\\{v\in V\mathrel{\mathop{\mathchar 58\relax}}d_{v}>0\\}$. There are
$M$ homogeneous vehicles with capacity $Q$ that must service all vertices with
positive demand.

For each vertex $v\in V$, $C(v)$ is the set of vertices that covers $v$ and
$D(v)$ is the set of vertices that are covered by $v$. It is assumed that
$v\in C(v)$ and $v\in D(v)$, $\forall v\in V$.

A route is a nonempty subset $R\subseteq E$ of edges for which the induced
subgraph $G[R]$ is a simple cycle containing $v_{0}$. The goal of CCSP is to
find $M$ routes of minimum cost with the following constraints:

  * •

each vertex is visited no more than once;

  * •

each demand $d_{v}\mathrel{\mathop{\mathchar 58\relax}}v\in V_{d}$ is serviced
by a route $R$, which implies in $v$ or some vertex in $C(v)$ being visited by
$R$, and the demand $d_{v}$ being deducted from the capacity of the vehicle;

  * •

the total demand serviced by any vehicle must not exceed its capacity $Q$.

Figure 2: Optimal solution for the CCSP instance $X$-$n115$-$w11$-$c7$.

Figure 2 shows an optimal solution for a CCSP instance. Routes are depicted
with black lines; the blue triangle is $v_{0}$; red squares are vertices with
positive demand; green points are visited vertices with no demand; arrows show
which route serviced each demand.

The following ILP formulation $CCSP_{1}$ is proposed for the CCSP. We denote
$\delta(v)$ as the edge cut-set of vertex $v$, and $\delta(S)$ the edge cut-
set of a subset $S\subseteq V$. The formulation includes the following
decision variables: $x_{e}\in\mathbb{Z}^{+}$ gives the number of times edge
$e\in E$ is traversed; $y_{v}\in\\{0,1\\}$ denotes if vertex $v\in V$ is
visited (1) or not (0); $z_{uv}\in\\{0,1\\}$ shows if vertex $u\in V_{d}$ is
serviced through vertex $v\in C(u)$ (1) or not (0); $K\in\mathbb{Z}^{+}$ is
the number of vehicles.

$\displaystyle(CCSP_{1})$ $\displaystyle MIN\quad\sum_{e\in E}{c_{e}x_{e}},$
(1) subject to $\displaystyle\sum_{e\in\delta(v_{0})}{x_{e}}=2K,$ (2)
$\displaystyle\sum_{e\in\delta(v)}{x_{e}}=2y_{v}\qquad$ $\displaystyle\forall
v\in V_{0},$ (3) $\displaystyle\sum_{v\in C(u)}{y_{v}}\geqslant 1\qquad$
$\displaystyle\forall u\in V_{d},$ (4) $\displaystyle z_{uv}\leqslant
y_{v}\qquad$ $\displaystyle\forall u\in V_{d},\forall v\in C(u),$ (5)
$\displaystyle\sum_{v\in C(u)}{z_{uv}}=1\qquad$ $\displaystyle\forall u\in
V_{d},$ (6)
$\displaystyle\sum_{e\in\delta(S)}{x_{e}}\geqslant\frac{2}{Q}\sum_{u\in
V_{d}}{\sum_{v\in(S\cap C(u))}{d_{u}z_{uv}}}\qquad$ $\displaystyle\forall
S\subseteq V_{0},$ (7) $\displaystyle x_{e}\in\\{0,1\\}\qquad$
$\displaystyle\forall e\notin\delta(v_{0}),$ (8) $\displaystyle
x_{e}\in\\{0,1,2\\}\qquad$ $\displaystyle\forall e\in\delta(v_{0}),$ (9)
$\displaystyle y_{v}\in\\{0,1\\}\qquad$ $\displaystyle\forall v\in V_{0},$
(10) $\displaystyle z_{uv}\in\\{0,1\\}\qquad$ $\displaystyle\forall u\in
V_{d},\forall v\in C(u),$ (11) $\displaystyle K\in\mathbb{Z}^{+}.$ (12)

The objective function ($1$) minimizes the total cost of the routes.
Constraints ($2$) state that the vertex depot is visited by all $K$ routes.
Constraints ($3$) ensure that the number of edges incident to a vertex $v\in
V_{0}$ is $2$ if $v$ is visited or $0$ otherwise. Constraints ($4$) impose
that each vertex in $V_{d}$ must be covered by at least one route. Constraints
($5$) state that if a vertex $u\in V_{d}$ is serviced by a vertex $v\in C(u)$,
then $v$ is visited. Constraints ($6$) ensure that every vertex $u\in V_{d}$
is serviced by a vertex $v\in C(u)$. Constraints ($7$) impose both the
connectivity and the vehicle capacity by forcing into the solution a
sufficient number of edges to each subset of vertices.

A second formulation, denominated $CCSP_{2}$, can be derived by eliminating
variables $y$ through variable substitution using constraints ($3$).

$\displaystyle(CCSP_{2})$ $\displaystyle MIN\quad\sum_{e\in E}{c_{e}x_{e}},$
subject to $\displaystyle\sum_{e\in\delta(v)}{x_{e}}\geqslant 2z_{uv}\qquad$
$\displaystyle\forall v\in V_{0},\forall u\in V_{d},$ (13)
$\displaystyle\sum_{e\in\delta(v)}{x_{e}}\leqslant 2\sum_{u\in
V_{d}}{z_{uv}}\qquad$ $\displaystyle\forall v\in V_{0},$ (14)
$\displaystyle\sum_{e\in\delta(v)}{x_{e}}\leqslant 2\qquad$
$\displaystyle\forall v\in V_{0},$ (15)
$\displaystyle(2),(6),(7),(8),(9),(11),(12).$

Constraints ($13$), ($14$), and ($15$) impose the correct number of edges
incident to a vertex $v\in V_{0}$ ($2$ if visited or $0$ otherwise).

Preliminary experiments have shown that, even though the $CCSP_{2}$ has fewer
variables than the $CCSP_{1}$, the overall quality of the upper and lower
bounds obtained by $CCSP_{1}$ is better than $CCSP_{2}$. Therefore, only the
$CCSP_{1}$ formulation will be considered in the computational experiments.

###  2.2 Models for a Multi-depot Variant

The Multi-Depot Covering Tour Vehicle Routing Problem (MDCTVRP), proposed by
Allahyari et al. [4], is defined next. Given a directed graph $G=(N,A)$, with
vertices $N=N_{c}\cup N_{d}$, and arcs $A$. Each customer $i\in
N_{c}=\\{1,2,...,n_{c}\\}$ has a positive demand $d_{i}$. Set
$N_{d}=\\{1,...,n_{d}\\}$ contains the depots. Each arc $(i,j)\in A$ has a
positive traversing cost $c_{ij}$. Each customer has to be covered by a route.
Set $C(v)$ represents the vertices that covers $v$. A cost $c^{\prime}_{ij}>0$
is attributed for servicing customer $i$ through $j$. A set of identical
vehicles $P=\\{1,2,...,p\\}$ is available, and $Q$ is the vehicle capacity.
Each depot $k\in N_{d}$ has a limited capacity $H$. Finally, to each depot is
attributed a unique set $P_{k}=\\{1,\ldots,p_{k}\\}$ of vehicles. The
objective of MDCTVRP is to find a minimum cost set of routes, such that all
demands are covered, the vehicles and depots capacities are satisfied, and
each vehicle starts and ends its route in the same depot.

Borrowing ideas from model $CCSP_{1}$ and from the flow-based formulation by
Allahyari et al. [4], we propose a new MILP formulation for the MDCTVRP. The
formulation, henceforth denominated $MDCTVRP_{m}$, includes the following
decision variables: $x_{ij}$ denotes if arc $(i,j)\in A$ is traversed ($1$) or
not ($0$); $y_{v}$ represents if vertex $v\in N_{c}$ is visited ($1$) or not
($0$); $z_{uv}$ shows if vertex $u\in N_{c}$ is serviced by vertex $v\in
N_{c}$ ($1$) or not ($0$); $f_{ij}$ gives the vehicle load while traversing
arc $(i,j)$. We represent $SP$ as the set containing all simple paths
connecting depots. Specifically, $SP_{(st)}\in SP$ denotes the set of all
simple paths between depots $s$ and $t$.

$\displaystyle(MDCTVRP_{m})$ $\displaystyle MIN\quad\sum_{(i,j)\in
A}{c_{ij}x_{ij}}+\sum_{i\in N_{c}}\sum_{j\in N_{c}}c^{\prime}_{ij}z_{ij},$
(16) subject to $\displaystyle\sum_{j\in N_{c}}{x_{jk}}=\sum_{j\in
N_{c}}{x_{kj}}\qquad$ $\displaystyle\forall k\in N_{d},$ (17)
$\displaystyle\sum_{j\in N_{c}}{x_{kj}}\leqslant\mathinner{\\!\left\lvert
P_{k}\right\rvert}\qquad$ $\displaystyle\forall k\in N_{d},$ (18)
$\displaystyle\sum_{j\in N}{x_{jv}}=\sum_{j\in N}{x_{vj}}=y_{v}\qquad$
$\displaystyle\forall v\in N_{c},$ (19) $\displaystyle\sum_{v\in
C(u)}{y_{v}}\geqslant 1\qquad$ $\displaystyle\forall u\in N_{c},$ (20)
$\displaystyle z_{uv}\leqslant y_{v}\qquad$ $\displaystyle\forall u\in
N_{c},\forall v\in C(u),$ (21) $\displaystyle\sum_{j\in N}{x_{vj}}\leqslant
z_{vv}\qquad$ $\displaystyle\forall v\in N_{c},$ (22) $\displaystyle\sum_{v\in
C(u)}{z_{uv}}=1\qquad$ $\displaystyle\forall u\in N_{c},$ (23)
$\displaystyle\sum_{(i,j)\in
SP_{(st)}}{x_{ij}}\leqslant\mathinner{\\!\left\lvert
SP_{(st)}\right\rvert}-1\qquad$ $\displaystyle\forall s,t\in N_{d},s\neq
t,\forall SP_{(st)}\in SP,$ (24) $\displaystyle\sum_{j\in
N}{f_{ji}}=\sum_{j\in N_{c}}{d_{j}z_{ji}}+\sum_{j\in N}{f_{ij}}\qquad$
$\displaystyle\forall i\in N_{c},$ (25) $\displaystyle\sum_{i\in
N_{c}}{f_{ik}}=0\qquad$ $\displaystyle\forall k\in N_{d},$ (26) $\displaystyle
f_{ij}\leqslant(Q-d_{i})x_{ij}\qquad$ $\displaystyle\forall(i,j)\in
A\mathrel{\mathop{\mathchar 58\relax}}i\in N,j\in N_{c},$ (27) $\displaystyle
d_{j}x_{ij}\leqslant f_{ij}\qquad$ $\displaystyle\forall(i,j)\in
A\mathrel{\mathop{\mathchar 58\relax}}i\in N,j\in N_{c},$ (28)
$\displaystyle\sum_{i\in N_{c}}{f_{ki}}\leqslant H\qquad$
$\displaystyle\forall k\in N_{d},$ (29) $\displaystyle
x_{i,j}\in\\{0,1\\}\qquad$ $\displaystyle\forall(i,j)\in A,$ (30)
$\displaystyle y_{v}\in\\{0,1\\}\qquad$ $\displaystyle\forall v\in N_{c},$
(31) $\displaystyle z_{uv}\in\\{0,1\\}\qquad$ $\displaystyle\forall u\in
N_{c},\forall v\in C(u),$ (32) $\displaystyle f_{ij}\in\mathbb{R}^{+}\qquad$
$\displaystyle\forall(i,j)\in A.$ (33)

The objective function ($16$) minimizes the total cost of the routes and
allocations costs. For each depot $k\in N_{d}$, constraints ($17$) impose that
the number of vehicles arriving $k$ must be equal to the number of vehicles
leaving $k$. Constraints ($18$) bound the amount of vehicles arriving each
depot. For each customer $v\in N_{c}$, constraints ($19$) state that the
number of arcs arriving and leaving $v$ is $1$ if $v$ is visited, or $0$
otherwise. Constraints ($20$) impose that each vertex in $N_{c}$ must be
covered by at least one route. Constraints ($21$) state that a vertex $u\in
N_{c}$ can only be serviced through a vertex $v\in C(u)$ if $v$ is visited.
Constraints ($22$) require that if a customer $v\in N_{c}$ is visited by a
vehicle, then its demand is serviced by itself. Constraints ($23$) ensure that
every vertex $u\in N_{c}$ is serviced by a vertex $v\in C(u)$. Constraints
($24$) prevent simple paths between depots, forcing each route to start and
end in the same depot. Constraints ($25$) impose the flow conservation on each
customer $i$. Constraints ($26$) ensure that the vehicle load is zero when
returning to the depot. Constraints ($27$) and constraints ($28$) bound the
vehicle load when traversing arc $(i,j)$. Constraints ($29$) impose that the
capacity of each depot is at most $H$.

The number of decision variables used in the new MILP formulation is
$O(V^{2})$ and the number of decision variables used in the model by Allahyari
et al. [4] is $O(V^{3})$. An $O(V^{2})$ algorithm can separate constraints
($24$) for integer solutions using a lazy constraint strategy. Given a graph
induced by an integer solution, the separation of constraints ($24$) is
performed using Depth-First-Search (DFS) [16]. For every pair $(i,j)$ such
that $i,j\in N_{d}$, a DFS is performed starting from $i$. If $j$ is reached,
the edges from the path between $i$ and $j$ are retrieved and then a
constraint ($24$) is added to the formulation.

##  3 BRKGA for Capacitated Covering Salesman Problem

Guided by the Darwinian principle of the survival of the fittest, the Biased
Random Key Genetic Algorithm (BRKGA) [17] is an evolutionary metaheuristic in
which a population of individuals, representing solutions of a combinatorial
optimization problem, evolves towards the optimal.

Each individual is represented by a chromosome encoded as a vector, in which
each allele is a random key uniformly drawn over the interval $[0,1)$. The
decoder method is the problem-specific component of the BRKGA which is
responsible for mapping a chromosome into a solution.

An initial population of random chromosomes is created and forced into a
selective pressure environment in which the best individuals are more likely
to survive throughout the generations producing offsprings.

The BRKGA partitions the population into elite and non-elite sets, with sizes
determined by fixed parameters. The elite set is composed by the best
individuals; all the remaining individuals form the non-elite set, including
the mutants, i.e., random chromosomes introduced into the population as a form
of diversification.

In each generation, the BRKGA executes the following steps:

  1. 1.

Decode the chromosomes, evaluating their fitness;

  2. 2.

Identify the best individuals to form the elite set;

  3. 3.

Preserve the elite set into the population for the next generation;

  4. 4.

Introduce the mutants in the next generation;

  5. 5.

Generate offsprings through the crossover of elite and non-elite chromosomes,
inserting them in the next generation.

The BRKGA has demonstrated its efficacy as a robust method for addressing
various routing problems [18, 19, 20, 21, 22]. In this sense, the following
sections describe how the BRKGA can be employed to solve the CCSP.

###  3.1 Solution encoding

The solution is encoded as a vector $\mathcal{X}=(x_{1},...,x_{n})$ of size
$n=\mathinner{\\!\left\lvert V_{d}\right\rvert}$, where $x_{i}$ is a random
number in the interval $[0,1)$, for $i=1,\ldots,n$. Each element of
$\mathcal{X}$ represents a vertex of $V_{d}$.

###  3.2 Decoder function

The decoder function takes as input a vector $\mathcal{X}$ and returns a
feasible solution for the CCSP represented by a set of routes $\mathcal{R}$.
Let $\mathcal{X}^{{}^{\prime}}$ be the vector resulting by sorting the keys of
$\mathcal{X}$ in non-decreasing order.

The proposed decoder for the CCSP has two phases, described in the following
sections.

####  3.2.1 First phase - Best Fit Algorithm

The minimum number of vehicles required to service all demands can be
determined by solving a Bin Packing Problem (BPP) [23], which is NP-hard. Our
decoder assigns vertices from $V_{d}$ to vehicles by solving the BPP
approximately, using the Best Fit Algorithm (BFA). The BFA assigns each vertex
to a vehicle with the least residual capacity that can still service the
vertex; if no such vehicle exists, a new one is assigned (Figure 3).

Figure 3: Example of Best Fit Algorithm.

Algorithm 1 presents the BFA pseudo-code applied in the decoder, which can be
implemented using self-balancing search trees leading to a worst-time
complexity of $O(n\lg n)$.

Algorithm 1 Best fit algorithm

Input: a vector $\mathcal{X}^{{}^{\prime}}$.
Output: a set of vehicles $\mathcal{M}=\\{1,\ldots,M\\}$ and their assigned
vertices $\mathcal{A}=\\{A_{1},\ldots,A_{M}\\}$.

1:$m\leftarrow 0;\mathcal{M}\leftarrow\\{\emptyset\\}$;
$\mathcal{A}\leftarrow\\{\emptyset\\}$;

2:for each $x^{\prime}_{i}\in\mathcal{X}^{{}^{\prime}}$ do

3: $v\leftarrow getVertex(i)$ – returns the vertex associated to element
$x^{\prime}_{i}$;

4: if $\left(\exists m\in\mathcal{M}\mathrel{\mathop{\mathchar
58\relax}}\displaystyle\sum_{u\in A_{m}}{d_{u}}\leqslant Q-d_{v}\right)$ then

5: $\displaystyle
m\leftarrow\arg\max_{m^{\prime}\in\mathcal{M}}{\left\\{\sum_{u\in
A_{m}^{\prime}}{d_{u}}\mathrel{\mathop{\mathchar 58\relax}}\sum_{u\in
A_{m}^{\prime}}{d_{u}}\leqslant Q-d_{v}\right\\}}$;

6: $A_{m}\leftarrow A_{m}\cup\\{v\\}$;

7: else

8: $m\leftarrow m+1$;

9: $\mathcal{M}\leftarrow\mathcal{M}\cup\\{m\\}$;

10: $A_{m}\leftarrow\\{v\\}$;

11: $\mathcal{A}\leftarrow\mathcal{A}\cup\\{A_{m}\\}$

####  3.2.2 Second phase - route construction

Consider that route $R_{m}$ of vehicle $m$ is a sequence of vertices
represented as $R_{m}=\\{R_{m}(0),\ldots,R_{m}(r_{m}+1)\\}$, where $R_{m}(i)$
and $r_{m}$ are, respectively, the $i$-th vertex visited by vehicle $m$ and
the number of vertices in $V_{0}$ visited by vehicle $m$. The route starts and
ends at the depot, i.e., $R_{m}(0)=R_{m}(r_{m}+1)=v_{0}$.

The second phase of the decoder creates a route for each vehicle by using the
following insertion cost function,

$\displaystyle
g(v,R_{m})=\min_{i=\\{0,\ldots,r_{m}\\}}{\left\\{c_{(u,v)}+c_{(v,w)}-c_{(u,w)}\mathrel{\mathop{\mathchar
58\relax}}u=R_{m}(i),w=R_{m}(i+1)\right\\}},$

which gives the minimum cost of inserting a vertex $v$ into a route $R_{m}$.

For each vehicle $m\in\mathcal{M}$ and each vertex $u\in A_{m}$, all unvisited
vertices $v\in C(u)$ are considered to be included in route $R_{m}$ by
checking the value of $g(v,R_{m})$ and taking the vertex resulting in the
least cost increment.

Algorithm 2 presents the route construction pseudo-code used in our decoder.

Algorithm 2 Construction of Routes

Input: a set of vehicles $\mathcal{M}=\\{1,\ldots,M\\}$ and their assigned
vertices $\mathcal{A}=\\{A_{1},\ldots,A_{M}\\}$.
Output: a set of routes $\mathcal{R}=\\{R_{1},\ldots,R_{m}\\}$.

1:$\mathcal{R}\leftarrow\emptyset$;

2:

3:for each vehicle $m\in\mathcal{M}$ do

4: $R_{m}(0)\leftarrow\\{v_{0}\\}$;

5:

6: $r_{m}\leftarrow 0$

7:

8: for each $v\in A_{m}$ do

9: ${\displaystyle S\leftarrow\left\\{u\in C(v)\mathrel{\mathop{\mathchar
58\relax}}u\neq R_{m^{\prime}}(u^{\prime}),\forall
m^{\prime}\in\\{1,\ldots,m\\},\forall
u^{\prime}\in\\{1,\ldots,r_{m^{\prime}}\\}\right\\}}$ – set of unvisited
candidates to service $v$

10:

11: $\displaystyle u\leftarrow\operatorname*{arg\,min}_{u^{\prime}\in
S}\left\\{g(u^{\prime},R_{m})\right\\}$ – find best candidate

12:

13: $insert(u,R_{m})$ – insert $u$ in the best position of route $R_{m}$

14:

15: $r_{m}\leftarrow r_{m}+1$

16:

17: $R_{m}(r_{m})\leftarrow\\{v_{0}\\}$;

18:

19: $\mathcal{R}\leftarrow\mathcal{R}\cup\\{R_{m}\\}$;

20:

A vertex $v$ is called redundant if when removed from a route it does not
change the solution feasibility. It occurs when the vertices serviced by $v$
can all be serviced by other vertices in the solution without violating the
capacity of any involved vehicle. After applying Algorithm 2, the decoder
greedily removes redundancies by considering their cost decrease, until a
maximal set of redundancies is removed.

###  3.3 Intra-Route

Once the BRKGA stopping criteria is triggered, the Lin-Kernighan (LK)
heuristic [24] performs the final intra-routes improvements. The LK heuristic
is based on $k$-opt neighborhood, which consists in applying up to $k$ edge
exchanges, and it is considered one of the best local searches for the
Traveling Salesman Problem.

###  3.4 Inter-Route Intensification

Following the ideas of Sartori and Buriol [25], this paper proposes a
matheuristic for the CCSP using a formulation with covering and packing
constraints. Let $F$ be the set of all CCSP feasible routes, $a_{if}$ the
covering matrix where for each pair $(i,f)$, $i\in V_{d}$ and $f\in F$,
$a_{if}=1$ if and only if vertex $i$ is serviced by route $f$, and $b_{if}$
the visiting matrix where for each pair $(i,f)$, $i\in V_{0}$ and $f\in F$,
$b_{if}=1$ if and only if vertex $i$ is visited by route $f$. The formulation
includes the binary variable $\lambda_{f}$, which denotes whether the feasible
route $f\in F$ is used ($1$) or not ($0$).

The formulation reads as follows:

$\displaystyle(Matheuristic)$ $\displaystyle MIN\quad\sum_{f\in
F}{c_{f}\lambda_{f}},$ (34) subject to $\displaystyle\sum_{f\in
F}{a_{if}\lambda_{f}}\geqslant 1\qquad$ $\displaystyle\forall i\in V_{d}$ (35)
$\displaystyle\sum_{f\in F}{b_{if}\lambda_{f}}\leqslant 1\qquad$
$\displaystyle\forall i\in V_{0}$ (36)
$\displaystyle\lambda_{f}\in\\{0,1\\}\qquad$ $\displaystyle\forall f\in F.$

The objective function ($34$) minimizes the costs of the routes. Constraints
($35$) ensure that each vertex in $V_{d}$ must be serviced by at least one
route, while constraints ($36$) impose that every vertex in $V_{0}$ must be
visited by at most one route. Considering that the cardinality of $F$ grows
exponentially, in this work we generate a pool of routes $F^{{}^{\prime}}$ in
the Matheuristic formulation. The pool of routes contains a set of CCSP
feasible routes generated as follows. First, an exhaustive search is conducted
to find every optimal route that services up to three vertices. All of these
routes are included into $F^{{}^{\prime}}$. The remaining routes of
$F^{{}^{\prime}}$ are filled with the elite individuals from the BRKGA
generations, starting from the last generation and continuing until either the
size limit of $F^{{}^{\prime}}$ is reached or all elite individuals from each
BRKGA generation are added to $F^{{}^{\prime}}$.

##  4 Computational Experiments

###  4.1 Instances Benchmark

The instances for the CCSP were obtained from the CVRP instances created by
Christofides and Eilon [26] and Uchoa et al. [27], containing between $101$
and $303$ vertices, and named as $E$-$nA$-$kB$ and $X$-$nA$-$kB$,
respectively. The symbol $A$ gives the number of vertices (with the depot),
and $B$ represents the number of vehicles required to service all the demands.

To generate CCSP instances, the following parameters were used:

  * •

$\mathinner{\\!\left\lvert V_{d}\right\rvert}$: number of vertices with
demand;

  * •

$\mathinner{\\!\left\lvert D(v)\right\rvert}$: covering size, where $v\in
V_{0}$.

The $\mathinner{\\!\left\lvert V_{d}\right\rvert}$ parameter varied in $10\%$,
$20\%$, and $40\%$ of $n$. The vertices with demand consist of the first
$\mathinner{\\!\left\lvert V_{d}\right\rvert}$ vertices, excluding the depot,
of the CVRP instance. It is worth mentioning that all demands associated with
$V_{d}$ remain unchanged in relation to CVRP instance. Similarly, the vehicle
capacity $Q$ in the CCSP instance remains the same as in the CVRP instance.

For each vertex $v\in V_{0}$, the set $D(v)$ is defined by the closest
vertices from $v$. The cardinality of $D(v)$ varied in $7$, $9$, and $11$.

For each CVRP instance, all pairings of $\mathinner{\\!\left\lvert
V_{d}\right\rvert}$ and $\mathinner{\\!\left\lvert D(v)\right\rvert}$ were
considered, resulting in nine combinations and a benchmark of $495$ instances.
A pre-processing was conducted in the set of instances to remove any vertex
$v\in V_{0}$ such that $D(v)\cap V_{d}=\emptyset$.

The MDCTVRP instances were created by Allahyari et al. [4], and they are
divided in small ($120$ instances) and large ($160$ instances). The small
instances contain up to $30$ vertices, and the large instances have up to $90$
vertices. In small instances, the vehicle capacity fluctuates between $140$
and $150$, while in large instances, the vehicle capacity alternates between
$160$ and $170$. The small instances are divided into three categories, and
the large instances are divided into four categories. Each category has eight
different groups of instances. The instances are named InputXYZT, where “X”,
“Y”, “Z”, and “T” give the category, number of depots, vehicle capacity, and
the coverage coefficient (which defines the cost of serving a vertex),
respectively. Five instances were generated for each group of instances.

###  4.2 Computational Settings

The ILP and MILP formulations were implemented and solved using Gurobi 8.1.1
version. The execution time limit were set to a one hour, except for the
$MDCTVRP_{m}$ formulation, which was set to two hours following Allahyari et
al. [4]. The experiments were conducted on a PC under Ubuntu $10.12$, and CPU
Intel Xeon(R) Silver $3114$ $2.20$ GHz, with $32$GB of RAM. The BRKGA
developed for the CCSP used the C++ framework from Resende and Toso [28]. The
parameters used by the BRKGA are listed in Table 1. The implementation of the
LK heuristic proposed by Helsgaun [29] was employed. The matheuristic adopted
a size limit for the pool $F^{{}^{\prime}}$ of $1$ million routes.

Table 1: BRKGA parameters. Parameter | Value
---|---
Population size | 1000
Fraction of population to be elite individuals | 40%
Fraction of population to be replaced by mutants | 20%
Crossover probability | 70%

###  4.3 Evaluated Methodologies

Five methodologies were implemented and evaluated in the computational
experiments:

  * •

$\mathbb{CCSP}_{1}$: solution of the $CCSP_{1}$ model, initially ignoring
Constraints $(7)$, and later including them in the formulation using a lazy
constraint strategy;

  * •

$\mathbb{BRKGA}$: implementation of the BRKGA for the CCSP described in
Section 3;

  * •

$\mathbb{CCSP}_{1s}$: same as $\mathbb{CCSP}_{1}$, however the solution
obtained by the BRKGA is given as warm start for the $CCSP_{1}$ model;

  * •

$Matheuristic$: solution of the matheuristic described in Subsection 3.4;

  * •

$\mathbb{MDCTVRP}_{m}$: solution of the $MDCTVRP_{m}$ formulation, initially
ignoring Constraints ($24$), and including them on-demand in the formulation
using a lazy constraint strategy.

The $\mathbb{MDCTVRP}_{m}$ was compared with the flow-based formulation
($F_{flow}$) and node-based formulation ($F_{node}$), both proposed by
Allahyari et al. [4], which are the state-of-the-art exact methodologies for
the MDCTVRP, to the best of our knowledge.

###  4.4 Results for the CCSP

Full experimental data, results, instances, and source codes are available on-
line111http://www.ic.unicamp.br/~fusberti/problems/ccsp. The results of the
computational experiments show that the $\mathbb{CCSP}_{1}$ methodology was
able to obtain upper bounds for $430$ out of $495$ instances. In addition, the
$\mathbb{CCSP}_{1}$ methodology proved optimality for $71$ instances size up
to $101$ vertices. Analyzing the results of the $\mathbb{BRKGA}$ methodology,
we can note that for $407$ instances, the obtained solutions were better than
the upper bounds obtained by $\mathbb{CCSP}_{1}$.

With respect to methodologies $\mathbb{CCSP}_{1s}$ and $Matheuristic$, the
results show that the matheuristic was more effective to improve the solutions
obtained from $\mathbb{BRKGA}$. $Matheuristic$ methodology improved the BRKGA
solutions for $187$ out of $495$ instances, while $\mathbb{CCSP}_{1s}$
improved for $88$ instances. The average cost of improvements made by
$\mathbb{CCSP}_{1s}$ and $Matheuristic$ on BRKGA solutions were approximately
$1.69\%$ and $2.3\%$, respectively.

Figure 4 shows, for each methodology, the percentage of solved instances in
function of the deviation from the best upper bound ($(\frac{UB-
BestUB}{UB})*100$). The performance profile clearly shows the $\mathbb{BRKGA}$
dominating $\mathbb{CCSP}_{1}$ with respect to upper bounds. The
$\mathbb{BRKGA}$ obtained the best solutions for approximately $48\%$ of
instances, while the $\mathbb{CCSP}_{1}$ obtained for approximately $16\%$ of
instances. The $\mathbb{CCSP}_{1s}$ was able to improve the warm start
$\mathbb{BRKGA}$ solution for several instances, obtaining the best solutions
for approximately $58\%$ of instances. Finally, comparing methodologies
$Matheuristic$ and $\mathbb{CCSP}_{1s}$, $Matheuristic$ was more effective in
improving the BRKGA solutions. The $Matheuristic$ methodology obtained the
best solution for approximately $74\%$ of instances, outperforming
$\mathbb{CCSP}_{1s}$.

Figure 4: Performance profiles in terms of deviation ($\%$) from the best
upper bound.

###  4.5 Results for the MDCTVRP

Tables LABEL:tab:mdctvrpSmallInstances and LABEL:tab:mdctvrpLargeInstances
report the results for the small and large instances, respectively. Table
LABEL:tab:mdctvrpSmallInstances reports for each methodology and for each
group of small-size instances, the average gap (Avg.gap), the number of
optimal solutions (#Opt), and the average running time (Avg.time).

For small instances, the overall optimality gaps were $0.10\%$, $8.99\%$, and
$30.28\%$ for the $\mathbb{MDCTVRP}_{m}$, $F_{flow}$, and $F_{node}$
methodologies, respectively. From $120$ small instances, $117$, $10$, and $4$
optimal solutions were obtained by $\mathbb{MDCTVRP}_{m}$, $F_{flow}$, and
$F_{node}$, respectively.

Table LABEL:tab:mdctvrpLargeInstances gives the results from
$\mathbb{MDCTVRP}_{m}$ for each group of large-size instances. The column
group $\mathbb{MDCTVRP}_{m}$ reports the averages upper bound (Avg.ub), lower
bound (Avg.lb), optimality gap (Avg.gap), running time (Avg.time), and number
of optimal solutions (#Opt). The column group GRASP x ILS [4] reports the
results obtained by the hybrid meta-heuristic proposed by Allahyari et al.
[4]. “Avg” gives the average cost obtained over five executions for each
instance. Avg.gapLP and Avg.gap ${}_{\mathbb{MDCTVRP}_{m}}$ give the “Avg” gap
from the linear relaxation of $F_{flow}$ formulation, and the average lower
bound (Avg.lb) of $\mathbb{MDCTVRP}_{m}$, respectively.

It should be noticed that, due to the large number of variables, Allahyari et
al. [4] have not executed experiments on large instances with $F_{flow}$. The
computational results have shown that $\mathbb{MDCTVRP}_{m}$ achieved good
lower bounds for large. Previously, the GRASP x ILS overall gap with respect
to the linear programming relaxation of $F_{flow}$ was $20.98\%$, while with
the new lower bounds obtained by $\mathbb{MDCTVRP}_{m}$ the GRASP x ILS
overall gap was improved to $7.98\%$. It is worth noting that even though
$\mathbb{MDCTVRP}_{m}$ is an exact methodology, the upper bounds were close to
the solutions cost obtained by the GRASP x ILS. More specifically, the
solutions cost obtained by GRASP x ILS are, on average, only $1.37\%$ apart
from the upper bounds obtained by $\mathbb{MDCTVRP}_{m}$.

Table 2: Results of computational experiments for the small-size instances. |  |  | $\mathbb{MDCTVRP}_{m}$ |  | $F_{flow}$ |  | $F_{node}$
---|---|---|---|---|---|---|---
Category | Group |  | Avg.gap | #Opt | Avg.time |  | Avg.gap | #Opt | Avg.time |  | Avg.gap | #Opt | Avg.time
1 | Input1000 |  | 0.00 | 5 | 8.00 |  | 6.37 | 0 | 7200.00 |  | 22.25 | 0 | 7200.00
Input1001 |  | 0.00 | 5 | 8.80 |  | 6.38 | 0 | 7200.00 |  | 21.29 | 0 | 7200.00
Input1010 |  | 0.00 | 5 | 6.60 |  | 1.74 | 2 | 6015.00 |  | 17.71 | 0 | 7200.00
Input1011 |  | 0.00 | 5 | 5.20 |  | 2.48 | 1 | 7066.00 |  | 18.63 | 0 | 7200.00
Input1100 |  | 0.00 | 5 | 7.00 |  | 4.96 | 2 | 5621.00 |  | 14.19 | 1 | 7200.00
Input1101 |  | 0.00 | 5 | 6.80 |  | 4.87 | 1 | 5848.00 |  | 12.44 | 1 | 7200.00
Input1110 |  | 0.00 | 5 | 5.80 |  | 3.14 | 2 | 5504.00 |  | 13.85 | 1 | 7200.00
Input1111 |  | 0.00 | 5 | 6.20 |  | 2.03 | 2 | 5220.00 |  | 11.57 | 1 | 7200.00
2 | Input2000 |  | 0.00 | 5 | 140.20 |  | 10.56 | 0 | 7200.00 |  | 42.30 | 0 | 7200.00
Input2001 |  | 0.00 | 5 | 184.60 |  | 10.81 | 0 | 7200.00 |  | 38.64 | 0 | 7200.00
Input2010 |  | 0.00 | 5 | 70.20 |  | 10.39 | 0 | 7200.00 |  | 37.45 | 0 | 7200.00
Input2011 |  | 0.00 | 5 | 115.40 |  | 11.14 | 0 | 7200.00 |  | 33.94 | 0 | 7200.00
Input2100 |  | 0.00 | 5 | 66.60 |  | 7.98 | 0 | 7200.00 |  | 31.33 | 0 | 7200.00
Input2101 |  | 0.00 | 5 | 138.20 |  | 7.63 | 0 | 7200.00 |  | 27.85 | 0 | 7200.00
input2110 |  | 0.00 | 5 | 73.20 |  | 9.02 | 0 | 7200.00 |  | 28.45 | 0 | 7200.00
Input2111 |  | 0.00 | 5 | 44.60 |  | 9.55 | 0 | 7200.00 |  | 27.43 | 0 | 7200.00
3 | Input3000 |  | 1.01 | 4 | 2653.20 |  | 14.48 | 0 | 7200.00 |  | 50.29 | 0 | 7200.00
Input3001 |  | 0.71 | 4 | 2853.20 |  | 14.93 | 0 | 7200.00 |  | 44.15 | 0 | 7200.00
Input3010 |  | 0.00 | 5 | 1865.80 |  | 15.23 | 0 | 7200.00 |  | 44.46 | 0 | 7200.00
Input3011 |  | 0.58 | 4 | 1923.60 |  | 14.29 | 0 | 7200.00 |  | 41.20 | 0 | 7200.00
Input3100 |  | 0.00 | 5 | 288.20 |  | 12.95 | 0 | 7200.00 |  | 39.75 | 0 | 7200.00
Input3101 |  | 0.00 | 5 | 246.40 |  | 11.83 | 0 | 7200.00 |  | 35.90 | 0 | 7200.00
Input3110 |  | 0.00 | 5 | 383.60 |  | 12.25 | 0 | 7200.00 |  | 36.70 | 0 | 7200.00
Input3111 |  | 0.00 | 5 | 492.20 |  | 10.85 | 0 | 7200.00 |  | 35.00 | 0 | 7200.00
Average |  |  | 0.10 |  | 483.07 |  | 8.99 |  | 6869.75 |  | 30.28 |  | 7200.00
Table 3: Results of computational experiments for the large-size instances. |  |  | $\mathbb{MDCTVRP}_{m}$ |  | GRASP x ILS [4]
---|---|---|---|---|---
Category | Group |  | Avg.ub | Avg.lb | Avg.gap | #Opt | Avg.time |  | Avg | Avg.gapLP | Avg.gap${}_{\mathbb{MDCTVRP}_{m}}$
4 | Input4000 |  | 799.45 | 751.98 | 6.22 | 0 | 7200.00 |  | 796.21 | 19.30 | 5.88
Input4001 |  | 808.23 | 764.91 | 5.55 | 0 | 7200.00 |  | 806.95 | 18.57 | 5.50
Input4010 |  | 787.18 | 729.22 | 7.86 | 0 | 7200.00 |  | 775.66 | 19.68 | 6.37
Input4011 |  | 792.13 | 744.53 | 6.26 | 0 | 7200.00 |  | 787.64 | 19.12 | 5.79
Input4100 |  | 737.27 | 692.92 | 6.24 | 0 | 7200.00 |  | 733.72 | 21.90 | 5.89
Input4101 |  | 750.94 | 701.21 | 6.98 | 0 | 7200.00 |  | 745.62 | 20.91 | 6.33
Input4110 |  | 721.12 | 678.30 | 6.09 | 1 | 6650.80 |  | 711.94 | 21.26 | 4.96
Input4111 |  | 730.01 | 689.79 | 5.72 | 0 | 7200.00 |  | 728.17 | 21.03 | 5.56
5 | Input5000 |  | 899.58 | 815.45 | 10.27 | 0 | 7200.00 |  | 880.01 | 19.80 | 7.92
Input5001 |  | 903.58 | 829.00 | 8.95 | 0 | 7200.00 |  | 895.99 | 18.93 | 8.08
Input5010 |  | 869.08 | 784.04 | 10.82 | 0 | 7200.00 |  | 857.27 | 21.41 | 9.34
Input5011 |  | 886.07 | 800.62 | 10.63 | 0 | 7200.00 |  | 873.99 | 20.46 | 9.16
Input5100 |  | 810.75 | 732.59 | 10.65 | 0 | 7200.00 |  | 796.88 | 22.12 | 8.78
Input5101 |  | 827.35 | 748.43 | 10.52 | 0 | 7200.00 |  | 813.70 | 20.85 | 8.72
Input5110 |  | 785.86 | 711.22 | 10.51 | 0 | 7200.00 |  | 777.99 | 23.23 | 9.39
Input5111 |  | 804.80 | 728.69 | 10.37 | 0 | 7200.00 |  | 794.78 | 21.71 | 9.07
6 | Input6000 |  | 1005.58 | 922.85 | 8.88 | 0 | 7200.00 |  | 997.18 | 20.01 | 8.05
Input6001 |  | 1037.50 | 936.43 | 10.75 | 0 | 7200.00 |  | 1016.10 | 19.43 | 8.51
Input6010 |  | 987.04 | 898.72 | 9.63 | 0 | 7200.00 |  | 968.81 | 20.59 | 7.80
Input6011 |  | 998.51 | 916.29 | 8.83 | 0 | 7200.00 |  | 989.60 | 20.16 | 8.00
Input6100 |  | 955.65 | 875.82 | 9.07 | 0 | 7200.00 |  | 946.88 | 20.63 | 8.11
Input6101 |  | 984.79 | 893.52 | 10.09 | 0 | 7200.00 |  | 967.23 | 20.11 | 8.25
Input6110 |  | 936.80 | 848.97 | 10.27 | 0 | 7200.00 |  | 920.24 | 21.58 | 8.40
Input6111 |  | 953.62 | 867.56 | 9.88 | 0 | 7200.00 |  | 939.51 | 20.77 | 8.29
7 | Input7000 |  | 1031.77 | 930.53 | 10.79 | 0 | 7200.00 |  | 1013.92 | 21.35 | 8.96
Input7001 |  | 1047.06 | 935.57 | 11.88 | 0 | 7200.00 |  | 1019.34 | 20.89 | 8.95
Input7010 |  | 1012.71 | 905.58 | 11.78 | 0 | 7200.00 |  | 989.22 | 21.90 | 9.24
Input7011 |  | 1018.47 | 910.80 | 11.83 | 0 | 7200.00 |  | 995.08 | 21.47 | 9.25
Input7100 |  | 933.58 | 842.19 | 10.81 | 0 | 7200.00 |  | 918.91 | 22.90 | 9.11
Input7101 |  | 948.35 | 849.03 | 11.65 | 0 | 7200.00 |  | 924.61 | 22.39 | 8.90
Input7110 |  | 917.68 | 830.41 | 10.51 | 0 | 7200.00 |  | 904.92 | 23.56 | 8.97
Input7111 |  | 919.48 | 832.89 | 10.37 | 0 | 7200.00 |  | 915.05 | 23.24 | 9.86
Average |  |  | 893.81 | 815.63 | 9.40 |  |  |  | 881.35 | 20.98 | 7.98

##  5 Final Remarks

This work proposes the Capacitated Covering Salesman Problem (CCSP), a problem
that approaches the notion of coverage in vehicle routing problems. Two ILP
formulations and a BRKGA are proposed to solve the CCSP. From the set of
instances for the CVRP [26, 27], a benchmark of instances for CCSP was
generated.

Computational experiments conducted on a benchmark of $198$ instances for CCSP
evaluated the ILP formulation and the BRKGA. The results show the
effectiveness of the BRKGA in obtaining upper bounds for all instances. The
$CCSP_{1}$ obtained optimal solutions for $71$ instances, with up to $101$
vertices.

Furthermore, a new MILP formulation is proposed for the Multi-Depot Covering
Tour Vehicle Routing Problem (MDCTVRP). Computational experiments were
conducted on a benchmark of $280$ instances from literature. The overall
results show unequivocally the new formulation outperforming the best known
exact methodology from literature, obtaining $118$ new optimal solutions and
improving all known lower bounds.

Future works should focus on valid inequalities and a branch-and-cut framework
for the solution of CCSP and MDCTVRP. Another promising field of research is
to consider multi-objective vehicle routing problem with covering range being
the additional objective function.

## Acknowledgments

This work was supported by CAPES, CNPq, and Fapesp (grants 140960/2017-1,
314384/2018-9, 435520/2018-0, 2015/11937-9).

## References

  * [1] George B Dantzig and John H Ramser.  The truck dispatching problem.  Management science, 6(1):80–91, 1959.
  * [2] Jean-François Cordeau, Gilbert Laporte, Martin WP Savelsbergh, and Daniele Vigo.  Vehicle routing.  Handbooks in operations research and management science, 14:367–428, 2007.
  * [3] Bruce L Golden, Subramanian Raghavan, and Edward A Wasil.  The vehicle routing problem: latest advances and new challenges, volume 43.  Springer Science & Business Media, 2008.
  * [4] Somayeh Allahyari, Majid Salari, and Daniele Vigo.  A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem.  European Journal of Operational Research, 242(3):756–768, 2015.
  * [5] John R Current and David A Schilling.  The covering salesman problem.  Transportation science, 23(3):208–213, 1989.
  * [6] David L. Applegate, Robert E. Bixby, Vasek Chvatal, and William J. Cook.  The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics).  Princeton University Press, Princeton, NJ, USA, 2007.
  * [7] Bruce Golden, Zahra Naji-Azimi, S Raghavan, Majid Salari, and Paolo Toth.  The generalized covering salesman problem.  INFORMS Journal on Computing, 24(4):534–553, 2012.
  * [8] Michel Gendreau, Gilbert Laporte, and Frédéric Semet.  The covering tour problem.  Operations Research, 45(4):568–576, 1997.
  * [9] Mondher Hachicha, M John Hodgson, Gilbert Laporte, and Frédéric Semet.  Heuristics for the multi-vehicle covering tour problem.  Computers & Operations Research, 27(1):29–42, 2000.
  * [10] Zara Naji-Azimi, Jacques Renaud, Angel Ruiz, and Majid Salari.  A covering tour approach to the location of satellite distribution centers to supply humanitarian aid.  European Journal of Operational Research, 222(3):596–605, 2012.
  * [11] Minh Hoang Ha, Nathalie Bostel, André Langevin, and Louis-Martin Rousseau.  An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices.  European Journal of Operational Research, 226(2):211–220, 2013.
  * [12] Keisuke Murakami.  A column generation approach for the multi-vehicle covering tour problem.  In Automation Science and Engineering (CASE), 2014 IEEE International Conference on, pages 1063–1068. IEEE, 2014.
  * [13] Nicolas Jozefowiez.  A branch-and-price algorithm for the multivehicle covering tour problem.  Networks, 64(3):160–168, 2014.
  * [14] Manel Kammoun, Houda Derbel, Mostapha Ratli, and Bassem Jarboui.  An integration of mixed vnd and vns: the case of the multivehicle covering tour problem.  International Transactions in Operational Research, 24(3):663–679, 2017.
  * [15] Frank A Tillman.  The multiple terminal delivery problem with probabilistic demands.  Transportation Science, 3(3):192–204, 1969.
  * [16] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms.  MIT press, 2022.
  * [17] José Fernando Gonçalves and Mauricio GC Resende.  Biased random-key genetic algorithms for combinatorial optimization.  Journal of Heuristics, 17(5):487–525, 2011.
  * [18] Efrain Ruiz, Valeria Soto-Mendoza, Alvaro Ernesto Ruiz Barbosa, and Ricardo Reyes.  Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm.  Computers & Industrial Engineering, 133:207–219, 2019.
  * [19] Alberto F Kummer N, Luciana S Buriol, and Olinto CB de Araújo.  A biased random key genetic algorithm applied to the vrptw with skill requirements and synchronization constraints.  In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pages 717–724, 2020.
  * [20] Levi R Abreu, Roberto F Tavares-Neto, and Marcelo S Nagano.  A new efficient biased random key genetic algorithm for open shop scheduling with routing by capacitated single vehicle and makespan minimization.  Engineering Applications of Artificial Intelligence, 104:104373, 2021.
  * [21] Alberto F Kummer, Olinto CB de Araújo, Luciana S Buriol, and Mauricio GC Resende.  A biased random-key genetic algorithm for the home health care problem.  International Transactions in Operational Research, 2022.
  * [22] Saúl Domínguez-Casasola, José Luis González-Velarde, Yasmín Á Ríos-Solís, and Kevin Alain Reyes-Vega.  The capacitated family traveling salesperson problem.  International Transactions in Operational Research, 2023.
  * [23] H Kellerer, U Pferschy, and D Pisinger.  Knapsack Problems, volume 1.  Springer-Verlag Berlin Heidelberg, 2004.
  * [24] Shen Lin and Brian W Kernighan.  An effective heuristic algorithm for the traveling-salesman problem.  Operations research, 21(2):498–516, 1973.
  * [25] Carlo S Sartori and Luciana S Buriol.  A matheuristic approach to the pickup and delivery problem with time windows.  In International Conference on Computational Logistics, pages 253–267. Springer, 2018.
  * [26] Nicos Christofides and Samuel Eilon.  An algorithm for the vehicle-dispatching problem.  Journal of the Operational Research Society, 20(3):309–318, 1969.
  * [27] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian.  New benchmark instances for the capacitated vehicle routing problem.  European Journal of Operational Research, 257(3):845–858, 2017.
  * [28] Rodrigo F Toso and Mauricio GC Resende.  A c++ application programming interface for biased random-key genetic algorithms.  Optimization Methods and Software, 30(1):81–93, 2015.
  * [29] Keld Helsgaun.  An effective implementation of the lin–kernighan traveling salesman heuristic.  European Journal of Operational Research, 126(1):106–130, 2000.