两个例子 - 节约里程法
- 格式:ppt
- 大小:1023.50 KB
- 文档页数:18
节约里程法的应用1.基本资料介绍①宝洁公司是广州配送中心最大的服务商,为其配送的客户和货量见下表,我们以广州配送中心为例来说明有装载限制的车辆调度的优化方法。
公司客户分布在全国各地,这里主要以广东省内7家客户及省外一家特殊客户的一次配送为例。
城市和货运量②广州配送中心为这次配送提供了三种车型,载重量分别为2吨、5吨和8吨,不同车型的运输单价不一样,具体见运输单价表。
配送中心的配送是由外协商提供车辆,因此汽车的数量没有限制。
运输单价表2.步骤第一步:各城市之间的距离见上表。
第二步:计算连接城市到同一线路上的距离节约值,具体见下表。
第三步:确定初始方案的运输线路及运输费用,现安排4辆2吨、4辆5吨的车给每个客户送货。
运输线路及运输费用见下表所示。
运输线路及运输费用运输路线车型距离单价运费广州-东莞5T 50 2.7 135广州-江门2T 53 2.4 127.2广州-惠州2T 116 2.4 278.4广州-阳江5T 173 2.7 467.1广州-汕尾5T 221 2.7 596.7广州-揭阳5T 333 2.7 899.1广州-汕头2T 344 2.4 825.6广州-漳州2T 478 2.4 1147.2合计1768 4476.3第四步:进行线路第一次优化。
第一次修改后的车辆调度结果运输路线车型距离单价运费广州-东莞5T 50 2.7 135 广州-江门2T 53 2.4 127.2 广州-惠州2T 116 2.4 278.4 广州-阳江5T 173 2.7 467.1 广州-汕尾5T 221 2.7 596.7 广州-揭阳5T 333 2.7 899.1 广州-汕头-漳州5T 502 2.7 1355.4 合计1148 3858.9第五步:继续进行线路优化。
第二次修改后的车辆调度结果运输路线车型距离单价运费广州-东莞5T 50 2.7 135广州-江门2T 53 2.4 127.2广州-惠州2T 116 2.4 278.4广州-阳江5T 173 2.7 467.1广州-汕尾5T 221 2.7 596.7 广州-揭阳-汕头-漳州8T 526 3.65 1919.19 合计1139 3523.59从表中可以看出,广州-惠州-揭阳-汕头-漳州路线上的总货运量达到7.9吨,再连接任何一个城市都将使货运量超过最高限制(8吨),则不能继续配载,所以可以首先确定的是这一条线路。
节约里程法路径优化节约里程法是一种用于路径优化的方法,通过选择最短路径来减少行程中的里程数。
在现实生活中,我们经常需要规划行程,比如出差、旅行或者日常的通勤。
而选择最优路径可以节省时间和精力,提高效率。
下面我将以一个出差的例子来说明如何使用节约里程法进行路径优化。
假设我需要从A市出差到B市,那么我可以通过多种交通方式进行选择,比如飞机、火车、汽车等。
为了节约里程,我需要考虑以下几个因素:距离、时间、费用和舒适度。
我可以考虑乘坐飞机。
飞机通常是最快的交通工具,可以快速到达目的地。
然而,飞机票价格较高,且需要提前预订。
如果我需要频繁出差,花费较多的机票费用可能会对我的财务造成一定的压力。
我可以选择乘坐火车。
火车通常比汽车更舒适,且价格相对较低。
但是,火车的速度可能较慢,行程可能需要更长的时间。
如果我需要在短时间内到达目的地,乘坐火车可能不是最佳选择。
我可以选择乘坐汽车。
汽车的灵活性较高,我可以根据需要随时停下来休息或处理其他事务。
然而,长途驾驶可能会让我感到疲劳,而且汽车的油费和路桥费用也需要考虑。
综合考虑以上因素,我可以做出最优选择。
如果时间充裕且预算充足,我可以选择乘坐飞机,以最快的速度到达目的地。
如果时间有限,但预算有限,我可以选择乘坐火车,虽然时间稍长,但价格相对较低。
如果我喜欢自驾旅行或者需要灵活性,我可以选择乘坐汽车。
节约里程法可以帮助我在出差或旅行时选择最优路径。
通过综合考虑距离、时间、费用和舒适度等因素,我可以做出最合适的决策。
这样不仅可以节约里程,还可以提高出差或旅行的效率和体验。
希望这种方法能对大家在路径优化方面提供一些参考和帮助。
物流方案设计(最优运输路线决策-节约里程法)典型实例:已知配送中心P O向5个用户P j配送货物,其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图与表所示:图中括号内的数字表示客户的需求量(单位:吨),线路上的数字表示两结点之间的距离,配送中心有3台2t卡车和2台4t两种车辆可供使用,1、试利用节约里程法制定最优的配送方案?2、设卡车行驶的速度平均为40公里/小时,试比较优化后的方案比单独向各用户分送可节约多少时间?第(1)步:作运输里程表,列出配送中心到用户及用户间的最短距离。
得初始方案配送距离=39X 2=78KM第(5)步:根据载重量约束与节约里程大小,将各客户结点连接起来,形成二个配送路线。
即A B 两配送方案。
序号 路线 节约里程 序号 路线 节约里程1 P 2P 3 10 6 P i F 52 2 P 3P 4 8 7 P i P3 1 3 P 2P4 6 8 F 2F5 0 4 P 4P 5 5 9 F 3F 5 0 5P l P 2410P i F 4第(2)步:由运输里程表、按节约里程公式,求得相应的节约里程数,如上表( 第(3)步:将节约里程 sij 进行分类,按从大到小顺序排列第(4)步:确定单独送货的配送线路)内。
(1.5)①配送线路A:P0-P2-P3-P4- P 0 运量q A= q 2+q3+q4 = 1.7+0.9+1.4 = 4t 用一辆4t 车运送节约距离S A =10 +8 = 18km②配送线路B: P 0-P5 -P 1-P0 运量q B =q 5+q1=2.4+1.5=3.9t<4t 车用一辆4t 车运送节约距离S B=2km第(6)步:与初始单独送货方案相比,计算总节约里程与节约时间总节约里程:△ S= S A+S B= 20 km与初始单独送货方案相比,可节约时间:△T = △ S/V=20/40=0.5小时。
物流方案设计(最优运输路线决策-节约里程法)典型实例:已知配送中心P O向 5 个用户 P j配送货物,其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图与表所示:图中括号内的数字表示客户的需求量(单位:吨),线路上的数字表示两结点之间的距离,配送中心有 3 台 2t 卡车和 2 台 4t 两种车辆可供使用,1、试利用节约里程法制定最优的配送方案?2、设卡车行驶的速度平均为40 公里 / 小时,试比较优化后的方案比单独向各用户分送可节约多少时间?( 0.9)P3 4( 1.7)5P2 6128( 1.4)12 P4 7 P0 1312 10 8P5 16P1 ( 1.5)需要量P0( 2.4)1.5 8 P11.7 8 12 P20.9 6 13 4 P31.4 7 15 9 5 P42.4 10 16 18 16 12 P5第( 1)步:作运输里程表,列出配送中心到用户及用户间的最短距离。
需要量0 P1.5 8 P11.7 8 ( 4)P12 20.9 6 (1)( 10)P3 13 41.4 7 (0)(6)(8)4 15 9 5 P2.4 10(2)(0)(0)(5)16 18 16 P512第( 2)步:由运输里程表、按节约里程公式,求得相应的节约里程数,如上表()内。
第( 3)步:将节约里程sij 进行分类,按从大到小顺序排列序号路线节约里程序号路线节约里程1 P2P3 10 6 P1 P5 22 P P 8 7 P P 13 4 1 33 P P 6 8 P P 02 4 2 54 P4P5 5 9 P3 P5 05 P1P2 4 10 P1 P4 0第( 4)步:确定单独送货的配送线路(0.9)P3 ( 1.7 )P268( 1.4)P4 7P0108P5P1(1.5)(2.4 )得初始方案配送距离 =39× 2=78KM第( 5)步:根据载重量约束与节约里程大小,将各客户结点连接起来,形成二个配送路线。
物流方案设计(最优运输路线决策-节约里程法)典型实例:已知配送中心P O向5个用户P j配送货物,其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图与表所示:图中括号内的数字表示客户的需求量(单位:吨),线路上的数字表示两结点之间的距离,配送中心有3台2t卡车和2台4t两种车辆可供使用,1、试利用节约里程法制定最优的配送方案?2、设卡车行驶的速度平均为40公里/小时,试比较优化后的方案比单独向各用户分送可节约多少时间?(0.9)第(1)步:作运输里程表,列出配送中心到用户及用户间的最短距离。
-第(2)步:由运输里程表、按节约里程公式,求得相应的节约里程数,如上表( )内。
第(3)步:将节约里程sij 进行分类,按从大到小顺序排列得初始方案配送距离=39×2=78KM第(5)步:根据载重量约束与节约里程大小,将各客户结点连接起来,形成二个配送路线。
即A 、B 两配送方案。
((2.4)1.5)((0.9))①配送线路A:P0-P2-P3-P4- P0运量q A= q2+q3+q4= 1.7+0.9+1.4= 4t用一辆4t车运送节约距离S A =10 +8 = 18km②配送线路B: P0-P5-P1-P0运量q B =q5+q1=2.4+1.5=3.9t<4t车用一辆4t车运送节约距离S B=2km第(6)步:与初始单独送货方案相比,计算总节约里程与节约时间总节约里程:△S= S A+ S B= 20 km与初始单独送货方案相比,可节约时间:△T =△S/V=20/40=0.5小时欢迎下载,谢谢观看!资料仅供参考学习-。
配送路径优化节约里程法事例一、配送的困扰说起配送这事儿,大家都有点经验吧?那种看似简单、实则复杂的送货过程,光是坐车的时间都能让人崩溃。
有时候就算是个小小的东西,送到手里的时间也不一定那么准时。
你看,那些送货员的车,东绕西绕的,绕了半天,回头一看,距离目的地明明就不远,怎么感觉走了好几条弯路,浪费了不少油,吃了不少时间。
说得通俗点,那就是配送路径没优化好!你说,谁家不想节省点里程呢?这不仅能省钱,还能节省油费,最重要的是,减少了送货员心里的压力。
所以啊,这个配送路径优化的事儿,真的得好好琢磨一番。
二、路径优化的作用那这优化到底是个啥意思呢?如果送货员每次都能按照最短的路程走,不用左拐右绕,不用在每个交叉路口犹豫半天,效率自然就高了。
这种“少走弯路”的办法,不仅能节省时间,车辆油耗也会降低,大家的心情也能轻松点。
你想想,不再碰到那种“导航指路,车却走偏”的尴尬局面,不再在车里等个十几分钟,真的是大大的爽。
再加上现在的技术那么先进,有了路径优化,送货员的负担轻了,企业的运营成本也降低了,一举两得,岂不是美滋滋?但是,如何优化呢?这可不是那么简单的事儿,得好好分析。
得从每一个配送的起点和终点开始算,合理规划每一条路线。
有的配送中心本来就不远,但因为道路复杂、交通状况不好,结果走了许多不必要的冤枉路。
你要知道,那种高峰期的交通,光是堵个红绿灯,差不多就得半小时过去。
再加上,某些路段的繁忙程度,早高峰、晚高峰的时候可不是闹着玩的。
那种时间上的浪费,实在是让人心烦。
你能想象吗?你本来预计一个小时就能到的地方,结果送了两小时才到,最后客户也没了耐心,甚至还得打个电话投诉。
那场面可真是尴尬死了。
三、具体实施路径优化说到这里,很多人可能就会问了,那要怎么实施路径优化呢?其实现在有很多高效的系统,可以根据实际情况帮你算出最短路径。
比如,根据每条道路的交通状况、道路的宽窄程度、甚至是天气情况来优化路线。
你要知道,不是所有的道路都能通行,尤其在一些小巷子里,车子一进去了,根本就转不过来。
算例:节约里程法以上一个二维码扫描算法算例为例,用节约里程法计算配送线路的安排。
解:① 首先根据上一个二维码扫描算法算例中的距离矩阵表计算出各点间的节约值矩阵表,如表1所示。
表1 节约值矩阵表② 从表1中选出节约值最大值为23,其对应的两个顶点为5、6。
5、6两处的需求量之和为8,未超过一辆车的运输能力14,因此,连接5、6成回路,即0—5—6—0。
再将顶点5与6的节约值赋为0,结果如表2所示。
表2 节约矩阵表计算过程1③ 从表2中再选出节约值最大值为20,其对应的两个顶点为7、8。
7、8两处的需求量之和为7,未超过一辆车的运输能力14,因此,连接7、8成回路,即0—7—8—0。
再将顶点7与8的节约值赋为0,结果如表3所示。
表3 节约矩阵表计算过程2④ 从表3中再选出节约值最大值为16,其对应的两个顶点为5、8或6、8。
如果连接5与8,则上述两条回路合并,其总需求量为15,超过一辆车的运输能力14,因此,5与8不能连接,同样6和8也不能连接,则将顶点5、8和6、8的节约值赋为0,结果如表4所示。
表4 节约矩阵表计算过程3⑤ 从表4中再选出节约值最大值为15,其对应的两个顶点为4、6。
如连接4与6,则形成:0—5—6—4—0回路,其总需求量为11,未超过一辆车的运输能力14,因此,连接4、6成新回路,即0—5—6—4—0。
再将顶点4与6的节约值赋为0,同时,由于顶点6成为回路的中间点,则与顶点6相关的节约值都赋为0。
表示顶点6不可能再与其他点相连,其结果如表5所示。
表5-33 节约矩阵表计算过程4⑥ 按算法步骤迭代运算,直到节约值矩阵表中的值均为0时,迭代结束。
最终的结果为:0—2—3—0,0—5—6—4—0,0—7—8—1—0这三条线路,其运输量分别为9、11、13,总里程数为93。
一般来说,节约里程法可以得到比较好的结果,但此算法也是一种贪婪启发式算法,对于一些特殊的算例,得不到最优解。
上一个二维码中算例的全局最优解是:选择0—1—3—0,0—2—7—8—0,0—5—6—4—0这三条线路,其运输量分别为11、11、11,总里程数为90。
节约里程法应用案例在当今竞争激烈的商业环境中,物流成本的有效控制对于企业的生存和发展至关重要。
节约里程法作为一种优化配送路线的有效方法,能够显著降低运输成本,提高物流效率。
接下来,让我们通过一个具体的案例来深入了解节约里程法的实际应用。
假设我们有一家位于城市中心的配送中心,需要向位于城市不同区域的五个客户(A、B、C、D、E)配送货物。
每个客户的需求量以及他们之间的距离如下表所示:|客户|需求量(吨)|与配送中心距离(公里)||||||A|5|10||B|8|12||C|3|8||D|6|15||E|4|11||客户|A|B|C|D|E|||||||||A| | 18 | 22 | 25 | 16 ||B| 18 || 10 | 18 | 12 ||C| 22 | 10 || 14 | 9 ||D| 25 | 18 | 14 || 20 ||E| 16 | 12 | 9 | 20 ||首先,我们按照传统的方法,即每个客户单独配送,计算出总运输里程。
配送中心到客户 A 的往返里程为 2×10 = 20 公里。
配送中心到客户 B 的往返里程为 2×12 = 24 公里。
配送中心到客户 C 的往返里程为 2×8 = 16 公里。
配送中心到客户 D 的往返里程为 2×15 = 30 公里。
配送中心到客户 E 的往返里程为 2×11 = 22 公里。
总运输里程为 20 + 24 + 16 + 30 + 22 = 112 公里。
接下来,我们应用节约里程法来优化配送路线。
第一步,计算两两客户之间的节约里程数。
例如,客户 A 和客户 B 之间的节约里程数为:(配送中心到 A 的距离+配送中心到 B 的距离 A 到 B 的距离)× 2 =(10 + 12 18)× 2 = 8 公里。
按照同样的方法,计算出所有两两客户之间的节约里程数,如下表所示:|客户|A|B|C|D|E|||||||||A| | 8 | 6 | 5 | 2 ||B| 8 || 4 | 3 | 4 ||C| 6 | 4 || 2 | 3 ||D| 5 | 3 | 2 || 5 ||E| 2 | 4 | 3 | 5 ||第二步,根据节约里程数的大小对路线进行合并和优化。
节约里程法例题
问题描述
某公司为了降低员工的交通成本,制定了节约里程法,规定员工在每周的通勤过程中,只能行驶一定的里程数。
具体规定如下:
•每位员工每周最多行驶300公里的里程数;
•员工每行驶一公里,公司会额外支付0.5元。
现在需要使用节约里程法计算员工每周的交通费用。
算法设计
节约里程法的核心思想是根据员工的行驶距离来计算交通费用。
算法的基本步骤如下:
1.设置变量total_mileage为员工总行驶里程数,初始值为0;
2.设置变量total_cost为员工总交通费用,初始值为0;
3.循环执行以下步骤:
–输入本次行驶的里程数mileage;
–如果mileage + total_mileage大于300,则将total_cost 增加300 - total_mileage * 0.5,并将total_mileage更新为300;
–否则,将total_cost增加mileage * 0.5,并将
total_mileage增加mileage;
–如果total_mileage等于300,则退出循环。
4.输出员工总交通费用total_cost。
算法实现
以下是使用Python语言实现节约里程法的代码示例:
```python def calculate_transport_cost(): total_mileage = 0 total_cost = 0
while total_mileage < 300:
mileage = float(input(\。
节约里程法1.原理设P 为配送中心,A 和B 为收货点,相互之间的道路距离为a , b , c 。
若分别使用两辆货车分别向A 、B 两地往返送货,其行驶里程为:2a+2b 。
但若使一辆货车(货车可以满载两地送货)由P → A →B →P ,单线巡回送货,其行驶总里程为a+c+b 。
两者相比,后一种方案比前一种送货方案可节省的运输距离是: (2a+2b )-(a+c+b )= a + b - c > 0这一节约距离称为节约里程,所以我们称这种方法为“节约里程法”。
2 .实例由于案例所给内容有限,所以我们自行上网查找了一些资料。
下图是我们找到的位于郑明现代物流有限公司上海总部周边的一些大型商超,下面我们就假设这些超市为郑明现代物流有限公司的配送点,利用节约里程法来设计末端配送网络的合理运输。
上海郑明现代物流有限公司周边的商超配送点PABacb图X-X备注:1 . 红色五角星所在位置即为郑明现代物流有限公司的所在地(P)2 . 紫色圆圈即为超市配送点的位置及其名称(从左至右依次为:城市超市(A)、沃尔玛超市(B)、世纪华联超市(C)、联华超市(F)、家乐福超市(D)、大润发超市(E))为直观清晰的了解郑明现代物流有限公司与给超市配送点之间的关系,我们将上图简化为下图(图X-X)的简易图形。
线段旁的数字为两者之间的距离,单位:km.图X-X节约里程法的求解过程如下:1.计算配送中心P 到各个配送点及各配送点之间的最短路距离,如下表最短距离表P ABCDEFP A 4.7B 2.8 6.8C 0.6 4.2 2.9D 8 12.7 6.1 8.6E 7.4 12.1 9.2 8 3.1F1.83.24.62.49.89.14.26.12.96.80.62.883.17.49.11.83.2BDFA C EP2.计算各个配送点之间的节约里程,如下表节约里程表A B C D E FAB 0.7C 1.1 0.5D 0 4.7 0E 0 1 0 12.3F 3.3 0 0 0 0.13.进行排序:节约里程排序表序号连接节约序号连接节约1 DE 12.3 8 AD 02 BD 4.7 9 AE 03 AF 3.3 10 BF 04 AC 1.1 11 CD 05 AB 0.7 12 CE 06 BC 0.5 13 CF 07 EF 0.1 14 DF 04.得出线路安排线路一:P →E →D →B →P 节约里程为:12.3+4.7= 17 km 线路二:P →F →A →C →P 节约里程为:3.3+1.1= 4.4 km如果没有使用节约里程法来进行商超的配送,那么结果是怎样的呢?假定初始配送方案是由中心点P 按最短路径向其余各个点分别进行送货,则总配送里程为:2x(0.6+4.2+1.8+7.4+8+2.8)=49.6 km 。
由配送中心A 向两个用户M 、N 送货,A 至M 、N 的最短距离分别为l1和l2,M 、N 之间的距离为l3,用户M 、N 对货物的需求量分别为q1和q2。
如图:若用两辆汽车分别对A 、B 两个用户所需货物,各自往返送货时,汽车直行总里程为:l=2(l1+l2)如果改为有一辆汽车向M 、N 两个用户巡回送货(设q1+q2<汽车标重载重量),则汽车走行里程为: l=l1+l2+l3后一种送货方案比前一种送货方案节约的汽车走行里程为: △l=[2(l1+l2)]-(l1+l2+l3)=l1+l2-l34 案例分析如图所示:由配送中心P 向A-H8个用户配送货物。
图中连线上的数字表示两点间的里程(km ),图中靠近个用户括号内的数字,表示各用户对货物的需求量(t )。
配送中心备有2t 和3t 载重量的汽车,且汽车一次巡回里程不超过35km 。
色送到时间均符合客户要求。
求改配送中心的最优送货方案。
﹙q1﹚(q2)节约里程表A B C D E F G HA 9 2 0 0 0 0 7B 8 5 0 0 0 6C 11 3 0 0 0D 10 5 0 0E 9 2 0F 13 3G 6H根据节约里程表中节约里程的顺序,由大到小排列,编制节约里程顺序表。
节约里程顺序表根据节约里程顺序表和配车(车辆的载重),车辆行驶里程等约束条件,渐进绘出如图所示配送路径.路径A:2t车,走行24km,载重量1.8t。
路径B:3t车,走行33km,载重量3.0t。
路径C:3t车,走行23km,载重量2.8t。
总共行走80km,节约里程60km。
从图中可看:一次确定的A、B、C三条路径均符合配送中心的约束条件。
需要2t汽车1辆,3t汽车2辆,总走行里程为80km,若简单的每个用户派一辆汽车配送,需要2t汽车8辆,走行总里程为140km。
通过比较可以看出,利用节约里程法制定配送方案确定送货路径,具有明显效果。
节约里程法及举例1当由一个配送中心向多个客户进行共同送货,在一条线路上的所有客户的需求量总和不大于一辆车的额定载重量时,由这一辆车配装着所有客户需求的货物,按照一条预先设计好的最正确路线依次将货物送到每一客户手中,这样既可保证按需将货物及时送交,同时又能节约行驶里程,缩短整个送货时间,节约费用。
节约里程法正是用来解决这类问题的较成熟的方法。
用节约里程法确定配送路线的主要思路是,根据配送中心的运输能力及其到各客户之间的距离和各客户之间的相对距离,来制定使总的配送车辆吨公里数到达或接近最小的配送方案。
节约里程法的根本思路如下图,P 为配送中心所在地,A 和B 为客户所在地,相互之间道路距离分别为a 、b 、c 。
最简单的配送方法是利用两辆车分别为A 、B 客户配送,此时,如图〔b 〕所示,车辆运行距离为2a 2b 。
然而,如果按图〔c 〕所示改用一辆车巡回配送,运行距离为abc 。
如果道路没有什么特殊情况,可以节省的车辆运行距离为2a 2b –abc =ab –c >0,这个节约量“ab –c 〞被称为“节约里程〞。
AAABPPPB(a )物流网络(c )用一辆车配送ac ba cb ab c图 配送中心配送路线的选择1郑克俊仓储与配送管理〔第四版〕科学出版社 修订。
步骤:实际上如果给数十家、数百家客户配送,〔1〕应首先计算包括配送中心在内的相互之间的最短距离,〔2〕然后计算各客户之间的可节约的运行距离,〔3〕按照节约运行距离的大小顺序连结各配送地并设计出配送路线。
下面举例说明节约里程法的求解过程。
例节约里程法举例图为某配送网络,P为配送中心所在地,A~J为客户所在地,共10个客户,括号内的数字为配送量〔单位:吨〕,路线上的数字为道路距离〔单位:千米〕。
现有可以利用的车辆是最大装载量为2吨和4吨的两种厢式货车,并限制车辆一次运行距离在30千米以内。
为了尽量缩短车辆运行距离,试用节约里程法设计出最正确配送路线。