露天矿生产的车辆安排模型毕业论文.doc

露天矿生产的车辆安排模型摘要本文成功引入了车次的概念。在对时间进行合理假设之后，在约束条件下建立了对车次的全局最优的整数线性规划，利用lindo软件迅速解出全局最优的任务分配。进一步，利用效率优先原则，对铲点进行优化，并根据物件可分的等容积装箱模型，最终得到了满足要求的计划安排。根据原则一建立模型的解为：铲位：1、2、3、4、8、9、10，卡车数：13，总运量：8.56万吨千米，车辆安排计划见表9；根据原则二建立模型的解为：铲位：1、2、3、4、8、9、10，卡车数：20，最大产量：10.35万吨，岩石量：4.93万吨，在最大产量下的最小运量：14.69万吨千米车辆安排计划见表14。一、问题的重述露天矿里有若干个爆破的铲位，已预先根据铁含量被分成矿石和岩石两种不同的石料。每个铲位至多配备一台电动铲车进行装车，并由电动轮自卸卡车将矿石和岩石分别运送至各自的卸货地点，满足各卸点的产量和品位要求（29.5%1%）。卡车有其本身的平均速度，随机的装卸时间和载重。根据所给定的条件，根据以下两条原则分别建立数学模型，并给出一个班次生产计划的快速算法，原则上在安排时不应发生卡车等待的情况。1、总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；2、利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。二、问题分析 1、本题是一个有约束条件的组合优化问题，涉及到单车型多货种送货满载车辆的优化调度，因而属于NP难题（文献1），随着系统规模的扩大，问题的求解难度也大大增加，求解时间呈几何级数上升。2、本问题最先应着重解决的是车辆的等待问题。车辆在铲位和卸点的等待主要由三方面引起：(1) 随机因素造成运输和装卸时间不精确从而形成等待；(2) 由于车辆在不同道路上循环的周期不同所偶尔出现的在时间上的重叠。这种交叉的可能性伴随着道路承载车辆数目的增加而增加，但也可以通过车辆自身的调整而加以避免，例如：改变路线、改变速度等；(3) 若车辆的密度超过了道路、铲点或卸点所能容纳的最大限，则在任意一个周期内都会出现的等待现象。在本题的条件下，第一种情况中的随机装卸和运输时间概率分布方差无法确定，故此时我们只能将其近似视为恒定，从而解决了随机时间所造成的等待。第二种情况的等待是可以预期的，但在速度恒定的前提下，只有通过临时改变路线的方法才可避免，将使问题的复杂性显著提高，而在一个班次的短暂时间内形成的影响却并不是很大，为了严格达到要求却引进了庞大的计算量，显然是很不可取的。第三种情况是我们唯一也必须要考虑的。车辆平均速度相同，且道路足够宽，则车辆在路上不会拥塞，只有在装卸点才会发生等待，如果与同一装卸点相连的车辆过多，则出现等待不可避免，这是无法容忍的。因此，在我们的模型中，着重避免的是第三种类型的等待。3、车辆所要完成的任务只有量的要求而已，即只要考虑在规定时间内运了多少次货即可，不需要再拘泥于该线路上运作车辆的数目。因此为了更好的表述这个概念，我们在模型中引入了一个在生活中常用的概念车次。它的定义为：所有车辆经过铲点或卸点的次数。它与运量直接相关，满足以下关系式：产量 = 车次 载重引入车次的概念后，完成相同数目的车次任务，可以用多辆车同时在短时间内完成，也可用少量车在长时间内完成。但一个固定路线（包含多个单一路线）的车次必然决定了其所需的最少车数，满足以下关系式：最少车数 班次时间 = （车次 路线周期）在上式中，最少车数可以取小数，表示在某一固定路线的任务完成过程中，某一车可以在完成自己任务后，换至其他路线，从而实现车辆的最大利用。本模型最终要得到的是对车辆的安排计划。根据上式，加上应有的约束条件后，求得车数就可求得最大车次，相反，求得各路线车次后即可求得所需的最少车数。这样，问题就转化为对车次的最优化问题。三、模型的条件和假设题目中重要条件的重述：1、卡车每次满载运输；2、一个铲位至多只有一部电铲；3、卸点和铲位在一个班次内固定不变；4、由于随机因素影响，装卸时间与运输时间都不精确，排时计划无效。5、矿石漏、倒装场只卸矿石，对矿石有品位限制；岩石漏、岩场只卸岩石，没有品位限制。模型基本假设：1、车辆的等待主要由车辆的密度超过了道路、铲点或卸点所能容纳的最大限额所引起。2、卡车在转换线路时不计时间损耗3、卡车的速度，等待时间记恒量，为其平均值。四、名词和符号的约定名词约定：铲位：露天矿里爆破生成的石料堆，每堆称为一个铲位铲点：有电铲工作的铲位卸点：卸下矿石或岩石的地方品位：矿石的含铁量原题中涉及到的常量：卡车满载重量：卡车平均速度：平均装车时间：平均卸车时间：一个班次： 品位限制： 自定义变量：总产量： 总运量： 总车数： 矿中铲点的数目： 矿石卸点的数目： ，岩石卸点的数目： 铲位中矿石产量： 铲位中岩石产量： 各铲位矿石含铁量： 铲位到卸点的距离： 铲位到卸点的运输次数： 卸点一个班次产量要求： 各运输线上的卡车数： 各运输线上卡车循环时间： 单线单车一个班次内的车次： 五、模型的建立和求解 首先将各铲点、卸点抽象成二分图中的结点，运输道路的路径抽象成边，并以彼此间距离定义边的权重矩阵。1、考虑第一条原则时的模型 即在满足各卸点产量和品位的前提下，使运输成本最小化。(1) 铲点数目满额时的模型(即铲点数铲位数)原问题可抽象成对运输成本的多目标规划模型： 保证运走的矿石不会超过铲点的供给量；(1)保证运走的岩石不会超过铲点的供给量；(2)保证满足各卸点的产量要求；(3)保证满足各卸点的品位要求；(4)保证满足各卸点的品位要求；(5)保证满足所有铲点在一个班次内可容纳的车次(6) 保证满足所有卸点在一个班次内可容纳的车次(7)定理：达到总运量最小时所用的车数即为最少应派遣的车数。证明：由各运输线上要求的总运行车数和每车的循环时间，可求得在该线上卡车运作的总时间为：其中，为始终在该运输线上运作的车数，为需要额外调用的车时。则矿场中总共所需的车数为： 由于、和可看作常数，而在总产量固定的，也为一个常数，则总运量最小即可保证派遣的车数最少。 据此定理，原题中的双目标规划问题便可简化为单目标规划，只需对总运量进行规划。则该模型即可转化为一个标准的整数规划模型，可用lindo等软件进行求解，当矿场规模不是很庞大的时候，可以以较快的速度寻取全局最优解。 (2) 铲点数目受限时的模型 根据前一个模型的求解结果，可以算出每一台电铲的利用率，并根据利用率优先原则进行排序，每次剔除一个铲点，直至铲点数目满足要求。 电铲利用率可用以下算式定义（文献2）： 其中为一个班次内累积电铲总空闲时间。该模型的求解与铲点数目满额的模型求解完全一样，每减少一个铲点即在二分图上删去对应的结点和关联的边，确定新的权重矩阵。但是对于该模型的求解还可以再提出两条简化方法： 1、若算出某一电铲的利用率为0时，则可以在舍弃后不必对模型重新求解，直接进行下一步骤的计算。因为利用率为0的铲点一定不与任一卸点相联，故一定是孤立点。将其从二分图中删去时不会对其求解结果造成影响。 2、根据在问题分析中提及的车次的概念，可以将电铲利用率的求解转化为简单的整数求和。电铲利用率的高低即为与该铲点相连的所有运输道路的车次之和，不需要再利用以上算式进行复杂计算。2、考虑第二条原则时的模型 即在车辆数目给定地前提下，使产量最大化。该模型和基于第一条原则建立的模型结构类似，约束条件(1)，(2)，(4)，(5)，(6)，(7)可仍然予以保留。目标函数更改为： 双目标规划添加约束条件： 当岩石卸点达到满负荷时，即岩石产量达到最大时，则可以去掉这个目标函数，使得多目标规划问题简化为单目标规划。其求解方法与第一问类似。六、对实际问题的求解和结果分析 针对题目中所给出的实例进行求解。1、考虑第一条原则时的求解(1) 铲点数目满额时的模型求解 经由lindo软件求解，得到各运输道路上的车次。(相关程序见附录1)算得总运量表110台电铲各运输道路的车次铲点12345678910产量目标量品位矿石漏135213787830.5倒装场4045 858530.12倒装场15268858530.49岩石漏8143124124岩场70158585矿石量684525281约束量16868688481岩石量81437015约束量281878781卸点目标车次的求取：铲点约束车次的求取： 矿石产量约束 岩石产量约束 此方法优化效果非常好：1到达卸点的实际车次与需要的车次吻合；2到达铲点的实际车次小于或等于约束车次；3满足品位要求，由表可见已趋于满足极限要求，即部分已到达30。5的上限由上可见卡车在不等待条件下满足产量和质量（品位）要求，而且已经很优化。(2) 铲点数目受限时的模型求解 由10台电铲求解结果可知，第5、6号铲点效率为0，不用配备铲车。剩余8台铲车根据利用率进行排序，得到如下排序结果：铲点101928437968170685245432采用末位淘汰制，取走7号铲点的铲车，重新进行规划，得到满足铲车数目的最优解，算得此时的总运量 总车数辆。相关程序见附录2表27台电铲各运输道路的车次铲点12345678910产量目标量品位矿石漏135411787830.5倒装场4243858530.02倒装场13270858530.49岩石漏8143124124岩场70158585矿石量682435481约束量6864688481岩石量81437015约束量81878781 对10台电铲和7台电铲的结果进行比较，发现7台电铲模型仅仅对10台电铲模型作了局部微调。铲点与卸点的距离（）表3铲点12345678910矿石漏5.265.194.214.002.952.742.461.900.641.27倒装场1.900.991.901.131.272.251.482.043.093.51倒装场4.423.863.723.162.252.810.781.621.270.50岩场5.895.615.614.563.513.652.462.461.060.57岩石漏0.641.761.271.832.742.604.213.725.056.10周期距离/平均速度28（）表4铲点12345678910矿石漏0.50910.50410.43410.41910.34410.32910.30910.26910.17910.2241倒装场0.26910.20410.26910.21410.22410.29410.23910.27910.35410.3841倒装场0.44910.40910.39910.35910.29410.33410.18910.24910.22410.1691岩场0.55410.53410.53410.45910.38410.39410.30910.30910.20910.1741岩石漏0.17910.25910.22410.26410.32910.31910.43410.39910.49410.5691单线单车一个班次内的车次8/周期表5铲点12345678910矿石漏15.715.918.419.123.324.325.929.744.735.7倒装场29.739.229.737.435.727.233.528.722.620.8倒装场17.819.620.022.327.223.942.332.135.747.3岩场14.415.015.017.420.820.325.925.938.346.0岩石漏44.730.935.730.324.325.118.420.016.214.1表6铲点12345678910矿石漏00.8176000001.818200.3081倒装场01.071401.1497000000倒装场00.66330.10000000001.4799岩场000000004.32101.0638岩石漏5.625002.86670000000表7铲场12345678910矿石漏0.81911.81610.30812.9433倒装厂11.07131.15052.2218倒装厂20.66470.09981.47922.2437岩场1.82920.32632.1555岩石漏1.81291.20433.01721.81292.55511.30411.15051.81611.82922.113612.582* 由各线路车次规划实现对车辆的具体安排算法设计：由于根据上表计算出的在各线路上的车辆数目表示为小数。这就相当于一个物件可分的等容积装箱问题。这种问题是一类简单的P问题。由于车辆是可以换线运行的，且换线成本为零，这说明在一条路上的任务可以分为多个车辆共同完成。对于一辆车来说，它的最大工作时间是固定的，即为一个班次。而各路线上的任务，可由在这条路上所需的工时确定，即所有车在该路线上工作的全部时间与所需工时相等，该路线的任务就被完成。对此问题，最简单的解决方案就是任意将各路线的工时依次添入各车辆中，当一部车的工作时间被填满后，将所剩的工时添如下一辆车中，直至将所有的工时添完。此算法程序见附录5。再将分配给各个车辆的工时化为在该路上所应完成的车次，这样就可以有一个可行的安排计划。改进方向： 但是对于实际情况总是希望尽量少的改变车所工作的路线。在搭配各路线工时将其尽量完整的添入各车中，实在无法完整放入的再考虑将其分割，这样就能得到比上述算法所得到得更加实际的安排。但由于时间有限，该算法没有程序实现。分析：这样体现了最少的车辆，一部分在一个班次中始终在一条路上运输，而有一部分则可以在不同时间在多条线路上运输，而根据假设卡车在转换线路时不计时间损耗，所以根据算法调整，其实有很多解，但均大同小异，本题仅用算法给出一可行解。表9i-j车123456789101112131-54536812-113132-2393422-313133-3223-5367434-2376438-13024549-438327010-1111110-347237010-4151545393637303847381628243841457注：i表示铲点1到10，j取值1到5分别表示：矿石漏、倒装厂1、倒装厂2、岩场、岩石漏分析：综上，算法的优点在于(1)很快地确定了铲点，如题铲点5，6，7被舍弃(2)很快地给出总车数(3)保证总运量最小，且满足模型中列举的所有约束条件(4)可较详细地安排各条路线上车辆的运行次数，具有很强的指导意义2、考虑第二条原则时的求解与第一问不同，发现若要岩石产量优先，则要使得岩石卸点的利用率要尽可能的高，事实上，题目条件7个铲点，20辆车，可以使得两个岩石卸场满负荷工作，这样 模型中的约束条件（2）改为 目标函数简化为，在相同的情况下再考虑 铲点数目满额时，将解1问中的程序略做改动，相关程序见附录3，得表1010铲点铲点12345678910矿石漏11858178倒装厂1434968160倒装厂22422462622140岩场8773160岩石漏812356160819196496846848796698可见可直接舍弃铲点6，根据减少铲点原则，去掉铲点7表118铲点铲点12345678910矿石漏29140979倒装厂14486840160倒装厂2203304435132岩场128761160岩石漏81106451608578967371969696691再去掉铲点5总产量最大表127铲位铲点12345678910矿石漏2431225284倒装厂123482168160倒装厂2187119108岩场1137175160岩石漏7228322816096969696969696672分析：当做到剩下7铲点时，求在总产量最大的时候的解，发现此时的解表现为所有铲点均满负荷运作，则总产量最大。在总产量相同的情况下，约束条件(1),(2)改为，目标为总运量最小。结果是，岩石产量优先；在产量相同的情况下，取总运量最小的解，相关程序见附录4。总运量最小表137铲位铲场12345678910矿石漏31361178倒装厂12068468160倒装厂2294837114岩场4128559160岩石漏7628322416096969696969696672根据题一中的调整算法，得一可行解：表14i-j车12345678910111213141516171819201-220201-54531762-23929682-528283-11813313-2443-32036293-532324-23731684-4444-524248-1306368-33216488-412129-111119-43838368510-3373710-44613594539182037303238384627374028263537284328672注：i表示铲点1到10，j取值1到5分别表示：矿石漏、倒装厂1、倒装厂2、岩场、岩石漏岩石产量49280万吨总产量10348810.35万吨总运量14691614.69万吨千米七、模型的评价和推广模型的评价：1本模型成功地引入车次的概念，在解答第一问时，在求总运量最小的情况下求得各路线上的车次，从而运用前文中证明的定理，等价地求得了最小车数。2合理的减少铲点的方法，使得铲点逐步减少，直至满足要求。减少铲点的原则简单，定铲点的位置方便3定下合理假设，使得运用Lindo软件计算本模型的问题，时间复杂性大大降低，解每个单一的问题软件运行时间少于一秒，十分快速4 用此算法可以快速地得到每条运输线上的车次和所需车辆数，使得安排工作计划方便5 满足约束条件，不发生等待，满足产量和质量（品位）要求，两个模型分别满足原则一和原则二6 最后的调整算法使得工作计划详尽可行，具有很强的指导意义改进方向：1 模型在考虑等待的时候只考虑了车辆在铲点和卸点的等待，即三方面原因之一，卸点和铲点能容纳的车次有限，若超过则产生等待。考虑其它因素导致的等待是模型改进的方向。对于第二种产生等待的原因，对模型可以添加得到如下两个约束条件： 其中为经过上述模型优化后与卸点j通车的所有道路的最大运行周期。决定了任意时刻卸点j所能承受的最大车数。该约束条件与优化结果有直接关系，我们可以在该方向采用自适应系统，运用神经网络进行求解。2 算法的计算量随着车辆优化问题规模的增大呈指数增长，当铲点和卸点数目过大时，采用算法花时间较多。八、参考文献1 纪寿文，物流配送车辆优化调度的一种神经网络算法，2 刘源张，保罗格雷，中美系统分析讨论会，中国学术出版社，1983九、附录附录1根据原则1,有10铲点的情况下,程序如下min 5.26n11+5.19n21+4.21n31+4n41+2.95n51+2.74n61+2.46n71+1.9n81+0.64n91+1.27n101+1.9n12+0.99n22+1.9n32+1.13n42+1.27n52+2.25n62+1.48n72+2.04n82+3.09n92+3.51n102+4.42n13+3.86n23+3.72n33+3.16n43+2.25n53+2.81n63+0.78n73+1.62n83+1.27n93+0.5n103+5.89n14+5.61n24+5.61n34+4.56n44+3.51n54+3.65n64+2.46n74+2.46n84+1.06n94+0.57n104+0.64n15+1.76n25+1.27n35+1.83n45+2.74n55+2.60n65+4.21n75+3.72n85+5.05n95+6.1n105subject to154n11+154n12+154n13=9500154n21+154n22+154n23=10500154n31+154n32+154n33=10000154n41+154n42+154n43=10500154n51+154n52+154n53=11000154n61+154n62+154n63=12500154n71+154n72+154n73=10500154n81+154n82+154n83=13000154n91+154n92+154n93=13500154n101+154n102+154n103=12500154n14+154n15=12500154n24+154n25=11000154n34+154n35=13500154n44+154n45=10500154n54+154n55=11500154n64+154n65=13500154n74+154n75=10500154n84+154n85=11500154n94+154n95=13500154n104+154n105=12000154n12+154n22+154n32+154n42+154n52+154n62+154n72+154n82+154n92+154n102=13000154n13+154n23+154n33+154n43+154n53+154n63+154n73+154n83+154n93+154n103=13000154n14+154n24+154n34+154n44+154n54+154n64+154n74+154n84+154n94+154n104=13000154n15+154n25+154n35+154n45+154n55+154n65+154n75+154n85+154n95+154n105=190001.5n11-0.5n21+0.5n31+3.5n41+2.5n51+4.5n61+3.5n71+2.5n81+4.5n91+2.5n101=01.5n12-0.5n22+0.5n32+3.5n42+2.5n52+4.5n62+3.5n72+2.5n82+4.5n92+2.5n102=01.5n13-0.5n23+0.5n33+3.5n43+2.5n53+4.5n63+3.5n73+2.5n83+4.5n93+2.5n103=0-0.5n11-2.5n21-1.5n31+1.5n41+0.5n51+2.5n61+1.5n71+0.5n81+2.5n91+0.5n101=0-0.5n12-2.5n22-1.5n32+1.5n42+0.5n52+2.5n62+1.5n72+0.5n82+2.5n92+0.5n102=0-0.5n13-2.5n23-1.5n33+1.5n43+0.5n53+2.5n63+1.5n73+0.5n83+2.5n93+0.5n103=0n11+n21+n31+n41+n51+n61+n71+n81+n91+n101=160n12+n22+n32+n42+n52+n62+n72+n82+n92+n102=160n13+n23+n33+n43+n53+n63+n73+n83+n93+n103=160n14+n24+n34+n44+n54+n64+n74+n84+n94+n104=160n15+n25+n35+n45+n55+n65+n75+n85+n95+n105=160n11+n12+n13+n14+n15=96n21+n22+n23+n24+n25=96n31+n32+n33+n34+n35=96n41+n42+n43+n44+n45=96n51+n52+n53+n54+n55=96n61+n62+n63+n64+n65=96n71+n72+n73+n74+n75=96n81+n82+n83+n84+n85=96n91+n92+n93+n94+n95=96n101+n102+n103+n104+n105=96endgin 50解： OBJECTIVE FUNCTION VALUE 1) 555.8900 VARIABLE VALUE REDUCED COST N11 0.000000 5.260000 N21 13.000000 5.190000 N31 0.000000 4.210000 N41 0.000000 4.000000 N51 0.000000 2.950000 N61 0.000000 2.740000 N71 0.000000 2.460000 N81 52.000000 1.900000 N91 0.000000 0.640000 N101 13.000000 1.270000 N12 0.000000 1.900000 N22 40.000000 0.990000 N32 0.000000