数学建模 物资调度问题.doc

物资调度问题摘要针对于问题问题一，我们EXCLE做出散点图，见图一，将仓库（即第30号站点） 抽象为“图”中顶点，由于街道和坐标轴平行，即任意两顶点之间都有路。在此模型中，将两点之间的路线权值赋为这两点横纵坐标之和。如A（ ，），B（ ，）两点，则权值为Q=| - |+| - |。并利用计算机程序对以上结果进行了校核。运用Dijkstra算法和Floyd算法会达到思路清晰、方法简便的效果，但随着物资需求站点数的增加，计算的复杂性逐渐增加，而且不具有一定的客观性。所以我们再利用动态规划的基础上引用了TSP模型，提高车辆的装载率，从而减少车辆的需求数，使运输车所行驶的路程最少，达到降低成本的目的。而使运输路程最小可用以下方法：（1） 每一个行程的第一个站点是距离仓库最近的未服务的站点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。（2） 每一个行程的第一个站点是距离总部最远的未服务的站点。然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。 然后比较两组结果，通过函数拟合即可得到最优化结果，由程序运行结果知总费用986.9元，所用时间总计7小时25分钟，需要四台车来运输物资。同时，我们利用题目中所给的条件:每辆车的工作时间在4小时之内，平均速度不大于40公里/小时等列出不等式，再利用LINGO解出不等式。针对于问题二，根据点的选择趋势可把较远区域的点集中运输，尽量用运送较远区域的剩余时间来运输离原点较近的区域的点：可尽量让8吨的车去距原点较远的区域，远点集中运输，剩余点先考虑6吨的车，再考虑4吨的车，这样就会达到省时经济的目标。关键字：动态规划 TSP问题 函数拟合 LINGO 物资调度 一、问题重述 某城区有29个物资需求点，每天凌晨都要从仓库（第30号站点）需求点。现有一种载重 6吨的运输车，运输车平均速度为40公里小时，每台车每日出发将物资运至每个工作 4小时，每个需求点需要用10分钟的时间街道方向均平行于坐标轴。（需求点的地理坐标和每天物资的需求量见附录一 ）问题： 1. 为了使得总运营费用最小，运输车应如何调度（下货，运输车重载运费2元/吨公里，空载费用0.5元/公里；并且假定需要投入多少台运输车，每台车的调度方案，运营费用）？ 2. 如果有载重量为4吨、6吨、8吨三种运输车，又如何调度？二、问题分析本题是物资运输问题，但最终可以归结为最优路径搜索问题。表一：任意两点间的距离矩阵因为距离是对称的，即从物资需求点i到物资需求点j的距离等于从j到i的距离。记作：di,j.表二给出了产品的需求，为了完成配送任务，每辆车在工作时间范围内，可以承担两条甚至更多的运输线路。表中给出了物资需求点编号，物资需求量T，以及物资需求点的直角坐标。从第30号站点发出去的每一辆车，到任意未得到物资的站点，然后将这辆车配到最近的未收到物资的站点范围之内的邻点，并使车辆工作时间小于4小时，平均速度小于40公里/小时，继续上述指派，直到各个站点都收到所需物资或者送货时间大于6小时。最后运输车返回仓库，记录得到的可行行程（即路线）。对另一辆运输车重复上述安排，直到没有未送到物资的站点。对得到的可行的行程安排解中的每一条路径，求解一个TSP问题，决定访问指派给每一条行程的运输车的顺序，最小化运输总距离。得到可行解的行程安排解后退出。上面的方法通过以下两种方法实现：（1） 每一个行程的第一个站点是距离仓库最近的未服务的站点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。（2） 每一个行程的第一个站点是距离总部最远的未服务的站点。然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。 然后比较两组结果，通过函数拟合即可得到最优化结果。三、基本假设1、运输车在运输路上不出现塞车现象；2、运输车在各个站点在10分钟内能完成卸载任务；3、各个运输车之间互不影响；4、运输车在运输的路上出现的特殊情况所消耗的时间忽略不计；5、运输车选择路线后就不再更改。四、符号说明符号表示意义 从原点到点的路程，即点的横纵坐标之和， 从原点到点的路程，即点的横纵坐标之和， 从原点到C点的路程，即C点的横纵坐标之和， 从原点到D点的路程，即D点的横纵坐标之和， 从点与点之间的路程，即 从点与点之间的路程，即 点的需求量点的需求量 运费时间消耗五问题的分析、模型的建立与求解利用公式 可得表一：表一、任意两点间的距离矩阵表（单位：km）距离站点号站点号123。30105452505634509。30569。0其中，4-30与1-3规律相同，故省略。5.2、模型的建立 5.2.1两点位置情况的分析将仓库抽象成坐标平面上的点，该点具有两个属性，即位置属性和重量属性；城市抽象成一个的一个方格网络。垃圾运输问题最终可以归结为最优路径搜索问题，用计算模拟搜索，可以搜寻到令人满意的可行解。先注意到两点的情况，设两点分别为A(X1,Y1)，B(X2,Y2)。主要有以下两种情况：图1 、 A、B有明显先后次序（递减状态） 图2 A、B无明显先后次序（并邻状态）图3、 A、B明显有先后次序，即递减状态。（如图1）不妨设X1X2,Y1Y2,不难看出在的后方,即比远。对于前方参考点，要将,对应站点的需求量全部运送再返回,一共有三种方式：1.,。（单独运输）这种情况下，总的路程消费等于空载运行费用(0.5元/公里)与装载时运行费用（2元/公里吨）的总和。所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值再加上在,两点停留的时间(每个站点上停留了10分钟，1/6小时)，于是有： = 2. 。（先远点再近点）即先货载至最远处，运完点需求后再返回至,再回O点，有：= = = 3. 。（先近点在远点）即先运点需求，然后载着点后剩余货物奔至点，再回O点，有：= = = 比较以上三种情况，远近点的遍历顺序，可以看出，“先近后远”绝对比“先远后近”在花费钱的数量上要少的多，省出这部分的钱主要是车货运点的后奔到点再返回点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选择“先近后远”。考虑到时间上单独运输比其余的两种运输要大的多，而且花费的钱仍不比“先远后近”省，还多了，所以 在两点递减的情况下，不采用单独运输。并且，一辆车一次运输所经过的几个点尽量从右上方向左下方递减。2) A、B两点没有明显先后顺序，即并邻状态。（如图2）不妨设，。还是一共有三种情况： 1、，。（单独运输）这种情况下，跟,两点有先后顺序中的情况完全相同，即有：= = 2、。（先纵坐标大的点，再横坐标大的点） = = 3). 。（先横坐标大的点，再纵坐标大的点）= = 若,两点间相距较远，并且其中一点靠近原点，则在不要求时间的情况下可采用单独运输。若,两点间相距较近，并且远离原点，显然单独运输除了浪费大量时间外，还有较大的花费。故此时不采用单独运输。用 ，得到如下判断式： 上式 0时， 选 ；上式 s&w(5,j)=0) s=w(2,j)+w(3,j); jg(i,j1)=w(1,j); sum=w(4,j); m=j; else continue; end end w(5,m)=1; j1=j1+1; while 1 js=0; q=40; for k=1:37 if(qw(2,m)-w(2,k)+w(3,m)-w(3,k)&w(2,m)w(2,k)&w(3,m)w(3,k)&(6-sum)w(4,k)&w(5,k)=0 q=w(2,m)+w(3,m)-w(2,k)-w(3,k); js=1; jg(i,j1)=w(1,k); i3=k; else continue; end end w(5,i3)=1; sum=sum+w(4,i3); j1=j1+1; m=i3; if(w(2,i3)=0&w(3,i3)=0|js=0) break end endendkcost=0;zcost=0;allcost=0;n=0;for u1=1:10 for u2=1:10 if jg(u1,u2)=0 n=jg(u1,u2); else continue end zcost=zcost+w(4,n)*2*(w(2,n)+w(3,n); end n=jg(u1,1); kcost=kcost+0.5*(w(2,n)+w(3,n);endallcost=zcost+kcostzcostkcosti=1:10;time=i;time(1,:)=0;n1=0;n2=0;n3=0;for u4=1:10 for u5=1:10 if jg(u4,u5)=0 n1=jg(u4,u5); n2=n2+1; else continue end end n3=jg(u4,1); time(1,u4)=(w(2,n3)+w(3,n3)*2)/40;endn2 time 程序2(* Content-type: application/mathematica *)(* Wolfram Notebook File *)(* /nb *)(* CreatedBy=Mathematica 7.0 *)(*CacheID: 234*)(* Internal cache information:NotebookFileLineBreakTestNotebookFileLineBreakTestNotebookDataPosition 145, 7NotebookDataLength 15932, 417NotebookOptionsPosition 14952, 384NotebookOutlinePosition 15297, 399CellTagsIndexPosition 15254, 396WindowFrame-Normal*)(* Beginning of Notebook Content *)NotebookCellBoxData RowBox:5404:7ad9:70b9:4e4b:95f4:7684:4f4d:7f6e:5173:7cfb:5982:4e0b:ff1a, IndentingNewLine, Input, CellChangeTimes-3.5120005708244057*9, 3.5120006314328723*9,CellCellGroupDataCellBoxData RowBoxb, =, RowBoxdata, =, RowBox, RowBox RowBox, RowBox3, , 2, , , RowBox, RowBox1, , 5, , , RowBox, RowBox5, , 4, , , RowBox, RowBox4, , 7, , , RowBox, RowBox0, , 8, , , RowBox, RowBox3, , 11, , , RowBox, RowBox7, , 9, , , RowBox, RowBox9, , 6, , , RowBox, RowBox10, , 2, , , RowBox, RowBox14, , 0, , , RowBox, RowBox17, , 3, , , RowBox, RowBox14, , 6, , , RowBox, RowBox12, , 9, , , RowBox, RowBox10, , 12, , , RowBox, RowBox7, , 14, , , RowBox, RowBox2, , 16, , , RowBox, RowBox6, , 18, , , RowBox, RowBox11, , 17, , , RowBox, RowBox15, , 12, , , RowBox, RowBox19, , 9, , , RowBox, RowBox22, , 5, , , RowBox, RowBox21, , 0, , , RowBox, RowBox27, , 9, , , RowBox, RowBox15, , 19, , , RowBox, RowBox15, , 14, , , RowBox, RowBox20, , 17, , , RowBox, RowBox21, , 13, , , RowBox, RowBox24, , 20, , , RowBox, RowBox25, , 16, , , RowBox, RowBox0, , 0, , , IndentingNewLine, RowBoxListPlot, , b, , Input, CellChangeTimes-3.511998037991536*9, 3.511998228661442*9, 3.5119989026439915*9, 3.5119989036430483*9, 3.511998948205597*9, 3.5119989931011653*9, 3.511999024148941*9, 3.511999288113039*9,CellBoxData RowBox, RowBox RowBox, RowBox3, , 2, , , RowBox, RowBox1, , 5, , , RowBox, RowBox5, , 4, , , RowBox, RowBox4, , 7, , , RowBox, RowBox0, , 8, , , RowBox, RowBox3, , 11, , , RowBox, RowBox7, , 9, , , RowBox, RowBox9, , 6, , , RowBox, RowBox10, , 2, , , RowBox, RowBox14, , 0, , , RowBox, RowBox17, , 3, , , RowBox, RowBox14, , 6, , , RowBox, RowBox12, , 9, , , RowBox, RowBox10, , 12, , , RowBox, RowBox7, , 14, , , RowBox, RowBox2, , 16, , , RowBox, RowBox6, , 18, , , RowBox, RowBox11, , 17, , , RowBox, RowBox15, , 12, , , RowBox, RowBox19, , 9, , , RowBox, RowBox22, , 5, , , RowBox, RowBox21, , 0, , , RowBox, RowBox27, , 9, , , RowBox, RowBox15, , 19, , , RowBox, RowBox15, , 14, , , RowBox, RowBox20, , 17, , , RowBox, RowBox21, , 13, , , RowBox, RowBox24, , 20, , , RowBox, RowBox25, , 16, , , RowBox, RowBox0, , 0, , , Output, CellChangeTimes-3.511999290371168*9, Open ,CellBoxData GraphicsBox Hue0.67, 0.6, 0.6, PointBoxCompressedData1:eJxTTMoPSmViYGCQA2IQDQEcDlAGlP5gD6FFHFBpATRaBqYPChQcUM1TQ1OnhEZLQGkVNPt10Mw1RDMXJg/Tr4FmrgqaOMx+uLlQ2gDNHCM0d8Ps1UMzzxjNPjMoDQsnUzT3W6Oph5lnjMaHuc8EzX6YeVpQ2gJNnSWUhvkHAQAMMRgE , AspectRatio-NCacheGoldenRatio(-1), 0.6180339887498948, Axes-True, PlotRange-Automatic, PlotRangeClipping-True, Input, CellChangeTimes-3.51237727059986*9, 3.5123772780892887*9,CellBoxData:7531:9898:610f:53ca:4e0a:56fe:53ef:5206:6790:5f97:51fa:ff1a:8c03:5ea6:95ee:9898:76ee:7684:5c31:5728:4e8e:5728:73b0:5b9e:5b9e:8df5:4e2d:8ba9:6d88:8017:7684:6210:672c:53ca:4e00:5207:8d44:6e90:5c3d:53ef:80fd:6700:4f4e:3002:5219:ff0c:53ef:8003:8651:4e3b:8981:56e0:7d20:ff0c:5ffd:7565:4e0d:5fc5:8981:7684:6b21:8981:56e0:7d20:ff0c:8fd9:624d:65b9:6709:53ef:884c:6027:ff01, IndentingNewLine, RowBox:4e00, , :ff1a, , :8981:8003:8651:7684:95ee:9898:ff1a, IndentingNewLine, RowBox RowBox RowBox:300a, 1, :300b, :8def:5f84S, RowBox :ff08, :5c3d:53ef:80fd:4f7f:8def:5f84S:6700:77ed, :ff09, :ff1b, , IndentingNewLine, RowBox , RowBox RowBox:300a, 2, :300b, :6240:8f7d:7269:7684:5206:914d:65b9:5f0f, RowBox :ff08, :4ee5:6240:5728:70b9:4e3a:4e2d:5fc3:6309:5468:56f4:6700:77ed:8ddd:79bb:7ad9:70b9:9700:6c42:91cf:7531:5927:5230:5c0f:8c03:5ea6, :ff09, :3002, , IndentingNewLine, RowBox , RowBox :4e8c:ff1a, , :8981:5ffd:7565:7684:95ee:9898:ff1a, IndentingNewLine, RowBox RowBox RowBox:300a, 1, :300b, :7269:8d44:8db3:591f, ;, IndentingNewLine, RowBox RowBox:300a, 2, :300b, :8fd0:8f93:8f66:8db3:591f:ff1b, IndentingNewLine, RowBox RowBox:300a, 3, :300b, :8f66:901f:4e0d:53d8:ff0c:5e76:6765:56de:8f66:901f:4e0d:53d8:ff1b, IndentingNewLine, RowBox RowBox:300a, 4, :300b, :6765:56de:6240:8d70:8def:5f84:4e0d:53d8:ff1b, IndentingNewLine, RowBox RowBox:300a, 5, :300b, :6bcf:53f0:8f66:6bcf:65e5:5de5:4f5c:65f6:95f4:548c:4e0b:8d27:65f6:95f4:4e3a:6052:5b9a:503c:ff1b, IndentingNewLine, RowBox RowBox:300a, 6, :300b, :5728:6574:4e2a:8d27:8fd0:5f53:4e2d:8f66:6ca1:6709:635f:574f:ff1b, IndentingNewLine, RowBox RowBox RowBox:300a, 7, :300b, :5728:6574:4e2a:8fc7:7a0b:5f53:4e2d:6ca1:6709:7a81:53d1:4e8b:4ef6:53d1:751f, RowBox:ff08, RowBox:5982:ff1a, , :5835:8f66:7b49, :ff09, :3002, IndentingNewLine, IndentingNewLine, RowBox:3010, :4e00, :3011, IndentingNewLine, RowBox RowBox :5148:8003:8651:4e24:70b9:95f4:7684:8ddd:79bb:95ee:9898:ff1a:8bbe:4e3aA, RowBox(, RowBoxx1, , y1, ), , RowBoxB, RowBox(, RowBoxx2, , y2, ), IndentingNewLine, RowBox:5219A, , RowBoxB:70b9:95f4:7684:8ddd:79bb:4e3a, |, AB, |, RowBox =, |x1-x2|+|y1-y2|, IndentingNewLine, :53ef:5f97:51fa:5f53:6bcf:4e24:4e2a:76f8:90bb:95f4:7684:8ddd:79bb:90fd:53bb:6700:77ed:65f6:ff0c:603b:8ddd:79bb:5219:53d6:6700:77ed:3002, IndentingNewLine, RowBox RowBox:4e0d:59a8:518d:8bbe:4e24:70b9C, RowBox(, x3:ff0cy3, ), , RowBoxD, RowBox(, RowBoxx4, , y4, ), IndentingNewLine, RowBoxC, , RowBoxD:4e24:70b9:95f4:8ddd:79bb:4e3a, |, CD, |, RowBox=, |x3-x4|+|y3-y4|, IndentingNewLine, RowBox RowBox:5f53, |, AB, |, RowBox, RowBox|, CD, |, :65f6:ff0c:6216, |, AB, |, RowBox, RowBox|, CD, |, :65f6, , :5c31:9700:8981:591a:589e:4e00:8f86:8f66:ff0c:8fd9:6837:53ef:4ee5:786e:5b9a:6240:9700:7684:8f66:8f86:6570:ff0c:5e76:8981:4fdd:8bc1:5728:89c4:5b9a:7684, IndentingNewLine, RowBox:65f6:95f4:5185:5b8c:6210:4efb:52a1, ., IndentingNewLine, :53ef:753b:51fa:4ece:7ad9:70b91:5230:7ad9:70b929:95f4:4f9d:6b21:7684:8fde:7ebf:5e76:6807:660e:5404:7ad9:6240:9700:6c42:91cf, IndentingNewLine, :7684:56fe:6848:89c1:526f:7a3f:3002, IndentingNewLine, RowBox RowBox :53c8:53ef:5f97:603b:97