Because of the large scale and practical constraints, the real-life application related to cigarette distribution can’t
be efficiently solved by existing methods. Firstly, a model based on the analysis of practical constraints is built. Then a
multi-stage algorithm based on the model is proposed. Dividing based on geographic information grading can reduce the
problem scale and eliminate geographic obstacles. The modified ??-means clustering method is used to dispatch routes, and
the original problem can be translated into small scale traveling salesman problem. Finally, taking the cigarette distribution in
Ji’nan city as an example, compared with several excellent methods, the advantage of multi-stage algorithm used in real-life
is verified.