作为烟草物流体系终端环节的地级市烟草物流中心,负责按订单把成品卷烟配送给零售商户。卷烟配送路线规划决定了物流成本和配送效率,关系到企业经济效益实现和卷烟客户满意度的提高,是企业核心竞争力提升和生存、发展的大问题。本文以卷烟配送路线优化问题为研究对象,以降低配送成本提高配送效率为目标,构建了卷烟配送路线优化问题的数学模型。通过分析现有卷烟配送路线优化问题的研究现状,结合A烟草公司B中转站的卷烟配送现状,选取了先分组后路线的两阶段算法对研究问题进行求解。算法的核心思路为,首先采用k-means聚类算法划分配送区域,接着在单个配送区域内采用禁忌搜索算法进行路线优化。在对初始优化结果进行分析时,发现部分路线存在车辆能力剩余的问题,因此利用禁忌搜索算法的结果调整配送区域。卷烟配送路线优化问题具有特殊的行业配送特点,本文为A烟草公司B中转站提供了一套较为完整的卷烟配送路线优化方案,对具有相似配送特点行业的物流配送具有一定的参考价值。