碎石运输方案设计.doc

道路改造项目中碎石运输的设计 编号： 4325摘要本文建立了道路改造项目中碎石运输的设计模型。该模型是一个双重优化模型，先用0-1线性规划，求出建码头个数及临时道路的分布，再用非线性规划进一步减少费用，经计算我们求得：最少总费用是16,5027,2857（元）从S1所取的碎石量是1043609 m3从S2所取的碎石量是 580816 m3模型中将码头、临时道路等看成一个运输系统，它有自己的整体结构与局部结构。整体结构是指码头个数、道路条数等。局部结构是指码头和道路的精确位置等。在确定该系统的整体结构时，我们用将连续变量离散化的思想引入了0-1线性规划，即将AB分成若干等长度的段，码头和AB上临时道路的入口则看成一些离散的点。该0-1线性规划模型可以求出很好的整体结构。我们用人工找出的三码头情形的整体结构经非线性规划优化后的总费用为：17,2501,1687 (元) 。比以0-1线性规划经非线性规划优化后的总费用多了7473,8830 (元)，可见我们的模型对工程实践中的科学决策具有十分重要的指导意义。在模型检验中我们进一步讨论了人工增删临时道路对总费用的影响.通过计算我们发现增删临时道路均会使总费用增大，从而验证了当前解趋近最优。当临时道路出现岔路时，我们计算得总费用并不会有所减少，故验证了我们关于“临时道路为直线且无岔路”的假设。关键词：双重优化 运输系统 0-1规划 非线性规划1、问题重述与分析1.1问题背景的理解1. 模型构建的重点：由计算我们发现修公路AB所用碎石材料费用仅为9000万元，仅占到估算总费用的1/16左右，而大量的费用消耗在临时道路建设及碎石运输上，而影响此两部分的关键在于确定码头个数、位置及临时道路的长度。故在下模型建立与求解中我们将以此三点为重点进行分析与建模。2运输系统的结构我们将所有用于运输的码头，临时道路及其分布称为运输系统，它们都是为运输碎石服务的。整个系统包括两个层次结构：第一层次：修建码头的个数，临时路线的拓扑结构。我们称这部分结构为整体结构；第二层次是精确的码头及临时道路的位置（AB上运进碎石的点称为进料点）,我们称这部分结构为局部结构。讨论有意义整体结构很难用连续变量表示，而局部结构可以用连续变量来描述。意即只有当整体结构确定了以后，总费用才可表示为连续变量的函数，从而可以规划求解得到在保持某一整体结构不变的前提下的最优局部结构。故此题目转化为依次确定运输系统二个层次的最优结构。1.2 关于运输系统结构的几点基本结论：1. 从S1不应修出直达AB的临时道路：通过计算我们发现从S1修出直达AB的临时道路以利用陆路运输的费用相比从S1修建临时道路至河边以利用水路运输的费用大很多，故我们认为在现有题目条件下S1不应再修出直达AB的临时道路，而应就近建码头以充分利用水路的廉价运力。2. 从S2不会修出跨AB至河下游码头的临时道路：显然S2不可能修建临时道路至河下游以利用水路，分析如下：1）此举修临时道路过长，耗费很大；2）如此长的临时道路运输费用昂贵；3）若逆流运输则费用较高。3. 具体运输流程：由前1、2知，从S1运出的碎石必然只能经水路调配到n个码头，再由各码头修建临时道路至AB以运输碎石，而从S2就必然直接修建临时道路至AB。可见，在这种情况下，各码头与S2功能等效，在此我们不妨将各码头及S2统一等效为出料点，则问题转化为从各出料点到公路AB运输碎石的调配问题。4.码头修建范围的限制：由费用平衡点的思想，我们总能在AB上找到一进料点X，使修建该段所需碎石从S1、S2分别进料的费用相等，我们将此进料点X记为S1与S2的费用平衡点。即在公路AX，XB两分部碎石分别由S1、S2单独提供。经计算我们发现，当x大于120 时，从S2进料的最小费用小于从S1进料的最小费用，从而得证应建码头的修建范围（横坐标）：（在此我们缩小了码头的修建范围，提高了后续大规模规划模型的计算精度及速度）5各临时道路均为连接出料点与进料点两点间的直线段且互不相交需要论证。由反证法显然得证。2、问题假设1、车辆运输碎石回程时不计运输费用；2、临时公路所铺碎石不能再重复利用于公路施工；3、铺设道路的工程费用为常数，在此不予考虑；4、S1，S2无碎石容量限制；5、忽略河流的自然环境因素对码头建造，水路运输的制约，即码头可建在河流两岸任意地点；6、各临时道路为连接出料点与进料点两点的直线段且互不相交；7、各临时道路均无岔路分支； 8、公路建设期间施工车辆可以通行；9、忽略碎石在装卸，配送过程中的自然损失；10、河上、下游点精确的分布在抛物线上；11、S1，S2运出的碎石已满足工程需要，不必再进一步进行粉碎。（以上仅给出全局性假设，其后还会按情况给出一些局部假设） 3、符号说明1. (xi,yi)第i号出料点（包括码头及S2）的坐标；2. (zi,100)公路上第j号进料点的坐标；3. (ri,100)将公路分段后第i号分界点坐标.（以上仅给出全局性变量，局部变量在使用时另行说明）4、模型的建立与求解：首先我们建立起在整体结构确定的情况下，用以寻求最优局部结构的非线性规划算法。因为此非线性规划算法的具体形式依赖于整体结构，故我们接下来以初步分析得到的较合理的三码头方案的整体结构为例，以引出用以寻求最优局部结构的非线性规划算法。上述三码头方案的整体结构如下图：4.1基于3码头的初等非线性规划：4.1.1模型准备1S1距河流的最短路及对应的固定码头位置：最短路长S=4.367（km）固定码头位置坐标（18.926，115.767）（注：此码头为固定码头，位置不变，即此模型中除了此码头外我们还需修建三个码头）2河流上任意一点与固定码头（18.926，115.767）间的距离函数：3临时道路修建费用：设第i号码头至固定码头水路距离为di，（i=1,2,3），临时道路长度分别为Li(i=1，2，3)（单位：km），则有如下关系：从S2引出的临时公路的修建费用（costA）=临时道路所需碎石成本（cost1）+临时道路建设过程中所需碎石的运输费用（cost2）易得：由简单积分：故 由S1引出的临时公路的修建费用同理计算，只需加上临时道路所需的碎石从S1固定码头临时道路旁码头的运输费用。同理得：4河流曲线方程判定：通过验算分别由mi（i=1,7）确定了上游和下游的近似抛物线方程。在此不妨设河流上所有点均精确地分布在抛物线上。上游抛物线方程：下游抛物线方程：4.1.2目标函数设各码头坐标为（xi ，yi）（i=1,2,3），公路AB上各进料点位置为（zi，100）（i=1,2,3），在三码头情形下，整条公路按照对应出料点的不同被分为4段，则设各段分界点坐标为（ri,100）(i=1,2,3)。（注：不妨设各出料点只有一条临时道路至对应的进料点）由前分析，目标函数（总费用）=临时道路的总建设费用+各临时道路上通过的碎石的总运输费用+公路建设所需碎石的成本费用+部分常量成本具体如下：1.对13号码头：总费用=临时道路修建费用（costBi）+各临时道路上通过的碎石的总运输费用 2.同理对S2：总费用3.公路建设所需碎石的成本费用4.部分常量成本=S1固定码头的临时道路建设费用+固定码头修建费用 =181109.4+100000=281109.4(元)总费用即为上述四部分之和。4.1.3 约束条件1.临时路长等式约束：2.水路长度约束：3. xi，zi，ri位置约束：4、码头位置约束：4.1.4 结果分析总费用：17,2501,1687(元)表1：出料点、进料点、分界点位置表编号出料点位置（横坐标/km）编号进料点位置（横坐标/km）编号分界点位置（横坐标/km）118.926117.265131.1392502502105.19393.7683111.83139.3741804173.374上述结果对应的最优运输系统结构如下图2：具体方案为3码头，3条临时道路，总费用为17,2501,1687（元）。虽然该模型采用了非线性规划模型，但由于在实现算法时整体结构由人为确定，主观性太大，故不可能达到最优。为了避免人工决定整体结构带来的盲目性，我们进一步提出了以下先从宏观上确定整体结构然后再用上述非线性规划算法从微观上确定最优局部结构的双重规划模型。整体思路好4.2双重规划模型基于先离散再连续的思想，我们进一步建立了可进行双重优化的两层规划模型：第一层：0-1线性规划第二层：非线性规划4.2.1模型阐释：此模型精髓在于“先离散再连续”的思想。所谓离散，是指将公路、河流长度均等分为n段（故有n-1个分界点），码头、进料点的可能位置均处于这些离散的分界点上，则由0-1线性规划可得出最终码头和进料点的确定数目和位置。如此必然可得在该分段情况下总费用的较优解及码头、临时道路的宏观布局。n越大，分段越密，码头和进料点的位置就趋近于连续变化，则结果就必然越趋近于最优解。所谓连续，是在0-1规划后整体结构已确定的情况下，利用4.1中的非线性规划算法优化局部结构，使总费用更加趋近于最优解。4.2.2 0-1线性规划4.2.2.1分段情况及三层运输网络介绍由前（ 3.2.4 ）分析可知，码头修建位置应在（0,120）之间，我们不妨将整段公路及码头的（0120）部分等分为40段，码头、进料点的可能位置均处于这些离散的分界点上。由于当碎石由公路的进料点运入后，还存在一个由进料点分发至各具体施工地点的过程，这部分运输费用显然也不能忽略，由积分的思想可知，我们不妨设公路每段的中点为可能的卸料点，如此便构成一个三层运输网络，如下图：4.2.2.2目标函数设0-1变量xijk,yij,tmi，含义如下：则目标函数为：总费用=公路建设所需碎石的总运输费用（c1）+临时道路的总建设费用（c2）+码头费用（c3）+部分常量成本（c4）（单位: 元）4.2.2.3 约束条件1） 系数计算： 设运输碎石从ijk的费用为,修建i j的临时道路费用为fij。则由三层运输网络图示可知,应分三种情况考虑：至15号码头属于逆流航行，至639号码头属于顺流航行，40号为S2应单独考虑。同理，也如此计算如下：2）每一个卸料点都必然只有一条运石路线到达：3）ij的道路存在与否对ijk碎石运输路线的约束：4）i号码头存在与否对ij碎石运输路线的约束：4.2.2.4 结果分析总费用：16,5685,9000（元）表2：出料点、进料点、分界点位置表编号出料点位置（横坐标/km）编号进料点位置（横坐标/km）编号分界点位置（横坐标/km）117（码头）110110220（码头）215220326（码头）325330435（码头）435440547（码头）545545650（码头）650690774（码头）7907105892（码头）811081309180（S2）91509155101701018011190t用lingo进行计算，得出在40分段下的最优整体结构，具体方案为8码头，11条临时道路，总费用为16,5685,9000（元）。前4.1中的三码头方案总费用为17,2501,1687（元）,相比上述方案增大了，增加的绝对数值达到了6815,2687（元），可见运输系统整体结构对最优解影响巨大，仅靠人工来寻求最优整体结构很难做到，这就凸显了用0-1规划来从全局角度优化整体结构的重要性和必要性。但由于该方案毕竟是将连续问题离散化，实际中若要得到全局最优解应将问题离散为无穷多段，但如果再将离散程度提高十倍，简单估算将使时间复杂度至少提高为原问题的103倍，所以我们无法再通过提高分段数来使得整体结构更优，因此我们认为整体结构已达到目前条件下的最优。至此我们已完成了对运输系统整体结构的优化，接下我们进行局部结构的非线性规划寻优。非线性规划寻优在前述0-1线性规划给出整体结构之后，我们只需以码头，进料点，分界点位置为变量，以总费用为目标函数，用4.1 中的非线性规划算法使其各点位置局部扰动，趋近最优即可，具体计算过程不再详述，结果如下：总费用：16,5027,2857（元）表3：从s1，s2所取的碎石量表临时道路建设所用碎石（单位：m3）公路AB建设所用碎石（单位：m3）所用碎石总量（单位：m3）s152878.63715990730.11451043608.752s271546.48796509269.8855580816.3735表4：出料点、进料点、分界点位置表编号出料点位置（横坐标/km）编号进料点位置（横坐标/km）编号分界点位置（横坐标/km）118.92600（码头）19.50724112.10011218.92600（码头）217.18754221.16109324.78833（码头）324.97344328.89557433.37084（码头）432.77693436.20283541.72291（码头）540.21071542.79226650.00000（码头）650.00067690.16619776.65349（码头）792.991787109.44589895.70385（码头）8113.617988132.097359180（S2）9151.860709158.4039210170.7696110179.2825111187.98254用lingo进行计算，得出具体方案为7码头，10条临时道路，总费用为16,5027,2857（元）。从图中可见码头1和码头2经过非线性优化后合并为一个码头，可节约10万元。这一方面说明了离散方案不可避免的局限性，另一方面也说明了双重规划模型的稳定性。前4.2.2 中用0-1规划运算后的总费用为16,5685,9000（元）,相比上述方案增大了，增加的绝对数值达到了648,6143（元），可见运输系统局部结构对最优解影响也很大，这就凸显了用非线性规划算法来进一步优化运输系统局部结构的重要性和必要性。5、模型检验由于我们所用的模型只能求出近似最优解，而本问题中涉及到的总费用达十几亿，故应持慎重的态度对模型做进一步的检验和调整，以充分节约资金。5.1增删临时道路对模型结果的影响为了检查我们用0-1规划得到的整体结构的合理性，我们在通过0-1规划得到的较优方案中，新增或删除1条临时道路，再以之以为基础运用非线性算法求解之，得到的总费用均比不增删时要大，这就充分证明了0-1规划模型对于运输系统整体结构优化的有效性。具体过程如下：我们选择了下图中的第4条临时道路（黄色线路）进行删除检验，选择在下图中的第7条临时道路与第8条临时道路之间加一条临时道路以进行增加检验。具体情况见下表：检验方式总费用（亿元）与最优值（16,5685,9000元）比较的相对增加量（万元）与最优值（16,5685,9000元）比较的绝对增加量（万元）删除第4号线路16.66670.59%980第7、8条临时道路之间增加一条临时道路16.74321.05%17465.2增加岔路对模型结果的影响经过观察我们发现从S2出发的最左端的临时道路斜率较小，故我们认为在该路线末端修岔路最有可能减少总费用。设D为AB中点。在AS2取一点C使AC=BC，易知S2A=63.56776（公里）， AC=BC=7.386871（公里）， AB=6.54（公里）。未分岔前AB段碎石全部沿S2A运达，分岔后，AD段沿ACS2运输碎石，DB段沿BCS2运输碎石，平均运输距离减少了（公里），这样减少运费=1.635206.547500=1603935（元）。而修BC的费用为3715556（元）。故总费用没有减少，反而增加了2111621（元），这主要是由于将修路用的碎石运到分岔口处的距离太远，运费十分高，故模型中关于临时道路是直线且不分岔是合乎实际的一般情况的论证更有意义。6、模型的进一步讨论将位置及长度离散化的方法，还能用在很多类似于确定修路位置，桥梁位置等问题中，离散化了之后，原来的非线性问题可转化为线性问题，一些难以用连续变量描述的约束，可以很简单地用0-1变量表示，避免做多次试探即能得到很好的初始方案，从理论上说离散化时分段越多，分点越密，越接近连续的实际情形，但分得越多0-1变量亦越多，直接用优化软件来解变得不可行，有必要针对此类问题设计高效率的近似算法， 0-1规划问题是NPC问题，但针对此类问题完全有可能设计出多项式时间算法求出很好的近似最优解，由于时间太仓促，我们暂时还未提出有效的算法。7.模型的优缺点优点：1、 本模型较正确地处理了道路改造项目中碎石运输问题，模型较为符合实际。2、 二层规划模型的使用贴近题意，能准确、快速地计算最小总费用，有很强的实用价值；3、 在计算模型的解时，我们利用了专业的数学软件matlab、lingo和excel，在推广中探讨了模型的实用性并分析其灵敏度。缺点：1考虑的因素比较全面，但算法较为单一。2部分假设还不太符合实际情况；8.参考文献1. 汤代焱.运筹学，中南大学出版社，。2叶其孝，大学生数学建模竞赛辅导材料，湖南教育出版社，长沙，19933姜启源，数学模型，高等教育出版社，北京，2003附录一、 Matlab主要程序function f = myobjfun10ok120jian1(ax)if ax=0for a=1:10 x(a)=ax(a);endfor a=11:20 z(a-10)=ax(a);endfor a=21:29 r(a-20)=ax(a);endx(9)=180;x(10)=180;x(8)=180;% r(1)=0;% r(5)=200;pt1=0;pt2=0;pt3=0; LL1=0; LL2=0;for i=2:7 l=sqrt(x(i)-z(i)2+(gety(x(i)-100)2); LL1=LL1+l; d=getcurvelong6(18.92600222,x(i); pt1=pt1+ 7500*(z(i)-r(i-1)*(6*d+20*(l+4.36731650690042+(z(i)-r(i-1)/2)+7500*(r(i)-z(i)*(6*d+20*(l+4.36731650690042+(r(i)-z(i)/2);end for i=8:9 l=sqrt(x(i)-z(i)2+(157-100)2); LL2=LL2+l; pt1=pt1+ 7500*(z(i)-r(i-1)*20*(l+(z(i)-r(i-1)/2)+7500*(r(i)-z(i)*20*(l+(r(i)-z(i)/2);end i=1; l=sqrt(x(i)-z(i)2+(gety(x(i)-100)2); LL1=LL1+l; d=getcurvelong6(18.92600222,x(i); pt1=pt1+ 7500*(z(i)-0)*(6*d+20*(l+4.36731650690042+(z(i)-0)/2)+7500*(r(i)-z(i)*(6*d+20*(l+4.36731650690042+(r(i)-z(i)/2); i=10; l=sqrt(x(i)-z(i)2+(157-100)2); LL2=LL2+l; d=getcurvelong6(18.92600222,x(i); pt1=pt1+ 7500*(z(i)-r(i-1)*20*(l+(z(i)-r(i-1)/2)+7500*(200-z(i)*20*(l+(200-z(i)/2);% pt1=pt1+ 7500*(z(i)-r(i-1)*(6*d+20*(l+4.36731650690042+(z(i)-r(i-1)/2)+7500*(200-z(i)*(6*d+20*(l+4.36731650690042+(200-z(i)/2); for i=1:7 l=sqrt(x(i)-z(i)2+(gety(x(i)-100)2); d=getcurvelong6(18.92600222,x(i); pt2=pt2+400*l*(60+6*d+20*(4.36731650690042+l/2); end for i=8:10 l=sqrt(x(i)-z(i)2+(157-100)2); pt2=pt2+400*l*(60+20*l/2); end f = pt1+pt2+181109.4+90000000+(105)*9;else sm=0;for a=1:29 if ax(a)200 sm=sm- 10000000000000000000000000000*(200-ax(a)+100000000000000000; end end f=sm/100000000000000 +100000000000000000;endlingo主要程序model:sets: cf10/w1.w40/:objectpoint; cf9/w1.w39/:inputpoint; cf7/w1.w40/:outputpoint; cf6/w1.w39/:tm; cx(cf7,cf9,cf10):x,c; cy(cf7,cf9):y,f;endsetsdata:l=40;M=40;c=2.47400E+007 2.47400E+007 2.84900E+007 3.22400E+007 3.59900E+007 3.97400E+007 4.34900E+007 4.72400E+007 5.09900E+007 5.47400E+007 5.84900E+007 6.22400E+007 6.59900E+007 6.97400E+007 7.34900E+007 7.72400E+007 8.09900E+007 8.47400E+007 8.84900E+007 9.22400E+007 9.59900E+007 9.97400E+007 1.03490E+008 1.07240E+008 1.10990E+008 1.14740E+008 1.18490E+008 1.22240E+008 1.25990E+008 1.29740E+008 1.33490E+008 1.37240E+008 1.40990E+008 1.44740E+008 1.48490E+008 1.52240E+008 1.55990E+008 1.59740E+008 1.63490E+008 1.67240E+008 2.89758E+007 2.52258E+007 2.52258E+007 2.89758E+007 3.27258E+007 3.64758E+007 4.02258E+00