配送路线选择和车辆调度.ppt

第六章 配送路线选择与车辆调度;第一节 配送路线安排与车辆调度问题及节约法原理; VRP问题的描述; VRP问题的分类; 二、VRP问题精确求解方法的局限性; 2.精确算法的局限性; 三、节约法原理 ;节约法的基本原理： ;;;第二节 单中心配送路线选择与车辆调度;;;;;;;;;;;;二、多车非满载配送路线安排与车辆调度;;;; 例：由配送中心B0向12个用户Bj (j=1,2,…12)送货，各点之间的运输里程和各用户的需求量见表6-1。表6-2为可供调度的车辆数目及其载重量。; 解：由表6-1中的数据，按节约量公式（6.5）计算每两用户之间的节约量Si,j 列于表6-3，称节约量表。;;迭代求解：;; 第二步，按下述条件在初始方案表中寻找具有最大节约量的用户i、j; 第三步，按ti,j的定义和公式6—7修正ti,j的值。;第四步，按以下原则修正bi、bj; 表6-6 第一次迭代方案 表6-7 该方案所用汽车台数; 重复第二步，按下述条件在第一次迭代方案表6－6中寻找具有最大节约量的用户i、j; 重复第三步，按ti,j的定义和公式（6.7）修正ti,j的值。;重复第四步，按以下原则修正bi、bj; 表6-8 第二次迭代方案 表6-9 该方案所用汽车台数; 表6-10 第三次迭代方案 表6-11 该方案所用汽车台数;; 表6-12 第四次迭代方案 表6-13 该方案所用汽车台数; 表6-14 第五次迭代方案 表6-15 该方案所用汽车台数;; 反复进行第二~第四步，直至没有可连接的用户时为止，得最终满意配送方案如表6-16，表6-17。 表6-16 满意配送方案 表6-17 最终方案所用汽车台数; 满意配送方案有四条配送路线，它们是：;第三节 多中心配送路线选择与车辆调度; 二、制定多中心配送方案的边界点方法 ; 2.非边界点的分派; 3.边界点的分派;;;; 例：假设有三个配送中心（编号是1,2,3）给10个用户（编号是4,…,13）配送货物。配送中心与用户以及用户与用户之间的运输距离如表6-18。?;; ;;;