Vehicle-Routing-Problem

Repository for solving the Vehicle Routing Problem (VRP) with Ant colony algorithm

Time was measured in seconds.

Algorithm without 2-opt

Benchmark A

File name	Number of Locations	Number of trucks	Capacity	Optimal	Achieved	2-opt	Work time
A-n32-k5	32	5	100	784	838.513	False	19.061
A-n33-k5	33	5	100	661	710.418	False	20.291
A-n33-k6	33	6	100	742	792.278	False	18.434
A-n34-k5	34	5	100	778	854.034	False	20.776
A-n36-k5	36	5	100	799	903.767	False	14.513
A-n37-k5	37	5	100	669	713.269	False	27.336
A-n37-k6	37	6	100	949	1019.855	False	30.556
A-n38-k5	38	5	100	730	790.968	False	21.582
A-n39-k5	39	5	100	822	906.743	False	24.396
A-n39-k6	39	6	100	831	888.053	False	49.762
A-n44-k6	44	6	100	937	1008.017	False	49.951
A-n45-k6	45	6	100	944	1011.057	False	31.133
A-n45-k7	45	7	100	1146	1228.177	False	50.246
A-n46-k7	46	7	100	914	1004.101	False	45.317
A-n48-k7	48	7	100	1073	1151.498	False	37.426
A-n53-k7	53	7	100	1010	1119.706	False	63.501
A-n54-k7	54	7	100	1167	1281.569	False	75.882
A-n55-k9	55	9	100	1073	1185.471	False	52.153
A-n60-k9	60	9	100	1354	1526.267	False	115.838
A-n61-k9	61	9	100	1034	1149.111	False	98.625
A-n62-k8	62	8	100	1288	1428.876	False	117.624
A-n63-k10	63	10	100	1314	1461.347	False	148.121
A-n63-k9	63	9	100	1616	1773.798	False	66.014
A-n64-k9	64	9	100	1401	1564.595	False	101.94
A-n65-k9	65	9	100	1174	1333.84	False	126.488
A-n69-k9	69	9	100	1159	1372.132	False	74.774
A-n80-k10	80	10	100	1763	2006.585	False	190.203

Benchmark B

File name	Number of Locations	Number of trucks	Capacity	Optimal	Achieved	2-opt	Work time
B-n31-k5	31	5	100	672	700.751	False	14.872
B-n34-k5	34	5	100	788	852.881	False	18.534
B-n35-k5	35	5	100	955	1006.735	False	24.572
B-n38-k6	38	6	100	805	874.97	False	19.687
B-n39-k5	39	5	100	549	590.971	False	47.795
B-n41-k6	41	6	100	829	861.346	False	30.483
B-n43-k6	43	6	100	742	810.218	False	25.977
B-n44-k7	44	7	100	909	978.233	False	52.813
B-n45-k5	45	5	100	751	807.073	False	25.902
B-n45-k6	45	6	100	678	730.22	False	65.313
B-n50-k7	50	7	100	741	837.268	False	30.562
B-n50-k8	50	8	100	1312	1376.369	False	56.709
B-n51-k7	51	7	100	1032	1082.473	False	30.565
B-n52-k7	52	7	100	747	792.922	False	94.959
B-n56-k7	56	7	100	707	786.707	False	66.116
B-n57-k7	57	7	100	1153	1201.903	False	89.831
B-n57-k9	57	9	100	1598	1733.814	False	77.207
B-n63-k10	63	10	100	1496	1603.709	False	60.723
B-n64-k9	64	9	100	861	941.439	False	97.327
B-n66-k9	66	9	100	1316	1382.895	False	99.382
B-n67-k10	67	10	100	1032	1161.153	False	82.781
B-n68-k9	68	9	100	1272	1364.355	False	72.228
B-n78-k10	78	10	100	1221	1357.165	False	171.261

Algorithm with 2-opt

In order to improve the quality, we used 2-opt after finding the ant with the lowest route length. We iterate over possible permutations and find the better one if it exists. Overall, it boosted our results.

Benchmark A

File name	Number of Locations	Number of trucks	Capacity	Optimal	Achieved	2-opt	Work time
A-n32-k5	32	5	100	784	815.491	True	25.6
A-n33-k5	33	5	100	661	671.72	True	17.165
A-n33-k6	33	6	100	742	767.781	True	17.509
A-n34-k5	34	5	100	778	810.92	True	44.747
A-n36-k5	36	5	100	799	826.682	True	49.409
A-n37-k5	37	5	100	669	701.55	True	83.833
A-n37-k6	37	6	100	949	975.524	True	23.108
A-n38-k5	38	5	100	730	744.34	True	65.455
A-n39-k5	39	5	100	822	852.058	True	85.091
A-n39-k6	39	6	100	831	838.973	True	50.695
A-n44-k6	44	6	100	937	967.384	True	99.46
A-n45-k6	45	6	100	944	969.418	True	51.22
A-n45-k7	45	7	100	1146	1191.383	True	103.915
A-n46-k7	46	7	100	914	958.255	True	35.831
A-n48-k7	48	7	100	1073	1129.993	True	53.386
A-n53-k7	53	7	100	1010	1069.636	True	128.176
A-n54-k7	54	7	100	1167	1211.529	True	90.794
A-n55-k9	55	9	100	1073	1127.406	True	111.258
A-n60-k9	60	9	100	1354	1461.465	True	66.459
A-n61-k9	61	9	100	1034	1086.256	True	79.684
A-n62-k8	62	8	100	1288	1376.086	True	99.49
A-n63-k10	63	10	100	1314	1404.418	True	123.143
A-n63-k9	63	9	100	1616	1691.819	True	73.807
A-n64-k9	64	9	100	1401	1461.67	True	117.551
A-n65-k9	65	9	100	1174	1233.52	True	218.257
A-n69-k9	69	9	100	1159	1267.978	True	135.436
A-n80-k10	80	10	100	1763	1919.752	True	280.383

Benchmark B

File name	Number of Locations	Number of trucks	Capacity	Optimal	Achieved	2-opt	Work time
B-n31-k5	31	5	100	672	699.51	True	34.459
B-n34-k5	34	5	100	788	829.642	True	59.781
B-n35-k5	35	5	100	955	974.02	True	45.877
B-n38-k6	38	6	100	805	826.113	True	59.304
B-n39-k5	39	5	100	549	590.861	True	57.37
B-n41-k6	41	6	100	829	844.207	True	36.119
B-n43-k6	43	6	100	742	753.388	True	60.439
B-n44-k7	44	7	100	909	928.846	True	52.073
B-n45-k5	45	5	100	751	769.897	True	76.021
B-n45-k6	45	6	100	678	694.705	True	60.087
B-n50-k7	50	7	100	741	775.428	True	78.655
B-n50-k8	50	8	100	1312	1346.812	True	124.519
B-n51-k7	51	7	100	1032	1042.951	True	135.982
B-n52-k7	52	7	100	747	758.429	True	91.849
B-n56-k7	56	7	100	707	751.654	True	167.417
B-n57-k7	57	7	100	1153	1165.82	True	85.106
B-n57-k9	57	9	100	1598	1655.861	True	63.948
B-n63-k10	63	10	100	1496	1559.475	True	174.113
B-n64-k9	64	9	100	861	909.52	True	87.539
B-n66-k9	66	9	100	1316	1363.598	True	91.111
B-n67-k10	67	10	100	1032	1092.285	True	170.478
B-n68-k9	68	9	100	1272	1330.882	True	94.303
B-n78-k10	78	10	100	1221	1312.699	True	173.531
Answers are in solutions folder