物流配送车辆调度优化方法比较研究(2)

物流配送车辆调度优化方法比较研究

!

!

好方法。Ｋｏｌｅｎａｔａ１．曾利用此方法求解含时间窗约束的车辆巡回问题，其实验的节点数范围为６￣１５。当节点数为６时，计算机演算所花费的时间大约１分钟（计算机机型为ＶＡＸ１１／７８５），当节点数扩大至１２时，计算机有内存不足的现象产生，所以分枝定界法比较适用于求解小型问题。Ｈｅｌｄ和Ｋａｒｐ指出分枝定界法的求解效率与其界限设定的宽紧有极大的关系。

３．１．３切平面法（Ｃｕｔｔｉｎｇｐｌａｎｅｓ）

此方法与分枝界限法类似，也是在求解与整数规划相对应的线性规划上，不断地增加新的约束，也就是另外加入线性约束条件，以切掉对应于非整数规划的所有可行解的集合，以使问题可达到整数线性规划求解的形式，从而获得最优解。求解时间过长，不适用于大规模问题。

３．２ＶＲＰＴＷ问题的传统启发式算法

传统的启发式算法在求解ＶＲＰＴＷ问题时通常是从初始解出发，以邻域搜索的方式实现解的改进，并在较短的时间内获得一个可以接受的解。

３．２．１节约算法（ＳａｖｉｎｇＭｅｔｈｏｄ）

节约算法最早由Ｃｌａｒｋｅ等于１９６４年提出该方法并用于求解车辆巡回问题。其思想是将每条路线只含一个配送点的ｎ条路线作为初始解，其中，每条路线中第一个和最后一个配送点分别称为路线的起点和终点。考察一条路线的起点与另一条路线的终点相连合并成新的一条路线。如果合并后的路线满足约束条件（车辆容量、时间窗），则说这样的合并是可行的，并将合并的节约值定义为连接这两条路线的边的节约值。选择节约值最大的可行合并进行一次路线的合并。当不存在可行合并时，算法结束。Ｓｏｌｏｍｏｎ于１９８３年将其用于求解有时间窗约束的车辆巡回问题。此方法的优点是可提高车辆的利用率。

３．２．２邻接算法（Ｎｅａｒｅｓｔ－Ｎｅｉｇｈｂｏｒ）

邻接算法是Ｓｏｌｍｏｎ于１９８３年所提出的求解ＶＲＰＴＷ的方法，它是一种序列构造路线法。算法从一条只含一个配送点的路线出发（通常取“距离”配送中心最近的点）。在未分配点中筛选出可加入点（未分配点且可行），并从可加入点中选取一个点作为当前路线的终点，使得路线的成本最小。如此不断对路线进行扩充，直到路线不存在可加入点为止。这时，如果所有点均已分配，则算法结束；否则，生成一条新的初始路线，重复前面的路线扩充程序。需要指出，对距离加上双引号是为了说明这样的距离未必指实际的距离，而是关于距离和时间等因素的函数。

３．２．３插入算法

插入法原本是Ｍｏｌｅ和Ｊａｍｅｓｏｎ于１９７６年所提出，用于求解ＶＲＰ问题的方法，其结合邻接算法与节约算法的观念，依序将顾客点插入路径中以构建配送路线。Ｓｏｌｏｍｏｎ于１９８３年将此方法应用于求解ＶＲＰＴＷ问题，因为时间因素加入，而使原问题的顾客的等待时间缩短。它的流程与邻接算法相似，也是从初始路线出发，序列构造路线。并在不存在可行插入时新增一条初始路线。插入算法的关键是选择最合适的未分配点在路线中进行最佳位置的插入。

３．２．４扫除算法

扫除算法最早由Ｇｉｌｌｅｔｔ和Ｍｉｌｌｅｒ在１９７４年提出，是一种“先分组后路线”的算法。１９８７年，Ｓｏｌｏｍｏｎ将其推广应用于ＶＲＰＴＷ问题的路线构造。所谓分组，即指分派给每辆车一组点。一种简单的分组方法是将以车站为原

，是指在每个区点的坐标平面划分为多个扇形区域，并初步将每个扇形区域的点分派给一辆车。而所谓的“路线”

域内，采用扫除法选择未分配点，然后应用插入算法扩充路线。如果在进行了一次“分组—路线”的路线构造后，还存在未分配点，则再进入“分组—路线”程序。如此反复，直到所有点均已分配为止。

３．３ＶＲＰＴＷ问题的现代启发式算法

相对于传统启发式算法，现代启发式算法不要求在每次迭代中均沿目标值下降方向，而允许在算法中适当接受目标值有所上升甚至不可行的解，其目的是能够跳出局部搜索邻域。

３．３．１禁忌搜索算法（ＴａｂｕＳｅａｒｃｈ，ＴＳ）

禁忌搜索算法最早由Ｇｌｏｖｅｒ在１９８６年提出，是局部搜索算法的扩展。该算法通过利用一个禁忌表记录已经到达过的局部最优点，并在后面的搜索中，根据某种限制循环的规则和禁忌表中记录的信息在当前搜索邻域中取一个合适的解。１９９４年，Ｇａｒｃｉａ等首先将禁忌算法应用于ＶＲＰＴＷ问题。为了减少搜索的计算量，一些文献提出了一些限定邻域的方法。另一方面，为了加速搜索进程，可采用平行机计算技术。较多算法都以车辆数最少为优

４７

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库物流配送车辆调度优化方法比较研究(2)在线全文阅读。