《配送路线选择与车辆调度》由会员分享，可在线阅读，更多相关《配送路线选择与车辆调度（59页珍藏版）》请在金锄头文库上搜索。
1、1 第六章配送路线选择与车辆调度 主要内容 配送路线安排与车辆调度问题及节约法原理 单中心配送路线选择与车辆调度 多中心配送路线选择与车辆调度 货车配载 2 第一节配送路线安排与车辆调度问题及节约法原理 一 配送路线安排与车辆调度问题配送路线安排与车辆优化调度问题常被分为车辆路线安排问题 VehicleRoutingProblem 简记VRP 和车辆调度问题 VehicleSchedulingProblem 简记VSP 前者仅从空间位置考虑车辆路线的安排和车辆调度 后者则要考虑时间要求 显然VSP问题比VRP问题讨论的范围宽 或者说 VSP问题是有时间约束的VRP问题 本书主要讨论VRP问题
2、3 VRP问题的描述 VRP问题一般可描述为 对一系列装货点或 和 卸货点 组织适当合理的行车路线 使车辆有序地通过它们 在满足一定的约束 如货物需求量 发送量 车辆容量 数目限制 车辆行驶里程限制等 条件下 达到一定的目标 如最短路程 最小费用 最短时间 最少车辆等 4 VRP问题的分类 VRP问题又根据不同标准分为 车辆满载问题 一个用户的货运量大于一辆车的容量 完成任务需要多辆车 与非满载问题 一个用户的货运量不大于一辆车的容量 完成任务只需要一辆车 单车场问题 一个货场或一个配送中心 与多车场问题 多个货场或多个配送中心 单车型 所有车辆容量相同 与多车型问题 车辆容量不全相同 以及优
3、化目标的单目标与多目标问题 5 二 VRP问题精确求解方法的局限性 1 VRP问题求解思路VRP问题的求解方法一般相当复杂 通常的做法是应用相关技术将问题分解或者转化为一个或多个已经研究过的基本问题 如旅行商问题 指派问题 运输问题 最短路问题 最小费用流问题 中国邮递员问题等 再使用相对比较成熟的基本理论和方法进行求解 6 2 精确算法的局限性 VRP问题的求解方法可分为两大类 即精确算法和启发式算法 精确算法主要有分枝定界法 割平面法 网络流算法 动态规划方法等 精确算法随着配送系统规模的增大 其计算量呈指数递增 使得获取系统最优解越来越困难 因此 精确算法在实际应用中受到很大的局限 7
4、三 节约法原理 为了克服精确优化方法的不足 人们提出了许多能获得 满意 解的启发式算法 启发式算法是一种基于直观或经验构造的算法 它运用一些经验法则 并通过模仿人的跟踪校正过程来求得系统的满意解 启发式算法中最具有代表性的是由Clarke和Wright提出的节约法 SavingMethod 8 节约法的基本原理 9 10 11 第二节单中心配送路线选择与车辆调度 12 如果将配送中心也作为一个用户点 货车从配送中心出发 对所有用户巡回送货后回到配送中心 这样就把单车非满载车辆的配送路线安排问题转化为个点的旅行商问题 TravelingSalesmanProblem 简记TSP 它的解是 从配送
5、中心出发 对所有用户巡回一次回到配送中心的距离最短的路线 13 14 15 16 17 18 19 20 21 22 23 二 多车非满载配送路线安排与车辆调度 24 25 26 此模型用精确算法求解更加困难 下面仍用节约法求解此类问题的满意解 求解的过程与例6 1基本相同 只是在方案改进的过程中 寻找具有最大节约量的用户i j时 增加了考虑车辆载重量和可调度车辆数的约束 而且 车辆调度时优先使用载重量大的车辆 27 例 由配送中心B0向12个用户Bj j 1 2 12 送货 各点之间的运输里程和各用户的需求量见表6 1 表6 2为可供调度的车辆数目及其载重量 表6 1各点之间里程表 单位 公
6、里 表6 2可供调度的汽车 28 解 由表6 1中的数据 按节约量公式 6 5 计算每两用户之间的节约量Si j列于表6 3 称节约量表 表6 3节约量表 单位 公里 如 S1 2 d0 1 d0 2 d1 2 9 14 5 18 S2 4 d0 2 d0 4 d2 4 14 23 17 20 29 设ti j i 0 1 12 j 1 2 12 i j 表示i j两点是否连接在一起的决策变量 并对其取值作如下定义 ti j 1表示i j用户连接 即在同一巡回路线中 ti j 0表示i j用户不连接 即不在同一巡回路线中 t0 j 2表示j用户只与配送中心B 连接 由一台车单独送货 根据以上定
7、义 对任一用户j 有以下等式成立 j 1 n 6 7 30 迭代求解 第一步 求初始解每用户各派一台车单独送货 得初始方案如表6 4 表中B0列中的数字为ti j的取值 此方案的总行程为728公里 按表6 4的初始方案 所用汽车台数如表6 5所列 31 表6 4初始方案表6 5初始方案所用汽车台数 32 第二步 按下述条件在初始方案表中寻找具有最大节约量的用户i j 1 t0 i t0 j 0i j 2 Bi Bj尚未连接在一条巡回路线中 3 考虑车辆台数和载重量的约束 如果最大节约量有两个或两个以上相同时 可随机取一个 按此条件 在初始方案表6 4中寻到具有最大节约量的一对用户为 i 11
8、j 12 其节约量为92公里 将11和12两用户连接到一个运输回路中 并在对应的格中记上t11 12的值 用 1 表示 33 第三步 按ti j的定义和公式6 7修正ti j的值 B11与B12连接 即令t11 12 1 由公式 6 7 得 t0 11 1t0 12 1其他不变 34 第四步 按以下原则修正bi bj 1 t0 i或t0 j等于0时 令bi或bj等于0 2 t0 i或t0 j等于1时 令bi或bj等于所在巡回路线中所有用户需求量之和 以此代替原bi或bj 因此b11 b12 1 1 1 7 2 8 吨 得改进方案 表6 6 表6 7 改进后的方案比原方案少一台发送车 总发送距离
9、减少92公里 35 表6 6第一次迭代方案表6 7该方案所用汽车台数 36 重复第二步 按下述条件在第一次迭代方案表6 6中寻找具有最大节约量的用户i j 1 t0i t0j 0i j 2 Bi Bj尚未连接在一条巡回路线上 3 考虑车辆台数和载重量的约束 如果最大节约量有两个或两个以上相同时 可随机取一个 按此条件 在表6 6中寻得具有最大节约量的用户有两对 分别为 i 10 j 11和i 10 j 12 其节约量均为84公里 任取一对i 10 j 11 将其连接到一个回路中 37 重复第三步 按ti j的定义和公式 6 7 修正ti j的值 B10与B11连接 则t10 11 1 由公式
10、6 7 得 t0 11 0t0 10 1其他不变 38 重复第四步 按以下原则修正bi bj 1 t0 i或t0 j等于0时 令bi或bj等于0 2 t0 i或t0 j等于1时 令bi或bj等于所在巡回路线中所有用户需求量之和 以此代替原bi或bj 因此b10 b12 2 8 1 6 4 4 吨 b11 0得第二次迭代方案 表6 8 表6 9 第二次迭代方案比第一次迭代方案又少一台配送车 只需10台 其中一台为5吨车 总发送距离比前一方案减少84公里 39 表6 8第二次迭代方案表6 9该方案所用汽车台数 40 表6 10第三次迭代方案表6 11该方案所用汽车台数 为什么不选B10 B9 B1
11、0 B8 可否将B11与B7连接 41 得到第一条配送路线 B0 B7 B10 B11 B12 B0 行程112公里 用6吨车配送 载重5 6吨 开始下一条配送路线的选择 过程如何 42 表6 12第四次迭代方案表6 13该方案所用汽车台数 43 表6 14第五次迭代方案表6 15该方案所用汽车台数 44 得到二条配送路线 B0 B6 B8 B9 B0 行程80公里 用6吨车配送 载重5 1吨 再开始下一条配送路线的选择 过程与前相同 45 反复进行第二 第四步 直至没有可连接的用户时为止 得最终满意配送方案如表6 16 表6 17 表6 16满意配送方案表6 17最终方案所用汽车台数 46
12、满意配送方案有四条配送路线 它们是 B0 B7 B10 B11 B12 B0 行程112公里 用6吨车配送 载重5 6吨 B0 B6 B8 B9 B0 行程80公里 用6吨车配送 载重5 1吨 B0 B5 B0 行程44公里 用4吨车配送 载重1 7吨 B0 B1 B2 B3 B4 B0 行程54公里 用6吨车配送 载重5 8吨 满意方案共用四台车配送 总行程290公里 47 第三节多中心配送路线选择与车辆调度 一 制定多中心配送方案的基本思想多中心配送与单中心配送不同的是 制定配送计划时 不仅要选择配送路线和调度车辆 还要确定各配送中心所服务的用户对象 所以 制定多中心配送的配送计划 首先将
13、所有用户按一定的方法分派给各配送中心 形成每个配送中心的服务区 然后用上一节讨论的节约法在各配送中心的服务区选择配送路线和调度车辆 48 二 制定多中心配送方案的边界点方法 1 边界点与非边界点设di t 表示用户i与配送中心t之间的距离 记集合 p是配送中心的个数 计算 minDi和subminDi分别表示集合Di中的最小值和次小值 取适当的 0 1 比较r i 与 的大小 当r i 称i为非边界点 否则为边界点 显然 通过改变 值的大小可以控制边界点的个数 49 2 非边界点的分派 对非边界点 按最近分派原则 将它们分别分派给离它们最近的配送中心 50 3 边界点的分派 对边界点的分派 按
14、r i 1和r i 1两种情况分别处理 1 当r i 1时 用节约法进行分派 首先考虑由最近的配送中心对每个点单独派车配送 构成初始解 一旦两个点或多个点已被分派给同一个配送中心时 这些点为永久分派 不能再分派给其他配送中心 如果i j不在同一配送中心 按一般节约法将其连接并分别试分配给某一配送中心 连接产生的节约量按下式 6 8 计算 51 式中 选最大者 将i j分派给对应的t j点还未给一永久分派 挪到非最近配送中心否则 i点还未给一永久分派 挪到非最近配送中心否则 52 2 当r i 1时 按如下方法分派 将i分别试分派给各配送中心t t 1 p 若j和k是已分派给配送中心t的用户 将
15、点i插入用户j与k之间 若t中心只有一个用户j 则将i插入j与t之间 对配送中心t产生的运输距离增加量按 6 9 式计算 按增加量最小原则 将用户i分派给使djik t 或dij t 最小的配送中心 6 9 53 对所有用户分派完毕后 分别在每个配送中心的服务区域内 用节约法确定配送路线和进行车辆调度 得到各配送中心的配送计划 54 例 假设有三个配送中心 编号是1 2 3 给10个用户 编号是4 13 配送货物 配送中心与用户以及用户与用户之间的运输距离如表6 18 表6 18配送中心及用户之间的距离 单位 公里 55 计算r i 得表6 19 表6 19r i 数值表 56 取 0 7 所
16、有r i 的用户分派给最近的配送中心 如表6 20 表6 20非边界点用户分派表 57 对r i 且r i 1的点8 10和12 根据式 6 8 计算 i j 8 10 12 t 1 2 3 并按从大到小的顺序排列 列于表6 21 表6 21r i 1的边界点用户试连接的节约量表根据表6 21 按节约量最大原则 把用户8和10分派给配送中心1 得到永久分配 把用户12分派给配送中心3 58 对r i 1的用户13 分别试分派给各配送中心 根据式 6 9 计算最小增加值 并按从小到大的顺序排列 列于表6 22 表6 22用户13试分派增加值根据表6 22 按增加值最小原则 把用户13分派给中心1 并插入到用户5和10之间 得最终分派方案 如表6 23 59 表6 23最终用户分派方案对各个配送中心分派的用户 再用节约法求每个配送中心的配送方案 得到最后结果
