In this paper, based on the analysis of the time urgency in medicine relief demand and kinds of complexity in the early period after earthquake disasters, the problem about vehicle scheduling in the medicine dispatching process is studied. A mathematical model of vehicle scheduling in the medicine dispatching process is built, which objective function is to minimize the total transportation time, under the condition of single depot, multi-type vehicles and multiconstraints. The solutions are obtained by using genetic algorithm based on natural number encoding. The impacts of different parameters on the results have been compared by software Matlab. The experiment results show that genetic algorithm is satisfactory to solve this problem.