数学建模运输问题送货问题

1、数学建模论文题目:送货问题学院（直属系）:数学与计算机学院年级、专业:2010级信息与计算科学姓铭:杨尚安刘洋谭笑指导教师:蒲俊完成时间：2012年3月20日摘要本文讨论的是货运公司的运输问题，根据各公司需求和运输路线图，建立了线性规划模型和0-1规划模型，对货运公司的出车安排进行了分析和优化，得出运费最小的调度方案。对于问题一，由于车辆在途中不能掉头，出车成本固定，要使得总成本最小，即要使在一定的车辆数下，既满足各公司的需求，又要尽量减小出车次数。故以最小出车数为目标函数，建立线性规划模型，并通过lingo求解，得出最小出车数27次。接着考虑车的方向问题，出车分为顺时针和逆时针，建立0-1模

2、型，并求解，得出满足问题一的调度方案（见附录表1）。对于问题二，车辆允许掉头，加上车辆装载货物和空装时运输费不同，要使总成本最小，故可以通过修改原目标函数，建立线性规划模型和0-1规划模型，求解，得出最佳派出车辆3辆并列出满足问题二的调度方案。对于问题三第一小问，增加了运输车辆的类型。即装载材料的方法很多，在上述分析的基础上，通过增加约束条件，建立新的线性规划模型，并求解，得出满足问题三的调度方案。在第二小问中，由于给出部分公司有道路相通，可采用运筹学中的最短路问题的解决方法加以解决。关键字：线性规划模型0-1规划模型调度一、问题重述某地区有8个公司（如图一编号至），某大某货运公司要派车将各公

3、司所需的三种原材料A,B,C从某港口（编号）分别运往各个公司。路线是唯一的双向道路（如图1）。货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次（车辆每出动一次为一车次）。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里/小时（不考虑塞车现象），每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足

4、各公司当天的需求量（见表1）。问题：1、货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。2、每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？3、（1）如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2,0.4,0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？（2）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法（可结合实际情况深入分析）。图1唯一的运输路线图和里程数司A41231025B15

5、01r2423C52424351、符号说明x1表示为一个车装一单位A和两单位C;x2表示为一个车装六单位C;x3表示为一个车装两单位B;x4表示为一个车装一单位B和三单位C;S表示最小运输次数；x5表示为一个车装一单位A和一单位C;x6表示为一个车装一单位A;Xi1表示第i次运输装A的单位数；Xi2表示第i次运输装B的单位数；Xi3表示第i次运输装C的单位数；Y i1表示第i次运输A到达目的地所走的路程；Y i2表示第i次运输B到达目的地所走的路程；Y i3表示第i次运输C到达目的地所走的路程；P表示运输车的方向（等于0按照顺时针即092;等于1按照逆时针即09）；M表示最小成本；Zij表示第

6、i次运输j的所走单位路程的单位成本；a表小8个公司对A的总需求量；b表示8个公司对B的总需求量；c表示8个公司对C的总需求量；三、模型假设1 .假设每辆车装载时发挥其最大的装载能力；2 .假设货运公司都是先考虑节省人力和出车次数最少的情况下再考虑如何安排运输方式以减少经费支出；3 .假设运输车行驶过程中不考虑塞车等各种抛锚现象，以保证每辆车每天可以达到最大的作业时间四、问题分析本题考虑从一个货源地往其余八个地运送货物，要求运输成本最少的运送方案。由于运输问题中涉及到车量的限载重量（6吨）、车速的最大值（60km/h）、汽车每天最多的工作时间（8小时）、汽车每次上货时间（15min）、每次下货的

7、时问（10min）以及ABCE种原材料每件的毛重和八个需货地分别所需ABC的件数等问题。对于问题一，由于车不可以跳头，我们通过考虑每辆车的容量、卸货顺序、满足各公司需求按需分配，首先找到一个符合要求的解，然后将其优化算出最终结果。如果假设一辆车在全程只装一次，也只卸一次，即用时最短，会花上85分钟，又因为一辆车工作时间不能超过8h,故一辆车最多跑5次，六辆车共30次o所以我们可以首先考虑在满足各地所需货物的前提下，设计出车的运货方案，利用lingo软件从方案选择出出车次数最少的一种方案作为汽车的运送方案，经计算车次最少需要27车次，其中9车次运2B,8车次运1A2c10车次运1A1G然后在利用

8、这种方案向各地安排输送货物的方案。由于运送B的车是单独的，所以我们可以首先将运送B的车单独考虑，然后在安排同时运送A和C的车次。这里可以使用0、1规划模型，0表示顺时针(即.)运送，1表示逆时针(即.)运货。对于问题二，解决方法和第一问中的解决方法是一样的，不过由于这时候运输车可以掉头，故可以减少由于运输车在途中空载的路程，而这只会影响模型中目标函数的中的价值系数的改变，其他和第一问的求解方法是一致的。对于问题三，题中给出了三种不同的运输车，每辆车有不同的装载方式。所以根据每个公司对A,B,C的需求，建立线性模型，使彳#8个公司可以从这些不同的运输方式中选择最为合适的运输方式的组合以满足要求，

9、然后根据每辆车的工作时间，结合这些公司所选择的不同的运输方式，确定出在保证完成任务的情形下，所需要不同类型运输车的最少数目。然后对不同类型运输车在运输途中的方案的分析，安排出合理的车辆数和调度方案。五、模型建立与求解5.1 问题一5.1.1 数据分析题中已经给出了固定的车辆数，6辆。首先考虑满足各公司需求的最少出车次数，在此基础上安排调度车辆，使总成本最少。一辆车在全程只装一次，只卸货一次的情况下所用时间最少，根据题中数据，全程会用85分钟，而一辆车的工作时间不能超过8小时，故一辆车最多只能跑5次，6辆车即最多只跑30次。接着对车辆的装载情况进行分析。一辆车最多只能装6吨货物，而一个单位的原材

10、料A,B,C分别毛重4吨、3吨、1吨，假设每辆车都能发挥最大装载力，故有装载情况(1)一车装一单位AJ口两单位C,(2)一车装六单位C,(3)一车装两单位B,(4)一车装一单位出口三单位C。故可建立如下模型：其中X1表示为一个车装一单位用口两单位C,x2表示为一个车装六单位C,x3表示为一个车装两单位B,x4表示为一个车装一单位出口三单位C,S表示最小运输次数min=x1+x2+x3+x4;Xl=18；J2*x3+x4=18;12*x1+6*x2+3*x4=26;求解得出满足各公司对于所口B的需求，却会多运C。上面得出的模型显然不是最优模型，经分析后优化模型，考虑第五种情况：一个车装一单位将口

11、一单位C。和第六种情况：一个车装一单位A。得出优化后的模型：其中4表示为一个车装一单位用口一单位C,x表示为一个车装一单位Amin=x1+x2+x3+x4+x5+x6;x1+x5+x6=18;J2*x3+x4=18;2*x1+3*x4+6*x2+x5=26;Lx1+x2+x3+x4+x5+x6=30;解得最少出车次数为27次，其中9次装两单位B,8次装一单位A和两单位C,10次装一单位A和一单位Co对于B,可单独考虑，27次中有9次装两单位的B,可先顺时针运两次给公司2,顺时针运1单位B合公司1,1单位B合公司2,以此类推。对于A,C,由于需要考虑卸货时小件先卸，大件后卸，公司1可以运3次一单

12、位府口一单位C,一次一单位用口一两单位C以此类推。5.1.2模型建立最少出车次数为27次，通过分析题中数据和线路图可得到如下求解最小运费的模型：其中Xn表示第i次运输装A的单位数,Xi2表示第i次运输装B的单位数，Xi3表示第i次运输装C的单位数，表示第i次运输A到达目的地所走的路程，丫2表示第i次运输B到达目的地所走的路程，Yi3表示第i次运输C到达目的地所走的路程，P表示运输车的方向（等于0按照顺时针即09；等于1按照逆时针即3），M表示最小成本，Zij表示第i次运输j的所走单位路程的单位成本，a表示8个公司对A的总需求量，b表示8个公司对B的总需求量，c表示8个公司对C的总需求量每辆车的

13、容量：Xi1Xi2Xi36卸货顺序：在P0时，YiY2Y2Y3在P1时，Yi1丫2丫2丫3mXi1ai1m满足各公司需求：Xi2bi1mXi3ci1其中：i1,2,.,m,j1,2,.,n5.1.3模型求解由于B的运输车次时单独的，故单独考虑B的运输。我们考虑到车只能顺时针或逆时针运送以及载重运费大于空载运费，所以就近下货会节省运费。又由于运B的车每次都是运2个单位的B,因此在就近下货的前提下在考虑八个需要地所需B件数的奇、偶问题求出运送B的最优方案。设计出1-8地所需原材料数量简表，例如(415)表示需要4单位A,1单位B,5单位C。12345678(415)(152)(204)(312)(

14、124)(043)(225)(531)利用首先满足需要偶数单位原材料的原则分配可得：顺时针往2送2*2B,逆时针往8送1*2B,7送1*2B,6送2*2B,5送1*2B后得到：12345678(415)(112)(204)(312)(104)(003)(205)(511)接着顺时针往1,2各送1*1B,逆时针往8,4各送1*1B。这样正好9次将B的运送完成。具体列表见附录表1:故运送B所需的载重总费用为：162+162+124.2+189.9+54+118.8+162+162+248.4=1383.3元空车所需的总费用为：(45+45+45+29+55+49+45+45+37*0.4=158元

15、运送B所需的总费用为：1383.3+158=1541.3元依次可彳#出运A,C的情况，见附录表2即运送A和C总费用为：4358.2元。综上所述，六辆车的固定出车成本是120元，从港口固定出车的成本为270元完成任务所需全部总费用为:1541.3+4358.2+120+270=6289.5元。5.2 问题二模型建立与求解0-1表示顺时针出发，卸完货后掉头回去；1-0表示逆时针出发，卸完货后掉头回去。方向15012423总运费(元)最短时间(min)0-12B弋r168550-12B2168550-112B1p130.26512B11206951-02B256351-012B2123.2471-0

16、2B2179.2551-02B2179.2551-0n2B2257.671总计150124231467.4533故运送向各地运送限物所需的总费用为：168+168+130.2+206+56+123.2+179.2+179.2+257.6=1467.4元方向公心车次、4,51,22,43,21,40,32,55,1总运费(元)最短时间(min)0-111A1C1.175.2410-11A1C1,175.2410-11A1C1,175.21410-111A1C1,1272.6830-11A1C1,1272.6831-011A1C：0,11,0209r5511-01A1CI0,11,0209551-

17、01A1C0,11,0209551-011A1C0,11,0338.6r81111A1C1,00,1276.2950-11A2C1,289.6410-111A2C1,2168r550-11A2C1,2268.8730-11A2C1,2268.8731-011A2C1,2123.2471-01A2C1,2123.2471-01A2C0,11,1153.2571-01A2C1,2257.671总计4,51,22,43,21,40,32,55,136451094即运送府DC总费用为：3645元。综上所述，四辆车的固定出车成本是80元，从港口固定出车的成本为270元完成任务所需全部总费用为：1467.

18、4+3645+80+270=5462.4元。5.3 问题三5.3.1 数据分析以尽可能装满车为原则，题中所给出的三种不同的运输车4,6,8吨三种车型有以下装法由于卸货也需要时间，故可根据装载的方式，使每辆车尽可能一次性卸完货物分析出每个公司所需车次。4吨（车型）6吨8吨Y1=B+CY4=2BY9=2AY2=AY5=A+2CY10=A+4CY3=4CY6=B+3Cy11=8CY7=B+CY12=2B+2CY8=B+2CY13=B+5C1Y14=B+AY15=B+4C5.3.2模型建立min=sum(yi)y2+y5+2*y9+y10+y14=18;y1+2*y4+y6+y7+y8+2*y12+y

19、13+y14+y15=18;y1+4*y3+2*y5+3*y6+y7+2*y8+4*y10+8*y11+2*y12+5*y13+4*y15=26;求解可以得出下表公司（需求）1.(4,1,5)2.(1,5,2)3.(2,0,4)4.(3,1,2)5.(1,2,4)6.(0,4,3)7.(2,2,5)8.(5,3,1)车次2Y9+Y13Y4+Y14+Y122Y5Y2+Y5+Y14Y4+Y10Y4+Y7+Y8Y10+Y14+Y7Y9+Y7+2Y14在考虑每辆车在规定的工作时间的前提下保证车辆尽量少。由表求出：4吨：83分钟6吨：567分钟8吨：621分钟而每辆车最多工作480分钟，故需要派出1+2+2=5辆车。求出总费用没4694.6元。六、模型评价与修正本题采用建立线性约束条件的方法得到用车量数最少的数学模型，然后根据此模型按需分配车辆的运送方案，得到了比较满意的结果，能较为准确的计算