A real vehicle scheduling problem concerning the urban public transportation system of the city of Mestre (Venice) has been approached by Genetic Algorithm enhanced using redundancies. Redundant alleles fix the string at cross-over positions in order to improve solution feasibility. The scheduling problem has been studied both as a single and as a multiple objective optimisation problem. A significant reduction of resources as compared to the currently used solution has been achieved.