露天矿卡车的调度

承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：西安交通大学参赛队员（打印并签名）：1.计红林2.万日栋3.尧文斌指导教师或指导教师组负责人(打印并签名)：日期：2012年8月10日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：露天矿生产的车辆调度一.问题提出钢铁工业是国家工业得到基础之一，铁矿是钢铁工业的主要原料基地。提高采矿玉树设备的利用率是增加露天矿经济效益的首要任务。露天矿里有若干个铲位，每个铲位已预先根据铁含量将石料分成平均铁含量不低于25%的矿石和低于25%的岩石。每个铲位的矿石、岩石数量以及矿石的平均铁含量都是已知的（如附表12-1和附表12-2所示）每个铲位之多能安排一台电铲，电铲平均装车时间为5分钟。卸货地点有卸矿石的矿石漏、2个铁路倒装场和卸岩石的岩石漏、岩场等（如附图所示），每个卸点都有各自的产量要求。要求应该尽量把矿石按矿石卸点需要的铁含量（假设都为29.5±1%，称为品味限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品味限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。所用卡车载重量为154t，平均时速28km/k。由于卡车损耗大，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。每个铲位到每个卸点的道路都是专用的宽60m的双向车道，不会出现堵车现象，每段道路的里程都是已知的。一个班次的生产计划应该包含以下内容：出动几台电车，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条线路上的卡车数及安排即可）。一个合格的计划要在卡车不等待的条件下满足产量和质量要求，而一个好的计划还应该考虑下面两个原则之一：总运量（t·km）最小，同时出动最少的卡车，从而运输成本最小；（2）利用现有车辆运输，获得最大产量（岩石产量优先；在产量相同的情况下，取总运量的最小解）。请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对题的实例，给出具体的生产计划、相应的总运量以及岩石和矿石产量。附表12-1各铲位和各卸点之间的距离（单位：km）附表12-2各铲位矿石、岩石数量和矿石的平均铁含量（单位：万t）二.基本假设与符号说明1.基本假设（1）.电铲在一个班次内不改变铲铲位，也就是说每台电铲在一个班次内只在一个铲位上工作。(2）矿石漏和铁路倒装场姿势卸矿石的不同地方，他们的开采对露天矿的经济效益没有影响。同样，卸矿石的岩石漏和岩场的属性页不影响开采公司的经济效益。开采公司的经济效益只与开采量和运输成本有关。（3）卸点的品位是指一个班次内在卸点内所卸载的总矿石的铁的综合含量并不是部分要求（4）卡车的运输量都是满载运输，不考虑卡车在运输过程中的损失，另外，卡车的运输始终以28km/h的平均速度行驶，发动和刹车的时间不考虑。（5）在同一班次内，卡车所走的路线是不固定的，即卡车选择哪条路线是随机的2.符号说明为在一个班次内从j铲位到i卸点单向路径上所通过的总车次为在一个班次内从i卸位到j铲点单向路径上所通过的总车次；n为铲位总数，m为卸点总数；为从i卸点到j铲位的路程；ijgijrijs装一辆车所需的时间为卸载一辆车所需的时间为i好卸点的需求量为i号铲位的岩石供应量为i号铲位的矿石供应Q为总的运输量F为总产量N为所需卡车总量三．问题分析及模型的准备通过直观的分析可知，本问题是一个较复杂的运输系统调度问题。问题分别要求满足运输原则的条件下，建立一个班次运输方案安排的数学模型，并且要给出所用电铲的台数和每台电铲的位置，卡车数量以及卡车的安排。所以本问题是一个大型的目标规划问题，目标函数是要求的两个原则，即一个是要求总运量最小，同时出动的卡车最少，另一个是要求获得的产量最大，对于开采公司来说，制定两个原则就是为了减少成本，增加收入，来提高公司的经济效益，这样就知道了解决该问题的方向是研究约束条件和目标函数。下面对问题做进一步的分析：1.运输矩阵的建立卡车路线的选择是双向的，随机的。为了便于描述卡车在一个班次内的调动状态，一般规定，铲位到卸点的方向为前进方向（Go）；t上t下iKiMiU反之则是返回方向（Return）设有m个卸点，n个铲位，可以建立以下矩阵描述GO方向的运输状态:G=其中，表示一个班次内从j铲位到i卸点的单向路径中所通过的总车次.1jm和1in同理可以得到Return矩阵:R=其中，表示一个班次内从i卸点到j铲位的单向路径中所通过的总车次以上两个矩阵统称为调度矩阵；2.原则一的数学分析原则一要求总运量最小，同时出动的卡车最少这实际上是要求运输最小，所以该原则又可以成为成本最小原则，则运输量可以理解为:1111............nijmmngggggijg1111............nijmmnrrrrrijr其中a为卡车满载时的重量。当卡车返回时，此时卡车所走路程不为零，但此时卡车所载货物的质量为零，所以返回时卡车运量为零。卡车最少有以下两个特点：（1）.卡车得到最大限度的利用，即卡车几乎没有等待的时间（闲置时间）（2）.卡车充分的工作，恰能完成运输问题，或者超额的部分不多。由于所有卡车一直在工作，即对每辆卡车在一个班次内都是装，运，卸三个状态。便有：其中，T为生产周期，即一个班次的时间，*t为在一个班次内所有卡车的等待时间于是有;由于整个运输过程中不应存在等待时间，所以*t的值应近似为零。11mnijijijQags*1111[()/](rt)tmnmnijijijijijijijNTgrsvgt下上*t*1111[()/](rt)t=mnmnijijijijijijijgrsvgtNT下上3.原则二的数学分析要求利用现有车辆，获得最大的产量，称为产量最大原则;这里指矿石和岩石的总产量：4.等待时间的控制在安排运输方案是原则不应有等待时间，但不排除等待时间存在的情况，所以在等待是应尽可能避免等待时间出现的情况，卡车在进行调度是可以根据“最小饱和度”原则（MSD）,以尽可能避免发生等待时间出现的情况。这一原则实质是指，将卡车调往具有最小饱和度的路线：choice(i)=j()()min{},1ichoicejDim其中choice(i)表示处于i卸点的车将去铲位的代号，choice（j）表示处于j铲位的车将去卸点的代号。表示卸点到j铲位的饱和度，iD表示铲位到i卸点的饱和度，其中和iD的数学表达式为：11amnijijFgmin{},1jDjnjDjDjD表示正装车估计剩余的装车时间表示j号铲位的卡车数，包括正装的卡车表示i卸点的卡车数，不包括正卸车的卡车数四.数学模型（模型1）的建立与求解1.模型的建立以上对问题的分析，给出了成本的数学表达式，再经过对目标函数的月数条件分析后，建立了以下的双目标线性规划模型：'j()ijjtsNtDvt上上'i()ijitsNtDvt上上'tjNiN=1j=1min=mnijijiQags*=1=1=1=1+r/++r+min=mnmnijijijijijijijgsvgtttNT下上=1mijjiagM=1nijijagK=1=129.5%1%njijjnijjbgaga=1mijjiagU*0,T*lim=0T=1,nijjTrt下1im=1,mijiTgt上1jn=1=1=1=1=mnmnijijijijgr0,0,ijijijijgrgr且，为整数min1=|jDjnchoiceijmin1=i|iDimchoicej关于约束条件的说明如下：（1）条件1是为保障在一个班次内满足各卸点的需求。（2）条件2是对铲位搭配的约束，即在同一班次内所有矿石的卸点都要达到品位要求的限制。（3）条件3与4都是基于铲位的岩石和矿石的储量都是有限的而进行的约束，即从任何铲位所输出的产量不应超过该铲位的储量。（4）条件5与6是对和的约束，他们的上下限不应超过（5）条件7描述了等待时间的情形，说明了可以存在等待时间，但尽量应使等待时间为0.（6）条件8给出了Go和Return矩阵元素之间的逻辑关系。（7）条件9是对目标函数中和的约束，这是由他们的现实意义而定的。（8）条件10和11是为了保证尽量避免等待时间而进行的实时调度的约束。2.模型求解模型1是典型的大型的双目标线性规划问题，即使在约束条件下对两个目标分别求解，也是困难的，困难在于模型中的变量太多，尤其是模型的约束条件中包含了实时调度限制，这种限制使模型变成非线性，而且不易控制的复杂的数学模型。因此不易直接由计算机进行搜索求解，只能另辟途径。1.模型算法的理论分析ijgijrijgijr模型的求解要求给出一个班次内出动电铲的台数、电铲分布的铲位、出动卡车的数量及卡车的线路分配。模型的目标函数为总运量最小，同时要求出动的卡车也是最少，但也要满足运输要求，所以先不考虑出动卡车的台数，直接以总运量最少为目标，求解模型。求解出运输方案后，卡车数量即可给出。直接的求解很复杂，为此采取分步求解的方法：（1）用线性规划的方法求出从每个铲位到每个卸点所发的车次，从而求解出Go矩阵。（2）从Go矩阵判断所需出动的电铲的台数和铲位分配（3）依据Go矩阵提供的信息，用线性规划的方法求出由每个卸点返回到每个铲位的车次，从而给出了Return矩阵。（4）依据GO矩阵和Return矩阵，根据卡车的充分利用条件求出在一个班次所需卡车的数量。2.分步求解的实现为求解Go矩阵，先要求每个铲位到每个卸点的岩石。为此，以总运量为目标函数，建立如下单目标线性规划模型。510i=1j=1minQ=aijijgs1055j=1=1=15j=15=1=1105=1=1,,[29.5%1%],10,16096UbtijijijijjjjijjijjmijjijijijjjaaaaaTjnaagggKMgggggg上且为整数，铲位铲位1铲位2铲位3铲位4铲位8铲位9铲位10合计矿石漏13551078倒装场1414485岩场701585岩石漏8143124倒装场2147185合计81684344557096457由于表格的形式更能直观地表现卡车的调动状态，所以只以表格的形式反映调动矩阵的信息。并由表中的信息可以推得：满载运程为553.72，最小总运量为85272.88吨/千米Return矩阵的求解由于卡车往返时所选的路线是随机的，但它选择的路线应使总路程最短，所以卡车返回时仍用线性规划模型求解。卡车返回的路线如图所示。此时将卡车都集中在卸点，任务是给出卡车的从卸点到铲位的最佳分配方案，使总路程最短。此时卸点相当于供求点，可以以总路程最短为目标函数，以卸点的供求限制、铲位的需求限制为约束条件，建立以下单目标线性规划模型：其中，H表示所有卡车返回时所走的总