全国研究生数学建模竞赛一等奖论文(E题)-乘用车物流运输计划问题.doc
《全国研究生数学建模竞赛一等奖论文(E题)-乘用车物流运输计划问题.doc》由会员分享,可在线阅读,更多相关《全国研究生数学建模竞赛一等奖论文(E题)-乘用车物流运输计划问题.doc(38页珍藏版)》请在三一文库上搜索。
1、参赛密码 (由组委会填写)全第十一届华为杯全国研究生数学建模竞赛 学 校西安理工大学参赛队号队员姓名参赛密码 (由组委会填写) 第十一届华为杯全国研究生数学建模竞赛题 目 乘用车物流运输计划问题摘 要:本文主要解决的是乘用车整车物流的运输调度问题,通过对轿运车的空间利用率和运输成本进行优化,建立整数规划模型,设计了启发式算法,求解出了各种运输条件下的详细装载与运输方案。针对前三问,由于不考虑目的地和轿运车的路径选择,将问题抽象为带装载组合约束的一维装车问题,优化目标是在保证完成运输任务的前提下尽可能满载,选择最优装载组合方案使得所使用的轿运车数量最少。对于满载的条件,将其简化为考虑轿运车的空间
2、利用率最大,最终建立了空间利用率最大化和运输成本最小化的两阶段装载优化模型。该模型类似于双目标规划模型,很难求解。为此,将空间利用率最大转换为长度余量最少,并为其设定一个经验阈值,将问题转换为求解整数规划问题,利用分支定界法进行求解。由于分支定界法有时并不能求得最优解,设计了一种基于阈值的启发式调整优化算法。最后,设计了求解该类问题的通用算法程序,并对前三问的具体问题进行了求解和验证。通过求解得出,满足前三问运输任务的1-1型轿运车和1-2型轿运车数量如下表所示(具体的乘用车装载方案见表2、表5、表7): 第一问 第二问 第三问1-1 16 12 251-2 2 1 5针对问题四,其是在问题一
3、的基础上加入了整车目的地的条件,需要考虑最优路径的选择。在运输成本上,加入了行驶里程成本,因而可以建立所使用的轿运车数量最少和总里程最少的双目标整数规划模型。对于此种模型,可以采用前三问所设计的通用算法进行求解。此时,需要重新设计启发式调整优化算法。为此,根据路线距离的远近和轿运车数量需要满足的比例约束条件设计了新的调整优化方案。最终求得的各目的地的轿运车使用数量如下表所示,此时的总路程为6404,具体装载方案见表9。ABCD总数1-1型1695211-2型40004总量569525针对问题五,作为问题四的扩展研究,类似于问题四建立了双目标规划模型。由于乘用车的种类达到了45种,导致轿运车的装
4、载组合方案急剧增多。如果仍采用穷举法确定装载组合方案,将产生“组合爆炸”。为此,采用基于排样算法的装载优化算法,来避免这种现象。这种算法的基本流程是:首先按照乘用车的宽、高将乘用车分为“高”、“低窄”、“低宽”三种车型; 然后根据不同类型的乘用车在不同目的地的需求量,构建关系树;接着根据关系树和启发式调整优化算法来确立初步配载方案;最后验证配载方案是否满足约束条件以求得最终方案。其中,启发式调整优化算法仍然是基于经验的,这里主要考虑轿运车上层空间的利用率最大化和距离较远的点以尽可能地减少轿运车的数量,同时也要满足不同轿运车型之间的数量比例约束。最终求得的各目的地轿运车的详细使用量如下表所示,并
5、且完成运输任务所需行驶的总里程为35140。序号目的地A目的地B目的地C目的地D目的地E余量101470002070100131100011041203000520008060000025700400080115000950000010430101目的地总量342529111927轿运车总量118关键词:整车物流 整数规划 分支定界法 经验阈值 启发式调整优化 排样算法一、 问题重述1.1 问题背景整车物流指的是按照客户订单对整车快速配送的全过程。随着我国汽车工业的高速发展,整车物流量,特别是乘用车的整车物流量迅速增长。乘用车生产厂家根据全国客户的购车订单,向物流公司下达运输乘用车到全国各地的
6、任务,物流公司则根据下达的任务制定运输计划并配送这批乘用车。为此,物流公司首先要从他们当时可以调用的“轿运车”中选择出若干辆轿运车,进而给出其中每一辆轿运车上乘用车的装载方案和目的地,以保证运输任务的完成。“轿运车”是通过公路来运输乘用车整车的专用运输车,根据型号的不同有单层和双层两种类型,而单层轿运车实际中很少使用,本题仅考虑双层轿运车。在确保完成运输任务的前提下,物流公司追求降低运输成本。但由于轿运车、乘用车有多种规格等原因,当前很多物流公司在制定运输计划时主要依赖调度人员的经验,在面对复杂的运输任务时,往往效率低下,而且运输成本不尽理想。1.2 已知信息(1)每种轿运车上、下层装载区域均
7、可等价看成长方形,各列乘用车均纵向摆放,相邻乘用车之间纵向及横向的安全车距均至少为0.1米,下层力争装满,上层两列力求对称,以保证轿运车行驶平稳。(2)1-1型及2-2型轿运车上、下层装载区域相同;第五问中1-2型轿运车上、下层装载区域长度相同,但上层比下层宽0.8米。(3)受层高限制,高度超过1.7米的乘用车只能装在1-1、1-2型下层,2-2型上、下层均不能装载高度超过1.7米的乘用车。(4)在轿运车使用数量相同情况下,1-1型轿运车的使用成本较低,2-2型较高,1-2型略低于前两者的平均值,但物流公司1-2型轿运车拥有量小,为方便后续任务安排,每次1-2型轿运车使用量不超过1-1型轿运车
8、使用量的20%。(5)在轿运车使用数量及型号均相同情况下,行驶里程短的成本低。1.3 需要解决的问题请为物流公司安排以下五次运输,制定详细计划,含所需要各种类型轿运车的数量、每辆轿运车的乘用车装载方案、行车路线。(前三问目的地只有一个,可提供一个通用程序;后两问也要给出启发式算法的程序,优化模型则更佳):(1)物流公司要运输车型的乘用车100辆及车型的乘用车68辆。(2)物流公司要运输车型的乘用车72辆及车型的乘用车52辆。(3)物流公司要运输车型的乘用车156辆、车型的乘用车102辆及车型的乘用车39辆。(4)物流公司要运输166辆车型的乘用车(其中目的地是A、B、C、D的分别为42、50、
9、33、41辆)和78辆车型的乘用车(其中目的地是A、C的分别为31、47辆)。(5)根据附件表1给出的物流公司需要运输的乘用车类型(含序号)、尺寸大小、数量和目的地和附件表2给出的可以调用的轿运车类型(含序号)、数量和装载区域大小,采用启发式算法,求解装载、运输方案,并自行设计运输方案的表达形式。二、 模型假设(1) 每辆轿运车装载乘用车的组合是独立的;(2) 轿运车装载乘用车时上下层部分是对称的,即数量一致;(3) 轿运车到达目的地后原地待命,无须放空返回;(4) 轿运车在运输过程中不存在往返情况;(5) 每次卸车成本可以忽略不计。三、 基本符号说明符号符号说明符号符号说明v_n第v辆车的装
10、载组合数L轿运车的长度Cvjk第v辆车第j个装载组合装载第k种类型物品的容量lj第j种乘用车的长度xivj物品i装载在车辆v的第j个装载组合c安全距离yvj车辆v选择第j个装载组合xi第i种方案的使用数量Cij第i种装载组合方案能承载第j种乘用车的数目r长度余量Nj需要装载的第j种乘用车的数量T经验阈值PkO到A、B、C、D、E的距离S轿运车的总路程bjk第j种乘用车运往第k个目的地的数量yik第i种方案去第k个目的地四、 问题分析本文研究的是乘用车物流运输计划问题,通过对轿运车的空间利用率和运输成本进行优化,设计启发式算法,以求解各种运输条件下详细的装载与运输方案,能够使得轿运车的利用率达到
11、最高、运输成本达到最低、行车路线最优。针对题中的五个问题,分析如下:4.1 问题一分析题目要求给出运输车型的乘用车100辆及车型的乘用车68辆时物流公司的运输方案。本问题即将给定数量的车型和车型乘用车装载到1-1型轿运车和1-2型轿运车上,并使得所用的1-1型轿运车和1-2型轿运车数量之和最少,亦即成本最少。并在满足数量最少的情况下,求解车型和车型乘用车的最佳装载组合方案,以使得两种轿运车空间利用率达到最大。由于两种乘用车的高度均不超过1.7米,且其宽度小于轿运车的下层宽度、两倍宽度也不超过轿运车的上层宽度,即车型和车型乘用车可以装载在1-1型和1-2型轿运车的任意层上。所以,问题可以归结为一
12、维组合装车问题,求解的目标是充分利用轿运车的长度,以使得轿运车的长度余量最少,则轿运车的空间利用率也将达到最大。4.2 问题二分析题目要求给出运输车型的乘用车72辆及车型的乘用车52辆时物流公司的运输方案。本问题即将给定数量的车型和车型乘用车装载到1-1型轿运车和1-2型轿运车上,并使得所用的1-1型轿运车和1-2型轿运车数量之和最少,亦即成本最少。并在满足数量最少的情况下,求解车型和车型乘用车的最佳装载组合方案,以使得两种轿运车空间利用率达到最大。由于车型乘用车的高度大于1.7米,根据题目中的要求,只能将其装载在1-1型和1-2型轿运车的下层上。而车型的乘用车,仍然可以装载在1-1型和1-2
13、型轿运车的任意层。问题仍为求解一维组合装车问题,求解的目标是充分利用轿运车的长度,以使得轿运车的长度余量最少。 4.3 问题三分析题目要求给出运输车型的乘用车156辆、车型的乘用车102辆及车型的乘用车39辆时物流公司的运输方案。本问题即将给定数量的车型、车型和车型乘用车装载到1-1型轿运车和1-2型轿运车上,并使得所用的1-1型轿运车和1-2型轿运车数量之和最少,亦即成本最少。并在满足数量最少的情况下,求解车型、车型和车型乘用车的最佳装载组合方案,以使得两种轿运车空间利用率达到最大。此问题可以看作是前两问的延伸,此时1-1型轿运车和1-2型轿运车下层均可以装载三种乘用车,而上层只能装载车型和
14、车型轿运车。4.4 问题四分析题目要求给出运输166辆车型的乘用车(其中目的地是A、B、C、D的分别为42、50、33、41辆)和78辆车型的乘用车(其中目的地是A、C的分别为31、47辆)时物流公司的运输方案。本问题可以看作是问题一的延伸,在问题一的基础上将路径加入到了考虑之列,目的地不再相同。问题变成将给定数量的车型和车型乘用车装载到1-1型轿运车和1-2型轿运车上,并运往相应的目的地,以满足各目的地的需求,使得运输成本最少。而影响运输成本的首要因素是轿运车使用数量,其次是行驶里程长短。因而问题转换为求解车型和车型乘用车的最佳装载组合方案,以使得两种轿运车的使用总数量最小且所需的路程最短。
15、这是一个双目标规划问题,此时轿运车有可能不再满足满载的条件。4.5 问题五分析题目要求利用10种不同规格轿运车,来装载45种不同规格的乘用车,以满足A、B、C、D、E五个目的地对45种乘用车的数量需求。本问题可以看作是问题四的扩展研究,只是问题比第四问要复杂的多,但整体的模型是一致的。对于这种NP难问题,寻找最优解是不切实际的,需要重新设计启发式算法,简化目标函数,使其更容易求解,以期能够求得满足约束条件的可行解。五、 问题求解与算法设计5.1装载问题的基本模型5.1.1 模型定性分析在不考虑整车目的地和轿运车的路径选择的情况下,问题可抽象为带装载组合约束的一维装车问题1,即有n个属于l种类型
16、的相同(单位)尺寸的物品,有w辆车,每辆车对这l种类型的物品有几种装载组合,不同车辆的装载组合不同,每辆车选择一种装载组合并严格按照物品组合进行装载。优化目标是在满载的情况下装载最多的物品,同时给出每个物品的具体配载方案。5.1.2 复杂性分析考虑带装载组合约束的一维装车问题的简化问题,当每辆车只有一个装载组合时,问题变为:有l种类型的物品,类型k的物品数Nk,有n个装载组合,第j个装载组合对类型k物品的容量Cjk,对所有类型物品的容量Cj,选择装载组合以尽可能装载最多的物品。已知多维背包问题为NP难问题2,而多维背包问题可以转化为一维组合装车问题的简化问题,则一维组合装车问题的简化问题为NP
17、难问题,显然一维组合装车问题更为复杂,也即一维组合装车问题为NP难问题。5.1.3 一维组合装车问题线性混合整数规划模型3问题最终结果是给出具体的装载方案,即物品装载在哪辆车的哪个装载组合上,因此以物品作为决策主体,物品选择车辆、装载组合。设物品数为m,类型数为l,车辆数为w,第v辆车的装载组合数为v_n,第v辆车第j个装载组合装载第k种类型物品的容量为Cvjk, xivj为物品i是否装载在车辆v的第j个装载组合上的0、1变量,yvj为车辆v是否选择第j个装载组合的0、1变量,则有如下数学模型: (5-1)优化目标为物品装载数最多;约束式第一式表示一辆车最多只能选择一种装载组合;第二式表示一个
18、物品最多只能被装载到一辆车的某个装载组合上;第三式表示每辆车必须严格按照装载组合装满每种类型的物品;第四、五式定义了变量的取值范围。5.2 两阶段装载优化模型的建立5.2.1 实际问题的分析与简化在本问题中,有三种类型的乘用车,其数量根据具体的运输任务而定,每种车的规格均不同。轿运车也有两种,其规格也有较大差异。现要考虑将给定数量的三种类型的乘用车装载到两种类型的较运车上,但轿运车的数量可以无限多。为了在保证完成运输任务的前提下,降低整车物流的运输成本,目标函数变为在满足满载的情况下,选择最优装载组合方案,使得所使用的轿运车数量最少。而满载的条件在本问题中不再适用,我们简化为考虑轿运车的空间利
19、用率最大,为此,建立了两阶段装载优化模型4。5.2.2 装载组合方案的确定在给定运输任务的乘用车类型后,根据各乘用车的规格和各装载用轿运车的规格,首先确定1-1型和1-2型轿运车每层可以装载的乘用车类型,然后依据1-1型和1-2型轿运车的实际长度,再加上纵向的安全车距的限制,采用穷举法,可以确立各类型轿运车的所有装载组合。假定轿运车的长度为L,第j种乘用车的长度为lj(j = 1, 2, 3分别代表型、型、型),并用kj表示装载组合中承载的第j种乘用车的数目,安全距离c=0.1,满足要求的装载组合方案应满足(只考虑单个下层的情况,其它层类似): (5-2)5.2.3 两阶段装载优化模型(1)第
20、一阶段:空间利用率最大化优化模型 a)目标函数的确定考虑到无论是使用1-1型轿运车还是1-2型轿运车,均采用双层装载。而且为了安全,下层装载的是重心高度较高的乘用车,如车型乘用车。再者,车型和车型乘用车的宽度均在轿运车的允许范围之内。因此,轿运车在装载乘用车时,在高度和宽度上并不存在利用的概念,在最大化空间利用率时仅需考虑长度的充分利用即可,而具体装载辆数取决于乘用车的类型。设Ci,j表示第i种装载组合方案能承载第j种乘用车的数目(i = 1, 2, , m, m+1, , M,m为使用1-1型轿运车的最大方案数,M为分别使用1-1型、1-2型轿运车的总方案数之和;j = 1, 2, 3, 4
21、, 5, 分别表示上(型车放在上层,后面依次类推)、上、下、下、下五种情况),n表示轿运车的列数(1-1型为2, 1-2型为3, 2-2型为4),则目标函数可以表示为:(5-3) b)约束条件的确定轿运车装载时,应保证乘用车与乘用车之间,乘用车与轿运车端壁之间的最小间隙, 避免发生碰撞,此安全距离为0.1米,同时应满足轿运车的装载长度约束。即,满足的约束条件如下: (5-4)(2)第二阶段:运输成本最小化优化模型 a)目标函数的确定由于影响整车物流运输成本高低的主要因素首先是轿运车使用数量,其次是在轿运车使用数量相同情况下的轿运车使用成本,最后是行驶里程成本。而在前三问的模型中,不考虑路径问题
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国 研究生 数学 建模 竞赛 一等奖 论文 乘用车 物流 运输 计划 问题
链接地址:https://www.31doc.com/p-3900006.html