On the basis of establishing an optimized model for optimal routing of cigarette delivery vehicle problem, the paper uses techniques such as roulette wheel selection, partially matched crossover and self adaptation for fitness function, designs a genetic algorithm based on natural numbers. At the end of the paper make some experimental calculations using this algorithm. The experimental calculations results demonstrate that the optimal or nearly optimal solutions to the Cigarette Delivery Vehicle routing problem can be easily obtained by using genetic algorithm.