Aiming at traffic volume and vehicle utilization，which are closely related to the cost of vehicle traffic，a vehicle scheduling model with the minimum fuel cost and fixed cost is established. According to the requirement of real-time and complicacy of the vehicle scheduling，a cloud adaptive genetic algorithm is proposed by combining cloud model theory with genetic algorithm. The way of the fixed set crossover and mutation probability in the standard genetic algorithm is improved by using the randomness and bias stability of the cloud droplet cloud model. Defects of slow search and easy precocious of the standard genetic algorithm is overcome. The convergence and robustness of the algorithm was improved by crossover and mutation that was designed based on maximum retention mechanism. Finally，an example authenticated the effectiveness of the model and algorithm.