车辆路径问题（Vehicle Routing Problem,VRP）是一种传统的组合优化问题,其广泛运用于物流、交通控制等领域。随着科技的发展以及交通、通信手段的日益丰富,该问题再度成为研究热点,焕发了新的生命力。一方面,人们不断尝试丰富各类约束条件,模拟现实中各种因素对模型的影响,使其更好的描述实际情况;另一方面,人们不断改进算法,以期能以更高的效率规划出最佳路径。车辆路径问题的求解涉及到较为复杂的组合优化,被证实为属于NP-Hard问题。随着客户数的增加,精确算法因计算量大幅增加而无法实现问题的求解。因此,由问题知识或搜索结果作为启发信息而形成的启发式算法成为求解VRP的主流方法。在此背景下,主要工作如下:一是提出了一种有效求解大规模带容量约束的车辆路径问题（Large Scale Capacitated Vehicle Routing Problem,LSCVRP）的新算法。大规模带容量约束车辆路径问题是基本车辆路径问题（Vehicle Routing Problem,VRP）在客户数上升至一定程度后形成的具有实际意义的热点问题,其难点在于如何在巨大的解空间中进行有效的搜索。本文将一种层次分解策略引入大规模带容量约束的车辆路径问题的求解,并使用变邻域搜索对解进行局部搜索,以进一步提高解的质量。为了验证所设计算法的有效性,在Golden和Li两个标准测试集上进行了计算,并和现有优秀算法进行对比。结果表明本文所设计的算法在较多算例上更新了问题的最优解,尤其在大规模测试集Li上,表现出色。二是模拟实际路况条件对基本带容量约束的车辆路径问题（Capacitated Vehicle Routing Problem,CVRP）模型进行修改,考虑了车流量周期性变化及突发事件对路况条件的影响,提出了不确定路况条件下的CVRP问题。而后,分别在确定路况条件及不确定路况条件下规划路径,并使用修正后的VRP国际标准数据集中的十组不同规模、不同客户需求、不同最大载重约束的算例作为测试集对两种情况下规划的路径进行了测试,对其中三组算例进行了统计分析,证明了不确定路况条件下规划的路径在实际路况测试中表现更优。