2013数学建模 C整车物流系统.doc

2013第十届五一数学建模联赛承 诺 书我们仔细阅读了五一数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其它公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们授权五一数学建模联赛赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号为（从A/B/C中选择一项填写）： C 我们的参赛报名号为： 参赛组别（研究生或本科或专科）： 本科 所属学校（请填写完整的全名） 参赛队员 (打印并签名) ：1. 2. 3. 日期： 2013 年 5 月 1 日获奖证书邮寄地址： 邮政编码 2013第十届五一数学建模联赛编 号 专 用 页竞赛评阅编号（由竞赛评委会评阅前进行编号）：评阅记录评阅人评分备注 裁剪线 裁剪线 裁剪线 竞赛评阅编号（由竞赛评委会评阅前进行编号）：参赛队伍的参赛号码：（请各参赛队提前填写好）：20132008542013第十届五一数学建模联赛题 目 整车物流调度系统 摘 要本文就国内某家物流公司如何提高物流运输效率、优化运营成本问题，对其运载货车的选派、运载过程中空车位的减少、订单的合理分配以及货车的评级分数进行了合理的分析、预测和优化，为物流公司提供了一套完整的物流运输优化系统，从而提高了物流的运输效率、降低了运营成本。对于问题一，根据各目的地在全国的分布和各条订单中所需要运载的小汽车的辆数以及运输过程中产生的主要运输成本，建立多元线性规划模型，利用附表一中所给的数据采用线性规划中目标函数和约束条件相结合的方法，得到整个运输过程中运输成本的近似表达式，并运用LINGO 8.0软件对模型进行分析，得出表达式中运输成本与选派货车的编号、里程以及所需要运载的小汽车的数量的关系。针对问题二，建立具有优先级指派问题的数学模型，根据附表二中各小汽车品牌级别的高低不同，考虑优先运送优先级别较高的小汽车，运用Eviews 7.0 软件对指派模型进行分析，通过模型估计结果，得到运输成本的预测模型，对模型进行分析得到最佳运输方案。在问题三上，首先根据附表三中提供的数据对各起运地所提供的货车的评级分数进行总体分析，在问题二的基础上建立VRP模型，其中分别令货车评级分数、小汽车品牌级别为决策变量，运输成本为目标函数，利用LINGO 8.0软件，编写程序，结合对货车的评级分数分析的结果，最终得到运输成本最低且优先调用评级分数较高的货车运输的优化方案。关键词：线性规划、优先级指派、多目标规划、VRP分析一、问题重述1、问题的背景随着我国经济突飞猛进的发展，物流成为社会分工中重要的环节。物流系统的优劣也影响了业务流程的运行效率及其成本。国内某家物流公司的主要业务是从分布在全国的M个主机厂，将N种品牌商品小汽车调运到全国多个城市的4S店。请为该物流公司设计一套物流运输优化系统，以提高物流运输效率、优化运营成本。2、问题的提出本题目不考虑小客车类型的差异，在运输过程中产生的主要运输成本包括：运输商品小汽车的业务费为0.7元/(公里辆)，货车运输途中因部分车位空闲而产生的空载运输成本为0.2元/(公里车位)，油耗动力成本为0.5元/公里，货车过路费用为0.4元/公里。 （1）建立数学模型考虑从某个主机厂调度货车来完成运输订单，如何安排货车，可以保证在完成运输任务的基础上运输成本最低。允许将不同订单用同一货车运输，但是不允许将同一订单拆分用不同货车运输；一个运力货车运单的目的地城市的数量不超过3个。（2）在同一个起运地优先安排货车运输这些级别高的小汽车。如果货车有剩余车位，则可以顺途运输其他城市的订单；如果起运地货车数量不足，可以从附近城市调运货车来运输本地订单。请建立数学模型，考虑如何安排货车，可以保证在完成运输任务的基础上运输成本最低。（3）故在安排货车运输方案的时候，首先考虑运输成本最小，其次优先安排车辆评级分数较高的货车，在问题2的基础上，利用附件3中的数据综合考虑运输成本和货车评级分数进行求解并给出新的运单。二、问题分析1、问题一的分析建立数学模型考虑从某个主机厂调度货车来完成运输订单，如何安排货车，可以保证在完成运输任务的基础上运输成本最低：在运输过程中产生的主要运输成本包括：运输商品小汽车的业务费，货车运输途中因部分车位空闲而产生的空载运输成本，油耗动力成本，货车过路费用。（1）根据订单中小汽车的数量和货车的车位安排运输方案，使货车的空载在完成任务的基础上达到最少。（2）由于一个运力货车运单的目的地城市的数量不超过3个，并且订单不能拆分。如果假设一个运力货车空载车位数量足够另一个顺途订单的小汽车数量，则可以对他们重新进行安排货车进行整合，这样就会使运输成本大大降低。根据图1-1和图1-2对货车车位和各地小汽车需求量进行分析，从图中可分析出大部分货车的车位集中在10-20之间，福州等地小汽车需求量大，在调度货车过程中根据订单情况考虑货车编号。 图1-1 货车车位分析图 图1-2 全国各地小汽车需求量2、问题二的分析问题二根据小汽车品牌不同，对小汽车进行分级，级别高的小汽车要优先运输。在调度运输过程中，还会出现以下两种情况：（1）如果货车有剩余车位，则可以顺途运输其他城市的订单；（2）如果起运地货车数量不足，可以从附近城市调运货车来运输本地订单。针对以上两种情况，对各地货车车位情况（图2-1），小汽车品牌级别（图2-2）进行综合分析，优先考虑小汽车品牌级别进行货车安排，然后在完成订单的基础上优化成本，使其降到最低。 图2-1 各地货车车位 图2-2 小汽车品牌级别3、问题三的分析在货车调度过程中考虑货车评级分数，优先安排评级分数高的货车进行运输。安排调度时考虑两个方面：运输成本，货车车辆评级。（1）运输成本：在保证完成任务的基础上使货车数量最少，货车车位（图3-1）空车位最少，调用附近城市的货车数量最少，即可达到优化目的，使运输成本最小。（2）货车车辆评级：根据货车的车辆评级分数(图3-2)，优先选择评级分数高的货车进行运输。但也要考虑货车的车位，数量，使运输成本降到最小。 图3-1 货车车位分析图 图3-2 货车评级分数三、模型假设1、假设题中所给数据基本真实有效、可靠；2、预测的数据均在误差范围内，可以接受；3、随着我国经济的发展，整车物流的运输成本中的各个要素所占的比例不会发生剧烈的波动；4、问题三中用到的VRP模型是被识别了的；5、由起运地到目的地运费均为线性函数；6、除上述因素外的其它因素（库存问题、供应商的成本问题、时间要求问题）对经济影响不予考虑。四、符号说明i 发点j 收点q 每辆车的车位xij 由i到j的空车位cij 由i到j的空驶里程z 总里程m 要完成的业务项数A1 ,A2 , Am 要完成的业务g1,g2 , gm 每项业务的货运量a1，a2，, am 完成每项业务所需的车辆数lgi ，pgi 由供货点g到物流中心i的单位运价及运量, iT,gGhij ,yij 由物流中心i到用户j的单位运价及运量,jC, iTHi 物流中心i的固定费用五、模型准备1、模型一：线性规划（1）线性规划模型【1】的结构具有如下特性、目标函数是决策变量Xi （i=1,2,3,）的线性函数、约束条件是决策变量Xi （i=1,2,3,）的线性等式或不等式； 具有以上结构特点的模型就是线性规划模型，记为LP（Linear Programming），具有以下一般形式：（2）线性规划的标准模型由于目标函数既可以是实现最大化，也可以是实现最小化，约束条件可以是等式，也可以是不等式，决策变量为非负或不受限制，这么复杂的情况，一定会给模型的求解带来不便，为此引入标准形式 ：（3）线性规划数学模型标准形式的特点、目标函数为最大化类型（有的书上为最小化）；、约束条件均为线性；、决策变量及方程右端非负。线性规划数学模型标准形式可以有向量形式表示：，如果所建的模型不符合标准形式，则可以用适当方法化为标准形式，主要有： 、如果目标函数为最小化问题，则将目标函数两边乘以“-1”； 、如果约束方程右端为负，在该方程两端同乘以“-1”； 2、模型二：具有优先级的指派问题的数学模型传统的指派问题不能很好解决任务的重要程度是不同的指派问题, 不同的任务具有不同的优先级, 然后在保证优先级高的问题先解决的原则, 再进行任务分配, 从而得到更合理的任务指派方案。 s.t.max 1 、min2 为目标函数，另外, 决策者在安排货车时, 一般先考虑优先级较高的小汽车的安排问题, 然后再考虑优先级一般的小汽车的安排, 该模型更接近实际生活。3、模型三：VRP模型最小目标函数:约束条件：运输车辆路线安排问题VRP【2】可定义为：运输车辆从一个或多个设施到多个地理上分散的客户点,优化设计一套货物流动的运输路线,同时要满足一系列的约束条件。六、模型建立及求解1、问题一的模型建立及求解（1）模型建立由假设和约束条件可列出此目标规划所满足的关系式,并记此问题为问题T。此处可由下式得出：式中，(gi/q)为数值不大于(gi/q)的最大整数；Cij根据实际情况选用，可取为点i到点j的广义最短距离。为避免有车场发出的空车不经重载点直接驶向车场，令Cij=M， i,j=m+1,m+2,m+n其中M为一足够大的正数。（2）模型求解 根据附表一中的数据得到各目的地在全国的分布如图4-1，分析此图可和附表1中每个目的地所需要的订单数量和每条订单中需要运送的小汽车数量，以及每种货车所能运载的小汽车数量，可以得到以下运输方案：图4-1 订单目的地分布图北京到蒙城共有2条订单，共需要运送10辆小汽车，1号货车正好可以运载10辆小汽车，所以选择1号货车即可；北京到福州共有7条订单，共需要运送50辆小汽车，2、3号货车可以运载20辆小汽车，由于1号货车已派往蒙城，所以不能再次选择，而7号货车可以运载10辆小汽车，所以选择2、3、7号货车；北京到龙岩共有2条订单，共需要运送5辆小汽车，因为没有可以刚好运载5辆小汽车的货车，所以只得选择可以运载10辆小汽车的10号货车；订单编号起运地目的地里程/km小汽车数量货车编号起运地货车编号车位1北京蒙城88431北京1102北京蒙城8847北京2203北京福州1965102.3.7北京3204北京福州196510北京4205北京福州19657北京5156北京福州19651北京6207北京福州19652北京7108北京福州196510北京8129北京福州196510北京92110北京龙岩2244410北京101011北京龙岩22441北京111212北京三明1834337北京121213北京三明18347北京131214北京兰州163054.6北京142015北京兰州163010北京152016北京兰州16305北京162017北京兰州163010北京172018北京兰州163010北京182023北京南宁24831014北京192024北京南宁248310北京201025北京贵阳24471020北京212026北京遵义2567722北京221027北京遵义25671北京232028北京漯河87945北京242029北京漯河8796北京252030北京漯河8793北京2612表1-1（注释：标注出来的表示已经发出去的货车）但是这并不是最优解决方案，为了得到最优方案，应该考虑货车在运载小汽车过程中所产生的空车位以及订单的合并运输问题，根据线性规划模型可以得到目标函数：运用LINGO软件，对模型进行验证，可以得到如下方案：订单编号起运地目的地里程/km小汽车数量调度方案起运地货车编号车位1北京蒙城88431北京1102北京蒙城8847北京2203北京福州1965102北京3204北京福州196510北京4205北京福州196575北京5156北京福州19651北京6207北京福州19652北京7108北京福州1965103北京8129北京福州196510北京92110北京龙岩224445北京101011北京龙岩22441北京111212北京三明183437北京121213北京三明18347北京131214北京兰州163054.6北京142015北京兰州163010北京152016北京兰州16305北京162017北京兰州163010北京172018北京兰州163010北京182023北京南宁24831014北京192024北京南宁248310北京201025北京贵阳24471020北京212026北京遵义2567726北京221027北京遵义25671北京232028北京漯河8794北京2420表1-2（注释：标注出来的表示已经发出去的货车，例如，对比表1-1和表1-2可以看出，北京到福州和北京到龙岩由原来的4辆货车减少到2辆货车，充分利用了车位，降低了成本）具体方案见附录。2、问题二的模型建立及求解（1）模型建立由问题二可知，小汽车品牌不同，在运输的时候将小汽车进行了分级标识，级别最高的为1，在运输过程中优先运送级别高的小汽车。可以分为以下两种情况：、货车有剩余车位，则可以顺途运输其他城市的订单；、起运地货车数量不足，可以从附近城市调运货车来运输本地订单。具有优先级别的指派模型是一个多目标规划问题，可采用加权和和法，乘除法等方法将其转换为单目标规划问题求解，然后，线性加权和法要求所有目标必须具有相同量纲，乘除法当目标数较多时显得复杂。将不同目标函数下的属性矩阵根据目标函数求极小作如下变化：当目标函数值为极小时：其中：分别表示属性l矩阵中的最大值、最小值根据各个分目标重要程度给出全输变量，=（1 ,2 ,L），其值可采用层次分析法等方法确定，且1 ,2 ,L 0。由此可得综合考虑L个目标后各属性值合成相对隶属度，即经过上述变换，目标函数式可转换为模型转换为约束条件式不变。（2）模型求解运用Eviews7.0软件【3】，结合附表二中的数据，对优先级别的指派模型分析，得到3 , 4 与Xi的关系如下：脉冲响应图为： 图5-1 脉冲响应图（3） 图5-2 脉冲响应图（4）由以上结论可得出运载方案如下（根据附件2以天津为例进行分析）：以天津为起运地需要往外地运送749辆小汽车，其中优先级为11的需要运送536辆，优先级为27的需要运送8辆，天津提供的货车可运载的小汽车辆数为490辆，北京需要运送的小汽车的优先级均为30，由于天津小汽车的优先级高于北京小汽车的优先级，而天津提供的货车数量不足，所以需要从北京调用货车车位54个。考虑到运输成本，应尽量使货车数量少且尽可能少的产生空载车位，故可选择8、9、28号货车从北京去天津协助运输级别为11、27的小汽车。3、问题三的模型建立及求解（1）模型建立分析问题三，可得知要根据每一辆货车的运输汽车质损率、及时到达率、信息反馈率和服务态度等多方面进行跟踪评价，对每一辆货车进行评级。在安排货车运输方案的时候，首先考虑运输成本最小，其次优先安排车辆评级分数（图6-1）较高的货车。故在模型建立过程中要从运输成本和车辆评级两方面入手。图6-1 车辆评级分数最小目标函数：约束条件：（2）模型求解运用VRP数学模型，结合数理规划软件LINGO 80，编写程序，将附件3中的数据输入模型中，以问题二中已考虑运输成本最低为基础，结合附件3中货车的评级分数，以天津为例，得到运输方案如下：以天津为起运地需要往外地运送749辆小汽车，其中优先级为11的需要运送536辆，优先级为27的需要运送8辆，天津提供的货车可运载的小汽车辆数为490辆，北京需要运送的小汽车的优先级均为30，由于天津小汽车的优先级高于北京小汽车的优先级，而天津提供的货车数量不足，所以需要从北京调用货车车位54个。考虑到运输成本，应尽量使货车数量少且尽可能少的产生空载车位，同时满足从北京调用货车的评级分数应尽量高，由图？得，应该调用北京的30、79、81号货车图7-1 北京车辆评级分数七、模型评价1、优点：（1）本文建立的3个数学模型有成熟的理论基础，又有相应的软件支持，可信度高。（2）利用数学工具软件的强大统计功能对附件中的数据进行了统计分析，并借助EVIEWS 7.0，LINGO8.0对文中3个模型进行严格求解，科学性强。（3）图表的使用在分析过程中形象直观。2、缺点：（1）本文问题的探究只是根据一些少量材料，针对某一特定范围，阶段或时刻的研究，准确性还有待改进。（2）数学模型没有考虑库存时间等问题,无法达到整车货运各环节的整体最优化。八、参考文献【1】运筹学教材编写组。运筹学（第三版）。北京：清华大学出版社，2005.【2】 姜启源，数学建模（第三版）【M】 北京 高等教育出版社 2003-08. 【3】 易丹辉. 数据分析与Evicws 应用 M . 北京: 中国统计出版社, 2002.九、附录订单编号起运地目的地里程/km小汽车数量起运地货车编号车位1北京蒙城88431北京1102北京蒙城8847北京2203北京福州1965102北京3204北京福州196510北京4205北京福州196575北京5156北京福州19651北京6207北京福州19652北京7108北京福州1965103北京8129北京福州196510北京92110北京龙岩224445北京101011北京龙岩22441北京111212北京三明183437北京121213北京三明18347北京131214北京兰州163054,6北京142015北京兰州163010北京152016北京兰州16305北京162017北京兰州163010北京172018北京兰州163010北京182023北京南宁24831014北京192024北京南宁248310北京201025北京贵阳24471010北京212026北京遵义256778北京221027北京遵义25671北京232028北京漯河8794北京242029北京漯河879615北京252030