研究生数学建模E题详解

--#-货运车物流运输计划问题在整数线性规划的基础上建立适当的模型、再运用分支定界法找到满足约束条件的较优变量，同时比较两种算法的迭代次数和运行时间，为进一步提高算法的利用率提供了依据。最后通过MATLABGUI做成软件模拟在不同配置下相对应的分配方案，在总费用最小的前提下，程序运行时间短、效率高、能够较精确快速的找到合适的解决方案。通过分析相应的整数线性规划建立相关的数学模型最后通过软件计算得到理想的效果，但是考虑到装箱调度决策过程中有多种可能，保证所有运输任务完成的情况下分配尽可能少的车辆来运输，因此，我们选择在货运车尽可能满载的情况下的分配方案。这样可以减程序中少大量的矩阵运算和程序运行时间以及变量的迭代次数。随着变量个数的增多，约束条件下不能得到较优的目标值，因此我们采用分支定界法先定出可选择的分配方案，再在优化的分配方案中找出相对较优的分配方案，例如运用整数线性规划得到不同车配置方案，运用分支定界法改变约束条件得到结果，在有路径的约束条件下我们运用两阶段法考虑整个分配方案。先考虑第一阶段数量上的优化再考虑第二阶段路径上的优化。运用逐步调优的策略在相同路程下就不优先考虑路径的优化，进一步调整配置方案。在给定装配任务和分配任务的同时我们运用关联分类器先按题目要求将两张表建立关联，通过所给轿用车型的长、宽、高建立一个分类器。按照表二中长、宽、高的不同分类分为12类，根据调度经验改用启发式算法将分类数降低至10类。在满足题目要求的前提下我们采用货运车车型混装的形式，在一定程度上减少货运车的使用数量。从而达到最充分的发挥资源的效能去获取最佳的经济效益。对整车装箱调度问题进行研究从而降低运输成本具有一定的意义。1、问题重述智能装载的问题描述：在一个配送中心，有N件货物需要分别配送至目的地A，B，C，可以使用M辆车。问如何规划车辆的配送路线，以及如何合理分配车辆的货物装载情况，提高车辆的实载率，减少车辆的数量。已知：1、 车辆的信息：载重量，车厢的长宽高2、货物的信息：货物的重量，货物的长宽高，货物的卸货地3、 卸货地：位置信息（经纬度）4、 每天的运单量（总量不固定、每个目的地每天有无订单以及订单多少不固定）限制条件：1、 车辆从始发地开始，顺序到达最后卸货地之前，不回头；2、 车辆中途只卸货，不上货；3、 货物的总体积不超过车厢的容积（长宽高均不超过）；4、 货物的总重量不超过车辆的载重量；5、 不考虑货物能否堆叠放置；6、 不考虑货物的朝向问题，全部正放（长宽在底）；7、 货物根据卸货地的顺序采取后进先出的原则；8、 相同一个卸货地的货物只装载在相同一辆车辆；整车物流是指按照客户订单对整车快速配送的全过程。随着我国汽车工业的高速发展，整车物流量，特别是货运车的整车物流量迅速增长。货运车物流计划问题主要是为了解决货运车运送货运车的装载过程中资源充分利用以及减少运输成本的问题。需要利用货运车按照要求将不同规格不同数量的货运车运送到各自的目的地。当前很多物流公司在制定运输计划时主要依赖调度人员的经验，在面对复杂的运输任务时，往往效率低下，而且运输成本不尽理想。我们需要解决的问题是根据可以调用的“货运车”中选择出若干辆货运车，进而给出其中每一辆货运车上货运车的装载方案和目的地。在确保任务完成的前提下，降低运输成本。2、 模型假设对于问题1-4假设在中转站有足够的货运车够调运，不考虑多次装卸产生的费用。在所有运输中不考虑在规定时间的因素，所有装配都没有时间限制。在运输过程中不考虑意外损失的消耗费用。不考虑3、 问题分析影响成本高低的首先是货车使用数量；其次，在货车使用数量相同情况下，不同车型的使用成本不同，由低到高进行排列，原则是先装费用低的货车，在费用低的货车使用完情况下，使用费用较高的原则；再次，在货运车使用数量及型号相同的情况下，行驶里程最短的成本低。（如果该公司是全国性的公司，在各地均会有整车物流业务，及无需放空返回。最后每次装卸车的成本忽略）如果不考虑该公司性质，则只需满足每次装卸车的成本忽略。解决策略：数据：车型选择（车的装载能力，长、宽、高），货物（大小、重量，目的地）选择，经度（longtitude），纬度（latitude）；运单量（订单量）。需求：完成货物运送，给出运送方案，目标：运送时间最少，费用最低；根据当天货物订单特征（大小，重量），目的地打点（1ongtitude,latitude），并根据目标地和配送中心的距离（计算距离）根据配送中心和配送货物的多少、远近（此处我们考虑相同货物聚类（以配送中心点为中心））的点，找出其最佳配送路线（按照距离最小，车型配置等）。优先装载远方的货物，并考虑货物大小，重量；为了考虑平稳性先将大件货物放在底层（具体装载方案）。单通道我们占时考虑将货物放在分叉点，多通道考虑分配优化方案。4、模型的建立与求解4.1问题一的分析：若物流公司要运输多箱产品我们考虑到装箱调度决策过程中有多种可能，在多目标约束条件下根据最优分配原则。保证所有运输任务完成的情况下分配尽可能少的车辆来运输。在此，我们选择在货运车尽可能满载的情况下的分配方案。这样可以减少大量的矩阵运算和程序运行时间以及变量的迭代次数。考虑到充分利用货运车空间，在满足题目要求的前提下我们采用货运车车型混装的形式，这样可以在一定程度上减少货运车的使用数量。4.1.1数学模型的建立建立目标函数：TOC\o"1-5"\h\zS.tmin(2工+2y) (1)i i于是我们建立约束条件：1)1-1型货运车满足的约束条件：19-3.615<(4.61+0.1)xa+(3.615+0.1)xb<19,i=1,2,3,4,51i 1i方案I型车数量II型车数量剩余长度(m)1050.4252133.1453222.154311.1555400.16TOC\o"1-5"\h\z一3.615<(4.61+0.1)xa+(3.615+0.1)xb<24.3,j=1,2,3,4,5,62j 1j2)在此约束条件下货运车还应该满足以下条件：方案I型车数量II型车数量剩余长度(m)1062.012151.0153240.024322.745411.7456500.753)同时满足以下约束条件:TOC\o"1-5"\h\z22ax+23ay>1001ii 2jj』 j=122bx+23by>1001ii 2jj』 j=12y<-2x〔j=1j5i=1i4.1.2模型的求解我们运用枚举法得到每一种可能性运用lingo和Matlab分支定界法得到相应的

结果:总和1-1型1-2型迭代次数运行时间(s)lingo181538210matlab181531537774.1.3结果说明在满足所有条件下1-1型有4种方案:1-1型1-2型I型II型I型II型方案30500方案11300方案30024方案五114000共计18辆，分别是1-1型15辆，1-2型3辆。具体安排是3辆1-1型车上装I型0辆货运车，II型5辆货运车。方案二是1-1型车1辆上装I型0辆货运车，II型5辆货运车。方案三是1-2型车3辆上装I型2辆货运车，II型4辆货运车。方案五是1-1型车11辆上装I型4辆货运车，II型0辆货运车。4.2问题二的分析在给定II车型和III车型的基础上我们还是和第一问一样建立相应的解法，但是我们要对车的上下层做条件约束，因为题目中考虑到以保证货运车行驶平稳。受层高限制，高度超过1.7米的货运车只能装在1-1、1-2型下层，所以我们建立以下模型：4.2.1模型的建立：建立目标函数：TOC\o"1-5"\h\zS.tmin(£y+£z) (2)i i于是我们建立约束条件：1)1-1型货运车满足的约束条件：19-3.615<(4.61+0.1)xm+(3.615+0.1)xn<19,i=1,2,3,4,5,1i 1i方案I型车数量II型车数量

104213322431550-3.615<(4.61+0.1)xm+(3.615+0.1)xn<24.3,j=1,2,3,4,5,6,72i 1j2)在此约束条件下1-2型货运车还应该满足以下条件：方案I型车数量II型车数量1062153244325416503）同时满足以下约束条件：如my+5y)+£(my+12y)-72i=111 1 j=12jjj£nv+£n7—523e£12产j£z<0.2*£y.j=1' i=114.2.2模型的求解我们运用枚举法得到每一种可能性运用Matlab分支定界法得到相应的结果:总和1-1型1-2型运行时间（s）matlab131122.4914.2.3结果说明在满足所有条件下有4种方案:1-1型1-2型II型III型II型III型方案一10（上层5,下层0）（上层0，下层4）00方案1（上层5,下层1）（上层0，下层3）00方案100（上层12,下层0）（上层0，下层4）

方案五100(上层12,下层1)(上层0,下层3)方案五100(上层12,下层1)(上层0,下层3)方案二是1-1型车1辆上装II型上层5,下层1辆货运车，III型上层0，下层3辆货运车。方案三是1-2型车1辆上装II型上层12，下层0辆货运车，III型上层0，下层4辆货运车。方案五是1-2型车1辆上装II型上层12,下层1辆货运车，III型上层0，下层3辆货运车。4.3问题三的分析：在给定I车型和II车型、III车型的基础上我们还是和前两问一样建立相应的解法，但是我们要对车的上下层做条件约束，因为题目中考虑到以保证货运车行驶平稳。受层高限制，高度超过1.7米的货运车只能装在1-1、1-2型下层，所以我们建立以下模型：4.3.1模型的建立：建立目标函数：S.tmin(£x+£y) (3)ii于是我们建立约束条件：1)1-1型货运车满足的约束条件：k1i194.63k1i194.63+0.1TOC\o"1-5"\h\z19-3.615<(4.61+0.1)xm+(3.615+0.1)xn+(4.63+0.1)xk<19,i=0,1,2,3,4,5,

ii 1i 1i上层的情况满足：19-3.615<(4.61+0.1)xs+(3.615+0.1)x丑<191i 1i在只使用1-2型货运车时应当满足以下条件：下层的情况满足：24.3-3.615<(4.61+0.1)xm+(3.615+0.1)xn+(4.63+0.1)xk<24.32j 2j 2j其中24.3其中4.63+0.1上层的情况满足：-3.615<(4.61+0.1)xs+(3.615+0.1)x门<24.32i 2itmx+tEx+£mn+£En>156TOC\o"1-5"\h\z1(i 1ii 2ji 2ji上0 i=0 j=0' j=0-tnx+tnx+tnn+tnn>1021ii 1ii 2ji 2ji<'=° '=° j=°' j=°' (i=0,1,2,3,4;j=0,1,2,3,4,5)tkx+tn>39\o"CurrentDocument"1ii ii=0 j=0tn<：*txi5ilj=0 =i=04.3.2模型的求解由于该模型所包含的参数过多我们调用解整数规划的函数包：W进一步我们运用Matlab工具箱调用该函数进行计算得到如下结果。相类，同轿用车装载方I型车上I型车下II型车上II型车下III型车上III型车下类型 式的车层 层 层 层 层 层辆数I-I 2 0 0 5 0 0 4I-I 3 4 0 0 0 0 4I-I 1 0 0 5 5 0 0I-I 1 4 0 0 5 0 0I-I 1 0 1 5 0 0 3I-I 1 4 1 0 0 0 3I-I 1 0 2 5 0 0 2I-I 3 4 2 0 0 0 2I-I 1 0 3 5 0 0 1I-I 6 4 3 0 0 0 1I-I 1 0 4 5 0 0 0I-I 5 4 4 0 0 0 0I-II 3 2 1 4 4 0 4I-II 2 2 2 4 4 0 4我们运用枚举法得到每一种可能性运用Matlab分支定界法得到相应的结果:总和1-1型1-2型运行时间（s）matlab3126510.0210754.3.3结果说明在满足所有条件下有14种方案：共计31辆，分别是1-1型26辆，1-2型5辆。具体安排是2辆1-1型车上装II型上层5辆，下层0辆货运车，III型上层0，下层4辆货运车。3辆1-1型车上装I型上层4辆，下层0辆货运车，III型上层0，下层4辆货运车。1辆1-1型车上装II型上层5辆，下层5辆货运车.其余结果如上表。4.4问题四的模型建立及求解(普通算法)。在有路径的约束条件下我们分两步考虑该问题，首先考虑数量的优化再考虑路径的优化，在不考虑折返的情况下，我们分段考虑OD段，就一个单向图路径也是最优的，考虑量上的优化，即共计166辆I型和78辆II型的货运车，则该问题转化为第一问的问题，在相同的约束条件和目标函数下我们得到最优的方案。同时，在在OD段运输的总费用为1-1型货运车和1-2型货运车耗费的费用之和。即：Z=Z+Z ⑷总费用 1—1 1-2在D段全部装载到货运车上，在D点卸下41辆I型车，由于每次卸车成本几乎可以忽略，现在需要125辆I型车和78辆II型车。重新分配时同时满足条件:19-3.615<(4.61+0.1)xm+(3.615+0.1)xn<19C点需要33辆I型货运车，47辆II型货运车，因此我们再转化为第一问进一步求解得到较优的结果为1-1型货运车的分配方案：数量I型II型方案X0305方案X3131方案X43401-2型货运车的分配方案：数量I型II型方案y1115又因为在DA段需要92辆I和31辆II，所以再考虑运用第一问的思路得到如下结果：数量I型II型方案X2122方案X3231方案X48061-2型货运车的分配方案：数量I型II型方案y2224最终需要25辆1-1型和4辆1-2型才能完成最终的任*4.4.1结果解释因为考虑到DA段需要92辆I和31辆II,则需要1-1型车1辆装I型2辆，装II型2辆。方案三需要2辆1-1型来装3辆I型和1辆II型。方案四需要8辆1-1型货运车，其中装载I型0辆，II型6辆。需要1-2型货运车2辆装载I型2辆和II型4辆。4.4.2问题四的启发式算法（遗传算法） ：为彳IP1-m遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的求解有很强的鲁棒性，所以遗传算法在函数和组合优化、生产调度、自动控制、智能控制、机器学习、数据挖掘、图像处理以及人工生命等领域得到了成功而广泛的应用.在各个不同的应用领域，为了取得更好的结果。针对本题的要求我们对数量进行优化，最后再将好的数量分配方案继续逐步遗传，到最后全局最优，由于Matlab自身带有遗传算法的工具箱最后我们通过调优得到最后的优化结果。总和1-1型1-2型运行时间（s）matlab252142.4914.5问题五的模型建立和求解首先根据附表从宏观角度可以看出问题五的装载以及运输方案会很多，首先表中不同货运车型的种类非常多，如果仍然依照前几问中的解决方案对其进行最优化分析将会导致变量数目极为庞大，几乎无法用程序进行实现，这就需要对数据进行聚类整合，进而简化目标函数，减少变量的个数。按照高大于等于1.7m和小于1.7m进行划分，在此条件下我们再考虑宽度大于等于1.7m和小于1.7m进行划分，得到结果不是很理想，所以我们继续按照长度划分，最后分为10类。由于可以调用的货运车类型都给出，数量和装载区域都给出，我们考虑1-1型和1-2型货运车的装配方案，由于装配方案很多，我们对可能的几种方案根据调度经验我们去掉可能性较小的几种结果，建立相关的模型。4.5.1模型的建立流程图：对于数据表格1与表格2中的数据进行分类，以简化模型的设计，尽可能的提高其运行效率。文章中采用分类算法对所有的货运车进行分类。由题目已知得到：高度大于1.7米的货运车只能放在1-1、1-2的下层。而宽度方面的也存在限制，1-1类型货运车可以装载任意类型的货运车，而1-2型货运车上层和2-2型货运车上下层在装载宽度超过1.7米的货运车时，会受到宽度的限制。对于长度，对于装载优化也有一定的影响，但是不如前两者对装载优化的影响大。鉴于此，我们采用高度作为一级分类标准，宽度作为二级分类标准，长度作为三级分类标准。流程图如下所示：注：单位mm

分类器的编码以及设计。运行界面如下所示:□洽走葬 '广 卜＜=-|-日-Im&bI«T抿谣取 n^F分关 Test车型常号主机厂名称品牌车理长度【瑚）ffiJSCjnn]砌-►1此*弭驰-戴克it^JEEP大切i若H1B2E皆£北京奔驰-顺克北京弃丈-戴壳5^StWJi300C501516003北点现代北南现代昨辑树<13101B9EL<10J=4北京顼代北京现代素轲®4T471B2DL44a|I5比亚辿比H迪F034001510L4Bo||&比亚谑比丑迪FQ■4船口1TQOmosr"7昌河佑木吕::菲咨木利亚泗423。1690L550B长安难粉■^点马自达马自送W劲可VMTQ1B85L<im■3长宾!H4fr长安福恃福无所三厢44301040L500!□长去铐木天理玷■41王17EELECE11长安土主长击志翔460。1600H7s|1E长城汽圭长tsi喜誉fler*1T04L84S13左风本田木间本田4BZICI1.TE5L49314主凤臼产布网曰产44Z。1590L39D15击凤曰产车:回曰户天赣49301T9EETS16车风悦诂起亚卓回悦诂起U穿g435。1735L4701T年囱粉igi'4*l-t电FWi1朋巳T分类结果如下:弟——买= L-1卞1-zT^白勺千里海口■=点用车作成<430aSfeFB军-fens^301□-<iaOQ112N。g用车长展>40005«—=ts^=1-1K1-z~r曰勺牛担nw=：俱FH至太康<300乘用*天建^=OC-xH3Da|SfiiFB车长J*>4S£iCiWE=X1X= t-1上V 1-2T?2-2上下自勺辛a*■曰H=乘j=s羊长nte<43oo形用牟*JSE-4300-^000<4O,911LOLOZ1ZZWNDO3-135530<1Z<15煦用辛*后XdodE15IBMDCO-41-K5玲美格四关=l-l上『l-=上『 =-=上干白勺牛型油号”=SfeFH车长rtfi<430ClSTS20272QMOiSQ-40vmenu_旦曰口口年由:^:乍旧Xmoc*这里我们根据上述对货运车数据的分析，并进行分类，从而得到10类主要的货运车型，由于不同类型货运车的长度变化较大，因此货运车不再进行分类，这里解决的主体思想仍然是根据货运车的长度，宽度给出对应约束条件，建立整数线性规划，然而这里要注意的是此问中即便已经对货运车进行了较好的分类方式，较大程度上减少了变量的个数，然而普通的求解整数线性规划的算法也并不容易实现。类似问题一中我们可以用枚举法加上循环中的一些限制条件可以得到问题的最优解，而运用分支定界的算法则更为容易算出结果；问题二通过分析需要对货运车上下层分配不同数量不同车型的货运车，变量数目会有所增加，此时枚举法不再适用；问题三中则是前两问的综合情况，一般求解线性规划的算法都会遇到耗时长，结果难以实现等问题。因此这一问中为了能够实现问题较好的解，可以从数据的归类分析，优化算法，或者增添更为有效，合理地约束条件以及从问题上进行一些假设估计，便于简化问题。这里我们主要是对货运车数据进行合理地分类，然后对问题中的分层进行假设，简化模型，即简化了目标函数；然后在程序中通过空间利用率的判断再次对各个方案进行筛选，这样做不仅从某个角度分析简化了该线性规划模型，而且也较好地避免那些接近最优解的方案被遗漏的问题。考虑到变量多的难题，我们运用matlab工具箱：yalmip解决多变量的整数线性规划，而变量个数的控制则结合之前的分类以及循环过程中一些条件限制；在该问题中通过对某些类型的车不考虑过于细致地上下层方案分析，而是视为一致，以减少变量(方案)的个数，然后确定变量个数进行最优化分析，最后我们根据题经验性以及成本上对上述得到的结果略微调整。考虑只是用1-1型下层，满足不等式：(3.675b0.1)xm+(4.196b0.1)xn+(4.427f0.1)kp+(4.579b0.1)xk+(4.753b0.1)xWTOC\o"1-5"\h\z1i 1i 1i 1i 1iH4.987b0.1Nv+(6.83+0.1)xf-0.1<20.541i 1i考虑只使用1-2型下层，满足不等式：(3.67+0.1)<m+(4.19+0.1)<n+(4.42+0.1)<p+(4.57+0.1)<k+(4.75+0.1)<w2j 2j 2j 2j 2j+(4.98+0.1*+(6.83+0.1)<f-0.1<23.52j 2j考虑只使用2-2型下层，满足不等式：(3.67+0.1Xm+(4.19+0.1Xn+(4.4230.1><p+(4.57+0.1Xk+(4.75+0.1)<w3/ 3/ 3/ 3/ 3/+(4.98异0.1州+(6.83+0.1Xf-0.1<20.543/ 3/对于1-1型货运车，其上下层规格相同，故其上层与下层具有相同的性质。对于1-2型货运车上层，满足不等式：10 44 30(3.675+0.1)xm+—(4.196+0.1)xn+—(4.427+0.1)xp+ (4.579+0.1)xk2j17 2j 73 2j59 2j3+栏(4.987+0.1)xv-0.1<23.537 2j对于2-2型货运车上层，满足不等式:

5361(3.67^0.15361(3.67^0.1>m+(4.19备0.1*n+(4.42¥0.1*p+—(4.57乎0.1*k+(4.75$0.1)<wC' C' C'S c，" 3/3/593/6927+_(4.98+0.1*v+(6.83+0.1Xf—0.K19TOC\o"1-5"\h\z37 3/ 3/E2mx+E3my+£4mz>181ii 2ji 3/iE2nx+E3ny+E四ny+E4pz>341ii 2ji172ji 3/i44E2px+Epy+Epy+E4pz>731ii 2ji732ji 3/i_ _ -30 _ -53E2kx+Eky+Eky+E2kz+E2—kz>591ii 2ji592ji 3/i5931iE2wx+Ewy+E2wz+E2—wz>691ii 2ji 3/i6931i27E2vx+Evy+E2vz+E2一vz>371ii 2ji 3/i3731iE2fx+Efy+E4fz>21ii 2ji 3/i我们建立目标函数为： R=Emin{x+y+z} (5)iii4.5.2模型的求解在分类器根据高度和宽度的条件约束得到如下的分类结果Sn—1-1 K的幸丑啊号右;~用圭:甘UVvodcj奉用车任.fg4300—ISOO1_12£52S5^用牟长ISXmODEQ第二沮：1-1T1-2T臼勺至型沮与百=旅用车乍点＜000未用车长.废Hg—g口口|欢所车长域xsoo1T食三主：1-1上卞