An EKM-PSA-based method for cigarette pick-up point site selection and distribution route planning was proposed, in order to address the problems of high costs, high path repetition rates, low efficiency and poor timeliness of retailer services in the traditional distribution mode for sparsely populated areas. For the problem of cigarette pick-up point site selection, an improved K-means clustering algorithm integrated with economic benefit indicators was proposed, a subsidy mechanism for pick-up retailers was constructed, and a site selection model for pick-up points was established. For the problem of cigarette distribution route planning, a multi-objective cigarette distribution route planning model with time window constraints was built, where the objective function included retailer service priority cost, vehicle fixed cost, vehicle transportation cost, pick-up point subsidy cost, as well as pick-up point construction and operation costs, and a priority simulated annealing algorithm was proposed for solving the model. Taking the cigarette distribution of Z city as an example, a case study and algorithm comparisons were conducted. The results indicated that the total cost was reduced by 20%, and the transportation distance was reduced by 19% compared with the original scheme, thereby verifying the effectiveness of the proposed model and the superiority of the proposed algorithm.