This dissertation focuses on vehicle routing problems, one of the major academic problems in logistics. We address NP-Hard problems that model some real world situations particularly those with different temporal constraints including time windows, visit synchronization and service balance. The aim of this research is to develop new algorithms for the considered problems, investigate their performance and compare them with the literature approaches. Two cases are carried out. The first case studies the Vehicle Routing Problem with Time Windows (VRPTW). We propose new lower bound methods for the number of vehicles. Then we present a Particle Swarm Optimization algorithm dealing with the Solomon objective. The second case studies the Vehicle Routing Problem with Time Windows and Synchronized Visits (VRPTWsyn). Both exact methods and heuristics are proposed and compared to the literature approaches.