车辆最短路径问题研究(2)

菜单

车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。车辆路线问题可以描述如下：

设有一个起始站，共有辆货车，车辆容量为，有位顾客，每位顾客的需求量为。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。

2 车辆路径问题的难点与解决方法

2.1 车辆路径问题的难点

对于解决车辆路径问题有一个难题，那就是NP完全问题，NP问题是世界七大数学难题之一。NP问题是指可以在多项式的时间里猜出一个解的问题，简单来说就是多项式复杂程度的非确定性问题。NP问题通常有个算法，它不可以直接告诉你答案是什么，但是能告诉你，某个可能的结果是正确的还是错误的。这个能告诉你“猜算”的答案正确与否的算法，如果可以在多项式时间内算出来，就可以叫做多项式非确定性问题。但如果这个问题的所有可能性答案，都是能够在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。

完全多项式非确定性问题可以用穷举法得到答案，一个一个的检验下去，最终能够得到结果。但是这样算法的复杂程度是指数关系，因此计算的时间随着问题的复杂程度成指数的增长，很快便变得不可以计算了。而车辆路径问题就属于一种NP问题。

2.2 车辆路径问题的方法

综合过去有关车辆路线问题的求解方法，可以分为精确算法与启发式解法，其中精密算法有分支界限法、分支切割法、集合涵盖法等；启发式解法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚁群算法等。1995年，Fisher曾经将求解车辆路线问题的算法分成三个阶段。第一阶段是从1960年到1970年，属于简单启发式方式，包括各种局部改善启发式算法和贪婪法等；第二阶段是从1970年到1980年，属于一种以数学规划为主的启发式解法，包括指派法、集合分割法和集合涵盖法；第三阶段是1990年开始至今，属于较新的方法，包括利用严谨启发式方法、人工智能方法等。

精确算法顾名思义就是可以求出最优解的方法。它是一种基于严格要求的数学手段，但是随着规模的扩大，算法也不可避免的变得复杂。所以精确算法只能求解小规模的车辆路径问题。

启发式算法是一个基于直观或经验构造的算法，在可以接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。

由于车辆路径问题是NP-hard问题，很难用精确算发求解，启发式算法是求解车辆运输问题的最主要的方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法。

下面就来介绍一下解决车辆路径问题的方法。

2.2.1 分支界限法

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就可以一次性产生其所有儿子结点。在这些儿子结点中，导致非可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一个结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。源'自:751`!论~文'网www.751com.cn