物资调运问题数学建模师哥给你们留下的财富下载吧

运筹学课程设计姓名：张竹强班级：数学与应用数学学院：成都信息工程学院物资调运问题摘要针对这个物资运输问题，现实生活中有很多的与之相似。比如说，城市垃圾的运输，或者城市旅游问题，或者快递发放问题等等。这些都是涉及到最优路线的选择的问题，资源的最大化，最充分，最有效的利用的问题。这里主要是从费用最小的角度来建模，每个点都有两个属性，第一是位置属性，第二是物资需求属性。我们可以把每个地点都放到直角坐标系中来分析，每个地点都有固定坐标。可假设发货点为坐标原点，而且每条街道都与坐标轴平行，由题目的要求我们可以得出：每两个点之间的距离就是两点横坐标之差的绝对值和纵坐标之差的绝对值之和。对距离我们利用计算机程序编程，来实现最最优路径的选取，从而取得最少费用。主要要用到迪杰斯特拉算法和Floyd算法。当然随着物资需求点的增加，计算的复杂性也随之增加。我们再利用动态规划算法，引用TSP模型，提高运输车的装载率。这样便能减少运输车的数量，也会减少运输车形式的路程，进而节约运输成本。使运输路程最小有以下策略：（1）每一个行程的第一个站点是距离仓库最近的未服务的站点。用这种方法，我们可以得到相应的数据。（2）每一个行程的第一个站点是距离总部最远的未服务的站点。然后以该点为基准，选择距它最近的点。然后得到第二组数据。然后比较两组结果，由程序运行得到结果。对于题目中所给的条件:每辆运输车的工作时间不大于四小时，平均速度不大于40公里/小时，列出线性规划不等式，然后软件利用LINGO求解。对于有载重量为4吨、6吨、8吨三种运输车，可尽量让8吨的运输车去距原点较远的地方，远点集中运输，余下的点先考虑6吨的车，最后考虑4吨的车，这样便能达到费用最小。关键字：TSP模型LINGO最优化多目标动态规划迪杰斯特拉算法Floyd算法问题背景资料某城区有29个物资需求点，需求点的地理坐标和每天物资的需求量见下表。每天凌晨都要从仓库（第30号站点）出发将物资运至每个需求点。现有一种载重6吨的运输车，运输车平均速度为40公里/小时，每台车每日工作4小时，每个需求点需要用10分钟的时间下货，运输车重载运费2元/吨公里，空载费用元/公里，并且假定街道方向均平行于坐标轴。问题：1、为了使得总运费最小，运输车应如何调度（需要投入多少台运输车，每台车的调度方案，营运费用）？2、如果有载重量为4吨、6吨、8吨三种运输车，又如何调度？（需求点物资需求量及地理坐标）问题分析对于物资运输问题，最终都可以化为最优路径的搜索问题。任意两点之间的距离是对成的，得到的矩阵是一个实对称矩阵，即从物资需求点i到物资需求点j的距离与从j到i的距离时相等的。记作：di,j.表二给出了产品的需求，为了完成配送任务，每辆车在工作时间范围内，可以承担两条甚至更多的运输线路。表中给出了物资需求点编号，物资需求量T，以及物资需求点的直角坐标。从第30号站点发出去的每一辆车，到任意未得到物资的站点，然后将这辆车配到最近的未收到物资的站点范围之内的邻点，并使车辆工作时间小于4小时，平均速度小于40公里/小时，继续上述指派，直到各个站点都收到所需物资或者送货时间大于6小时。最后运输车返回仓库，记录得到的可行行程（即路线）。对另一辆运输车重复上述安排，直到没有未送到物资的站点。对得到的可行的行程安排解中的每一条路径，求解一个TSP问题，决定访问指派给每一条行程的运输车的顺序，最小化运输总距离。得到可行解的行程安排解后退出。上面的方法通过以下两种方法实现：（1）每一个行程的第一个站点是距离仓库最近的未服务的站点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。（2）每一个行程的第一个站点是距离总部最远的未服务的站点。然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。然后比较两组结果，即可得到最优化结果。模型假设1、运输车的开车速度都很稳定；2、运输车在每个需求点的货物均能在10分钟之内卸载完成；3、运输车之间没有干扰；4、在运输车运行的过程之中没有堵车情况；5、运输车均正常运行，无特殊情况发生；6、运输车在运行的过程中无红绿灯现象也没有意外的发生，即不花时间7、运输车中途不停8、运输车回到仓库的配货时间不计9、每个物资点只停留一次10、运输车沿街道方向均平行于坐标轴11、运输车在中途除了送货之外没有别的时间耽搁12、本文所用的资料和数据均真实可靠符号约定|A|原点到A点的距离|A|=+|B|原点到B点的距离|B|=+|C|原点到C点的距离|C|=+|D|原点到D点的距离|D|=+|AB|从A点到B点的距离|AB|=||+|||CD|从C点到D点的距离|CD|=||+||A点的需求量B点的需求量S运费T时间消耗问题的分析根据任意两个站点的距离公式jijijiYYXXD,1可得表一：表一、任意两点间的距离矩阵表（单位：km）距离站点号站点号123。。。30105452505634509。。。30569。。。0模型的建立两点位置情况的分析将仓库站点转换成坐标平面上的点，每个点具有两个属性，位置属性和重量属性；城市抽象成一个3020的一个方格网络。垃圾运输问题最终可以归结为最优路径搜索问题，用计算模拟搜索，可以搜寻到令人满意的可行解。先注意到两点的情况，设两点分别为A(X1,Y1)，B(X2,Y2)。主要有以下两种情况：图1图2图3不妨设X1X2,Y1Y2,不难看出A在B的后方,即A比B远。对于前方参考点O，要将A,B对应站点的需求量全部运送再返回O,一共有三种方式：1.OAO,OBO。（单独运输）这种情况下，总的路程消费等于空载运行费用元/公里)与装载时运行费用（2元/公里吨）的总和。所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值再加上在A,B两点停留的时间(每个站点上停留了10分钟，1/6小时)，于是有：S2T=1224026AB32.OABO。（先远点再近点）即先货载至最远处，运完A点需求后再返回至B,再回O点，有：S=0.522AABAABTBTT4=0.522ABAATBTT=124026A53.OBAO。（先近点在远点）即先运B点需求，然后载着B点后剩余货物奔至A点，再回O点，有：S=0.522BABBABTATT6=0.52222ABBBATBTABTT=124026A比较以上三种情况，远近点的遍历顺序，可以看出，“先近后远”绝对比“先远后近”在花费钱的数量上要少的多，省出22BABT这部分的钱主要是车货运B点的后奔到A点再返回B点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选择“先近后远”。考虑到时间上单独运输比其余的两种运输要大的多，而且花费的钱仍不比“先远后近”省，还多了0.5B，所以在两点递减的情况下，不采用单独运输。并且，一辆车一次运输所经过的几个点尽量从右上方向左下方递减。A、B两点没有明显先后顺序，即并邻状态。（如图2）不妨设21XX，21YY。还是一共有三种情况：1、OAO，OBO。（单独运输）这种情况下，跟A,B两点有先后顺序中的情况完全相同，即有：S=0.520.52ABAATBBT7BATYXYXTYXYX*)(*2)(*5.0*)(*2)(*5.022221111T=1224026AB82、OABO。（先纵坐标大的点，再横坐标大的点）S=0.522AABAABTBTT9BABAATYXTYXXTTYXTYYXXYX*)(*2*)*2(*2()*5.0)(*)(*2*)(*2*5.02211222211211）（T=14026AABB10OBAO。（先横坐标大的点，再纵坐标大的点）S=0.522BABBABTATT11ABBTYXTYYYYXTTYXTYYXXYX*)(*2*)2(*2)(*5.0)(*)(*2**2*5.011212222111211222）（）（T=14026AABB12若A,B两点间相距较远，并且其中一点靠近原点，则在不要求时间的情况下可采用单独运输。若A,B两点间相距较近，并且远离原点，显然单独运输除了浪费大量时间外，还有较大的花费。故此时不采用单独运输。用23，得到如下判断式：)91)(()91)((1212BATYYTXX上式0时，选OABO；上式0时，选OBAO；上式=0时，任意选上述两路线。点的选择趋势的讨论如图4中情形，C点与A、与B均明显有先后次序，呈递减状态。而A，B两点没有明显的先后顺序，相对C属于并邻点。因为当运输车载重行驶时费用会成倍的增长，比其空载时所花费用要大的多，所以排除CAB或CBA这样的一次经过3点的往返路线，仅选择A，B中的某一点与C完成此次运输，将另一点留到下次。那么C点选择A还是选择B呢？这需要比较A与B的大小，并且应该先到大的点，即距离原点更远的点。图4设AB，因为就这三点而论，C无论是选A还是B，三点的需求总要运完，所以花费的钱是一样的。但选择CB后，下次运输车运到A点时就无需跑的更远。多点的情形同理。故当出现多点同时与上一点呈递减状态，且这些点两两并邻，那么应该选取离原点较远的点作为下一点。综上可得车辆运行的路线为：而数字化结果如表二所示：表二、经分析后的数字化结果数字化结果路线站点号所用时间所需费用10-8-02．2+5/620-3-8-12-0+1/230-10-22-0+1/340-1-9-11-0+1/250-3-4-6-7-14-0+5/660-13-20-23-0+1/270-+2/380-24-27-29-0+1/2由题意每台运输车每日工作四小时，由上表时间得：至少需要四台运输车，调配方案如表三：表三、四台车的分配路线运输车路线总时间112．2+5/622+0633+1/6544+1/6758+5/69由程序运行，得到结果，知总费用：元，所用时间总计十七小时分钟。根据点的选择趋势可把较远区域的点集中运输，尽量用运送较远区域的剩余时间来运输离原点较近的区域的点。那么，可尽量让8吨的车去距原点较远的区域，远点集中运输，节约空载的时间及费用。由于需求量有限，所以8吨的车也不宜太多，否则不太经济。剩余点先考虑6吨的车，再考虑4吨的车，尽量充分利用，使得花费甚至时间尽量少。模型的推广本模型可以得到广泛的推广，首先当然是物资运输问题，当然还可以用在垃圾的运输，旅客在城市的旅游问题等。最为主要的是处理关于最优路线，进而充分利用资源，节约成本，提高经济效应上面。同是在车辆选录，机器人控制，芯片设计，甚至在基因测序方面都有广泛的应用。基于未来经济的发展，对于建设节约型社会，节约资源，都有很大的用处。而该模型因其有广泛的实际应用背景，所以在未来相当长的一段时间里将会被广泛应用。模型的评价这个模型有优点，也有不足之处。优点在于：模型简单，易于实现。而且能够最大效用的利用物流中心，坐标原点的车辆资源能够得到充分的利用，进而优化车辆资源和得到最优运输路线。这样一来便能节约运输成本，有效的提高经济效益。不足之处在于：对于更多的站点，计算就越来复杂，同时得到的数据的精确度不够。参考文献[1]、旅行商问题（TravelingSalesmanProblem）的简记，由在1932年提出。[2]、刘育兴，钟剑，垃圾运输问题的模型及其求解，赣南释放学院学报，27卷3期：52-55页，2006.[3]、Floyd算法，是Floyd-Warshall算法的简称，又称弗洛伊德算法；[4]、Dijkstra算法，是由荷兰计算机科学家迪克斯特拉（Dijkstra）于1959年提出；附录一需求点物资需求量及地理坐标坐标（km）坐标（km）站点编号需求量Txy站