车辆路径问题是经典的NP-hard问题,它有很高的科学研究价值。对车辆路径问题的研究有利于运输路径的合理规划,而现实中合理的路径规划能够提高效率,降低成本和节约资源。本文研究带容量约束的车辆路径问题。这个问题自提出以后,一直是众多学者研究的热点问题,先后提出了一系列优秀算法。本文在前人工作的基础上,研究并提出了一种基于Spark计算框架下的并行启发式算法,目标是在较短的时间内求出质量较高的可行解。这项研究涵盖三项主要工作:第一,实现了经典的禁忌搜索算法,包含五种邻域变换,并使用了 Granular策略来减少搜索时间;第二,提出了一种并行算法,可在多个搜索结点并行执行。将结点分成两类,算法通过结点之间设立的一个公共的Solution Pool机制进行相互协作。每个结点都将自己找到的最好解发送给Solution Pool,并且接收来自Solution Pool的解。各个解在Solution Pool中根据相似度形成不同的种群;第三,在Spark计算框架下实现了并行算法,并采用分别由Christofides和Golden生成的两种不同的数据进行测试。实验结果表明,本文讨论的禁忌搜索是可行的,并行算法能在短时间内取得不错的结果。