Abstract: To optimize operational efficiency in urban sanitation vehicle scheduling under multiple constraints—service level matching, en-route replenishment, and multiple customer visits—this paper formulates a mixed-integer programming model minimizing total costs including fixed dispatch, travel, replenishment, and soft time window penalties. Given its NP-hard nature, an improved adaptive large neighborhood search (IALNS) algorithm is developed, which employs an enhanced ant colony optimization to generate high-quality initial solutions, explores infeasible solutions, designs tailored destruction and repair operators, and integrates a simulated annealing criterion with dynamic weight adjustment to maintain solution diversity. Compared with Gurobi, IALNS achieves solutions within 1 ~ 3 seconds for small-scale instances with an average gap of 0.98% ~ 2.19% versus Gurobi’s runtime exceeding 3 000 seconds; for large-scale instances, Gurobi fails to obtain feasible solutions within 3 600 seconds while IALNS consistently outputs high-quality solutions within 10 seconds. Using the enhanced ant colony optimization for initial solution generation improves optimization performance by 40% ~ 80% over random initialization and reduces computation time. Sensitivity analysis shows that increasing the number of replenishment points reduces dispatch cost but increases replenishment cost with diminishing marginal benefits, while allowing service downgrading effectively integrates vehicle resources and reduces total cost. This study provides an efficient optimization methodology and operational decision support for urban sanitation vehicle scheduling.