没有合适的资源?快使用搜索试试~ 我知道了~
规划问题算法-乘用车物流运输计划问题.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 1 下载量 33 浏览量
2022-05-01
19:59:37
上传
评论
收藏 1.71MB PDF 举报
温馨提示
试读
31页
规划问题算法-乘用车物流运输计划问题.pdf
资源推荐
资源详情
资源评论
1
参赛密码
(由组委会填写)
第十一届华为杯全国研究生数学建模竞赛
第十一届华为杯全国研究生数学建模竞赛
题 目 乘用车物流运输计划问题
摘 要:
整车物流计划的制定,其问题本质上是一个整数线性规划问题。前四问优化模型的
建立都是以满载为先决条件的方案作为决策对象的,其中,前三问目的地只有一个,直
接以成本作为目标进行优化。第四、五问的问题复杂性增加,轿运车的使用数量转化为
约束。
前三问,本文构建“每种类型轿运车的满载方案”作为模型的决策对象,使得轿运
车与乘用车之间的复杂关系转化为两个阶段的优化:①每种类型轿运车装载方案的优
化,即决策对象集合的优化;②不同装载方案下的各型轿运车线性组合优化。决策对象
构建及优化过程如下:穷举单层满载方案→上下层随机组合→整体归一剔除→极端条件
排除→冗余率筛选→形成决策对象集合。这些决策对象均满足“下层装满、上层平衡”
的限制。在此决策对象集合基础上,建立了仅有数量约束和 20%约束以及成本最低的优
化模型。由于决策对象架构合理,模型表现清晰明了,求解简单易行。最后分别得出问
题一需要 1-1 型车 16 辆,1-2 型车 2 辆;问题二需要 1-1 型车 12 辆,1-2 型车 1 辆;问
题三需要 1-1 型车 25 辆,1-2 型车 5 辆。需要指出的是每一问最优解繁多,但使用轿运
2
车类型和数量都相同,本文只取其中之一。
问题四,应用启发性思想得到三条准则,首先计算轿运车需求量的下限并考察了各
型轿运车运输的“成本效率”,给出准则
1
和
2
:成本效率高的
1-2
型轿运车运载单位
乘用车的成本低,而其数量最多为四辆,应该优先运往最远处以降低总体成本。然后将
各目的地按距离远到近排序,给出准则
3
:优先规划距离远的点,即按照
A
→
B
→
C
→
D
顺序规划各个目的地的运输方案。问题四对路径规划的考量就转化为这三条准则。准则
1
和
2
转化为模型附加约束条件,准则
3
提供了分步求解策略,最后,问题四模型则转
化为前三问模型进行求解。得出问题四需要
1-1
型轿运车
21
辆,
1-2
型轿运车
4
辆,具
体行车方案参考图
5-2
。
问题五是问题四模型的“巨大化”,必须对问题进行降维。通盘考虑轿运车和乘用
车的规格,拆分轿运车并归并为
A
、
B
两类宽度上仅容纳一辆乘用车的“板”
(18
页
)
,
乘用车归并为
24
种类型(表
5-8
)。成本考量与问题四一致,路径规划以问题四为基础。
问题五规模增大不再考虑用远方目的地的轿运车富余空间为途径目的地“捎带”(合理
性见
p
页码),因此路线图转化为类同问题四的星型路线图。在问题的求解过程中,采
取分地点分板类型的方法进一步降低维度。问题五使用新的决策变量改为每块板上放置
的每种类型乘用车数量。规划过程中先进行
B
类,在进行
A
类板的规划,分步进行。
最后的结果是需要
118
辆轿运车。
本文问题是一个典型的、复杂的指派问题,约束条件复杂,目标影响机制不明确。
最后的前四问的结果均通过了本文设计的冗余上限验证法的验证(
13
页,
17
页),证
实为最优解。第五问结果比较接近下限值
113
辆车,说明模型设计策略的合理性。
关键词:满载方案 冗余率优化 分步规划 冗余上限验证法 类型归并
一、问题重述
整车物流指的是按照客户订单对整车快速配送的全过程。乘用车生产厂家根据全国
客户的购车订单,向物流公司下达运输乘用车到全国各地的任务,物流公司则根据下达
的任务制定运输计划并配送这批乘用车。为此,物流公司首先要从他们当时可以调用的
轿运车中选择出若干辆轿运车,进而给出其中每一辆轿运车上乘用车的装载方案和目的
地,以保证运输任务的完成。轿运车是通过公路来运输乘用车整车的专用运输车,本题
仅考虑双层轿运车。双层轿运车又分为三种:上下层各装载 1 列乘用车,记为 1-1 型;
下、上层分别装载 1、2 列,记为 1-2 型;上、下层各装载 2 列,记为 2-2 型,每辆轿运
车可以装载乘用车的最大数量在 6 到 27 辆之间。
在确保完成运输任务的前提下,物流公司追求降低运输成本。但由于轿运车、乘用
车有多种规格等原因,当前很多物流公司在制定运输计划时主要依赖调度人员的经验,
在面对复杂的运输任务时,往往效率低下,而且运输成本不尽理想。
装载具体要求如下:每种轿运车上、下层装载区域均可等价看成长方形,各列乘用
车均纵向摆放,相邻乘用车之间纵向及横向的安全车距均至少为 0.1 米,下层力争装满,
上层两列力求对称,以保证轿运车行驶平稳。受层高限制,高度超过 1.7 米的乘用车只
能装在 1-1、1-2 型下层。
整车物流的运输成本计算简化为:影响成本高低的首先是轿运车使用数量;其次,
在轿运车使用数量相同情况下,1-1 型轿运车的使用成本较低,2-2 型较高,1-2 型略低
于前两者的平均值,但物流公司 1-2 型轿运车拥有量小,为方便后续任务安排,每次 1-2
型轿运车使用量不超过 1-1 型轿运车使用量的 20%;再次,在轿运车使用数量及型号均
3
相同情况下,行驶里程短的成本低,注意轿运车到达目的地后原地待命,无须放空返回。
最后每次卸车成本几乎可以忽略。为物流公司安排以下五次运输,制定详细计划,含所
需要各种类型轿运车的数量、每辆轿运车的乘用车装载方案、行车路线。
1.
物流公司要运输
I
型乘用车
100
辆及
II
型乘用车
68
辆。
2.
物流公司要运输
II
型乘用车
72
辆及
III
型乘用车
52
辆。
3.
物流公司要运输
I
型乘用车
156
辆、
II
型乘用车
102
辆及
III
型乘用车
39
辆。
4.
物流公司要运输
166
辆
I
型乘用车(其中目的地
A
、
B
、
C
、
D
分别为
42
、
50
、
33
、
41
辆)和
78
辆
II
型乘用车(其中目的地
A
、
C
分别为
31
、
47
辆),具体路线长
度:
OD=160
,
DC=76
,
DA=200
,
DB=120
,
BE=104
,
AE=60
。
5.
附件给出的物流公司需要运输的乘用车类型、尺寸大小、数量和目的地,附件给
出可以调用的轿运车类型、数量和装载区域大小,
1-1
型及
2-2
型轿运车上、下层装载
区域相同;
1-2
型轿运车上、下层装载区域长度相同,但上层比下层宽
0.8
米。此外
2-2
型轿运车因为层高较低,上、下层均不能装载高度超过
1.7
米的乘用车。
二、安全车距数据处理
纵向及横向的安全车距均至少为 0.1 米,需要对乘用车型的长宽及轿运车类型的长
宽进行处理,如图 2-1 所示。
图 2-1 乘用车、轿运车空间扩展示意
乘用车型号长和宽各加
0.1
米,轿运车型号长和宽各加
0.1
米,形成乘用车与轿运
车安全存放扩展空间如表
2-1
,
2-2
所示。这样以来,在编程中原问题就转化为矩形空间
的密铺,能直接用于累加,列写不等式计算。如无特殊说明,下文的“乘用车、轿运车
长度与宽度”均指“乘用车、轿运车扩展空间长度与宽度”。
表 2-1 乘用车安全存放数据等效处理
乘用车型号 长度(米) 宽度(米) 高度(米)
I 4.71 1.8 1.51
II 3.715 1.705 1.394
III 4.73 1.885 1.77
更多数学建模资料请关注微店店铺“数学建模学习交流”
https://k.weidian.com/RHO6PSpA
4
表 2-2 轿运车安全存放数据等效处理
轿运车类型 上下层长度(米) 上层宽度(米) 下层宽度(米)
1-1 19.1 2.8 2.8
1-2
24.4 3.6 2.8
三、问题分析
3.1 前三问分析
前三问要求解决在给定乘用车需求量的条件下每辆轿运车的乘用车装载方案。模型
建立的难点在于如何确定决策的对象:同种类型的轿运车可以有不同的装载方案,同种
装载方案的轿运车也可以是不同类型,所以单单取轿运车类型或者是装载方案类型作为
模型决策对象都是无效的。只有把两者结合起来,即每种类型轿运车的装载方案,作为
模型的决策对象,才能把本优化模型表达出来。
这样以来,前三问的模型建立的方法就显得非常清晰,可以分为两个阶段去考察:
1
)求解决策对象集合。通过轿运车和乘用车空间限定条件去,列举出各型轿运车
的所有可能的装载方案;
2
)优化模型建立并求解。在成本最低的目标下,通过数量限定、需求限定等条件
建立整数规划模型。
其中,可能出现的问题是:虽然这个方法理论上是可实现的,但因为决策对象集合
庞大,可能性过多,程序量过大,也许会导致寻优耗时很长甚至无法运行。因此,需要
考虑削减解决策对象集合,需要挑选出具有代表性的、装载量大的装载方案。
筛选装载方案,必须得保证模型的最优解不受影响,换一个角度看,在不影响模型
最优解的情况下,如何削减装载方案都是可行的,因为在寻优时装载量低的方案自动会
被淘汰掉。因此,注意力还是放在保留装载量大的方案,剔除装载量小的方案。
图 3-1 单辆轿运车装载方案优化思路
首先,如果让每一辆轿运车都满载,可以保证给出的每一个决策对象都是饱和的,
剔除所有能继续容纳下多一辆乘用车的方案。
5
然后,满载方案里也有效率高和效率低之分,劣势的方案肯定可以通过优势方案线
性组合得到,所以可以考虑剔除。衡量满载方案好坏的标准应该是冗余的空间,通过判
断冗余空间大小,进一步剔除低效率方案。
最后,值得注意的是,每辆轿运车都分上下两层,它们的装载方案相互独立,可以
有不同的组合,但它们又是一个整体,局部组合不同的情况下整体总和可能相同。这要
求我们先分开考虑,进行组合,然后从整车的角度出发去归并整体总和相同的方案。
综上,按照这样的思路建立的前三问模型是合理的,模型是被降维而可以求解的。
3.2 问题四分析
问题四纳入了行车路线的规划,而它的本质还是建立在前三问模型上的。如果融为
一体去考虑,决策对象就会变成每条行车路线上的每种类型轿运车装载方案,而各路线
和目的地间仍有前后连锁,可能性成倍剧增,恐怕模型十分复杂,难以解决。因此,需
要分步去拆解这个问题。
第一,要解决这个复杂的规划,可以先考察模型中轿运车需求下限,有了模型的下
限,最优解应该就在其附近,为模型建立确定方向。
第二,要使得行车成本最低,首先要保证让最节约成本的型号轿运车跑最远的距离,
以此类推。因此,一方面需要衡量轿运车节约成本的能力,可以考察轿运车上每辆乘运
车的单位距离上成本高低,它的倒数就是一辆轿运车的单位距离成本投资回报率。应用
这一指标,可以将各型号轿运车按节约成本能力排序,投资回报率高的跑远的路,以节
约成本。另一方面,需要将各目的地按距离远近进行排序,先规划距离远的点,再规划
距离近的点。以上的策略,使得问题四模型即可被拆解成由远及近目的地点上的轿运车
装载模型规划,可以转化成前三问模型求解。
第三,值得注意的是,虽然行车路线问题被转化成了由远及近的规划顺序,目的地
点上的轿运车装载模型可以用前三问模型求解,但这是一个步步为营的策略,下一点的
约束条件跟着前一点模型的结果在改变。一方面,因为远的点在规划中出现富余的空间,
富余空间可以直接提供给中途停靠点上的规划,因此,在中途停靠点乘运车需求约束要
相应减去这一项。另一方面,先把回报率高的轿运车安排给远的点,而其数量有限,所
以每一个点的规划也要更新轿运车数量约束条件。
综上,按照这样的分步策略建立的问题四模型是简洁有效的,求解过程中可以多次
使用前三问所建立的模型。
3.3
问题五分析
问题五的在问题四的基础上增加了轿运车和乘用车的复杂性,这是本质的一点。前
面考虑的满载方案实在种类过于繁多,本问不再采用。为此,首先考虑通过拆分轿运车、
归并类型等策略降低轿运车和乘用车的类型,然后重新构建优化模型。
模型的成本、路径背景与问题四基本一致,可以利用问题四的模型构建经验。
由于整个问题规模的复杂性,考虑不再规划富余空间的再利用。因为富余空间可以
根据调整换一辆长度较短的轿运车。
剩余30页未读,继续阅读
资源评论
- zjut小飞鼠No.22022-08-28资源中能够借鉴的内容很多,值得学习的地方也很多,大家一起进步!
普通网友
- 粉丝: 12w+
- 资源: 9335
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功