第7次课运输路线选择(1)

1、运输调度管理运输调度管理 运输路线选择运输路线选择 本次课程本次课程 项目项目2.3 任务任务2.3.1 情境2.3.1：远大公司的汽车配件需从义乌运至北 仑，结合浙江省详细地图，做好运输路径优化： 现要求你找出路程最短的运输路线。 案例1：百胜物流降低连锁餐饮企业运输成本之道 任务任务1 运用标号法完成起讫点不同的单一运输路线优化选择运用标号法完成起讫点不同的单一运输路线优化选择 情境2.3.2：由于时间很赶，需要你找出花费时间最短的运输路线。 任务任务2 运用标号法和软件操作完成起讫点不同的单一运输路线优化选择运用标号法和软件操作完成起讫点不同的单一运输路线优化选择 情境2.3.3：这票货

2、物赚的不多，在时间允许的情况下，需要你找出成本 最低的运输路线。 情境2.3.4：义乌公司的仓库有多个，现接到联发的装货通知，义乌公司 需从其各个仓库提货到总公司。请为该业务设计运输路线并调度。 任务任务3 运用扫描法完成起讫点重合的运输路线优化选择运用扫描法完成起讫点重合的运输路线优化选择 知识目标：知识目标： 1.了解运输路线的类型；了解运输路线的类型； 2.掌握最短路（单一起讫点运输路线）的原理和计算方法掌握最短路（单一起讫点运输路线）的原理和计算方法 3.了解起讫点重合运输路线的优化问题了解起讫点重合运输路线的优化问题 4. 了解多起讫点的运输路线优化问题了解多起讫点的运输路线优化问题

3、 能力目标：能力目标： 1.能运用最短路方法正确制定运输路线选择方案；能运用最短路方法正确制定运输路线选择方案； 2.能运用计算机软件正确制定运输路线选择方案能运用计算机软件正确制定运输路线选择方案 素质目标：素质目标：成本意识、优化思维能力成本意识、优化思维能力 、自主学习能力。、自主学习能力。 案例1：百胜物流降低连锁餐饮企业运输成本之道 合理安排运输排程合理安排运输排程 运输排程的意义在于，尽量使车辆满载，只要货量许可，就应该做相 应的调整，以减少总行驶里程. 运输排程的构想最初起源于运筹学中的路线原理，其最简单的是从起 点A到终点O有多条路径可供选择，每条路径的长度各不相同，要求找到最

4、 短的路线。实际问题要比这个模型复杂得多，首先，需要了解最短路线的 点数，从几个点增加到成百甚至上千个，路径的数量也相应增多到成千上 万条。其次，每个点都有一定数量的货物流需要配送或提取，因此要寻找 的不是一条串联所有点的最短路线，而是每条串联几个点的若干条路线的 最优组合。另外，还需要考虑许多限制条件，比如车辆装载能力、车辆数 目、每个点在相应的时间开放窗口等，问题的复杂度随着约束数目的增加 呈几何级数增长。要解决这些问题，需要用线性规划、整数规划等数学工 具，目前市场上有一些软件公司能够以这些数学解题方法作为引擎，结合 连锁餐饮业的物流配送需求，做出优化运输路线安排的软件。 运输优化策略运

5、输优化策略 运输路线选择运输路线选择 微课：运输路线和时间安排的原则微课：运输路线和时间安排的原则 情境2.3.1：远大公司的汽车配件需从义乌运至北仑，结合浙江省详细地图， 做好运输路径优化：现要求你找出路程最短的运输路线。 任务任务1 运用标号法完成起讫点不同的单一运输路线优化选择运用标号法完成起讫点不同的单一运输路线优化选择 宁波联发物流有限公司需要在本月底将浙江远大 汽车配件从义乌运送到北仑。该公司根据这两个城市 之间可选择的行车路线的地图,绘制了如图的公路网络. 图中,圆圈称为节点,代表起点、目的地和与行车路线 相交的其他城市，箭头代表两个节点之间的公路，每 条公路都表明运输里程。求A

6、市到B市的最短路？ 义乌 50 75 85 150 140 100 85 135 100 150 100 200 80 60 75 50 北仑 计算步骤： 0 50 75 85 175 160 210 275 240 315 义乌 50 75 85 150 140 100 85 135 100 150 100 200 80 60 75 50 北仑 1、标号，如下图所示： 2、反向搜寻，过程如下： 3、结论：结论：义乌到北仑的的路线选择为1（义乌）-4-5-8-10（北仑）， 最短距离为315公里。 0 50 75 85 175 160 210 275 240 315 义乌 50 75 85 1

7、50 140 100 85 135 100 150 100 200 80 60 75 50 北仑 最短路问题最短路问题 理论总结 起讫点不同的单一运输问题起讫点不同的单一运输问题 采用方法：Dijstra算法 应用条件：1、权非负；2、求一给定点到其余各点最短 通路及其长度。 标号法 临时标号 固定标量给定点到该点的最短通路的长度， 最后用反向搜索法可计算总长度。 原理：如果U= e1, e2, e3 en 为v1到vn的最短距离,则 U1= e1, e2, e3 ek 是v1到vk的最短路. 注： （1）有固定标号的点（检查过的大 上 表示） （2）在所有的临时标号中选最小的 作固定标号，即

8、为将被检查的点； （3）边检查边修改临时标号。 情境2.3.2：由于时间很赶，需要你找出花费时间最短的运输路线。 任务任务2 运用标号法和软件操作完成起讫点不同的单一运输路线优化选择运用标号法和软件操作完成起讫点不同的单一运输路线优化选择 练习：1、标号法完成。 义乌 1 1.5 1 2.5 3 1.5 2 3 2 2.5 1 3 2 1 1 1 北仑 义乌到北仑的运输路线如下（数值代表运输时间：义乌到北仑的运输路线如下（数值代表运输时间：h)h)： 2、软件操作：见微课“最短路EXCEL操作过程” 任务任务2 运用标号法和软件操作完成起讫点不同的单一运输路线优化选择运用标号法和软件操作完成起

9、讫点不同的单一运输路线优化选择 情境2.3.3：这票货物赚的不多，在时间允许的情况下，需要你找出成本最低 的运输路线。 A市 100 150 175 300 275 200 175 275 200 300 200 400 250 125 150 100 B 义乌到北仑的运输路线如下（数值代表运输成本：元义乌到北仑的运输路线如下（数值代表运输成本：元) )： 练习：练习：1、标号法 2、EXCEL求解操作 某配送中心与一个客户之间的公路网络示意图，O起点为配送中心所 在位置，P终点为客户所在位置，其它A、B、C、D代表从O到P途中要经过 的节点，节点与节点之间有线路连接, 线路上标明了两个节点之

10、间的距离， 以运行时间 ( 分钟 ) 表示（当然也可以用距离表示）。现在要在该图找出一 条从配送中心（O起点）到客户（J终点）之间的最短路线。 O P C BD A 18 12 28 4 32 17 32 11 17 练习练习 理论总结 1、运输网络图有点和线组成。点即节点，线即路线； 2、运输网络图：有向图和无向图； 3、起讫点不同的单一运输路线优化选择：标号法、excel求 解。 情境2.3.4：义乌公司的仓库有多个，现接到联发的装货通知，义乌公司 需从其各个仓库提货到总公司。请为该业务设计运输路线并调度。 任务任务3 运用扫描法完成起讫点重合的运输路线优化选择运用扫描法完成起讫点重合的运

11、输路线优化选择 义乌公司从其所属的仓库用送货车辆到各客户点提义乌公司从其所属的仓库用送货车辆到各客户点提 货，然后将客户的货物运回仓库，以便集运成大的批量再货，然后将客户的货物运回仓库，以便集运成大的批量再 进行远程运输。全天的提货量见下图，提货量以件为单位进行远程运输。全天的提货量见下图，提货量以件为单位 。送货车每次可运载。送货车每次可运载1万件，完成一次运行路线一般需要万件，完成一次运行路线一般需要 一天时间。该公司要求确定：需多少条路线（即多少辆送一天时间。该公司要求确定：需多少条路线（即多少辆送 货车）；每条路线上有哪几个客户点；送货车辆途经有关货车）；每条路线上有哪几个客户点；送货

12、车辆途经有关 客户点的顺序。（具体内容见下图）客户点的顺序。（具体内容见下图） 义乌 总公司 4000 1000 3000 2000 1000 2000 2000 2000 2000 3000 2000 3000 总结 物流管理人员经常遇到的一个路线选择问物流管理人员经常遇到的一个路线选择问 题是始发点就是终点的路线选择，又常称题是始发点就是终点的路线选择，又常称 为为“旅行推销员旅行推销员”问题。这类问题通常在问题。这类问题通常在 运输工具是同一部门所有的情况下发生。运输工具是同一部门所有的情况下发生。 邮递员问题邮递员问题 起讫点重合的运输问题起讫点重合的运输问题 是 是 开始 将所有的停

13、留点位置画在地图上 选择最大的车辆装载这个停留点的货物 然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。 通过仓库位置放置一直尺，直尺指向任何方向均可 是否超过车辆容积或体 积的限度 是否扫描完所有 停留点 安排下一辆车装载货物，得到一条运行线路 结束 继续转动直尺，扫描到下一个停留点，分配该 车辆装载货物 优化每条运行路线的停留点顺序，以求运行距离最小化 否 否 扫描法扫描法 扫描法求解过程扫描法求解过程 4000 1000 3000 2000 1000 2000 2000 2000 2000 3000 2000 3000 总结 尽管路线选择问题种类繁多，但可以归为三种基本类型：尽管

14、路线选择问题种类繁多，但可以归为三种基本类型：起迄起迄 点不同的单一问题、起迄点重合的问题、多起迄点问题点不同的单一问题、起迄点重合的问题、多起迄点问题。 多起迄点问题多起迄点问题：如果有多个货源地可以服务于多个目的地时，那么我们面临如果有多个货源地可以服务于多个目的地时，那么我们面临 的问题是，要指定为各目的地服务的供货地，同时要找到供货地、目的地之的问题是，要指定为各目的地服务的供货地，同时要找到供货地、目的地之 间的最佳路径。该问题常发生在多个供应商、工厂或仓库服务于多个客户的间的最佳路径。该问题常发生在多个供应商、工厂或仓库服务于多个客户的 情况下。情况下。 作业 尽管路线选择问题种类繁多，但可以归为三种基本类型：尽管路线选择问题种类繁多，但可以归为三种基本类型：起迄起迄 点不同的单一问题、起迄点重合的问题、多起迄点问题点不同的单一问题、起