Vehicle Routing Problem (VRP) is an area which has been widely dealt with for the last four decades. Methodologies have been developed for many variants of the VRP. This work considers concurrent and sequential delivery and pick-up in VRPs, encountered in practice but rarely considered in theory. In addition, constraints on maximum route length and on time-windows have also been considered. Mathematical models incorporating such features have been developed. While the NP-hardness of these problems mandates the use of meta-heuristics, recognition of inherent characteristics of the problem led to the development of construction heuristics based on cluster analysis to obtain good feeder solutions that speed up the intensive search at the end. Genetic Algorithms (GA), an enhanced version of Simulated Annealing (ESA) and a hybrid of the two are the meta-heuristics proposed for optimization. The heuristics performed exceedingly well in the evaluations, recording better or equally good results in comparison to the existing methodologies.