In order to further optimize the vehicle routing in tobacco distribution centers, a vehicle routing evaluation model based on data envelopment analysis (DEA) method was proposed. The preliminary of DEA was introduced first. Then, a fuzzy DEA evaluation model was established, whose inputs were vehicle number and mileage and outputs were customer satisfaction, total distribution area, application degree, and customer number. Finally,taken certain distribution system with 13 tobacco distribution centers as the examples, the technical efficiency, scale efficiency, and technique-invalid slack variables were evaluated using proposed model, and the optimal distribution scheme was reported.