The tobacco industry is closely related to government revenue. Smuggling of counterfeit cigarettes will not only cause the loss of national tax, but also disrupt the market and endanger consumers′ health. How to effectively regulate cigarette-smuggling vehicles is of great significance to the development of the tobacco industry. Aiming at the issue of cigarette-smuggling vehicles, this paper combines the actual collected vehicle data and proposes an anomaly detection algorithm based on label propagation. Firstly, the features of the vehicle data set are extracted. Second, random forest algorithm is adopted to conduct the feature selection. On this basis, label propagation algorithm is utilized to classify the anomaly vehicles. The results show that in the case of less historical data and abnormal vehicle tags, the anomaly detection algorithm of cigarette-smuggling vehicles based on label propagation can effectively detect most cigarette-smuggling vehicles. In the given dataset, the recall rate of the proposed algorithm in detecting anomaly is 57. 7% , which outperforms those of other traditional machine learning models. The algorithm can provide auxiliary support for the detection of the vehicles transporting prohibited items.