构造算法最早提出来解决旅行商问题,这些方法一般速度快,也
很灵活,但这类方法有时找到的解离最优解差得很远。
两阶段法(Two-phase Algorithm)
第一阶段得到一可行解,第二阶段通过对点的调整,在始终保持
解可行的情况下,力图向最优目标靠近,每一步都产生另一个可行解
以代替原来的解,使目标函数值得以改进,一直继续到不能再改进目
一种以数学规划为主的启发式解法,包括指派法、集合分割法和集合
涵盖法;第三阶段是从1990开始至今,属于较新的方法,包括利用严
谨启发式方法、人工智能方法等。
综合过去有关VRP的求解方法,可以将其分为精确算法(exact
algorithm)与启发式算法(heuristics),其中精确算法有分支界
限法、分支切割法、集合涵盖法等;启发式算法有节约法、模拟退火 法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算
(Simulated Annealing)、禁忌搜索算法(Tabu Search)、遗传算法
(Genetic Algorithm)、蚁群算法(Ant Colony)和神经网络(Neutral
Networks)、粒子群算法(Particle Swarm Optimization,PSO)方
法等。
5.车辆路径问题的研究现状
分重要,采用不同的估价可以有不同的效果。目前已提出的启发式算
法较多,分类也相当多,主要的启发式算法有以下几类:构造算法、
两阶段法、智能化算法。
构造算法(Constructive Algorithm)
这类方法的基本思想是:根据一些准则,每一次将一个不在线路
上的点增加进线路,直到所有点都被安排进线路为止。
标函数值为止。。