包钢水泥配送路线优化

1、物流系统规划 课程设计学 院 班 级 姓 名 学 号 成 绩 指导老师 2012年 6 月 15日包钢水泥配送路线优化摘要 物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中，配送成本占了相当高的比例。本文以“包钢水泥的配送系统”为研究和实践背景，对现有配送车辆线路优化问题（VRP）算法归类分析，以VRP车辆线路优化运筹学理论为指导，重点运用启发式VRP节约算法，先分组后路径的扫描算法，通过两种方法的理论比较，同时结合实际情况，提供合理可行的配送线路以及车辆安排的方案，以期达到降低物流成本的目的。关键词 线路设计 VRP模型 节约算法 扫描算法 0引言高效率合理的配送是物流系统顺利

2、运行的保证，配送线路安排的合理与否对配送速度、成本、效益影响很大。正确合理地安排车辆的配送线路，实现合理的线路运输，可以有效地节约运输时间、增加车辆利用率，从而降低运输成本，提高企业经济效益与服务水平，使企业达到科学化的物流管理，也是企业提高自身竞争力的有效途径之一。因此本文将以包钢水泥的配送线路的优化问题作为理论研究点，通过对各个分厂的需求量以及运输距离进行理论分析计算，建立车辆配载能力的VRP数学模型，运用节约算法和扫描算法，对建立的模型进行求解。结合实际情况，对两种方法球的的结论进行比较分析，为包钢物资原料配送站提供合理可行的配送路线以及车辆安排方案，以达到降低物流成本的目的。1背景介绍

3、1.1公司简介包钢集团是新中国成立后最早建设的钢铁工业基地之一，1954年开始建设，1959年投产，周恩来同志亲临包钢为1号高炉出铁剪彩。包钢拥有“包钢股份”和“包钢稀土”两个上市公司，是我国主要钢轨生产基地之一、品种规格较齐全的无缝钢管生产基地之一、西北地区最大的板材生产基地，是我国稀土工业的发端和最大的稀土科研、生产基地。始终致力于多元发展，除钢铁、稀土两大主业外，还拥有矿业、非钢两大产业。“十二五”期间，将建设“大包钢”，成为世界最大的稀土钢生产基地和最具竞争力的稀土生产、科研基地，年销售收入达到1000亿元以上。1.2配送现状包钢物资供应公司原料配送站要向选矿厂，焦化厂，热电厂下属的1

4、0个车间配送水泥，各车间配送量（见表1）已知，配送站送货时都是从调配中心租赁货车，调配中心现有载重为2t，4t的两种货车，由于配送过程中要在车间进行卸货和办理手续，一般情况下每天只能给4个车间送货。 表1 各车间配送量表 (单位：t)序号abcdefghij车间名称破碎车间检修车间强磁车间尾矿车间选煤车间备煤车间焦油车间回收车间维修车间余热车间配送量0.70.90.80.41.41.50.60.81.50.6 （注 数据来源于公司网站）2 车辆选型 表2 车辆型号规格表吨数2t4t车型东风EQ5061XXY5D3五十铃CLW5080XZLARZJ货箱外部尺寸长5100mm×宽2000

5、mm×高1900mm长5512mm×宽2250mm×高2203mm载重空间19.38m327.32 m3核定在质量2000 KG4000KG油耗15L百公里28L百公里空间利用率22%32%3基本原理3.1 节约算法的基本原理1设配送中心Po对应两个收货点P1，P2，如图所示，如采取两辆车分别只送，距离为2C01+2C02，若改用一辆车一次配送，则距离为C01+C02+C12（C12为P1 到P2的最短距离），节约运距为C01+C02-C12，称C01+C02-C12 为P1 -P2的“节约里程”，记为S12 并按下式计算： Cij = Cio-+C0j-Cij

6、（2-1）P1P2P0P0P2P1 图1 节约算法图像描述因此，采用两条配送路径合并为一条配送路径的思想，可以缩短总运输距离，降低运输成本。该方法的原理是首先求出任意两点间的“节约里程”，按大到小的顺序合并配送路径。在合并线路时，只有在两条不同线路上并直接与配送中心相连接的点对才能合并，即每个点最多只能合并两次，在同一路径能重合并，在合并时还需要检验车辆的载重量。3.2 扫描算法的基本原理1扫描算法也是用于求解车辆数目不限制的VRP问题，即先分组后路径中的扇形分派法，扫描算法主要分以下四个步骤完成：以起始点O点作为极坐标原点，建立极坐标系。2 从最小角度的顾客开始建立一个组，按逆时针方向，将顾

7、客逐个加入到组中，直到顾客的需求总量超出了负载的限制；3 然后建立新的组，重复（2）中的过程；4 对各个组内的单回路进行路径优化。4 配送线路设计4.1建立VRP模型1VRP模型最早是由Dantzing和Ramser在1950年首次提出。该问题的研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在满足一定的约束条件（如货物需求量、发货量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的优化目标（如里程最短、费用最少、时间尽量少、车队规模尽量小、车辆利用率高等）。一个典型的VPR模型可以如下表述：（1）基本条件。现有m辆相同的车停在一个共同的源点V0，需要给1

8、2个客户提供货物，配送城市为V1，V2，V12.（2）模型目标。确定所需的车辆数N，并指派这些车到一个回路中，同时包括回路内的路径安排和调度，使总费用最低。 （3）限制条件。N不大于m；每一个订单都要完成；每辆车完成任务后都要回到源点V0；车辆的容量限制不能超过2吨和4吨；每天只能给4个车间送货。 4.1.1基本条件调配中心现有载重为2t，4t的两种货车共6辆，由于配送过程中要在车间进行卸货和办理手续，一般情况下每天只能给4个车间送货。货车停在一个共同的原点Q，它需要给10个车间配送水泥，车间点依次为a,b,c,d,e,f,g,h,i,j。4.1.2模型目标确定所需要的车辆数目N，车辆类型以及

9、各车行走的路径，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使得总运输费用最小。4.1.3限制条件（1）N6 （2）每一辆车都要在规定的4个车间内完成 （3）每辆车完成任务之后都要回到原点Q处 （4）车辆的容量限制不能超过4.2运用节约算法设计配送线路已知调配中心为Q点，分别向10个车间配送货物，其拥有共6辆的2t和4t的货车，每辆车每天只能给4个车间送货。设各点间的距离为C,C=Cij|i,j=1,.10,节约距离为Coi+Coj-Cij，每辆车的载重量为ri（i=1，6）,个点需求量为Ri(i=1,10),每辆车的行驶里程为Li（i=1，10）,，配送中心Q点为v0，客户点

10、1,2，。10依次为V1，.V101 设定初始方案，从配送中心V0处分别向10个车间进行配送。需要2t货车10辆，总行程141.8kmQbcdhgijfea图2 初始方案配送路线图计算调配中心道车间和各车间的最短距离。Qbcdhgijfea 图3 调配中心道各车间和各车间的连通图 表3调配中心到车间和各车间的最短距离表 （单位：km）车间QabcdefghijQ03.33.24.014.510.414.63.54.15.15.6a01.32.711.56.58.16.27.47.97.7b01.413.47.19.15.57.58.08.2c011.18.011.24.58.88.59.1d0

11、8.011.818.917.02219.1e04.112.415.313.812.9f014.215.214.712.2g02.06.79.5h05.57.5i02.6j0（注 数据来源于公司网站）2 根据表2最短距离表，利用节约算法计算出车间的节约里程表3，并由大到小排列，标志节约里程顺序表。 表4车间的节约里程表 （单位：km） 序号路程节约里程序号路程节约里程序号路程节约里程1e-f20.916f-h6.131e-h1.82d-f17.317b-c5.832e-i1.73d-e16.918a-b5.233e-g1.54a-f9.819f-i5.034a-j1.25b-f8.720h-j4

12、.835b-g1.26g-h8.221a-c4.636d-j1.07i-j8.122b-d4.337a-g0.68f-j8.023d-h4.238b-j0.69c-d7.424f-g3.939c-i0.610c-f7.425e-j3.140b-j0.511a-e7.226c-g3.041c-j0.512b-e6.527a-h2.642b-i0.313c-e6.428b-h2.243g-j0.214a-d6.329c-h1.944d-g0.115h-i6.330g-i1.945d-i0.03(4)根据节约里程顺序表和配送中心的约束条件，求解配送路线。根据节约里程顺序表中节约量大的路线，连接a,d

13、,e,f点，形成Q-f-e-d-a-Q回路,需要一辆4t货车，总行程是41.5km，载运能力为4t车辆每天能送达的车间数也达到上限。继续根据节约里程顺序表中其他节约量较大的路线，连接b,c点，行成Q-b-c-Q回路，需要一辆2t货车，总行程是8.6km,载运量为1.7t。继续根据节约里程顺序表中其他节约量较大的路线，连接g,h,i,j点，形成Q-g-h-i-j-Q回路，需要 一辆4t货车，总行程是19.2km,载运量为3.5t,车辆每天能送达的车间数上限。因此节约算法下的配送路线和车辆安排如下：QfedaQ或反向运输，此路线安排一辆4t货车进行配送；QghijQ或反向运输，此路线安排一辆4t货

14、车进行配送；QbcQ或反向运输，此路线安排一辆2t货车进行配送。Qbcdhgijfea图4节约算法下的运输路径已知一包水泥为50kg,尺寸为730mm×500mm×300 mm车辆配载俯视图如下：图5 2t货车俯视图 图6 4t货车俯视图图 图7 4t货车俯视图车辆配载左视图如下：图8 2t货车左视图 图9 4t货车左视图图 图10 4t货车左视图4.3运用扫描算法设计配送线路已知条件同前所述，设每辆车的运载能力是4t和2t，并有足够的车辆且配载中心Q点为VQ, 车间点a,b,c,d,e,f,g,h,I,j,依次为Va,Vj。对车间的位置图建立极坐标系。Qbcdhgijfe

15、a 图11扫描算法的扫描过程分组过程。从角度为零向逆时针进行扫描，以j开始扫描，第一个被分组的车间是j得到Load1=0.6t;继续转动，下一个被分组的客户是f,得到Load1=2.1t; 继续转动，下一个被分组的客户是e, 得到Load1=3.5t; 继续转动，下一个分组的客户是a, 得到Load1=4.2t>Loadlimit=4t,则第一个组为j,f,e。 继续上面步骤，直到分组完毕。Qbcdhgijfea图12扫描算法的分组结果根据图5得，配送中心对10个车间的多回路运输问题就转化为三个单回路运输问题由于所学知识的局限性，因此针对上述三个单回路运输问题采用启发式算法中的最近插入法

16、来寻求一个相对比较满意的可行解。回路1：此回路有3个车间点Ve,Vf,Vj表5各区域之间的运输距离 车间QefjQ010.414.65.6e04.112.9f012.2j0比较表中从VQ出发的所有路径大小minCQi|iN,iQ=CQj=5.6km这样就由节点VQ和Vj构成一个子回路T=VQ,Vj，VQ然后考虑剩下节点Ve,Vf到VQ,Vj中某一节点的最小距离 minCQi，Cji |iN,iQ,j=CQe=10.4 km由于无对称性，无论e插入到Q和j之间往返路径中，结果都是一样，构成一个新回路，T=VQ,Vj，Ve,VQ接着考虑Vf到VQ,Vj，Ve中某一节点的最小距离 minCQi，Cj

17、i Cei |iN,iQ,j,e=Cef=4.1 km将Vf 插入到（Q,e）间，= CQf+Cfe-CQe =14.4+4.1-10.4=8.1 km将Vf 插入到（Q,j）间，= CQf+Cfj-CQj =14.6+12.2-5.6=21.2 km将Vf 插入到（e,j）间，= Cfe+Cfj-Cej =4.1+12.2-12.9=3.4 km比较以上3种情况的增量，插入到（e,j）之间的增量最小，所以应将节点Vf 插入到（e,j）之间，结果为 T=VQ,Vj，Vf，Ve,VQ此回路的运输路径为QjfeQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=32.3km，需求量R1=3.5

18、t回路2：此回路有3个车间点Va,Vb,Vd,表6 各区域之间的运输距离 车间QadbQ03.314.53.2a011.51.3d013.4b0比较表中从VQ出发的所有路径大小minCQi|iN,iQ=CQb=3.2 km这样就由节点VQ和Vb构成一个子回路T=VQ,Vb，VQ然后考虑剩下节点Va,Vd,到VQ,Vb中某一节点的最小距离 minCQi，Cbi |iN,iQ,b=Cab=1.3 km由于无对称性，无论a插入到Q和b之间往返路径中，结果都是一样，构成一个新回路，T=VQ,Va，Vb,VQ接着考虑Vd,到VQ,Va，Vb中某一节点的最小距离 minCQi，Cai Cbi |iN,iQ

19、,a,b=Cad=11.5 km将Vd插入到（Q,a）间，= CQd+Cad-CQa =14.5+11.5-3.3=22.7 km将Vd插入到（Q,b）间，= CQd+Cbd-CQb=14.5+13.4-3.2=24.7 km将Vd插入到（a,b）间，= Cad+Cdb-Cab =11.5+13.4-1.3=23.6 km比较以上3种情况的增量，插入到（Q,a）之间的增量最小，所以应将节点Vc 插入到（Q,a）之间，结果为 T=VQ,Vd,Va，Vb，,VQ此回路的运输路径为QdabQ或反向运输，此线路需要配备一辆2t货车，运输距离S1=30.5km，需求量R2=2t回路3：此回路有4个车间点

20、Vc,Vg,Vh,Vi表7 各区域之间的运输距离 车间QcghiQ04.03.56.75.1c04.58.85.5g02.06.7h05.5i0比较表中从VQ出发的所有路径大小minCQi|iN,iQ=CQh=2.0 km这样就由节点VQ和Vi构成一个子回路T=VQ,Vh,VQ，然后考虑剩下节点VcVg,Vi到VQ,Vh中某一节点的最小距离 minCQi，Chi |iN,iQ,h=CQg=3.5 km由于无对称性，无论g插入到Q和h之间往返路径中，结果都是一样，构成一个新回路，T=VQ,Vg,，Vh VQ 接着考虑VC 和Vi到VQ,Vg，Vh中某一节点的最小距离 minCQi，Cgi Chi

21、 |iN,iQ,g,h=CQc=4.0 km将Vc插入到（Q,g）间，= CQc+Cgc-CQg=4.0+4.5-3.5=5 km将Vc插入到（Q,h）间，= CQc+Chc-CQh=4.0+8.8-6.7=6.1 km将Vc插入到（g,h）间，= Ccg+Cch-Cah=4.5+8.8-2.0=10.5 km比较以上3种情况的增量，插入到（Q,g）之间的增量最小，所以应将节点Vc 插 入到（Q,g）之间，结果为 T=VQ,Vc,Vg，Vh，,Vb接着考虑Vi到VQ,Vg，Vh,Vc中某一节点的最小距离 minCQi，Cgi Chi |iN,iQ,g,h=CQi=5.1 km将Vi插入到（Q,

22、c）间，= CQi+Cci-CQc=5.1+8.5-4.0=9.6 km将Vi插入到（c,g）间，= Cci+Cig-Ccg=8.5+6.7-4.5=10.7 km将Vi插入到（g,h）间，= Cgi+Chi-Cgh=6.7+5.5-2.0=10.2 km将Vi插入到（h,Q）间，= Chi+CQi-ChQ=5.5+5.1-6.7=3.9 km比较上4种情况的增量，插入到（Q,h）之间的增量最小，所以应将节点Vi插入到（Q,g）之间，结果为 T=VQ,Vc,Vg，Vh，Vi,VQ 此回路的运输路径为QcghiQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=21.1km，需求量R3=3.

23、7tQbcdhgijfea图 13以j开始扫描,扫描算法下的运输路径所以以j开始扫描, 可得:回路为QjfeQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=32.3km，需求量R1=3.5t； 回路为QdabQ或反向运输，此线路需要配备一辆2t货车，运输距离S1=30.5km，需求量R2=2t；回路为QcghiQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=21.1km，需求量R3=3.7t。以f,e,a,b,d,c,g,h,i为起点的扫描结果见附录1所以根据扫描算法，得到最优解为以f为起点：回路为QfeaQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=28.5km，需

24、求量R1=3.6t；回路为QbadcQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=31.1km，需求量R1=2.1t；回路为QghijQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=19.2 km，需求量R1=3.5t。Qbcdhgijfea 图14 扫描算法的最优解的运输路径5结论通过对节约算法，扫描算法结果进行比较，得到表9如下：表9 各算法与规划前比较表 方法规划前节约里程算法扫描算法行驶总里程141.8km69.3km78.8km回路回路回路41.5km8.6km19.2km28.5km31.1km19.2km油耗21.27L18.286L22.064L车辆 需求数量

25、2t 10辆2t 1辆4t 2辆4t 3辆可以得知，节约里程算法算法得到的配送路线为最优路线，行驶总里程为69.3km,需要2t货车1辆，4t货车2辆，该次配送2t货车的里程为8.6km，油耗为1.29L，4t货车的里程为60.7 km，油耗为16.996L，故此次配送共需要油耗18.286L，与规划前油耗比较节约2.984L，节约率为14.1%。根据调查，包钢原料配送站目前的供应额为8500万元，年运费支出为136万元如果能对所有的配送路线进行优化，按14.1%的节约率计算，每年可节约运费19.176万元；物资公司每年可配送辅助材料的总额为107600万元，年运费支出为1721.60万元，也

26、按14.1%的节约率计算，每年可节约运费242.75万元。可见，对配送路线进行优化后，仅油料一项的节约就十分可观！参考文献1蔡临宁.物流系统规划建模及案例分析M.机械工程出版社.2003.2052112邬星根.仓储与配送管理M复旦大学出版社.2005.2222263贾楠，吕永波，付蓬勃，任远，物流配送问题中VRP的数学模型及求解算法J物流技术.2007.26附录附录1 扫描算法以其他点为起始点的扫描结果以f开始扫描，可得:回路为QfeaQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=28.5km，需求量R1=3.6t；回路为QbadcQ或反向运输，此线路需要配备一辆4t货车，运输距离S

27、1=31.1km，需求量R1=2.1t；回路为QghijQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=19.2 km，需求量R1=3.5t。以e开始扫描, 可得:回路为QedabQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=34.4km，需求量R1=3.4t；回路为QcghiQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=21.1km，需求量R1=3.7t；回路为QjfaQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=29.2km，需求量R1=2.1t。以a开始扫描, 可得:回路为QbadcgQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=35.1k

28、m，需求量R1=3.4t；回路为QhijQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=20.4m，需求量R1=2.9t；回路为QfeQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=29.4km，需求量R1=2.9t；以b开始扫描,可得:回路为QbdcghQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=40.9km，需求量R1=3.5t；回路为QijfQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=34.5km，需求量R1=3.6t；回路为, QeaQ或反向运输，此线路需要配备一辆4t货车，运输距离S1=20.2km，需求量R1=2.3t。以d开始扫描,可得:回路为QdcghQ或反向运输，此线路需要配备一辆2t货车，运输距离S1=38.8km，需求