第六章_配送运输路线设计1

第六章配送运输路线设计 第一节配送运输概述 一 配送运输 一 概念配送运输是指将顾客所需要的货物通过运输工具从供应点送至顾客手中的活动 特点 配送运输通常是一种短距离 小批量 高频率的运输形式 如果单从运输的角度看 它是对干线运输的一种补充和完善 属于末端运输 支线运输 他以服务为目标 以尽可能满足客户要求为优先 可能是从工厂等生产的仓库直接送至客户 也可能通过批发商 经销商或由配送中心 物流中心转送至客户手中 二 影响配送运输的因素 动态因素 静态因素 三 配送运输的特点 时效性 快速及时 即确保在客户指定的时间内交货 安全性 货物完好无损的送到目的地 沟通性 通过送货上门服务直接与客户接触 方便性 尽可能的让顾客享受到便捷的服务 经济性 以较低的费用 完成配送作业 车流辆变化 道路施工 配送客户的变动 可供调动的车辆变动 如配送客户的分布区域 道路交通网络 车辆运行限制 二 配送运输的基本作业程序 一 划分基本配送区域 二 车辆配载 三 暂定配送先后顺序 四 车辆安排 五 选择配送线路 六 确定最终的配送顺序 七 完成车辆积载 费用 1 外雇车辆 2 自有车辆 运输量 t km 车辆安排 自营还是外包 第二节配送线路优化技术 一 线路优化设计的意义配送线路设计就是整合影响配送运输的各种因素 适时适当地利用现有的运输工具和道路状况 及时 安全 方便 经济地将客户所需的商品准确地送达客户手中 在配送运输线路设计中 需根据不同客户群的特点和要求 选择不同的线路设计方法 最终达到节省时间 运距和降低配送运输成本的目的 第二节配送线路设计 二 配送线路类型1 往复式行驶路线供应点 1个客户 1个客户需求量 可用车辆的核定载重量2 环形式行驶路线供应点1个对应多个客户或客户1个对应多个供应点3 汇集式行驶路线 供应点 客户 第二节配送线路设计 二 配送线路类型2 环形式行驶路线供应点1个对应多个客户或客户1个对应多个供应点 A CA BA A CA B DA EA F 单环形式 交叉环形式 复合环形式 三角环形式 第二节配送线路设计 二 配送线路类型3 汇集式行驶线路 B A C D 分送式 B C D 汇集式 B A C D 分送 汇集式 三配送线路设计 1 直送式配送运输 1 最短路径设计最短线路的方法 Dijkstra算法 也叫标号法 直送式配送运输 是指由一个供应点对一个客户的专门送货 线路 V7 2 4 6 7 V4 2 7 V5 7 2 V2 5 V1 0 2 5 1 6 3 6 2 分送式配送运输 分送式配送是指由一个供应点对多个客户的共同送货 基本条件 同一条线路上所有客户的需求量总和不大于一辆车的额定载重量 送货时 由这一辆车装着所有客户的货物 沿着一条精心挑选的最佳路线依次将货物送到各个客户手中 这样既保证按时按量将用户需要的货物及时送到 又节约了车辆 节省了费用 缓解了交通紧张的压力 并减少了运输对环境造成的污染 一 节约法的基本规定 利用里程节约法确定配送路线的主要出发点是 根据配送方的运输能力及其到客户之间的距离和各客户之间的相对距离来制定使配送车辆总的周转量达到或接近最小的配送方案 二 节约法的基本思想 方案a 的配送路线为p0 pi p0 pj p0 配送距离为da d0i d0j方案b 配送路线p0 pi pj p0 配送距离为db d0i d0j dij显然 da不等于db 我们用sij表示里程节约量 即方案b 比方案a 节约的配送里程 1 节约里程法 案例分析 例 某一配送中心p0向10个客户pj j 1 2 10 配送货物 其配送网络如图11 9所示 图中括号内的数字表示客户的需求量 T 线路上的数字表示两节点之间的距离 配送中心有2t和4t两种车辆可供使用 试制定最优的配送方案 第一步 计算最短距离 根据配送网络中的已知条件 计算配送中心与客户及客户之间的最短距离 结果见下表 第二步 计算节约里程sij 第三步 将节约sij 进行分类 按从大到小的顺序排列 得表 第四步 确定配送线路 从分类表中 按节约里程大小顺序 组成线路图 1 初始方案 对每一客户分别单独派车送货 结果如图所示 修正方案4 2 两阶段法 一 先求出一个可行解 然后对现有可行解进行反复地局部扰乱 以达到较好的解 二 利用VSP模型的特征 将一个整体优化问题分解成两步进行优化计算 2 两阶段法 先路径后分组算法第一阶段 形成包含所有需求点的路径第二阶段 根据一定的约束 如车辆容量 距离 时间等 对它进行划分 形成各配送车辆的路径 2 两阶段法 先路径后分组算法步骤第一步 寻求对于每个节点通过一次且只通过一次的巡回路径 设表达巡回路径的序列为 i 表示回路第i个通过的点 而 0 为配送中心 第二步 按照车辆路径上的客户必须在 上是连续的 并且满足给定条件 如最大装载量 最大运输距离等 进行分组 第三步 确定各组需求的访问顺序 2 两阶段法 先路径后分组算法步骤 第三步 确定各组需求的最优访问顺序 最优访问顺序可应用最优划分法求解 最优划分法 当访问所有需求点的巡回路径已经确定的条件下 最优划分法给出了一种不破坏巡回路径顺序的 最优 分组方法 设巡回路径的序列为0 1 n 令 Cij为满足装载量约束和的按巡回路径 的顺序从第i 1个需求点到第j个需求点的费用加上两端点到配送中心费用 在计算Cij时 还需满足不超出最大运输距离或运输时间 最优划分法 求解步骤 第一步 将需求点集合N构筑成为每个点恰好通过一次的巡回路径 设表示巡回路径的序列为 第二步 应用Cij确定 中任意两点间的距离费用矩阵 Cij 第三步 以点0为起点 以点 n 为终点 求解最短路径L 第四步 对于最短路径L上的所有有向枝 i j 输出分组路径0 i 1 j 0 第三节车辆调度 一 影响因素 一 货物 二 车辆 三 配送中心 四 客户 五 运输网络 六 约束条件 七 目标函数 60 B330 50 20 第三节车辆调度 二 方法 一 图上作业法1 绘制交通图设有A1 A2 A3三个配送点分别有化肥40t 30t 30t 需送往四个客户点B1 B2 B3 B4 而且已知各配送点和客户点的地理位置及它们之间的道路通阻情况 可据此制出相应的交通图 A330 B110 A140 B440 B220 A230 40 30 40 50 运距运量交通图 2 将初始调运方案反映在交通图上 凡是按顺时针方向调运的货物调运线路 如A3至B1 B1至B4 A2至B3 其调运箭头线都画在圈外 称为外圈 否则 其调运箭头线 A3至B3 都画在圈内 称为内圈 3 检查与调整 首先分别计算线路的全圈长 内圈长和外圈长 圈长即指里程数 如果内圈长和外圈长都分别小于全圈长的一半 则该方案即为最优方案 否则 即为非最优方案 需要对其进行调整 第三节车辆调度 二 方法 三 基于时间窗车辆调度1问题的描述设Ti为任务i装 卸 货所需时间 ETi为任务i的允许最早开始时间 LTi为任务i的允许最迟开始时间 即任务i的开始时间需在一定的时间范围 ETi LTi 内 求满足货运要求的费用最少的车辆行驶线路 称此问题为有时间窗的车辆优化调度问题 第三节车辆调度 1问题的描述以si表示车辆到达i点的时间 tij表示车辆由点i行驶到点j的时间 一般应满足以下关系式s0 0ETi si LTi式中 s0 0表示从车场出发 若每项任务必须在要求的时间范围内完成 即必须满足上式 否则得到的解为不可行解 称之为硬时间窗VSP 若某项任务不能在要求的时间范围内完成 则给予一定的惩罚 称之为软时间窗VSP 第三节车辆调度 2模型建立 第三节车辆调度 2模型建立 第三节车辆调度 2模型建立 第三节车辆调度 3算法原理 第三节车辆调度 3算法原理 第三节车辆调度 3算法原理 第三节车辆调度 案例 第三节车辆调度 二 方法 四 遗传算法1基本思想 第三节车辆调度 二 方法 四 遗传算法2基本步骤 第三节车辆调度 二 方法 四 遗传算法2基本步骤 第三节车辆调度 二 方法 四 遗传算法2基本步骤 第三节车辆调度 二 方法 四 遗传算法2基本步骤 第三节车辆调度 二 方法 四 遗传算法2基本步骤 比如有些危险品必须减载运送才能保证安全 第四节配送车辆积载技术 一 影响配送车辆积载因素 货物特性因素 货物包装情况 不能拼装运输 由于装载技术的原因 造成不能装足吨位 轻泡货物吨位利用率降低 如车厢尺寸不与货物包装容器的尺寸成整倍数关系 则无法装满车厢 二 车辆积载的原则 一 轻重搭配的原则 二 大小搭配的原则 三 货物性质搭配原则 四 到达同一地点的适合配装的货物应尽可能一次积载 五 确定合理的堆码层次及方法 将重货置于底部 轻货置于上部 避免重货压坏轻货 并使货物重心下移 拼装在一个车厢内的货物 其化学性质 物理属性不能互相抵触 可根据车厢的尺寸 容积 货物外包装的尺寸来确定 六 装载时不允许超过车辆所允许的最大载重量 七 装载易滚动的卷状 桶状货物 要垂直摆放 八 货与货之间 货与车辆之间应留有空隙并适当衬垫 防止货损 九 装货完毕 应在门端处采取适当的稳固措施 以防开门卸货时 货物倾倒造成货损 十 尽量做到 后送先装 三 提高车辆装载效率的具体办法 研究各类车厢的装载标准 根据不同货物和不同包装体积的要求 合理安排装载顺序 努力提高装载技术和操作水平 力求装足车辆核定吨位 根据客户所需要的货物品种和数量 调派适宜的车型承运 这就要求配送中心根据经营商品的特性 配备合适的车型结构 凡是可以拼装运输的 尽可能拼装运输 但要注意防止差错 配载模型 装载货物的价值最大 假设配送车辆的最大载重量为G 用于运送n种不同的物品 此n种不同物品的重量分别为W1 W2 Wn 每一种物品的价值系数 可表现为价值 运费等 用P1 P2 Pn表示 另设Xk表示第k种物品的装入数量 则在条件下 配载模型 考虑优先级情况下 1问题描述 配载模型 考虑优先级情况下 1建立模型 客户需求优先系数表 两阶段算法思路 先将装剩余的 n一k 件货物看作为 n一k 个阶段完成 用j j