A Compact Model for the Clustered Orienteering Problem

Abstract

Background: The Clustered Orienteering Problem is an optimization problem faced in last-mile logistics. The aim is, given an available time window, to visit vertices and to collect as much profit as possible in the given time. The vertices to visit have to be selected among a set of service requests. In particular, the vertices belong to clusters, the profits are associated with clusters, and the price relative to a cluster is collected only if all the vertices of a cluster are visited. Any solving methods providing better solutions also imply a new step towards sustainable logistics since companies can rely on more efficient delivery patterns, which, in turn, are associated with an improved urban environment with benefits both to the population and the administration thanks to an optimized and controlled last-mile delivery flow. Methods: In this paper, we propose a constraint programming model for the problem, and we empirically evaluate the potential of the new model by solving it with out-of-the-box software. Results: The results indicate that, when compared to the exact methods currently available in the literature, the new approach proposed stands out. Moreover, when comparing the quality of the heuristic solutions retrieved by the new model with those found by tailored methods, a good performance can be observed. In more detail, many new best-known upper bounds for the cost of the optimal solutions are reported, and several instances are solved to optimality for the first time. Conclusions: The paper provides a new practical and easy-to-implement tool to effectively deal with an optimization problem commonly faced in last-mile logistics.

1. Introduction

The Orienteering Problem (OP) was introduced in [1,2] in the 1980s. In an interpretation of the problem from the viewpoint of logistics, there is a single vehicle, leaving from and returning to a depot, which serves a set of customers, each one associated with a spacial location and profit, with such a profit collected upon visiting the location. The travel times among the locations are known, deterministic, and given. However, not all the customers can typically be serviced, since the vehicle mission cannot be longer than a given maximum time. The aim of the problem is to maximize the total profit collected by the vehicle in the available time. The problem has attracted a lot of attention due to its practical implications, and many variations of the original problem have been introduced over the years. We refer the interested reader to [3,4,5,6] for exhaustive reviews of the scientific literature on these problems. Optimization approaches for last-mile logistics, in general, have become more and more popular in recent years due to the dramatic increase in e-commerce [7], which automatically generates a great need for effective operational solutions [8,9,10,11,12].

A generalization of the OP, called the Clustered Orienteering Problem (COP), was originally proposed in [13], and is the topic of the present study. There is a set of customers that are grouped into clusters. Associated with each cluster there is a profit, which is collected once all customers of the cluster are visited. A classic application of the COP is in last-mile distribution in the retail sector: sometimes contracts allow collection of the profit only if all the warehouses (or shops) of a chain (cluster) are visited. Another typical application is again in last-mile logistics, which is about the collection of goods from the customers in order to aggregate them for further shipping. In this case, the profit is collected only if all the goods planned to be aggregated together (typically to form a container) are collected, otherwise the shipment cannot happen and there is a delay. The growth of e-commerce associated with globalization gives a measure of the impact on the pollution of the activities associated with these logistics problems. It is safe to state that any improvement on their solution is a clear step towards a more sustainable society.

The COP should not be confused with the Set Orienteering Problem [14,15], which shares the same input information, but with a different objective, namely, the profit is collected once a single vertex of a cluster is visited. This problem was introduced to model a different family of last-mile logistics applications.

The first algorithmic approaches to solve the COP were proposed in [13], where exact solving approaches, based on a mixed-integer linear program (MILP) and on a branch-and-cut method were proposed. In the same paper, three different variations of a tabu search heuristic were also proposed to deal with those instances that could not be effectively be treated by the exact solvers. More recently, other heuristic approaches were discussed, respectively, in [16], where a hybrid heuristic (HH) method was proposed, and in [17], where the authors propose a hybrid evolutionary algorithm (HEA). A cutting plane method was introduced as an exact method in [18] for the Clustered Team Orienteering Problem, a version of the COP with multiple vehicles. In the same paper, a generalization of the heuristic algorithm HH is also discussed. A summary of the contributions of these works can be found in

Table 1. Summary of the contributions of the publications dealing with the solving methods for the Clustered Orienteering Problem and its generalizations.

Paper	Exact Methods	Heuristic Methods	Multiple Trucks
Angelelli et al. [13]	Yes	Yes	No
Yahiaoui et al. [16]	No	Yes	No
Yahiaoui et al. [18]	Yes	Yes	Yes
Wu et al. [17]	No	Yes	No
This paper	Yes	No	No

.

In the present work—which is along the line of recent successful applications of constraint programming (CP) to other last-mile logistic problems [19,20]—we introduce a novel exact solving method for the COP, which is able to take advantage of the technologies available in modern solvers and modern hardware. The results achieved indicate that the new approach is able to provide state-of-the-art results, notwithstanding an implementation complexity that is substantially lower than that of the exact methods previously available in the literature, with improved upper bounds for the optimal cost of several instances, and many instances closed here for the first time.

The real-world implications of our results in terms of last-mile logistics derive from the availability of the new tool we make available to practitioners, which allows them to have a better understanding and higher-quality solutions while carrying out operational planning. This, coupled with a better strategic organization, can lead to a more optimized and harmonized logistics, leading to direct social benefits for citizens (higher quality service), providers (less costs), and the cities themselves (less traffic in the urban environment).

2. Problem Description

Let $G=(V,A)$ be a directed graph, where $V=\left\{0\right\}\cup C$ is the set of vertices of the graph and A is the set of arcs. The depot (starting and ending point of the route) is vertex 0, while C is the set of locations of the customers. A set of $m+1$ clusters $C_0,C_1,\cdots ,C_m$ is given, such that $C_i\subseteq C\forall i\in \{0,1,\cdots ,m\}$ and they cover C: (${\bigcup }_{i=0}^m{C}_i=C$). Notice that clusters can overlap. Each vertex $j\in C$ is part of at least one cluster, but it can be part of several. A profit $p_i$ is associated with each cluster $C_i$, and such a profit is collected only if all the vertices $j\in C_i$ are visited. Cluster $C_0$ contains only the depot 0 and has a null profit. A travel time $c_{jk}$ is associated with each arc $(j,k)\in A$, representing travel times, and a maximum time $T_{max}$ is given. The Clustered Orienteering Problem (COP) consists of finding a route on vertices V with a total travel time not longer than $T_{max}$ that maximizes the total profit collected. In the remainder of the paper, we assume—consistently with the previous literature—that the travel times satisfy triangle inequalities. An example with a COP instance and a relative solution is provided in Figure 1.

3. A Model Based on Constraint Programming

The COP can be described through the following constraint programming model, designed according to the syntax of the Google OR-Tools [21] CP-SAT solver [22]. The idea behind the model is to define for each cluster a representative vertex, which will be used to easily identify the visited clusters and to define constraints effectively. Let $r_i$ be the representative of cluster $C_i$. Such a vertex is either selected as one of the vertices belonging solely to cluster $C_i$ or, if such a vertex does not exist, by adding the artificial vertex $a_i$ to the cluster $C_i$ (and to the vertex set V), with distances defined as follows. Let $b_i\ne a_i$ an arbitrary vertex from $C_i$, then we define $c_{a_i{b}_i}=0$ and $c_{j{a}_i}=c_{j{b}_i},c_{a_{i}j}=+\infty \forall j\in V\setminus \{a_i,b_i\}$. In such a way, node $a_i$ can be freely be visited without increasing the length of the tour as soon as node $b_i$ is visited. Building on Figure 1, an example of the creation of an artificial representative vertex is provided in Figure 2, together with the sketch of a relative solution.

In the model, a binary variable $x_{ij}$, with $i,j\in V$, takes value 1 if vertex i is visited right before vertex j in the solution tour, and value 0 otherwise. In case a vertex $i\in C$ is not visited, then $x_{ii}$ is set to 1, and 0 otherwise.

$$\begin{array}{ccc}\hfill & max\sum _{i\in C}{p}_i\neg x_{r_i{r}_i}\hfill & \end{array}$$

(1)

$$\begin{array}{ccc}\hfill s.t.& \mathrm{AddCircuit}(x_{ij};i,j\in V;i\ne 0\vee j\ne 0)\hfill & \end{array}$$

(2)

$$\begin{array}{ccc}\hfill & \sum _{i\in V}\sum _{j\in V,j\ne i}{c}_{ij}{x}_{ij}\le T_{max}\hfill & \end{array}$$

(3)

$$\begin{array}{ccc}\hfill & x_{jj}⟹x_{r_i{r}_i}\hfill & \hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}i\in C,j\in C_i\setminus \left\{r_i\right\}\end{array}$$

(4)

$$\begin{array}{ccc}\hfill & x_{ij}\in \{0;1\}\hfill & \hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}i,j\in V\end{array}$$

(5)

The objective function (1) maximizes the profit collected in the tour. Constraint (2) imposes that the tour associated with the active x variables forms a feasible circuit. This is imposed by the CP-SAT statement AddCircuit that also ensures that $x_{ii}=1$ for each variable $i\in C$ not touched by the circuit itself. Constraint (3) is a budget constraint requiring that the length of the tour described by the active x variables has a length of, at most, $T_{max}$. Constraints (4) use the AddImplication statement (here represented as ⟹) and impose that if a vertex of a cluster is not visited, then also the representative of the cluster cannot be visited. As a consequence, a representative vertex can be visited only if all the nodes of its cluster are visited. This is necessary in order not to overestimate the profit collected in the objective function. Constraints (5) finally define the domain of the variables.

4. Computational Experiments

After having introduced the benchmark set adopted in Section 4.1 and described the experimental settings in Section 4.2, in Section 4.3 we position the new model within the exact methods that have previously appeared in the literature. In Section 4.4, the new best-known results obtained by the model CP are detailed.

4.1. Benchmark Instances

The benchmark instances commonly adopted in the previous COP literature for the exact algorithms are those proposed in [13] and are available at [23]. They are derived from the classic TSPLIB95 instances available at [24]. The instances have a number of vertices ranging between 42 and 318 (as indicated in the names), and the following elements have been added and reflected into the names to make them suitable for the COP (on top of slightly modifying some of the distance matrices):

• Clusters: the number of clusters (field s in the instance name) takes the value of 10, 15, 20, or 25;
• Profits: the profit of a given vertex is generated in two alternative ways ($g1$ or $g2$ in the instance name) based either on the number of vertices in a cluster, or on a pseudo-random value, as explained in details in [13];
• Threshold: two different values are considered for $T_{max}$ ($q2$ or $q3$ in the instance name), which are obtained by considering a fraction of the optimal value of the original TSPLIB95 problem from which the instance is derived, as described in [13].

4.2. Experimental Settings

In this section, we present the results obtained by solving the model we proposed in Section 3 via the CP-SAT solver [22] version 9.8 using standard settings on a computer running an Intel Core i7 12700F processor and equipped with 32 GB of RAM. A maximum computation time of 3600 is allowed for each run, and the solver is launched from scratch without any clue about bounds previously calculated. Notice that we decided to leave out all the preprocessing rules described in [18] when solving the model described in Section 3. The reason is that the remaining rules were either not helping the solver or extremely time-consuming to calculate, and anyway, relying on previously calculated upper and lower bounds, which are normally not available in real applications, when a new instance is faced.

The results are compared with those obtained by all the other methods available in the literature that we are aware of.

The other exact methods we consider are as follows:

• The mixed-integer linear program BASIC presented in [13], with experiments run on a computer with an Intel Xeon W3680 CPU and 12 GB of RAM, using CPLEX 12.2 [25] as a MILP solver. A maximum computation time of 3600 is allowed for each run;
• The branch-and-cut algorithm COP-CLU presented in [13], with experiments run on a computer with an Intel Xeon W3680 CPU and 12 GB of RAM, using CPLEX 12.2 [25] as a MILP solver. A maximum computation time of 3600 is allowed for each run;
• The branch-and-cut algorithm CUT-PLA presented in [18], with experiments run on a computer with an Intel Xeon(R) E2-2670 and 128 GB of RAM, using CPLEX 12.6 [25] as a MILP solver. A maximum computation time of 3600 is allowed for each run. Unfortunately, for this method, only aggregated results are available.

Concerning heuristic approaches, we consider the following:

• The three different tabu search methods COP-TS-∗ discussed in [13] with experiments run on a computer with an Intel Xeon W3680 CPU and 12 GB of RAM;
• The hybrid heuristic HH approach discussed in [16] (see also [18]) with experiments run on a computer with an Intel Xeon X7542 CPU;
• The hybrid evolutionary algorithm HEA presented in [17] with experiments run on a computer with an Intel Core i5-8400 CPU and 16 GB RAM.

4.3. Comparison with Exact Methods

A first comparison of the results obtained by the CP model compared to all the other exact solvers available in the literature, in terms of success and optimality gap, is presented in

Table 2. Comparison against published exact methods—aggregated results.

Classes of Instances	BASIC			COP-CLU			CUT-PLA			CP
	(Angelelli et al. [13])			(Angelelli et al. [13])			(Yahiaoui et al. [18])
	# Opt	Gap %	Sec	# Opt	Gap %	Sec	# Opt	Gap %	Sec	# Opt	Gap %	Sec
dantzig42	16	0.0	8.1	16	0.0	0.6	16	0.0	2.9	16	0.0	4.6
swiss42	16	0.0	6.6	16	0.0	1.0	16	0.0	4.1	16	0.0	5.1
att48	16	0.0	13.2	16	0.0	8.5	16	0.0	34.8	16	0.0	25.9
gr48	16	0.0	11.9	16	0.0	4.9	16	0.0	12.5	16	0.0	18.5
hk48	16	0.0	10.9	16	0.0	5.5	16	0.0	12.4	16	0.0	19.3
eil51	16	0.0	16.7	16	0.0	6.8	16	0.0	16.6	16	0.0	30.2
berlin52	16	0.0	12.0	16	0.0	2.3	16	0.0	10.0	16	0.0	13.9
brazil58	16	0.0	16.4	16	0.0	5.5	16	0.0	26.7	16	0.0	24.0
st70	16	0.0	52.7	16	0.0	57.7	16	0.0	95.7	16	0.0	400.2
eil76	16	0.0	20.2	16	0.0	18.2	16	0.0	25.8	16	0.0	62.6
pr76	16	0.0	94.4	15	0.5	501.7	16	0.0	196.4	16	0.0	276.9
gr96	16	0.0	34.8	16	0.0	23.3	16	0.0	37.2	16	0.0	78.7
rat99	16	0.0	232.4	16	0.0	93.1	16	0.0	159.3	16	0.0	458.6
kroA100	14	3.7	1112.5	16	0.0	279.0	16	0.0	241.0	16	0.0	520.4
kroB100	11	7.0	1386.0	16	0.0	468.6	16	0.0	272.5	16	0.0	762.3
kroC100	11	7.2	1968.0	16	0.0	602.8	15	0.5	746.3	16	0.0	696.5
kroD100	14	2.1	1613.8	16	0.0	647.2	16	0.0	581.6	16	0.0	1022.8
kroE100	13	2.8	1107.8	15	2.1	562.5	16	0.0	179.1	16	0.0	717.3
rd100	10	3.8	1702.8	16	0.0	537.0	16	0.0	225.1	16	0.0	1387.9
eil101	16	0.0	94.0	16	0.0	50.9	16	0.0	116.0	16	0.0	236.5
lin105	16	0.0	104.4	16	0.0	59.4	16	0.0	72.7	16	0.0	184.1
pr107	16	0.0	171.3	16	0.0	61.6	15	1.9	332.5	16	0.0	112.2
gr120	10	4.8	1854.9	15	1.8	948.2	15	0.6	688.8	16	0.0	1013.0
pr124	16	0.0	139.7	16	0.0	78.5	16	0.0	100.5	16	0.0	293.6
bier127	16	0.0	283.8	16	0.0	97.4	16	0.0	92.2	16	0.0	211.0
ch130	5	11.7	2717.6	12	2.6	1844.0	15	0.4	767.3	12	3.1	2480.0
pr136	11	4.6	2024.1	16	0.0	765.1	16	0.0	326.3	16	0.0	1106.1
gr137	16	0.0	144.9	16	0.0	62.9	16	0.0	149.9	16	0.0	204.6
pr144	16	0.0	229.0	16	0.0	119.4	16	0.0	135.7	16	0.0	407.1
ch150	1	37.2	3438.7	0	44.4	3600.7	9	5.8	2098.0	5	13.3	2859.9
kroA150	2	32.5	3488.5	3	32.8	3232.8	10	5.8	1713.4	7	13.9	2641.9
kroB150	1	33.3	3591.2	1	34.6	3571.2	11	5.6	1913.8	6	12.2	2782.9
pr152	16	0.0	266.4	16	0.0	130.0	16	0.0	559.2	16	0.0	545.8
u159	13	1.3	923.5	16	0.0	442.1	14	1.1	1185.8	15	0.1	1844.1
si175	16	0.0	844.0	16	0.0	424.5	16	0.0	315.5	16	0.0	950.3
brg180	16	0.0	597.5	16	0.0	141.5	16	0.0	155.6	16	0.0	422.0
rat195	5	7.5	3020.1	7	8.1	3004.0	10	4.5	1757.7	8	4.9	2821.1
d198	16	0.0	179.5	14	1.4	1035.5	12	3.3	1431.6	16	0.0	1334.7
kroA200	0	62.5	3600.8	0	74.6	3601.0	6	14.7	2562.2	3	24.1	3281.1
kroB200	2	45.6	3471.5	0	64.2	3600.4	6	17.7	2550.0	3	24.6	3142.6
gr202	13	1.3	814.4	13	1.4	1255.6	16	0.0	557.1	15	0.6	1799.6
ts225	0	36.9	3600.5	0	71.2	3600.4	0	27.3	3600.7	0	23.5	3600.0
tsp225	1	26.2	3504.6	3	14.8	3335.7	10	6.8	2461.4	4	8.7	3428.1
pr226	10	11.0	1782.0	14	1.9	1485.8	5	14.4	3066.9	11	10.9	2342.3
gr229	16	0.0	299.6	13	2.1	1645.3	16	0.0	1063.6	14	0.5	2023.9
gil262	0	61.4	3601.5	0	91.8	3601.6	4	19.9	3084.4	1	28.9	3436.3
pr264	8	6.6	2499.8	10	17.5	2105.1	2	35.0	3155.6	8	8.6	3191.0
a280	1	17.6	3415.7	1	23.5	3464.0	2	17.7	3357.5	1	13.4	3424.3
pr299	1	17.6	3569.6	2	54.8	3554.8	1	28.4	3449.9	2	10.9	3421.6
lin318	1	15.3	3543.9	0	53.1	3600.6	1	15.5	3430.7	1	15.4	3563.4
Average	11.2	9.2	1344.8	12.0	12.0	1166.9	12.9	4.5	982.6	12.6	4.3	1312.6

. For each of the exact methods considered, the results after one hour of computation are reported, covering for each class of instances the number of instances solved to optimality over the 16 ones in each group (# Opt); the average optimality gap (Gap %), calculated as $100\left(UB\right(m)-LB(m\left)\right)/UB\left(m\right)$ where $UB\left(m\right)$ and $LB\left(m\right)$ are the upper and lower bounds retrieved by the generic method m at the end of the 3600 s; the average computation time (Sec).

Before commenting the results, some considerations have to be made. First, the different experiments are taken from different papers and made on different computers and using different solvers. These settings inevitably affect the comparison, but we believe the main conclusions remain valid independently of these (inevitable) perturbations. Moreover, no preprocessing rule is used by the methods BASIC, COP-CLU and CP, while an extremely time-consuming preprocessing phase is carried out before CUT-PLA. It involves the solution of multiple maximum clique problems [26], multiple smaller COPs, and relies on pre-calculated tight bounds for the original problem. Unfortunately, the time spent on these very time-consuming activities is not accounted for within the computation times reported. In our opinion, this gives the method CUT-PLA a clear advantage, turning the comparison against it biased. We report the results anyway for the sake of completeness.

The aggregated results presented in Table 2 indicate that the new model CP is competitive with the state-of-the-art exact solvers discussed in the literature. In particular, the statistics indicate that the CP model is able to provide the smallest optimality gap of all the methods, notwithstanding it does not take advantage of the aggressive preprocessing run before the solver CUT-PLA. The latter has slightly better results in terms of the average number of instances solved to optimality, and shorter computation times, although the time of the heavy preprocessing run for CUT-PLA is not accounted for in these figures. The methods BASIC and COP-CLU appear to deliver worse performance, although the fact that for some groups of instances they are the best, indicate that a clear dominance among the approaches is not present.

In Figure 3 and Figure 4, a graphical representation of the results of Table 2 is proposed, in terms of average optimality gaps and computation times. The instances are presented in a non-decreasing order of size, in order to allow considerations on the scalability for the different approaches. For this purpose, quadratic trend lines are also inserted in the charts.

Figure 3 suggests that our proposal CP is the one scaling better among the methods, having a fairly flat curvature of the trend line. In detail, CP emerges as the most effective method on the larger instances, while CUT-PLA is superior on the small and medium ones—always keeping in mind the preprocessing advantage of the latter method mentioned before. The method COP-CLU presents the worst figures in terms of scaling. It is finally interesting to observe the presence of a cluster of hard instances, difficult to solve for all the methods considered, with a size around 150.

Figure 4 highlights that the approach CP we propose appears to have a similar trend to BASIC and COP-CLU in terms of average computation times, although with different spikes, sometimes worse, sometimes better, with a trend line worse than that of BASIC but better than that of COP-CLU. Although it is not possible to draw accurate conclusions about the method CUT-PLA due to the unknown time spent by the method in preprocessing, it appears to be the fastest of all, but with a degradation in performance associated with the larger instances that poses doubts on scalability, as highlighted by the least promising trend line of all.

The detailed results obtained by solving the model CP are available in Appendix A for future reference.

4.4. Improved Best-Known Results

In this section, we compare the results retrieved by CP with the best-known lower and upper bounds for the optimal costs available in the literature, and obtained by all the exact and heuristic methods listed in Section 4.2. The best lower bounds are mainly obtained by the tailored heuristic methods, while the upper bounds are exclusively made available by exact methods. In general, the new CP model was able to retrieve many improved upper bounds with respect to those reported in the previous literature, leading also to the first optimality proof for the solutions of several instances. In the following

Table 3. New best bounds and new optimality proofs.

Instance	s	g	q	Best Known		CP		Instance	s	g	q	Best Known		CP
				LB	UB	UB	Opt					LB	UB	UB	Opt
gr120	15	1	2	49	56.1	49	★	kroB200	15	1	3	123	156.2	139
ch130	25	1	2	52	59.7	59		kroB200	15	2	3	6204	7828.3	7565
ch150	10	1	3	85	105.3	85	★	kroB200	20	1	2	48	106.2	84
ch150	10	2	2	1773	2580.9	1773	★	kroB200	20	1	3	132	166.9	144
ch150	10	2	3	4380	5119.7	4380	★	kroB200	20	2	3	6814	8354.2	8239
ch150	15	2	2	1882	3639.6	1882	★	kroB200	25	1	2	60	120.0	90
ch150	15	2	3	4961	5736.1	5515		kroB200	25	1	3	140	176.8	160
ch150	20	1	2	56	79.3	65		kroB200	25	2	3	7390	8931.2	8671
ch150	20	1	3	114	127.0	117		gr202	15	1	2	124	133.2	124	★
ch150	20	2	2	2781	3913.2	3541		ts225	10	1	2	81	131.4	107
ch150	20	2	3	5665	6524.3	6308		ts225	10	1	3	160	197.3	186
ch150	25	1	2	48	94.1	72		ts225	10	2	2	4058	6613.6	6127
ch150	25	1	3	120	130.7	128		ts225	10	2	3	8036	9680.9	9386
ch150	25	2	2	2597	4593.7	3801		ts225	15	1	2	102	129.2	102	★
kroA150	10	1	3	85	102.2	85	★	ts225	15	1	3	170	198.6	187
kroA150	10	2	3	4379	4990.1	4379	★	ts225	20	1	2	107	136.8	121
kroA150	15	1	2	36	60.0	36	★	ts225	20	1	3	186	206.3	199
kroA150	15	2	2	1882	3302.7	2925		ts225	25	1	2	121	144.0	132
kroA150	20	1	2	40	74.1	59		ts225	25	1	3	187	215.0	209
kroA150	20	1	3	108	127.9	120		ts225	25	2	2	6072	7269.2	7147
kroA150	20	2	2	2109	3634.2	3354		tsp225	10	1	2	107	110.9	108
kroA150	20	2	3	5532	6338.2	6196		tsp225	10	2	2	5274	5591.4	5362
kroA150	25	1	2	48	78.1	64		tsp225	15	1	2	102	112.9	102	★
kroA150	25	1	3	120	128.3	127		tsp225	15	1	3	170	180.9	170	★
kroA150	25	2	2	2424	4003.0	3890		tsp225	20	1	2	107	117.3	108
kroB150	10	1	2	34	38.9	34	★	tsp225	20	1	3	186	187.2	186	★
kroB150	10	1	3	85	105.9	85	★	gil262	10	1	2	61	110.4	61	★
kroB150	10	2	3	4390	5431.1	4390	★	gil262	10	1	3	151	203.9	181
kroB150	15	1	2	36	64.7	48		gil262	10	2	2	3125	5337.1	4640
kroB150	15	1	3	107	116.0	107	★	gil262	10	2	3	7750	10,191.2	9245
kroB150	15	2	2	1882	3654.9	2496		gil262	15	1	2	78	123.6	99
kroB150	15	2	3	5421	5762.8	5421	★	gil262	15	1	3	175	205.9	195
kroB150	20	1	2	45	68.7	59		gil262	15	2	3	8961	10,313.3	10,012
kroB150	20	1	3	112	122.7	117		gil262	20	1	2	76	139.7	121
kroB150	20	2	2	2212	3782.5	3336		gil262	20	1	3	181	214.1	196
kroB150	20	2	3	5733	6222.1	6194		gil262	20	2	3	9184	11,051.5	10,780
kroB150	25	1	2	48	96.3	64		gil262	25	1	2	87	135.0	133
kroB150	25	1	3	119	130.8	128		gil262	25	1	3	188	221.7	215
kroB150	25	2	2	2488	4270.7	3724		gil262	25	2	3	9649	11,393.6	11,283
rat195	10	1	2	87	90.8	87	★	pr264	10	2	2	4682	7196.4	5416
rat195	20	1	3	167	167.3	167	★	pr264	15	2	3	8985	10,164.7	9967
rat195	25	2	2	5695	5948.4	5695	★	a280	10	1	2	128	140.2	128	★
kroA200	10	1	2	44	76.7	44	★	a280	10	1	3	224	230.1	224	★
kroA200	10	1	3	110	140.8	110	★	a280	20	1	2	144	154.0	144	★
kroA200	10	2	2	2258	3698.8	2258	★	a280	20	1	3	224	233.5	224	★
kroA200	10	2	3	5655	7390.1	6660		a280	25	1	2	147	158.4	157
kroA200	15	1	2	48	105.1	78		pr299	10	1	2	136	146.7	136	★
kroA200	15	1	3	124	157.7	139		pr299	10	1	3	236	242.7	238
kroA200	15	2	2	2470	4643.7	4598		pr299	10	2	2	6792	7720.7	7263
kroA200	15	2	3	6200	8056.5	7613		pr299	10	2	3	11,986	12,117.3	12,057
kroA200	20	1	2	48	98.8	84		pr299	15	1	2	132	153.2	153
kroA200	20	1	3	132	178.0	144		pr299	20	1	3	238	253.9	238	★
kroA200	20	2	3	6654	8429.2	8302		pr299	25	1	3	238	257.2	252
kroA200	25	1	2	60	116.7	80		lin318	10	1	2	152	173.5	152	★
kroA200	25	1	3	140	174.0	159		lin318	10	1	3	265	265.2	265	★
kroA200	25	2	3	7170	9118.2	8901		lin318	15	1	2	152	174.3	152	★
kroB200	10	1	3	110	143.1	110	★	lin318	15	1	3	252	271.0	252	★
kroB200	10	2	3	5675	7276.5	6680		lin318	20	1	2	162	176.9	162	★
kroB200	15	1	2	47	89.2	78		lin318	25	1	2	175	184.4	180

, we detail these new state-of-the-art bounds. In the table we indicate, for each instance affected by an improvement, the previous best-known lower and upper bounds, and the upper bounds obtained by the new model CP. In the column Opt, we finally mark (with ★) those instances for which an exact solution is documented for the first time in this study. According to the table, a total of 118 new improved lower bounds are presented, with optimality proven for the first time for 37 of the instances. For the sake of completeness, we report that for 27 of these 37 instances the model CP was able to close the instance, while for the remaining 10 optimality was inferred by comparing the new upper bounds with the lower bounds previously known.

5. Conclusions

In this work, we have considered the Clustered Orienteering Problem, an optimization problem faced in last-mile logistics. The aim is, given an available time window, to select the vertices to visit among a set of service requests in order to maximize the total profit collected. In particular, vertices belong to clusters, and the profits are associated to clusters, and the price relative to a cluster is collected only if all the vertices of such a cluster are visited.

We propose a constraint programming model for the problem and we empirically evaluate the potential of the new model by solving it with out-of-the-box software. The results indicate that, when compared to the exact methods currently available in the literature, the new approach proposed is dominant. Several improved upper bounds are provided in the study, and different instances are closed here for the first time. Overall, we provided an easy-to-implement tool providing well-optimized solutions, which, in turn, translates into a more sustainable logistics organization.

Future work should be in the direction of integrating the new model we propose with the high-performance heuristic methods available in order to enhance the quality of the lower bounds. Moreover, the approach should be extended to deal with the Team Orienteering version of the problem—where several vehicles operate together—and compared with the existing literature on these settings.