2014年研究生数学建模E题三等奖

-1-参赛密码（由组委会填写）第十一届华为杯全国研究生数学建模竞赛学校云南农业大学参赛队号10676001队员姓名1.王良泽南2.冯宵3.王淑文-2-参赛密码（由组委会填写）第十一届华为杯全国研究生数学建模竞赛题目乘用车物流运输计划问题研究摘要：本文建立最优化模型，用于解决乘用车物流运输计划问题。用线性加权法求解多目标优化模型，用两阶段启发式算法将复杂实际问题简化为最优化问题。我们分两步优化：先优化最优装载方案，再优化最优运输路线，最终实现成本最优。结果表明：能够较好的为实际问题提供解决方案。对于问题一、二、三：我们对1-1型和1-2型轿运车分别给出一种装载方案，结合实际情况：1.轿运车尽量装满2.不超出轿运车容量，3.使轿运车数量最少，要考虑4个因素，考虑因素1：1-2型轿运车运输的平稳，上层的乘用车应对称摆放；因素2：1-2型轿运车数量不超过1-2型轿运车数量的20%；因素3：每辆轿运车可以装载乘用车的最大数量在6到27辆之间；因素4：所求的为各种类型的车辆数应为0或正整数。最终得出模型一：装载方案的优化模型，并计算得出结果，符合实际情况。对于问题四：在问题一、二、三的基础上，可以得出最优装载方案，得到装载方案，所需解决的是轿运车行驶路线的问题，首先可以很容易的从路线图中找出O点到A、B、C、D的最短路线，要求所有轿运车都走最短路线，用轿运车经过各点次数来确定总路线，要使总路线最短需要考虑3个因素，考虑因素1：轿运车可能会途径某地但是不卸货；因素2：D点是必经之路来限制通过后次数；因素3：根据实际路线图确定通过次数范围；因素4：所求的通过次数应为0或正整数。最终得出模型二：运输路线的优化模型，并计算得出结果，并根据计算结果得出总路程最短的运输路线，符合实际要求。对于问题五：要解决复杂的实际问题，考虑实际限制因素太多，无法得出-3-最优化模型，采用两阶段启发式算法，将实际情况的多个限制因素缩减为可以优化的几个因素，把较多乘用车和轿运车类型，重新分类，分成乘用车5大类，轿运车3大类，在问题一、二、三、四的基础上，根据实际情况以模型一的思想为基础，加入限制轿运车使用数量的约束条件建立模型三，以模型二的思想建立模型四，最终得出计算结果和运输路线，尽可能的达到了实际需求的最优效果。关键词：最优化模型线性加权法启发式算法运输-4-1.问题重述整车物流指的是按照客户订单对整车快速配送的全过程。随着我国汽车工业的高速发展，整车物流量，特别是乘用车的整车物流量迅速增长。乘用车生产厂家根据全国客户的购车订单，向物流公司下达运输乘用车到全国各地的任务，物流公司则根据下达的任务制定运输计划并配送这批乘用车。为此，物流公司首先要从他们当时可以调用的“轿运车”中选择出若干辆轿运车，进而给出其中每一辆轿运车上乘用车的装载方案和目的地，以保证运输任务的完成。“轿运车”是通过公路来运输乘用车整车的专用运输车，根据型号的不同有单层和双层两种类型，由于单层轿运车实际中很少使用,本题仅考虑双层轿运车。双层轿运车又分为三种子型：上下层各装载1列乘用车，故记为1-1型；下、上层分别装载1、2列，记为1-2型；上、下层各装载2列，记为2-2型，每辆轿运车可以装载乘用车的最大数量在6到27辆之间。在确保完成运输任务的前提下，物流公司追求降低运输成本。但由于轿运车、乘用车有多种规格等原因，当前很多物流公司在制定运输计划时主要依赖调度人员的经验，在面对复杂的运输任务时，往往效率低下，而且运输成本不尽理想。装载具体要求每种轿运车上、下层装载区域均可等价看成长方形，各列乘用车均纵向摆放，相邻乘用车之间纵向及横向的安全车距均至少为0.1米，下层力争装满，上层两列力求对称，以保证轿运车行驶平稳。受层高限制，高度超过1.7米的乘用车只能装在1-1、1-2型下层。轿运车、乘用车规格如下：表1乘用车规格乘用车型号长度(米)宽度(米)高度(米)Ⅰ4.611.71.51Ⅱ3.6151.6051.394Ⅲ4.631.7851.77表2轿运车规格轿运车类型上下层长度(米)上层宽度(米)下层宽度(米)1-1192.72.71-224.33.52.7整车物流的运输成本计算较为繁杂,这里简化为：影响成本高低的首先是轿运车使用数量；其次，在轿运车使用数量相同情况下，1-1型轿运车的使用成本较低，2-2型较高，1-2型略低于前两者的平均值，但物流公司1-2型轿运车拥有量小，为方便后续任务安排，每次1-2型轿运车使用量不超过1-1型轿运车使用量的20%；再次，在轿运车使用数量及型号均相同情况下，行驶里程短的成本低，注意因为该物流公司是全国性公司，在各地均会有整车物流业务，所以轿运车到达目的地后原地待命，无须放空返回。最后每次卸车成本几乎可以忽略。需要解决的问题为物流公司安排以下五次运输，制定详细计划，含所需要各种类型轿运车的数量、每辆轿运车的乘用车装载方案、行车路线。1.物流公司要运输Ⅰ车型的乘用车100辆及Ⅱ车型的乘用车68辆。-5-2.物流公司要运输Ⅱ车型的乘用车72辆及Ⅲ车型的乘用车52辆。3.物流公司要运输Ⅰ车型的乘用车156辆、Ⅱ车型的乘用车102辆及Ⅲ车型的乘用车39辆。4.物流公司要运输166辆Ⅰ车型的乘用车（其中目的地是A、B、C、D的分别为42、50、33、41辆）和78辆Ⅱ车型的乘用车（其中目的地是A、C的，分别为31、47辆），具体路线见图4，各段长度：OD=160，DC=76，DA=200，DB=120，BE=104，AE=60。5.附件的表1给出了物流公司需要运输的乘用车类型（含序号)、尺寸大小、数量和目的地，附件的表2给出可以调用的轿运车类型（含序号)、数量和装载区域大小（表里数据是下层装载区域的长和宽,1-1型及2-2型轿运车上、下层装载区域相同；1-2型轿运车上、下层装载区域长度相同，但上层比下层宽0.8米。此外2-2型轿运车因为层高较低，上、下层均不能装载高度超过1.7米的乘用车。2.问题假设假设1：每种轿运车按同一种方案装载。假设2：问题一、二、三、四所需的轿运车的数量足够。假设4：轿运车行驶只走最短路线，不走往返路线。假设4：问题五中轿运车及乘用车分类后每一类当成一种车型计算。假设5：每一类乘用车车型长度为该车型长度的加权平均数。3.符号说明符号符号说明1-1型轿运车上层Ⅰ车型乘用车的数量1-1型轿运车上层Ⅱ车型乘用车的数量1-1型轿运车下层Ⅰ车型乘用车的数量1-1型轿运车下层Ⅱ车型乘用车的数量1-1型轿运车下层Ⅲ车型乘用车的数量1-2型轿运车上层Ⅰ车型乘用车的数量（单列）1-2型轿运车上层Ⅱ车型乘用车的数量（单列）1-2型轿运车下层Ⅰ车型乘用车的数量1-2型轿运车下层Ⅱ车型乘用车的数量1-2型轿运车下层Ⅲ车型乘用车的数量𝑙Ⅰ车型乘用车的长度加0.1m安全车距𝑙Ⅱ车型乘用车的长度加0.1m安全车距𝑙Ⅲ车型乘用车的长度加0.1m安全车距𝐿1-1型轿运车的长度𝐿1-2型轿运车的长度𝑛Ⅰ车型乘用车的数量𝑛Ⅱ车型乘用车的数量𝑛Ⅲ车型乘用车的数量𝑁1-1型轿运车数量𝑁1-2型轿运车数量-6-𝑛1-1型轿运车经过A点的次数𝑛1-2型轿运车经过A点的次数𝑛1-1型轿运车经过B点的次数𝑛1-2型轿运车经过B点的次数𝑛1-1型轿运车经过C点的次数𝑛1-2型轿运车经过C点的次数𝑛1-1型轿运车经过D点的次数𝑛1-2型轿运车经过D点的次数𝑁需送达A地的Ⅰ车型乘用车数量𝑁需送达A地的Ⅱ车型乘用车数量𝑁需送达B地的Ⅰ车型乘用车数量𝑁需送达C地的Ⅰ车型乘用车数量𝑁需送达C地的Ⅱ车型乘用车数量𝑁需送达D地的Ⅰ车型乘用车数量𝑎1-1型轿运车装载Ⅰ车型乘用车的数量𝑏1-1型轿运车装载Ⅱ车型乘用车的数量𝑐1-2型轿运车装载Ⅰ车型乘用车的数量𝑑1-2型轿运车装载Ⅱ车型乘用车的数量4.问题分析随着汽车行业的飞速发展，与之密切相关的车务运输企业也获得了前所未有的机遇,同时也面临着巨大的成本压力和时刻变化的市场环境的挑战。乘用车物流作为汽车行业中新兴的产业，作为连接生产、销售以及消费者的重要环节。虽然已经得到了很大的发展，但受轿运车、乘用车不同规格，运输计划以及人员调度方案的限制，当前很多物流公司在面对复杂的运输任务时，往往效率低下，运输成本偏高。因此，在乘用车物流受到了汽车生产商前所未有的重视的前提下，不断提高乘用车物流企业的服务质量，降低运输成本，优化运输方案，必将成为当今发展形势下的必然要求。本研究的目的在于寻求企业在实际决策中的解决方法，着眼于降低企业运输总成本，用于解决乘用车物流运输计划问题，为企业在物流决策中提供一个完整最优的流程。此题研究的是车辆运输及配送的数学建模问题，如何能够既节约成本，又能够合理配送是这次建模的关键。我们需要建立最优化模型来找到最理想的运输方法。针对问题一：物流公司要运输Ⅰ车型的乘用车100辆及Ⅱ车型的乘用车68辆，由本题可知，轿运车有1-1（上下层各装载1列乘用车型）和1-2型(下、上层分别装载1、2列乘用车型)，每次1-2型轿运车使用量不超过1-1型轿运车使用量的20%，并且由于受层高限制，高度超过1.7m的乘用车只能装在1-1、1-2型下层。且根据本题提供的轿运车、乘用车规格资料可知，Ⅲ型乘用车的高度1.77m大于1.7m，则Ⅲ型乘用车只能放在轿运车1-1、1-2的下层，于是得出所有轿运车的上层只能放Ⅰ型或Ⅱ型乘用车，下层可放Ⅰ型、Ⅱ型或Ⅲ型乘用车。同时我们既需要将所要运输的乘用车全部运走，又要使得每辆轿运车都载满且轿运车总量最少，进而使得物流公司将规定的运输车辆达到最优分配，从而使运输成本最低。由此建立满足以上约束条件的数学模型，计算得到在已-7-知条件下的最优解。针对问题二：物流公司要运输Ⅱ车型的乘用车72辆及Ⅲ车型的乘用车52辆。由于该题异于第一题主要不同之处在于选择了Ⅲ车型的乘用车，没有Ⅰ车型的乘用车，基于本题要求前三问需要制定统一的程序，则其分析方法与问题一的解决方法相同。则在此不需在赘述。针对问题三：物流公司要运输Ⅰ车型的乘用车156辆、Ⅱ车型的乘用车102辆及Ⅲ车型的乘用车39辆。由于该题异于第一、二题主要不同之处在于选择了Ⅰ、Ⅱ、Ⅲ车型的乘用车，基于本题要求前三问需要制定统一的程序，则其分析方法与问题一、二的解决方法相同。则在此不需在赘述。针对问题四：前三问已经解决如何装载车辆的问题，对本问题则需利用前三问得出的程序，求出第四问的最优装载方案，然后根据所得到的最优装载方案，再去选择行车的最优路线。而本题强调在轿运车使用数量及型号均与前三问相同的情况下，行驶里程短从而成本低，而物流公司所需运输乘用车的数量及抵达的地方已经确定，则需找到合理的行车路线，使其总共车辆的总体行程最短，这样才能使得运输成本最低。由此我们需要构建满足上述条件的数学模型，利用LINGO软件求得满足条件的最优解。针对问题五：物流公司所运乘车资料如附件表1、2所示，根据前四问求解经验，我们仍需先解决如何确定车辆的最优装载方案，然后根据所得到的最优装载方案，再去选择行车的最优路线，从而使得物流公司的总成本最低。但本题所给乘用车及轿运车的型号复杂，车辆居多，不利于对本题进行合理求解，则需要我们将其进行归类统计进而使其简化。在统计归类完的车型确定以后，我们接下来需要制定最优的装载方案。而对于本题，我们需要采用两阶段启发式算法对其进行求解求优。首先启发式算法的第一阶段是如何确定行车的装载方案，找出相应装载方案的约束条件，然后根据题目要求列出装载方案的目标函数，最后制定满足该约束条件下的数学模型，利用LINGO软件求得满足条件的最优解。其次启发式算法的第二阶段是如何将已经装载好的车以最短路径运送到所到达目的地，并找出相应行车路线的约束条件，然后根据题目要求列出行车路线的目标函数，最后制定满足该约束条件下的数学模型，利用LINGO软件求得满足条件的最优解。5.问题一、二、三的解答本文研究的是从当时可以调用的“轿运车”中选择出若干辆轿运车，进而给出其中每一辆轿运车上乘用车的装载方案，以保证运输任务的完成。利用线性加权法，简化多目标函