摘要：本文在对车辆路径问题中的一种启发式算法—Clarke-Wright法以及各种改进算法进行概论性说明的基础上，本文对Clarke-Wright法不能对原有路线中的内点进行合并这一约束条件进行了证明。最后，本文引入一种节约算法的改进形式——并行节约算法，并利用算例体现了并行算法相对于经典节约算法的优势。

关键词：车辆路径问题  节约法  优化  并行算法

1 引言

车辆路径问题(vehicle routing Problem，VRP)是根据各有关道路情况、客户需求情况、车辆情况，为一些车辆设定访问客户的最佳路线。车辆的最佳路线必须满足：车辆从配送中心出发，完成配送任务，回到配送中心；每个客户由一辆车完成发送任务，且每辆车只能访问客户一次；车辆线路上的配送总任务不能超过车辆容量；完成任务运输费用最少；带有时间窗约束的车辆路径问题还需要满足时间窗的要求。

         车辆路径问题最早由Dantzig和Ramser于1959年提出^【1】，并将其作为旅行商问题(TSP)来求解，属于NP难问题(Non-deterministic Polynomial hard problem)。但随着客户数量的增加，组合爆炸的问题随之显现出来，致使其求解过程复杂而耗时，在实际运用的过程中受到了诸多的限制。启发式算法的运用成为解决车辆路径问题一种有效的方法。

目前用于解决车辆路径问题的启发式算法有遗传算法、禁忌搜索法、蚁群算法、模拟退火法、扫描法、两阶段法、神经网络算法等^【2】。各种算法在实际运用的过程中各有所长，其中节约法是一种灵活性很高，易于扩展，应用最为广泛的一种算法。^【3】