A new hybridized algorithm based on Particle Swarm Optimization is proposed for the solution of the Vehicle Routing Problem with Time Windows. The algorithm uses a relative new topology, the Combinatorial Neighborhood Topology and, thus, a solution is not needed to be transformed in continuous values during the iterations, which makes Particle Swarm Optimization a competitive algorithm in solving routing problems. Also, in the proposed algorithm all the parameters (acceleration coefficients, iterations, local search iterations, upper and lower bounds of the velocities and of the positions and number of particles) are optimized during the procedure and, thus, the algorithm works independently and without any interference from the user. All parameters are randomly initialized and, afterwards, during the iterations the parameters are adapted based on a number of different conditions. The algorithm uses a number of different velocities’ equations and each particle selects randomly its velocity equation and during the iterations the particle has the possibility to change the velocity equation based on the produced quality of the solution. The algorithm is tested in known benchmark instances from the literature and gives very good results. It is also compared with other algorithms from the literature.