中国虽是世界上第一烟草大国,拥有庞大的消费群体,但是随着外烟品牌的涌入,香烟替代品的出现以及国内的控烟行动等,使得烟草企业面临着更多的挑战,中国烟草企业若要在有限的市场中扩大市场份额,在严峻的国内外形势下保证自己的行业利润,不仅要开源,更要节流,管控自己的成本。鉴于烟草企业在物流配送上存在车载率未达到最优、配送过程未得到有效监控及客户服务水平有待提高等,本文选择M公司的物流进行研究,主要研究内容包括:(1)烟草背景及相关理论简介,在第一章对烟草企业面临的行业背景做了介绍,第二章对与之相关的理论进行了介绍,包括路径优化理论、时间窗车辆路径理论以及解决路径优化问题的算法,为之后的研究做理论上的准备。(2)第三章对M公司的物流现状进行了介绍,包括M公司的配送网络现状、配送流程现状、配送人员及车辆的现状等,通过了解,发现M公司在物流配送中存在车载率未达最优、送货成本未达最优、未考虑零售客户的需货时间等问题。(3)针对公司现存的问题在第四章建立时间窗车辆路径模型,针对零售户呈簇类分布特征及M公司原有配送线路存在的配送量差异较大的状况,使用K-means聚类算法将样本数据分为四类,使用改进蚁群算法求解每一类的最优送货线路。最后的求解结果证明本文提出的线路优化方法可以降低M公司的配送费用,同时可以基本满足零售客户的需货时间,从而提高客户满意度。总之,本文的研究不仅有助于M公司解决物流问题,也从一定程度上丰富了烟草物流配送的相关理论。