乘用车物流运输计划

1第第十十一一届届华华为为杯杯全全国国研研究究生生数数学学建建模模竞竞赛赛题目乘用车物流运输计划问题摘要：本文针对如何制定总成本最低的装载运输方案，建立了3个模型分别解决在不同运输需求情况下，轿运车的装载运输方案。对于问题1、2和3，本文采用分步最优方法，第一步将轿运车分层讨论，建立单层轿运车最优装载的线性规划模型，求出每一类轿运车在不同乘用车装载组合方式中，使轿运车使用率最大的I型、II型和III型乘用车数量；第二步根据前一个模型求得的数据，建立最优装载方案模型，使得轿运车的总数量最少。利用MATLAB软件编程求解出3个问题所需轿运车的数量和每辆轿运车的详细装载方案。第1问需要16辆1-1型轿运车和2辆1-2型轿运车；第2问需要12辆1-1型轿运车和1辆1-2型轿运车；第3问需要25辆1-1型轿运车和5辆1-2型轿运车。对于问题4，本文采用了两种方法求解。一种是人工调整运输方法，一种建模求解法。人工调整方法有两种方案，方案一是根据每个目的地需要的乘用车数量，利用最优装载方案模型求得单独对每点运输的轿运车数量，然后按照各点对乘用车的需求量调整轿运车的行驶路径和配送目的地，计算得到需要23辆1-1型轿运车和3辆1-2型轿运车。方案二是将全部目的地对I型和II型乘用车需求量当成一个整体，先对整体需求利用最佳装载模型求出装载这些乘用车的轿运车数量分别为21辆1-1型和4辆1-2型，然后再根据各目的地的需求安排配送。建模求解法分为两步，第一步利用最优装载方案模型得到使用轿运车总数最少的装载方案：需要21辆1-1型和4辆1-2型轿运车。第二步在轿运车使用数量最少前提下，利用最优运输路径模型，采用遗传算法对25辆轿运车进行路径规划，保证所有轿运车行驶的总路程最短。对于问题5，本文首先将其转化为三维装箱问题建立最优装载方案模型，采用遗传算法求出最优解，使轿运车使用数量最少，结果为126辆轿运车。利用问题4中建立的最优运输路径模型规划所有轿运车的行驶路径。关键词：最优装载方案模型；最优运输路径模型；遗传算法；三维装箱21问题重述整车物流指的是按照客户订单对整车快速配送的全过程。根据用户订单的要求，物流公司制定运输计划并配送乘用车。先选出可调用的轿运车，然后再给出其中每一辆轿运车中乘用车的装载方法和目的地。根据型号的不同，本题中轿运车有三种车型：上下层各装载1列乘用车，记为1-1型；下、上层分别装载1、2列，记为1-2型；上、下层各装载2列，记为2-2型，每辆轿运车可以装载乘用车的最大数量在6到27辆之间。影响成本高低的首先是轿运车使用数量；其次，在轿运车使用数量相同情况下，1-1型轿运车的使用成本较低，2-2型较高，1-2型略低于前两者的平均值，但物流公司1-2型轿运车拥有量小，为方便后续任务安排，每次1-2型轿运车使用量不超过1-1型轿运车使用量的20%；再次，在轿运车使用数量及型号均相同情况下，行驶里程短的成本低。轿运车到达目的地后原地待命，无须放空返回。最后每次卸车成本几乎可以忽略。每种轿运车上、下层装载区域均可等价看成长方形，各列乘用车均纵向摆放，相邻乘用车之间纵向及横向的安全车距均至少为0.1米，下层力争装满，上层两列力求对称，以保证轿运车行驶平稳。受层高限制，高度超过1.7米的乘用车只能装在1-1、1-2型下层。轿运车、乘用车规格（第五问见附件）如表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）物流公司要运输Ⅰ车型的乘用车100辆及Ⅱ车型的乘用车68辆。（2）物流公司要运输Ⅱ车型的乘用车72辆及Ⅲ车型的乘用车52辆。（3）物流公司要运输Ⅰ车型的乘用车156辆、Ⅱ车型的乘用车102辆及Ⅲ车型的乘用车39辆。（4）物流公司要运输166辆Ⅰ车型的乘用车（其中目的地是A、B、C、D的分别为42、50、33、41辆）和78辆Ⅱ车型的乘用车（其中目的地是A、C的，分别为31、47辆），具体路线如图1所示，各段长度：OD=160，DC=76，DA=200，DB=120，BE=104，AE=60。3图1路线图（5）附件的表1给出了物流公司需要运输的乘用车类型（含序号)、尺寸大小、数量和目的地，附件的表2给出可以调用的轿运车类型（含序号)、数量和装载区域大小（表里数据是下层装载区域的长和宽,1-1型及2-2型轿运车上、下层装载区域相同；1-2型轿运车上、下层装载区域长度相同，但上层比下层宽0.8米。此外2-2型轿运车因为层高较低，上、下层均不能装载高度超过1.7米的乘用车。2问题分析对于问题1、2、3，由于运输过程中的目的地只有一个，故可以暂时不讨论行车路线对运输方案的影响，只需在乘用车数量被限定的情况下，找出使轿运车车使用率最大的车辆分配方案。首先考虑到轿运车具有两层结构，而高于1.7m的乘用车只能装载在轿运车的下层，故而1-1型和1-2型轿运车的上层只能装载I型和II型乘用车，因此在混合装载时轿运车上层和下层的混合方式不完全相同，必须将轿运车进行分层研究，分别找到每一层中使轿运车的使用率达到最大的最优组合方式。其次，确定了对轿运车进行分层寻优的方案后，在宽度和高度的限制达到要求的情况下，可以将这一层中所有乘用车总长度最大作为目标问题的判断标准。可以使用线性规划的方法单独对每一层中的不同乘用车组成形式做线性计算，由此可以得到一个关于每种组合的每一种轿运车的每一层中分别含有的I、II、III型乘用车的数量表格。最后，根据该数量表格中对每一层不同组合下的I、II、III型乘用车的数量，以及问题1、2、3对于车型和数量的不同要求作为约束条件，建立线性规划模型，求解出满足题目运输要求的1-1型和1-2型轿运车的数量。对于问题4，由于运输过程中的目的地变成了4个，则行车路线对成本的影响较大。如果按照人的经验分配和从可行结果的多样性角度进行装载方案的分配，可以得到不同的解。所以可以先考虑按每个目的地对乘用车的需求去分配装载轿运车，也可根据先用最少的轿运车转载全部运输需求的乘用车，然后进行人工调整。只需要考虑运输I型和II型两种乘用车，就不需要因为考虑到III型乘用车只能放在轿运车下层而将轿运车上下两层分开求出最优组合分配后在对各层组合。如果仍按照模型I中对轿运车每一层分别求组合比，再对上、下层不同装载方式进行组合，这样每一辆轿运车中能够装载的I型和II型轿运车的装载比就有很多种可能。为了减少这种多组合的可能，将模型I中原本按照上、下层组合分配的方式改为根据整车装载最优重新进行分配。再根据得到的最优装载方案建立一个以行驶总路程最短的模型，可按照从整体需求求解最优运输方案，此时EBACDO4就可以利用遗传算法对行驶的最短路径求解。对于问题5，要求根据附件表1和附件表2中提供的有限的10种轿运车对5个目的地配送45种乘用车。每个目的地对各种乘用车的需求量不同。由于附件表中提供的车型数量较多，如果依照前面的模型建立方法对最少轿运车使用数量进行研究，一方面系数矩阵很大，另一方面这种系数矩阵需要手动整理，这样不利于编程和结果的输出。于是可建立一个新的三维装箱模型对最少轿运车数量求解，最终利用问题4的模型和遗传算法对最优运输方案进行优化求解。3模型假设1、假设在有两列的1-2型和2-2型轿运车中，装载乘用车时左右两列是对称的；2、假设在轿运车装载乘用车时，不考虑乘用车与轿用车车壁间的距离；3、假设1-1型轿用车的运输成本为1。4符号说明符号说明in在轿用车单列第i种乘用车的数量il第i种乘用车的长度F乘用车的总长度jL第j种轿运车的长度(1,2)jX1-1型轿运车总数Y1-2型轿运车总数ijx在第i层中的第j种组合的1-1型轿运车数量(1,2;1,2,,7)ijijy在第i层中的第j种组合的1-2型轿运车数量(1,2;1,2,,7)ijk2-2型的运行成本nA1-1型轿运车装载第(1,2,3)nn型乘用车总数量的系数矩阵ia第(1,2,,10)ii种组合的1-1型轿运车系数nB1-2型轿运车所装载的n型乘用车总数的系数矩阵ib第(1,2,,10)ii种组合的1-2型轿运车系数ix以第i种组合方式装载的1-1型轿运车层数(1,2,,10)iiy以第i种组合方式装载的1-2型轿运车层数(1,2,,10)inC第(1,2,3)nn种乘用车的需求量矩阵S所有轿运车行驶的总路程5问题1、2、3的模型建立与求解5.1最优装载方案模型的建立通过对轿运车中装载乘用车的高度和宽度的限制可以知道，各车型的宽度在组合中只有I型和III型的不能并列放置，而又有层高高于1.7m的乘用车只能放5在轿运车的下层的要求，那么III型车只能放在下层，所以不用考虑轿运车的宽度和高度对乘用车组合的限制。因为III型乘用车只能放在1-1型和1-2型的下层，又因为1-2型轿运车的上层有两列，为了让每一层中的每一列都能达到最大的使用率，可以把每一种轿运车分为上下两层，每一层中的乘用车就有不同的组合形式，组合方案如表3所示。表3乘用车各层组合方案1-1下层I型II型III型I型和II型I型和III型II型和III型I型、II型和III型1-1上层I型II型\I型和II型\\\1-2下层I型II型III型I型和II型I型和III型II型和III型I型、II型和III型1-2上层I型II型\I型和II型\\\由此便得到每一层的组合形式分别为：1-1型下层7种，1-1型上层3种；1-2型下层7种，1-2型下层3种。假设要使得轿运车的使用率达到最大（即装载的车辆最多），就要使得乘用车中上下两层每一列的总长度达到最大。因此只要分别得出每一层里面每一种组合方式中使轿运车的使用率达到最大的车辆数，就可以使得每一种乘用车组合在每一种轿运车的一层中达到最大使用率。5.1.1各乘用车组合在轿运车单层中的最优装载方案由于要求1-2型轿运车的上层两列力求对称，以保证轿运车行驶平稳，那么只需要考虑单列的最优数量即可。于是首先建立一个线性规划模型，求出在每一层的单列中，每种组合情况下个型号乘用车的数量。因为在每一层中有不同的组合模式，故可设置一个0-1函数，即：1,1,2,3iiii在该组合中有第型乘用车；0，在该组合中没有第型乘用车；又假设各组合中第i种乘用车的数量为(1,2,3)ini，第i种乘用车的长度为il，则在一列的组合中，乘用车的总长度F为31iiiiFnl显然只要使每一种组合中单列乘用车的总长度达到最大即可，于是可得目标函数为31maxiiiiFnl而每一种轿运车的长度有限制，且每两辆乘用车间至少间隔0.1m，则在轿运车的一列中就有约束条件33110(1)0.1iiiiijiinlnL其中(1,2)jLj表示第j种轿运车的长度。根据实际情况组合的不同，可知在各组合中每一种乘用车的数量in为不为0的正整数。于是得到在不同组合形态下，每一辆轿运车单层单列的最多能放置组合乘用车数量的线性规划模型6313311max0(1)0.1..0,iiiiiiiiijiiiiFnlnlnLstnn（1）由表1和表2可知各型号乘用车和轿运车的长度il和jL。根据组合模型中各种乘用车的数量，利用LINGO软件求解出使轿运车的利用率最大时各列组合中乘用车的数量。但是1-2型轿运车上层是对称的，故1-2型轿运车上层各乘用车数量应为其结果的两倍。最后每一层中各组合情况下使轿运车达到最大利用率的乘用车数量结果如表4所示。表4单层每种组合达到最大利用率的乘用车数量组合形式I型（1）II型（2）III型（3）I型和II型（4）I型和III型（5）II型和III型（6）I型、II型和II