(2)邻接算法(Neearst 一 Neighbor)。邻接算法是 Solmon 于 1983 年用来提出解决 带有时间窗问题的车辆路径问题,它是一种序列构造路线法。算法从一条只含一个配送 点的路线出发(通常取这个点为一“距离”配送中心最近的点)。在未分配点中筛选出 可加入点(所谓可加入点,是指一个未分配点,将它作为一条路线的终点仍然保持路线 的可行性),并从可加入点中选取一个点作为当前路线的终点,使得路线的成本最小。如 此不断对路线进行扩充,直到路线不存在可加入点为止。这时,如果所有点均已分配, 则算法结束;否则,生成一条新的初始路线,重复前面的路线扩充程序。需要指出,对距 离加上双引号是为了说明这样的距离未必指实际的距离,而是关于距离和时间等因素 的函数[15]。

(3)插入算法。Mole 和 Jnalenos 于 1976 年提出的插入算法,主要是用来解决 VRP 即时问题。该种算法主要结合了节约算法和邻接算法的基本思想。其主要步骤就是依 照次序将顾客需要服务的点插入到路径中去以此构建物流配送的优化路线。

（4）扫除算法。扫除算法最早由 Ginett 在 1974 年提出，是一种“先分组后路线” 的算法[17]。1987 年，Solomon 将这种算法应用于了带有时间窗问题的路线构造中。这 里面提到了分组问题，就是指给每一辆车分配一组点。比较简单的分组方式就是以配 送中心为原点的坐标，然后将整个坐标平面区域分成多个扇形的区域。紧接着给每个 扇形的区域的点分派一辆车辆。而其中的路线就是在区域内，采用扫除法选择没有分 配的点，然后使用插入算法补全路线。然后如此反复，直到所有的节点被平均分配为 止。