Constrained Clustering for the Capacitated Vehicle Routing Problem (CC-CVRP)

Figures & data

Figure 1. CC-CVRP example (step 1): two vehicles starting from a warehouse serve five customers assigned to three clusters.

Figure 2. CC-CVRP example (step 2): the minimum cost routes of the vehicles assigned to clusters are determined by solving seperate TSPs.

Table 1. Nomenclature

Sets	Description
$U{ }^{\mathrm{\prime }}$	$U{ }^{\mathrm{\prime }}=\{1,\dots ,n\}$ is the set of all customers.
Parameter	Description
$q_k$	aggregate customer demand of the $k$-th cluster
$d_{kl}$	distance between the cluster heads of the $k$-th and the $l$-th clusters
$u_i$	location of $i$-th customer
$K$	set of clusters
$R$	maximum searching radius (maximum allowed distance between a customer and a cluster head)
$W$	maximum number of customers that can belong to a single cluster
$V$	number of available vehicles
$Q$	vehicle capacity
${\mu }_i$	demand of customer $i$
$n$	number of customers
Variable	Description
${\theta }_k$	load of the vehicle after visiting the $k$-th cluster.
$y_{kl}$	{0,1} variable indicating whether traveling from cluster head $k$ to cluster head $l$ is part of the solution
$c_k$	location of $k$-th cluster head
$A_k$	set of customer locations associated with the $k$-th cluster $A_k=\{u_i|i\in k\}$
$a_k$	the set of customers that belong to the $k$-th cluster

Figure 3. CC-CVRP example (step 1): Customers are ordered by distance. In this way, customers that are assigned to another cluster are the most distant ones from the centroid.

Figure 4. Implementation overview of the CC-CVRP approach.

Table 2. Performance evaluation for the class A instances of Augerat et al. (1995) reported in http://vrp.galgos.inf.puc-rio.br

instance	tightness	dispersion	best known	proven	CC-CVRP		CVRP
			solution	optimal
					solution	optimality	solution	optimality
						gap (%)		gap (%)
A-n32-k5	4.1	49.40	784	yes	832	6.1	797	1.7
A-n33-k5	4.5	54.10	661	yes	691	4.6	776	17.4
A-n33-k6	5.4	53.40	742	yes	812	9.4	812	9.4
A-n34-k5	4.6	52.27	778	yes	796	2.3	857	10.2
A-n36-k5	4.4	51.29	799	yes	849	6.3	870	8.9
A-n37-k5	4.1	49.33	669	yes	717	7.2	673	0.7
A-n37-k6	5.7	48.83	949	yes	1061	11.8	1025	8
A-n38-k5	4.8	50.19	730	yes	827	13.3	837	14.6
A-n39-k5	4.8	50.57	822	yes	895	8.9	846	2.9
A-n39-k6	5.3	48.42	831	yes	907	9.2	902	8.6
A-n44-k6	5.7	50.97	937	yes	1034	10.4	1032	10.1
A-n45-k7	6.3	48.77	1146	yes	1208	5.4	1167	1.8
A-n46-k7	6.0	50.10	914	yes	1029	12.5	1057	15.7
A-n48-k7	6.3	50.17	1073	yes	1158	7.9	1168	8.9
A-n53-k7	6.6	49.31	1010	yes	1204	19.2	1119	10.8
A-n54-k7	6.7	48.82	1167	yes	1254	7.5	1288	10.4
A-n55-k9	8.4	49.42	1073	yes	1205	12.3	1174	9.4
A-n60-k9	8.3	48.45	1354	yes	1504	11.1	1523	12.5
A-n61-k9	8.9	49.12	1034	yes	1301	25.8	1720	66.3
A-n62-k8	7.3	49.16	1288	yes	1402	8.9	1414	9.8
A-n63-k9	9.3	49.38	1616	yes	1827	13	1827	13.1
A-n63-k10	9.3	49.47	1314	yes	1420	8.1	1436	9.3
A-n64-k9	8.5	49.04	1401	yes	1545	10.3	1515	8.1
A-n65-k9	8.8	47.26	1174	yes	1358	15.7	1284	9.4
A-n69-k9	8.5	48.64	1159	yes	1241	7.1	1231	6.2
A-n80-k10	9.4	49.63	1763	yes	1910	8.3	1959	11.1
Average						10.1		11.4

Table 3. Comparison of CC-CVRP solutions computed in up to 100 seconds and the FCM solutions of Shalaby, Mohammed, and Kassem (2021) computed in up to 15 minutes

instance	best known solution	CC-CVRP	Original FCM
A-n32-k5	784	832	840
A-n33-k6	742	812	769
A-n36-k5	799	849	857
A-n33-k5	661	691	695
A-n39-k6	831	895	876

Table 4. Performance evaluation for the instances of class X for $100<n<350$ reported in http://vrp.galgos.inf.puc-rio.br

instance	tightness	dispersion	best known solution	proven optimal	CC-CVRP
					solution	optimality
						gap (%)
X-n101-k25	25.0	51.12	27591	yes	29838	8.1
X-n106-k14	13.1	64.67	26362	yes	27515	4.4
X-n110-k13	12.4	48.75	14971	yes	16885	12.8
X-n120-k6	5.7	49.46	13332	yes	14279	7.1
X-n125-k30	29.4	60.09	55539	yes	58535	5.4
X-n129-k18	17.1	49.51	28940	yes	32101	10.9
X-n134-k13	12.8	63.15	10916	yes	12319	12.9
X-n139-k10	9.8	47.99	13590	yes	15973	17.5
X-n148-k46	45.4	51.51	43448	yes	45358	4.4
X-n157-k13	13.0	71.20	16876	yes	17751	5.2
X-n162-k11	10.4	51.06	14138	yes	15354	8.6
X-n167-k10	9.3	48.70	20557	yes	22891	11.4
X-n172-k51	50.3	50.54	45607	yes	48406	6.1
X-n181-k23	22.5	58.34	25569	yes	26315	2.9
X-n186-k15	14.2	48.60	24145	yes	27121	12.3
X-n190-k8	7.6	74.32	16980	yes	18168	7
X-n195-k51	50.9	50.42	44225	yes	48409	9.5
X-n200-k36	35.5	70.58	58578	yes	60922	4
X-n204-k19	18.1	54.57	19565	yes	22157	13.2
X-n209-k16	15.3	48.84	30656	yes	33128	8.1
X-n214-k11	11.0	53.94	10856	yes	13163	21.2
X-n219-k73	72.7	48.18	117595	yes	118305	0.6
X-n223-k34	33.4	50.52	40437	yes	44187	9.3
X-n228-k23	16.0	51.70	25742	yes	28649	11.3
X-n233-k16	13.1	48.45	19230	yes	21346	11
X-n237-k14	47.3	48.66	27042	yes	29594	9.4
X-n242-k48	27.1	55.36	82751	yes	87106	5.3
X-n251-k28	27.1	55.18	38684	yes	40661	5.1
X-n256-k16	15.9	51.41	18839	no	20623	9.5
X-n261-k13	12.4	48.77	26558	yes	30318	14.2
X-n266-k58	57.6	52.36	75478	yes	78460	4
X-n270-k35	34.9	51.57	35291	yes	37116	5.2
X-n275-k28	27.4	54.18	21245	yes	22666	6.7
X-n280-k17	16.8	48.72	33503	no	37602	12.2
X-n284-k15	14.0	54.38	20215	yes	22953	13.5
X-n289-k60	59.8	50.84	95151	yes	100104	5.2
X-n294-k50	49.6	48.34	47161	no	51941	10.1
X-n298-k31	30.7	48.26	34231	yes	39052	14.1
X-n303-k21	20.1	59.65	21736	no	24867	14.4
X-n308-k13	12.7	49.47	25859	no	29168	12.8
X-n313-k71	70.7	54.00	94043	no	101650	8.1
X-n317-k53	52.7	62.73	78355	yes	79023	0.9
X-n322-k28	27.7	48.55	29834	yes	34597	16
X-n327-k20	19.2	51.13	27532	no	30735	11.6
X-n331-k15	14.3	48.50	31102	yes	33929	9.1
X-n336-k84	83.4	48.65	139111	no	145695	4.7
X-n344-k43	42.7	50.11	42050	no	45300	7.7
Average						9.0

Table 5. Performance evaluation for the instances of class X for $n\ge 350$ reported in http://vrp.galgos.inf.puc-rio.br

instance	tightness	dispersion	best known solution	proven optimal	CC-CVRP
					solution	optimality
						gap (%)
X-n351-k40	39.7	60.14	25896.0	no	28745	11
X-n359-k29	28.6	49.46	51505.0	no	55485	7.7
X-n367-k17	16.7	54.53	22814.0	no	25236	10.6
X-n376-k94	93.8	48.60	147713.0	yes	148790	0.7
X-n384-k52	51.7	48.24	65938.0	no	69757	5.8
X-n393-k38	37.4	56.76	38260.0	yes	41846	9.4
X-n401-k29	28.6	56.13	66154	no	69155	4.5
X-n411-k19	18.1	59.59	19712	no	22694	15.1
X-n420-k130	129.2	55.35	107798	yes	113708	5.5
X-n429-k61	60.2	47.99	65449	no	70343	7.5
X-n439-k37	36.5	50.03	36391	yes	39359	8.2
X-n449-k29	28.9	48.46	55233	no	60931	10.3
X-n459-k26	25.7	60.44	24139	no	27636	14.5
X-n491-k59	58.3	51.61	66483	no	71898	8.1
X-n502-k39	38.5	72.96	69226	no	70986	2.5
X-n513-k21	20.5	53.94	24201	no	28422	17.4
X-n548-k50	49.7	48.19	86700	yes	91028	5
X-n561-k42	41.3	49.38	42717	no	48334	13.1
X-n573-k30	29.4	60.66	50673	no	54030	6.6
X-n586-k159	158.2	51.65	190316	no	200107	5.1
X-n599-k92	91.9	48.19	108451	no	113937	5.1
X-n613-k62	61.2	48.22	59535	no	67638	13.6
X-n627-k43	42.8	64.79	62164	no	66463	6.9
X-n641-k35	34.4	50.68	63684	no	69888	9.7
X-n655-k131	130.8	63.67	106780	yes	107824	1
X-n685-k75	74.3	50.41	68205	no	79762	16.9
X-n701-k44	43.6	51.09	81923	no	89991	9.8
X-n716-k35	34.0	63.87	43373	no	47091	8.6
X-n733-k159	158.8	48.19	136187	no	147320	8.2
X-n749-k98	97.0	51.86	77269	no	83399	7.9
X-n766-k71	70.5	50.80	114417	no	127806	11.7
X-n783-k48	47.4	48.00	72386	no	80590	11.3
X-n801-k40	40.0	48.29	73305	no	79500	8.5
X-n876-k59	58.3	66.01	99299	no	105036	5.8
X-n895-k37	36.9	48.17	53860	no	60440	12.2
X-n957-k87	86.9	52.81	85465	no	90644	6.1
X-n979-k58	57.5	66.58	118976	no	125254	5.3
X-n1001-k43	42.4	48.04	72355	no	82174	13.6
Average						8.7

Table 6. Performance evaluation for the instances of Arnold, Gendreau, and Kenneth (2019a) presented in http://vrp.galgos.inf.puc-rio.br

instance	best known solution	proven optimal	CC-CVRP
			solution	optimality
				gap (%)
Antwerp1-n6000	477277	no	535304	12.2
Antwerp2-n7000	291371	no	332856	14.2
Brussels2-n16000	345551	no	432440	25.1
Ghent2-n11000	257802	no	301728	17.0
Leuven1-n3000	192848	no	211946	9.9
Leuven2-n4000	111399	no	128756	15.6
Average				15.7

Augerat, P., D. Naddef, J. M. Belenguer, E. Benavent, A. Corberan, and G. Rinaldi. 1995. “Computational results with a branch and cut code for the capacitated vehicle routing problem.”.

 Google Scholar

Shalaby, M., A. Mohammed, and S. Kassem. 2021. Supervised Fuzzy C-means techniques to solve the capacitated vehicle routing problem. INTERNATIONAL ARAB JOURNAL OF INFORMATION TECHNOLOGY 18 (3 A):452–63.

 Google Scholar

Arnold, F., M. Gendreau, and S. Kenneth. 2019a. Efficiently solving very large-scale routing problems. Computers& Operations Research 107:32–42. doi:10.1016/j.cor.2019.03.006.

 Web of Science ®Google Scholar