Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is a problem often encountered in the logistics industry, where, on a daily basis, vehicles are required to pick up parcels from depots and deliver them to clients. This paper introduces an approach to solve the Capacitated Vehicle Routing Problem with Time Windows  for a high number of nodes by splitting the problem into smaller sub-problems with lower number of nodes. It introduces an approach based on clustering nodes together using Recursive-DBSCAN - a method that recursively applies DBSCAN until clusters below the preset maximum number of nodes per cluster are obtained. That approach leads to improvement in runtimes of the CVRPTW solver as benchmarked against Google Optimization Tools, while the difference in quality of found solutions, as measured in terms of total distance and number of vehicles used , is below 7\%. The improvement of runtimes with the Recursive-DBSCAN method is because of splitting the node-set into constituent clusters, which limits and decreases the number of possible solutions checked by the optimiser, consequently driving down the runtime .
 This paper introduces a new approach to improve the performance of the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) solvers for a high number of nodes . It proposes to cluster nodes together using Recursive-DBSCAN - an algorithm that recursively applies DBSCAN until clusters below the preset maximum number of nodes are obtained. That approach leads to 61\% decrease in runtimes of the CVRPTW solver as benchmarked against Google Optimization Tools, while the difference of total distance and number of vehicles used by found solutions is below 7\%. The improvement of runtimes with the Recursive-DBSCAN method is because of splitting the node-set into constituent clusters, which limits the number of solutions checked by the solver, consequently reducing the runtime. The proposed method consumes less memory and is able to find solutions for problems up to 5000 nodes, while the baseline Google Optimisation Tools solves problems up to 2000 nodes .
D
Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is a problem often encountered in the logistics industry, where, on a daily basis, vehicles are required to pick up parcels from depots and deliver them to clients.
R
an approach to solve the
a new approach to improve the performance of the
A
(CVRPTW) solvers
R
by splitting the problem into smaller sub-problems with lower number of nodes. It introduces an approach based on clustering
. It proposes to cluster
R
a method
an algorithm
D
per cluster
R
improvement
61\% decrease
R
in quality of found solutions, as measured in terms of
of
R
,
by found solutions
D
and decreases
D
possible
R
optimiser, consequently driving down the runtime
solver, consequently reducing the runtime. The proposed method consumes less memory and is able to find solutions for problems up to 5000 nodes, while the baseline Google Optimisation Tools solves problems up to 2000 nodes