随着现代城市经济的快速发展,企业与企业之间,企业与个人之间的商品交易发展日益迅速,物资流通的频繁也进一步显现了物流的力量。配送作为物流系统的重要组成部分,与人们的生活息息相关,是反映城市物流服务水平的重要因素。随着城市规模的扩大,商品交易日益频繁,城市配送客户点规模日益增大,物流企业在大规模客户点的配送中如何合理地规划车辆配送线路,如何有效地减少配送车辆行驶距离,降低运输成本,实现效益的最大化,成为企业关心的重要课题。车辆路径问题由于问题本身是从实际生活中抽象出来,与现实生活密切相关,因此一直是学术界中多个学科的研究热点。小规模车辆路径问题的各种算法研究已经相对成熟,已经可以在50个点的范围内得到精确解,但是由于实际问题的大规模及多样性,增加了该类问题的复杂程度。在目前各种分区聚类算法的研究基础上,本文针对大规模车辆路径问题的特点,提出了“先分区,再排程,后改进”的三阶段求解算法,首先,利用改进的k-means算法将大规模客户点进行分区,通过分区,将大规模数据集分成若干个小规模数据集,并通过详细的试验对比分析了分区数目对结果的影响；然后,在第一阶段分区的基础上,采用并行节约算法对各个区域进行车辆排程；最后,为了提高区域之间的关联性,采用可变邻域搜索算法改进结果。为了验证算法的有效性,本文进行了大量的仿真试验。试验算例不仅包括分布密度均匀的客户点算例,同时结合现实生活中真实配送数据,构造分布密度不均的客户点算例,得到不同规模客户点不同分区个数的仿真结果,由于相同算法在不分区时得到的结果优化程度较高,而分区后得到的试验结果比不分区时结果偏差在1%～3%,验证了算法的可行性。另外,本算法在较短时间内求解了3189个客户点的大规模车辆路径实际问题,体现了较高的求解质量和算法效率最后,本文对大规模车辆路径问题的配送分区研究前景进行了展望,结合自身不足,提出后续研究方向。