搜索
2014数学建模课程大作业题目：物流装载优化问题组别：队员1队员2队员3姓名学号学院专业电话Email西南交通大学1乘用车物流装载优化模型【摘要】本文对乘用车物流计划问题进行建模，结合枚举法、约束解除、动态寻优的方法对题目所给的三个装载问题进行求解。我们记用1-1型货运车每层装运的I型乘用轿车的数量为a1，用1-2型货运车每层装运的I型乘用车的数量为a2；用1-1型货运车每层装运的II型乘用车的数量为b1，用1-2型货运车每层装运的II型乘用车的数量为b2；用1-1型货运车每层装运的III型乘用车的数量为c1，用1-2型货运车每层装运的III型乘用车的数量为c2。对于问题一，只需要考虑I型车和II型车，来寻找最优装载方案；对于问题二，是对问题一的扩展，我们需要考虑到由于III型车的高度问题，它只能装在1-1和1-2型货运车的下层；对于问题三，这是问题一和问题二的结合，所以结合前两问的寻找最优解的方法和得到的结论来寻找问题三的最优装载方案。本文详细介绍了寻找装载方案最优解的方法；以及对于所给的问题一、二、三，使用所给方法得到的最优装载方案的过程和结果。关键词：物流最优化动态规划整数规划西南交通大学2§1问题的重述一、问题背景众所周知，我国已经成为了世界第二大经济体，国民生活水平和人均GDP也在大幅提高。家用轿车已经日渐成为国人出行代步的重要工具，国内汽车消费增长趋势明显,乘用车市场需求旺盛。1、整车物流的概述整车物流是指按照客户订单对整车快速配送的全过程。随着我国汽车工业的高速发展，整车物流量，特别是乘用车的整车物流量迅速增长。乘用轿车生产厂家根据全国客户的购车订单，向物流公司下达运输乘用车到全国各地的任务，物流公司则根据下达的任务制定运输计划并配送这批乘用车。为此，物流公司首先要从他们当时可以调用的“货运车”中选择出若干辆货运车，进而给出其中每一辆货运车上乘用轿车的装载方案和目的地，以保证运输任务的完成。“货运车”是通过公路来运输乘用车轿车的专用运输车，物流公司选用的货运车都是双层货运车。双层货运车又分为两种类型：下、上层各装载1列乘用轿车，记为1-1型（图1）；下、上层分别装载1、2列，记为1-2型（图2）。2、本题整车物流的运输成本计算的简化介绍影响成本高低的首先是货运车使用数量；其次，在货运车使用数量相同情况下，1-1型货运车的使用成本较低，1-2型要略高于前者，但物流公司1-2型货运车拥有量小，为方便后续任务安排，每次1-2型货运车使用量不超过1-1型货运车使用量的20%；再次，在货运车使用数量及型号均相同情况下，行驶里程短的成本低，本题中，目的地只有一个故不考虑里程因素，每次装卸车成本也可以忽略。二、具体实验数据每种货运车上、下层装载区域均可等价看成长方形，各列乘用轿车均纵向摆放，相邻乘用轿车之间纵向及横向的安全车距均至少为0.1米，下层力争装满，上层两列力求对称，以保证货运车行驶平稳。受层高限制，高度超过1.7米的乘用车只能装在1-1、1-2型下层。货运车、乘用轿车规格如下：乘用车型号长度(米)宽度(米)高度(米)Ⅰ4.611.71.51Ⅱ3.6151.6051.394Ⅲ4.631.7851.77表1乘用轿车规格货运车的类型上下层长度(米)上层宽度(米)下层宽度(米)1-1192.72.71-224.33.52.7表2货运车规格西南交通大学3三、要解决的问题假设每次的运输目的地只有一个，在确保完成运输任务的前提下，物流公司追求降低运输成本。但由于货运车、乘用轿车有多种规格等原因，当前很多物流公司在制定运输计划时主要依赖调度人员的经验，在面对复杂的运输任务时，往往效率低下，而且运输成本不尽理想。现物流公司有以下三次运输任务，分别为物流公司制定详细计划（含所需要两种类型货运车的数量、每辆货运车的乘用轿车最优装载方案）1．物流公司要运输I车型的乘用轿车100辆及II车型的乘用轿车68辆。2．物流公司要运输II车型的乘用轿车72辆及III车型的乘用轿车52辆。3．物流公司要运输I车型的乘用轿车156辆、II车型的乘用轿车102辆及Ⅲ车型的乘用轿车39辆。图11-1型货运车图21-2型货运车§2问题的分析本题要求我们优化轿运车的数量和选择型号，用尽可能少的车，最低的成本来解决乘用车的装配问题。2.1相关知识介绍货运车：是通过公路来运输乘用车整车的专用运输车，根据型号的不同有单层和双层两种类型，由于单货运车在实际中很少使用，本题仅考虑双层货运车。双层货运车又分为三种子型：上、下层各装载1列乘用车，故记为1-1型；下、上层分别装载1、2列，记为1-2型；每辆货运车可以装载乘用车的最大数量在6到27辆之间。整数规划：在线性规划问题中，有些最优解可能是分数或小数，但是由于对于某些具体问题，常有的要求解答为整数的情形，即要求求最优整数解的问题。2.2对优化货运车数量的分析针对问题一至三，都是要求我们对已知乘用车各型号数量的条件下，找到最优的货运车安排方案。货运车的安排过程中，需要满足一些约束条件，如：1、高度超过1.7米的乘用车只能装在下层；2、相邻的两车之间要有安全间距0.1米；3、1-2型车的使用量不能超过1-1型的20%。我们需要的目标函数在于：找到最少货运车的安排方案，之后再最少的货运车安排上，找到最低成本的安排方案。2.3对问题的分析西南交通大学4我们先计算了对于两种货运车每列可以最多装载同一型号的轿车的辆数，这时要考虑车距问题。2.3.1对问题一的分析通过简单的分析可知，在同一辆货运车上装载同一类型轿车得到的总装载车数最少；同时用1-2型车装载轿车得到的总装载车数最少。首先我们解除约束，即不考虑1-2型货运车尽量使用量不超过1-1型货运车使用量的20%，这时的最优解就是所有轿车在尽量不混装的情况下全部用1-2型车来装载，这时肯定有装不满的情况存在。现在带进刚刚解除的约束条件，我们一辆一辆地减少装载II型轿车的1-2型货运车，把放下来的II型车用1-1型车来装载；当II型车转移完毕后，如果还没有满足约束条件，就用同样的方法来转移I型车。直到达到约束条件为止，这样即可得到最优装载方案。2.3.2对问题二的分析由于运输的III型车的高度超过1.7m，只能将其放在运载车的下层。对于解决运输的最优方案我们仍采用第一问中的方法。首先我们将要运输的所有的乘用车都用1-2型车运输，得到其最优方案即最少1-2型用车量，再逐一递减1-2型车将其装在1-1型运载车上直到满足即1-2型货运车尽量使用量不超过1-1型货运车使用量的20%是在1-2运载车下层都装载上III型车，然后再在上层装上II型车，剩余的II型车再进行单独装配。这样即可得到最优装载方案。2.3.3对问题三的分析这一问中需要装载的同时有I、II、III型车，和问题二中一样由于运输的III型车的高度超过1.7m，只能将其放在运载车的下层。首先我们解除约束，即不考虑1-2型货运车尽量使用量不超过1-1型货运车使用量的20%，这时的最优解就是所有轿车在尽量不混装的情况下全部用1-2型车来装载，III型车只能装在下层，下层装III型车的货运车上层全配装II型车，这时肯定有装不满的情况存在。现在带进刚刚解除的约束条件，我们一辆一辆地减少装载III型轿车的1-2型货运车，把放下来的III型车用1-1型车来装载；当III型车转移完毕后，如果还没有满足约束条件，就用同样的方法来转移II型车；如果还没有满足约束条件，就用同样的方法来转移I型车。直到达到约束条件为止，这样即可得到最优装载方案。§3模型的假设假设1：为了方便，假设将1-2型运载车的上层两列命为上、中层；假设2：假设装载轿车时只考虑车与车之间的车距，乘用车与车厢车尾和车头刚好接触不影响装载；假设3：1-1型，1-2型的车的数量满足运输要求；假设4：不考虑路程上出现突发事件。§4符号说明西南交通大学5变量符号变量含义A代表I型乘用轿车B代表II型乘用轿车C代表III型乘用轿车x1-1型货运车使用的数量y1-2型货运车使用的数量min1-1、1-2型货运车使用数量的最小值G消除约束消除约束时的最优方案G原问题的最优方案G消1问题一消除约束时的最优方案G消2问题二消除约束时的最优方案G消3问题三消除约束时的最优方案aI型乘用轿车需要运输的数量bII型乘用轿车需要运输的数量cIII型乘用轿车需要运输的数量a1I型乘用轿车装在1-1型货运车中的数量a1,max1-1型货运车每层装载I型乘用轿车的最大数量A1用来装载I型车的1-1型货运车的使用量a2I型乘用轿车装在1-2型货运车中的数量a2,max1-2型货运车每层装载I型乘用轿车的最大数量A2用来装载I型车的1-2型货运车的使用量b1II型乘用轿车装在1-1型货运车中的每层数量b1,max1-1型货运车每层装载II型乘用轿车的最大数量c2,max1-2型货运车每层装载III型乘用轿车的最大数量c1,max1-1型货运车每层装载III型乘用轿车的最大数量B1用来装载II型车的1-1型货运车的使用量b2II型乘用轿车装在1-2型货运车中的数量b2,max1-2型货运车每层装载II型乘用轿车的最大数量B2用来装载II型车的1-2型货运车的使用量C1用来装载III型车的1-1型货运车的使用量C2用来装载III型车的1-2型货运车的使用量c1III型乘用轿车装在1-1型货运车中的每层数量c2III型乘用轿车装在1-2型货运车中的每层数量ga1不能满装于1-1型货运车上的A型乘用轿车gb1不能满装于1-1型货运车上的B型乘用轿车ga2不能满载于1-2型货运车上的A型乘用轿车的数量gb2不能满载于1-2型货运车上的B型乘用轿车的数量西南交通大学6§5模型的建立与求解由表1、表2可以得出，Ⅲ型车的高度大于1.7米，只能装在1-1和1-2型货运车的下层。并且，发现1-2型的上层Ⅰ和Ⅱ型车均可以自由并排放置。使用小型计算器计算可得到1-1型和1-2型每层最大装各型乘用车的数量下表所示：货运车型号乘用轿车型号1-11-2Ⅰ45Ⅱ56Ⅲ45表31-1和1-2型货运车各层最大装载不同型号乘用车数量表5.1问题一：乘用轿车的类型只有I型和II型5.1.1问题一求解的主要步骤为方便区别，在解答过程中，我们记I型乘用轿车为A车，II型乘用轿车记为B车，III型乘用轿车为C车。本题中，轿运车对A车（I型乘用车）和B车（I型乘用车）的宽度和高度都无限制，无需考虑。我们记用1-1型货运车装运的I型乘用轿车的数量为a1，用1-2型货运车装运的I型乘用车的数量为a2；用1-1型货运车装运的II型乘用车的数量为b1，用1-2型货运车装运的II型乘用车的数量为b2；用1-1型货运车装运的III型乘用车的数量为c1，用1-2型货运车装运的III型乘用车的数量为c2。先对1-1型货运车上下层满载时每一层装A、B型乘用轿车的辆数进行分析。由给出的相邻乘用轿车之间纵向及横向的安全车距均至少为0.1米的车距约束，可得：19=a1×4.61+b1×3.615+(a1+b1-1)×0.1（a1、b1取整）计算并取整，得到的关于1-1型货运车每层装载A型、B型乘用轿车的组合状态有：a1=0b1=5；a1=1b1=3；a1=2b1=2；a1=3b1=1；a1=4b1=0。再对1-2型货运车上下层满载时每一层装A、B型乘用轿车的辆数进行分析。由于1-2型货运车上层可装2列，我们在这里将其看作该种货运车具有上、中、下3层，且每层只装载1列乘用轿车。现对每一层装载A、B型乘用轿车的辆数进行分析。由给出的相邻乘用轿车之间纵向及横向的安全车距均至少为0.1米的车距约束，可得：24.3=a2×4.61+b2×3.615+(a2+b2-1)×0.1（a2、b2取整）计算并取整，得到的关于1-2型货运车每层装载A型、B型乘用轿车的组合状态有：西南交通大学7a2=0b2=6；a2=1b2=5；a2=2b2=4；a2=3b2=2；a2=4b2=1；a2=5b2=0。由上面的结果分析可知，在每一辆乘用货运车满装时，每一辆乘用货运车装同一种乘用轿车车型达到的运载效率