数学建模城市垃圾运输问题.docx

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

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

3、步骤：第一，使8吨车次满载并运往同一公司；第二，6吨位车次满载并运往同一公司；第三，剩下的货物若在16吨内，则用6吨货车运输，若在78吨内用8吨货车运输。最后得出耗时最少、费用最省的方案。耗时为19.6833小时，费用为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)多辆运输车可以在港口同时装车，不必等待。5)8个公司之间没有优先级别，货运公司只要满足他们的需求量就可

6、以。三、问题分析运输过程的最大特点是三种原料重量不同，分为大小件，当大小件同车，卸货时必须先卸小件，而且不允许卸下来的材料再装上车，要区别对待运输途中是否可以调头的费用。在问题一中，运输途中不能调头，整个送货路线是一个环形闭合回路，如果沿着某一方向同时给多家公司送货时，运输车必须为距离港口近的公司卸下小件，为距离港口远的公司运送大件；而在问题二中，运输途中可以调头，可以首先为远处公司运送小件，在返回途中为距离较近的公司卸下大件。从表面上看，这样运输能够节省车次，降低出车费用。但通过分析，在本题中，载重调头运输并不能降低费用。运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成

7、本、载重费用和空载费用。建立模型时，要注意以下几方面的问题：目标层：如果将调度车数、车次以及每车次的载重和卸货点都设为变量，模型中变量过多，不易求解。由于各辆运输车之间相互独立，可以将目标转化为：求解车次总数和每车次的装卸方案，安排尽量少的车辆数，每车次尽量满载，使总的运费最小。约束层：(1)运输车可以从顺时针或者逆时针方向送货，要考虑不同方向时的载重费用；(2)大小件的卸车顺序要求不同原料搭配运输时，沿途必须有序卸货;(3)每车次的送货量不能超过运输车的最大载重量；(4)满足各公司当日需求。四、符号说明和名词约定表2符号含义单位备注s1(n)从港口到各个公司的货运最短里程集公里n=1、2、8

8、;s2(n)卸载后从各公司返回港口的最短空载里程集公里n=1、2、8;w(n)两批次货物运至第n公司货物的总重量集吨n=1、2、8;times(n)两批次货物运至第n公司的总次数集次n=1、2、8;times(j,n)两类货车运至第n公司的次数集次n=1、2、8;j=1、2;yd第d问中组合运输的费用集元d=1、2、3；charge(d)第d问中所有的运输费用集元d=1、2、3；ttd第d问中组合运输的耗时集小时d=1、2、3；Time(d)第d问中所有的运输耗时集小时d=1、2、3；五、建立模型一、问题一i.车次规划模型的分析在符合载重相对最大化情况下，公司顺时针送货为最佳方案，公司逆时针送

9、货最佳方案。ii.模型建立根据车辆载重条件，可分为四种满载方案：第1种是每个车次装载2个单位B；第2种是每个车次装载6个单位C；第3种是每个车次装载1个单位A和2个单位C；第4种是每个车次装载1个单位B和3个单位C。但基于要使总运费最少以及满足各公司每日需求。筛选出两种运载方案：第1种为每个车次装载1单位A和2单位C；第2种是每个车次装载2个单位B。并使每一车次在同一公司卸货。具体程序见附录一。然后，第一批次运输，我们使A材料有优先运输权，在保证满足各公司对A需求量条件下，1C与1A搭配满足载重相对最大化方法运输；第二批次运输，我们使B材料有优先运输权，在此次运输我们满足各公司尚缺B材料的量小

10、于或等于2个单位；第三批次运输剩下所需的货物。由此可知共出车28次。如下表：表3车辆车次数公司货物时间（小时）运费（元）各车工作时间（小时）111A,2C1.4167107.27.083521A,2C1.4167107.232A,2C1.416718043A,2C1.4167273.653A,2C1.4167273.6264A,2C1.4167325.67.083575A,2C1.4167263.287A,2C1.4167138.497A,2C1.4167138.41022B1.416718031122B1.41671807.08351252B1.4167263.21362B1.4167180

11、1462B1.41671801572B1.4167138.441682B1.4167767.0835178A,C1.416767188A1.416758198A1.416758208A1.4167585218A1.4167586.1334221A,C1.416792.8231A1.416778.4241，22B1.5833142.26254A1.4167221.26.0333264A1.4167221.2277,6，56C1.75198.4288，42B1.5833206iii.目标分析运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成本、载重费用和空载费用。符号说明和名词

12、约定见表2。操作程序见附录二。最后经过模型的计算, 运输总费用为4864元，运输总时间为40.3333小时。二、问题二i.车次规划模型的分析运载里程与空载里程相同（表四中的第28车次例外），且每次出车均不绕圈工作。车辆载重行程是各公司到港口的最短路，且载重费用固定不变。ii.模型建立根据第（1）问的分析，分为两种满载方案：第1种为每个车次装载1单位A和2单位C；第2种是每个车次装载2个单位B。并使每一车次在同一公司卸货。然后，采用批次运输方案：第一批次运输，使A材料有优先运输权，在保证满足各公司对A需求量条件下，C与A搭配满足载重相对最大化方法运输；第二批次运输，使B材料有优先运输权，在此次运

13、输满足各公司尚缺B材料的量小于2个单位；第三批次运输剩下的货物。最终车次运载方案如下表：表4车辆车次公司货物时间（小时）运费各车工作时间（小时）111A,2C0.683489.67.283721A,2C0.683489.632A,2C0.916716843A,2C1.2167268.853A,2C1.2167268.864A,2C1.3834324.875A,2C1.1834257.6287A,2C0.7834123.27.783897A,2C0.7834123.21022B0.91671681122B0.91671681252B1.1834257.61362B0.91671681462B0.

14、91671681572B0.7834123.21682B0.5834563178A,C0.5834474.2838188A0.583438198A0.583438208A0.583438218A0.583438221A,C0.683475.2231A0.683460.84241，22B1.0833130.26.9501254A1.3834220.4264A1.3834220.4277，6，56C1.5167192.8288，42B1.5833206iii.目标分析运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成本、载重费用和空载费用。符号说明和名词约定见表2。操作程序见附

15、录三。最后经过模型的计算, 运输总费用为4487.2元，运输总时间为26.3000小时。三、问题三第（1）小问：根据第题目分析，题目中给出了3种型号的货车，4吨，6吨，8吨。而且没有规定不能掉头，故认为可以掉头。假设在距离港口公里的地方，需要货物吨，则使用4吨和8吨货车运送的费用如下（因为将吨货物运送到目的地的载重费是相同的，故只关注空载费用和出车费用）4吨货车运送费用，M/4*(0.2*+10)；8吨货车运送费用，M/8*(0.7*+10)；当33.3时，使用4吨货车运输比8吨货车更省费用。然而在允许掉头的情况下，按之前方案进行运送，没有超过33.3公里。所以不需要使用4吨货车，只使用6吨，

16、8吨货车搭配运货即可。i.模型建立第一步，使8吨车次满载并运往同一公司；第二步，使6吨位车次满载并运往同一公司；运载方案如下表：表5车辆车次公司货物时间（小时）运费各车工作时间（小时）第一辆8吨车112A0.6834120.86.9504212A0.6834120.831B,5C0.6834120.842A,B,C0.9167226.5532A1.2167362.4642A1.3834437.974A,B,C1.3834437.9第二辆8吨车85A,B,C1.1834347.35.4171962B,2C0.9167226.51072A0.7834166.11172B,2C0.7834166.1

17、1282A0.583475.51382A0.583475.5148A,B,C0.583475.5第一辆6吨车1522B0.91671687.31691622B0.9167168175B,3C1.1834257.61862B0.91671681982B0.583456第三步，经计算可知只剩下2,3,4,6,7公司需要C货物10吨，必须要用至少两个车次来运。为了使费用降低，决定用2个6吨车次来运货，具体运载方案如下表：表6车辆车次公司货物时间（小时）运费各车工作时间（小时）第一辆6吨车202，3，41C，4C，1C1.7167263.61.7167217,63C,1C1.083392.41.083

18、3ii.目标分析运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成本、载重费用和空载费用。符号说明和名词约定见表2。操作程序见附录四。最后经过模型的计算, 运输总费用为4403.2元，运输总时间为19.6833小时。第（2）小问：当部分公司接通后，对于各个车辆的运输安排并不改变，就是找到通往该公司的路径最短，使总的运输费用最少，但是由于连通了各个公司的路径变得复杂，因此我们就忽略空载时的返回路径，仅仅考虑每一吨货物以最短的路径到达目的地。此问题就可以看作是无向图来研究路线拓扑图，将所有公司和港口看作是节点，得到各节点之间最短的距离矩阵如下，A9*9=a11,a12a19;a

19、21,a22a29;a91,a92a99其中aij表示公司i到公司j的最短路径，当aij不存在时，记为无穷大，由Dijkstra算法得到港口九到其他公司的最短路径，按照最短路径运输货物可以将费用降到最低。六、附录附录一:model:sets:num/1.4/:x,a,b,c;endsetsdata:a=0,0,1,0;b=2,0,0,1;c=0,6,2,3;enddatamin=sum(num(i):x(i);sum(num(i):a(i)*x(i)=18; !满足A类货物总数sum(num(i):b(i)*x(i)=18; !满足B类货物总数sum(num(i):c(i)*x(i)=26;

20、!满足C类货物总数end附录二：clcs1=8,15,24,29,23,15,11,5;s2=52,45,36,31,37,45,49,55;w=21,18,12,14,12,12,18,27;times=4,3,2,3,2,2,3,6;tt1=4.9166;y1=576.6;sum1=0;sum2=0;sum3=0;for n=1:8 sum1=sum1+1.8*s1(n)*w(n); sum2=sum2+0.4*s2(n)*times(n); sum3=sum3+10*times(n);endchange(1)=120+y1+sum1+sum2+sum3;disp(问题一运输总费用：);d

21、isp(change(1);tt=0;for n=1:8 tt=tt+times(n)*(1+5/12);endTime(1)=tt1+tt;disp(问题一运输总时间 ：);disp(Time(1);结果为：问题一运输总费用：4.8640e+003问题一运输总时间：40.3333附录三：clcs1=8,15,24,29,23,15,11,5;w=21,18,12,14,12,12,18,27;times=4,3,2,3,2,2,3,6;tt2=4.1833;Y2=559;sum1=0;sum2=0;sum3=0;for n=1:8 sum1=sum1+1.8*s1(n)*w(n); sum2

22、=sum2+0.4*s1(n)*times(n); sum3=sum3+10*times(n);endchange(2)=80+y2+sum1+sum2+sum3;disp(问题二运输总费用：);disp(change(2);tt=0;for n=1:8 tt=tt+times(n)*(5/12+s1(n)/30);endTime(2)=tt2+tt;disp(问题二运输总时间 ：);disp(Time(2);结果为：问题二运输总费用：4.4872e+003问题二运输总时间：26.3000附录四：clcs1=8,15,24,29,23,15,11,5;w=0,12,0,0,6,6,0,6;24

23、,8,8,16,8,8,16,24;times=0,2,0,0,1,1,0,1;3,1,1,2,1,1,2,3;tt3=2.8;y3=376;sum1=0;sum2=0;sum3=0;for n=1:8 sum1=sum1+1.8*s1(1,n)*(w(1,n)+w(2,n); sum2=sum2+0.4*s1(1,n)*times(1,n)+0.7*s1(1,n)*times(2,n); sum3=sum3+10*(times(1,n)+times(2,n);endchange(3)=60+y3+sum1+sum2+sum3;disp(问题三运输总费用：);disp(change(3);tt=0;for n=1:8 for j=1:2 tt=tt+times(j,n)*(5/12+s1(n)/30); endendTime(3)=tt3+tt;disp(问题三运输总时间 ：);disp(Time(3);结果为：问题三(1)运输总费用：4.4032e+003问题三(1)运输总时间：19.6833 （注：可编辑下载，若有不当之处，请指正，谢谢!）