编辑推荐:
(2010-12-06)
建议您关注读书人网站：http://www.reader8.com/exam/wuliu/
1、求解方法演进
综合过去有关车辆路线问题的求解方法，可以分为精确算法(exact algorithm)与启发式解法(heuristics)，其中精密算法有分支界限法、分支切割法、集合涵盖法等;启发式解法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算法等。1995年，Fisher[5]曾将求解车辆路线问题的算法分成三个阶段。第一阶段是从1960年到1970年，属于简单启发式方式，包括有各种局部改善启发式算法和贪婪法(Greedy)等;第二阶段是从1970年到1980年，属于一种以数学规划为主的启发式解法，包括指派法、集合分割法和集合涵盖法;第三阶段是从1990开始至今，属于较新的方法，包括利用严谨启发式方法、人工智能方法等。
2、启发式算法
由于VRP是NP-hard问题，难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法。
简单启发式方法包括节省法或插入法、路线内/间节点交换法、贪婪法和局部搜索法等方法。节省法或插入法(savings or insertion)是在求解过程中使用节省成本最大的可行方式构造路线，直到无法节省为止。交换法则是依赖其他方法产生一个起始路线，然后以迭代的方式利用交换改善法减少路线距离，直到不能改善为止。1960年，Clarke和Wright[6]首先提出一种启发式节省法(savings methods)来建立车队配送路线。简单启发式方法简单易懂、求解速度快，但只适合求解小型、简单的VRP问题。
两阶段方法包括先分组后定路线(clusterfirst-route second)和先定路线后分组(routefirst-cluster second)两种启发式策略。前者是先将所有需求点大略分为几个组，然后再对各个组分别进行路线排序;后者则是先将所有的需求点建构成一条路线，再根据车辆的容量将这一路线分割成许多适合的单独路线。
