数学建模大赛-货物运输问题.doc

上传人:夺命阿水 文档编号:13131 上传时间:2022-06-27 格式:DOC 页数:17 大小:579KB
返回 下载 相关 举报
数学建模大赛-货物运输问题.doc_第1页
第1页 / 共17页
数学建模大赛-货物运输问题.doc_第2页
第2页 / 共17页
数学建模大赛-货物运输问题.doc_第3页
第3页 / 共17页
数学建模大赛-货物运输问题.doc_第4页
第4页 / 共17页
数学建模大赛-货物运输问题.doc_第5页
第5页 / 共17页
点击查看更多>>
资源描述

《数学建模大赛-货物运输问题.doc》由会员分享,可在线阅读,更多相关《数学建模大赛-货物运输问题.doc(17页珍藏版)》请在课桌文档上搜索。

1、word货物配送问题【摘要】本文是针对解决某港口对某地区8个公司所需原材料A、B、C的运输调度问题提出的方案。我们首先考虑在满足各个公司的需求的情况下,所需要的运输的最小运输次数,然后根据卸载顺序的约束以与载重费用尽量小的原如此,提出了较为合理的优化模型,求出较为优化的调配方案。针对问题一,我们在两个大的方面进展分析与优化。第一方面是对车次安排的优化分析,得出公司顺时针送货,公司逆时针送货为最优方案。第二方面我们根据车载重相对最大化思想使方案分为两个步骤,第一步先是使每个车次满载并运往同一个公司,第二步采用分批次运输的方案,即在第一批次运输中,我们使A材料有优先运输权;在第二批次运输中,我们使

2、B材料有优先运输权;在第三批次中运输剩下所需的货物。最后得出耗时最少、费用最少的方案。耗时为40.5007小时,费用为4685.6元。针对问题二,加上两个定理与其推论数学模型与问题一几乎一样,只是空载路径不同。我们采取与问题一一样的算法,得出耗时最少,费用最少的方案。耗时为26.063小时,费用为4374.4元。针对问题三的第一小问,我们知道货车有4吨、6吨和8吨三种型号。我们经过简单的论证,排除了4吨货车的使用。题目没有规定车子不能变向,所以认为车辆可以掉头。然后我们仍旧采取公司顺时针送货,公司逆时针送货的方案。最后在满足公司需求量的条件下,采用不同吨位满载运输方案,此方案分为三个步骤:第一

3、,使8吨车次满载并运往同一公司;第二,6吨位车次满载并运往同一公司;第三,剩下的货物假如在16吨,如此用6吨货车运输,假如在78吨用8吨货车运输。最后得出耗时最少、费用最省的方案。耗时为19.6844小时,费用为4403.2。一、 问题重述某地区有8个公司(如图一编号至),某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号)分别运往各个公司。路线是唯一的双向道路(如图)。货运公司现有一种载重 6吨的运输车,派车有固定本钱20元/辆,从港口出车有固定本钱为10元/车次(车辆每出动一次为一车次)。每辆车平均需要用15分钟的时间装车,到每个公司卸车时间平均为10分钟,运输车平均速度

4、为60公里小时(不考虑塞车现象),每日工作不超过8小时。运输车载重运费1.8元/吨公里,运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨,原材料不能拆分,为了安全,大小件同车时必须小件在上,大件在下。卸货时必须先卸小件,而且不允许卸下来的材料再装上车,另外必须要满足各公司当天的需求量(见表)。 问题:1、货运公司派出运输车6辆,每辆车从港口出发(不定方向)后运输途中不允许掉头,应如何调度(每辆车的运载方案,运输本钱)使得运费最小。2、每辆车在运输途中可随时掉头,假如要使得本钱最小,货运公司怎么安排车辆数?应如何调度?3、(1)如果有载重量为4吨、6吨、8吨三种运

5、输车,载重运费都是1.8元/吨公里,空载费用分别为0.2,0.4,0.7元/公里,其他费用一样,又如何安排车辆数和调度方案?(2)当各个公司间都有或者局部有道路直接相通时,分析运输调度的难度所在,给出你的解决问题的想法(可结合实际情况深入分析)。图唯一的运输路线图和里程数公司材料A41231025B15012423C52424351 表各公司所需要的货物量二、模型假设1) 港口的容量足够大,多辆运输车同时到达港口时不会发生阻塞现象;2) 多辆运输车可以在港口同时装车,不必等待;3) 双向道路上没有塞车现象;4) 8个公司之间没有优先级别,货运公司只要满足他们的需求量就可以;货车完成他们日常的送

6、货任务之后,回到港口。5) 假设运输车不会因天气状况,而影响其行驶速度,和装载、卸载时间。6) 运输路不会影响运输车行驶速度。7) 运输车正常出车。三、问题分析运输过程的最大特点是三种原料重量不同,分为大小件,当大小件同车,卸货时必须先卸小件,而且不允许卸下来的材料再装上车,要区别对待运输途中是否可以调头的费用。在问题一中,运输途中不能调头,整个送货路线是一个环形闭合回路,如果沿着某一方向同时给多家公司送货时,运输车必须为距离港口近的公司卸下小件,为距离港口远的公司运送大件;而在问题二中,运输途中可以调头,可以首先为远处公司运送小件,在返回途中为距离较近的公司卸下大件。从外表上看,这样运输能够

7、节省车次,降低出车费用。但我们通过分析,在此题中,载重调头运输并不能降低费用。运费最小是货运公司调度运输车的目标,运费包括派车固定本钱、从港口出车本钱、载重费用和空载费用。建立模型时,要注意以下几方面的问题:目标层:如果将调度车数、车次以与每车次的载重和卸货点都设为变量,模型中变量过多,不易求解。由于各辆运输车之间相互独立,可以将目标转化为两个阶段的求解过程,第一阶段是规划车次阶段,求解车次总数和每车次的装卸方案;第二阶段是车辆调度阶段,安排尽量少的车辆数,每车次尽量满载,使总的运费最小。约束层:(1) 运输车可以从顺时针或者逆时针方向送货,要考虑不同方向时的载重用;(2) 大小件的卸车顺序要

8、求不同原料搭配运输时,沿途必须有序卸货;(3) 每车次的送货量不能超过运输车的最大载重量;(4) 满足各公司当日需求。四、符号说明和名词约定符号含义单位备注S1(n)从港口到各个公司的货运最短里程集公里n=1、2、8;S2(n)卸载后返回港口的最短空载里程集公里n=1、2、8;Q(i)(n)n公司对货物i的实时需求量集单位/天n=1、2、8;i=A、B、C;W(j)(n)第j批运至第n公司货物的重量集吨n=1、2、8;j=1、2;Times(j)(n)第j批运至第n公司次数集次n=1、2、8;j=1、2Yj(n)第j批运至第n公司的费用集元n=1、2、8;j=1、2;Y(d)第d问中组合运输的

9、费用集元d=1、2、3;Charge(d)第d问中所有的运输费用集元d=1、2、3;TT(d)第d问中组合运输的耗时集小时d=1、2、3;Time(d)第d问中所有的运输耗时集小时d=1、2、3;五、建立模型一、 问题一i. 车次规划模型的分析车次规划阶段只涉与到载重费用、空载费用和港口出车费用。运输途中不能掉头,所以每车次都是沿闭合回路绕圈行驶。1) 运输途中不能掉头,所以为某些公司送货时,运输车从港口出发,按顺时针方向沿闭合回路绕行,为其它公司送货时,按逆时针方向沿闭合回路绕行。公司和港口之间存在顺时针距离和逆时针距离,如下表:公司编号顺时针距离815242937454955逆时针距离52

10、4536312315115由表可知,运输过程中不可以掉头,为使得货运费用最低,我们按照问题分析中给出的最优运输路径进展货物的分配运输。即假如港口按顺时针和逆时针两个不同方向出发,根据货运里程短,点为顺时针货运方向最远点,也是空载回港口的最近点,根据货运里程短,点为逆时针货运方向最远点,也是空载回港口的最近点。结论:在符合载重相对最大化情况下,公司顺时针送货为最优方案,公司逆时针送货最优方案。如如下图所示:2) 根据3种原料的重量和运输车的最大运载量可以看出,A和C可以搭配运输,B和C可以搭配运输,而A与B不能同车运输。不论是以顺时针方向送货还是以逆时针方向送货,当大小件搭配运输时,必须首先卸下

11、小件,在后续公司卸下大件。我们把这种特点总结如下:1、假如在第j个公司卸下的是大件A,说明本车次的货物已经卸完,不能够再为后续公司运送小件CA与B不能同车运输,更不可能有B;2、假如在第j个公司卸下的是B,说明本车次的货物已经卸完,不能够再为后续公司运送小件C。ii. 模型建立基于以上约束条件建立如下模型:第一步:根据车载重相对最大化的根本思想。可以分为两小步:分为两种满载方案:第1种为每个车次装载1单位A和2单位C;第2种是每个车次装载2个单位B。并使每一车次在同一公司卸货。满载运载方案如下表1:表1车辆车次数公司货物时间小时运费元各车工作时间小时111A,2C21A,2C32A,2C180

12、43A,2C53A,2C264A,2C75A,2C87A,2C.497A,2C.41022B18031122B1801252B1362B1801462B1801572B.441682B76对于剩下各公司所需要货物单位数量如下表:材料 A20020005B11010001C10002311第二步:我们采用批次运输方案:第一批次运输,我们使A材料有优先运输权,在保证满足各公司对A需求量条件下,1C与1A搭配满足载重相对最大化方法运输;第二批次运输,我们使B材料有优先运输权,在此次运输我们满足各公司尚缺B材料的量小于或等于2个单位;第三批次运输剩下所需的货物。具体运输方式:首先优先考虑A货物的处理方

13、法,可知1公司还需1个车次的1A和一个车次的1A1C,4公司还需要2个车次的1A,8公司还需要4个车次的1A和1个车次的1A1C;接着处理B货物,1公司和2公司共需要1个车次的2B,8公司和4公司共需要1个车次的2B;最后处理C货物,5、6、7公司共需要1个车次的6C。由此可知共出车28次。如下表2:表2车辆车次数公司货物时间小时运费元各车工作时间小时41682B76178A,C67188A58198A58208A585218A58221A,C231A241,22B6254A264A277,6,56C.4288,42B2062) 根据1和2的结论与方法,不记派车本钱和出车本钱的28车次方案所需

14、运费与时间如下表3:表3车辆车次数公司货物时间小时运费元各车工作时间小时111A,2C21A,2C32A,2C18043A,2C53A,2C264A,2C75A,2C87A,2C.497A,2C.41022B18031122B1801252B1362B1801462B1801572B.441682B76178A,C67188A58198A58208A585218A58221A,C231A241,22B6254A264A277,6,56C.4288,42B206 总4464模型中变量对应的数值含义S1(n) n=1、2、8;8 15 24 29 23 15 11 5从港口到各个公司的货运最短里程

15、集S2(n)n=1、2、8;52 45 36 31 37 45 49 55卸载后返回港口的最短空载里程集Q(i)(n)n=1、2、8;i=A、B、C;4 1 2 3 1 0 2 5; 1 5 0 1 2 4 2 3; 5 2 4 2 4 3 5 1n公司对货物i的实时需求量集Wj(n)n=1、2、8;j=1、2;21 6 12 14 6 0 12 21; 0 12 0 0 6 12 6 6第j批运至第n公司货物的重量集Times(j)(n)n=1、2、8;j=1、2;4 1 2 3 1 0 2 5; 0 2 0 0 1 2 1 1第j批运至第n公司次数集(d)ttd=15.0832第d问中组合

16、运输的耗时集)yd=1565.2第d问中组合运输的费用集iii. 目标分析运费最小是货运公司调度运输车的目标,运费包括派车固定本钱、从港口出车本钱、载重费用和空载费用。最后经过模型的计算得到最少费用为:4840.6元,最少耗时为:40.4999小时。二、 问题二i. 车次规划模型的分析两个定理的证明定理一、车辆当且仅当运完最后一件货物时才调头途中允许调头,运输车可以先为较远的公司送去小件原料,然后调头,为比拟近的公司送去大件。从外表上看,这样运输能够节省车次,降低出车费用。但我们通过分析,在此题中,载重调头运输并不能降低费用。证明过程如下:NOMS1S2在上图中,记O点为港口,N、M为两公司。

17、M到港口的距离是S1,NM两个公司之间的距离为S2。假设将两种货物a和b重量分别为x吨、y吨,分别运往N和M两公司,现有两种运输方案:1.假如先运货a、b到N,将a卸到N,调头返回,将货物b运往M,那么a必为C原料x1,b为A或B,记运费用为f1 2.假如先单独运送货物a到N,返回港口后,再次出车,将货物b运往M,即出车两次,记运费用为f2。 两种方案需要的车辆一样时,为比拟两种运输方式费用的大小,两种运输的种类质量均一样,记:假如f 0恒成立,如此载重调头送货不节省费用,通过数据处理提取函数:因为 并且N、M两公司在此题中的最小距离代入到 f 中,化简得到令 得到 而港口到所有公司最短路的最

18、大值为29公里,所以恒成立。说明前一种花费较高。 方案二比方案一需要的车辆多时第二种方案是出车两次,运输时间较长,在8小时的工作时间,可能会比调头载重运输时多安排车辆,派车费用增加。我们考虑一种最差情况,因多运一次而增派一辆车,此时有得到 因为港口到所有公司的最短路径 所以 综上,载重调头运输花费较高。证明了以运费用最小为目标时,车辆当且仅当运完最后一件货物时才调头。定理一的推论:运载里程与空载里程一样表四中的第28车次例外,且每次出车均不绕圈工作。定理二、车辆载重行程是各公司到港口的最短路,且载重费用固定不变在定理一的根底上,车辆当且仅当运完最后一件货才调头,且每次出车均不绕圈工作,那么每一

19、单位的原料都可以由最短路径运至需货公司。我们变换视角,从宏观的角度看去,对8个公司所需货物的数量分别乘以公司和港口的最短距离和载重单价1.8元/吨公里就是将货物运至公司的载重费用,载重费用因子:货物的数量、公司和港口的最短距离、载重单价都是定值,因此,载重费用是固定不变的。车次规划阶段只涉与到载重费用、空载费用和港口出车费用。运输途中可以掉头,即货车可以送完货沿原路返回港口。ii. 模型建立根据问题一约束条件:在符合载重相对最大化情况下,公司顺时针送货为最优方案,公司逆时针送货最优方案。此结论也可以适用货车可以掉头的情况。加上上面两个定理,数学模型与问题一几乎一样,只是空载路径不同。故同样分为

20、两步骤:第一步分为两种满载方案:第1种为每个车次装载1单位A和2单位C;第2种是每个车次装载2个单位B。并使每一车次在同一公司卸货。第二步我们采用批次运输方案:第一批次运输,我们使A材料有优先运输权,在保证满足各公司对A需求量条件下,C与A搭配满足载重相对最大化方法运输;第二批次运输,我们使B材料有优先运输权,在此次运输我们满足各公司尚缺B材料的量小于2个单位;第三批次运输剩下的货物。最终车次运载方案如下表4:表4车辆车次公司货物时间小时运费各车工作时间小时111A,2C21A,2C32A,2C16843A,2C53A,2C64A,2C75A,2C287A,2C97A,2C1022B16811

21、22B1681252B1362B1681462B1681572B1682B563178A,C47188A38198A38208A38218A38221A,C231A4241,22B254A264A277,6,52B288,42B206总iii. 目标分析运费最小是货运公司调度运输车的目标,运费包括派车固定本钱、从港口出车本钱、载重费用和空载费用。由表4得知,第二问的总费用charge(2)总时间Time(2)三、 问题三1) 第一小问:结论:这次运货不需要使用4吨货车。只使用6吨、8吨货车搭配运输即可。i. 模型建立我们经过上述论证,排除了4吨货车的使用。题目没有规定车子不能变向,所以认为车辆

22、可以掉头。我们仍旧采取公司顺时针送货,公司逆时针送货的方案。根据上述条件我们建模如下:第一步,使8吨车次满载并运往同一公司;第二步,使6吨位车次满载并运往同一公司;运载方案如下表5: 表5车辆车次公司货物时间小时运费各车工作时间小时第一辆8吨车112A212A31B,5C42A,B,C532A642A74A,B,C第二辆8吨车85A,B,C962B,2C1072A1172B,2C1282A1382A148A,B,C第一辆6吨车1522B1681622B168175B,3C1862B1681982B56对于剩下各公司所需要货物单位数量如下表:材料 A00000000B00000000C01410

23、130第三步,从上表可知只剩下2,3,4,6,7公司需要C货物10吨,必须要用至少两个车次来运。我们已经论证排除了4吨货车的使用,为了使费用降低,我们决定用2个6吨车次来运货,具体运载方案如下表6: 表6车辆车次公司货物时间小时运费各车工作时间小时第一辆6吨车202,3,41C,4C,1C217,63C,1C1.0833第四步,上述三个步骤,不记派车本钱和出车本钱的21车次方案所需运费与时间如下表7: 表7车辆车次公司货物时间小时运费各车工作时间小时第一辆8吨车112A212A31B,5C42A,B,C532A642A74A,B,C第二辆8吨车85A,B,C962B,2C1072A1172B,

24、2C1282A1382A148A,B,C第一辆6吨车1522B1681622B168175B,3C1862B1681982B56202,3,41C,4C,1C217,63C,1C总ii. 目标建立运费最小是货运公司调度运输车的目标,运费包括派车固定本钱、从港口出车本钱、载重费用和空载费用。由表3得知,总时间Time(d)九、附录程序一:求解出问题一的答案 s1=8,15,24,29,23,15,11,5;s2=52,45,36,21,37,45,49,55;q=4 1 2 3 1 0 2 5;1 5 0 1 2 4 2 3;5 2 4 2 4 3 5 1;w=21 6 12 14 6 0 12

25、 21;0 12 0 0 6 12 6 6;times=4 1 2 3 1 0 2 5; 0 2 0 0 1 2 1 1;ttd=5.0832;yd=565.2;sum1=0;sum2=0;sum3=0;for n=1:8 for j=1:2sum1=sum1+1.8*s1(1,n)*w(j,n);sum2=sum2+0.4*s2(1,n)*times(j,n);sum3=sum3+10*times(j,n);endendcharge=yd+sum1+sum2+sum3charge = 4.7206e+003 tt=0; for n=1:8 for j=1:2 tt=tt+times(j,n)*(1+5/12);endend ttd=ttd+ttttd =对车次规划阶段,以每次运输量为决策变量,规划车次阶段的最小运费为目标,建立混合动态规划模型17 / 17

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 在线阅读 > 生活休闲


备案号:宁ICP备20000045号-1

经营许可证:宁B2-20210002

宁公网安备 64010402000986号