数模论文.docx
《数模论文.docx》由会员分享,可在线阅读,更多相关《数模论文.docx(28页珍藏版)》请在冰点文库上搜索。
数模论文
2013第十届五一数学建模联赛
承诺书
我们仔细阅读了五一数学建模联赛的竞赛规则。
我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与本队以外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其它公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。
如有违反竞赛规则的行为,我们愿意承担由此引起的一切后果。
我们授权五一数学建模联赛赛组委会,可将我们的论文以任何形式进行公开展示(包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等)。
我们参赛选择的题号为(从A/B/C中选择一项填写):
C
我们的参赛报名号为:
2013200244
参赛组别(研究生或本科或专科):
本科
所属学校(请填写完整的全名)山东科技大学
参赛队员(打印并签名):
1.杨斌
2.王颖
3.管雯瑞
日期:
2013年5月1日
获奖证书邮寄地址:
山东省青岛经济技术开发区前湾港路579号邮政编码266510
2013第十届五一数学建模联赛
编号专用页
竞赛评阅编号(由竞赛评委会评阅前进行编号):
评阅记录
评
阅
人
评
分
备
注
裁剪线裁剪线裁剪线
竞赛评阅编号(由竞赛评委会评阅前进行编号):
参赛队伍的参赛号码:
(请各参赛队提前填写好):
2013200244
2013第十届五一数学建模联赛
题目整车物流调度系统的优化设计
摘要
本文围绕整车物流调度系统在不同的约束条件下进行了优化设计。
对多起运地和多目的地的物流运输问题,考虑小汽车分级标识,考虑货车评级分数的问题分别建立了相应的模型,并计算出对应的运输最低成本及运单结果。
对问题一,分析题意后可以看出本题属于普通的运输优化问题。
需建立0-1优化及多层次线性规划模型并借助于LINGO软件进行最优解的求解。
对问题二,分析附件二中的数据以及题意之后,可以看出本题属于多起运地对多目的地的物流运输问题,如果只考虑以单个起运地进行优化,效果不佳,故我们先将相邻的目的地和同一目的地的不同订单进行聚类分析,在保证最优解的前提下,进行近似运算。
除此之外,本题还增加了分级以及货车附近调度和顺途运输问题,显然采取简单的线性优化模型是不可行的。
因此,我们可以采取启发式算法(遗传结合模拟退火),由局部最优到全局最优,逐步递进,借助MATLAB数学软件进行最优解的求解。
对问题三,分析题意,问题三在问题二的基础上又增加了评级分数,显然需要考虑调运货车的顺序。
但运输成本与货车的评级分数间有主次关系,因此需要考虑两者的权重,即货车优先运输的可能性。
关键词:
线性规划模型0-1优化聚类分析遗传结合模拟退火算法
一.问题重述
随着我国经济突飞猛进的发展,物流成为社会分工中重要的环节。
物流系统的优劣也影响了业务流程的运行效率及其成本。
国内某家物流公司的主要业务是从分布在全国的M个主机厂,将N种品牌商品小汽车调运到全国多个城市的4S店。
请为该物流公司设计一套物流运输优化系统,以提高物流运输效率、优化运营成本。
本题目不考虑小客车类型的差异,在运输过程中产生的主要运输成本包括:
运输商品小汽车的业务费为0.7元/(公里·辆),货车运输途中因部分车位空闲而产生的空载运输成本为0.2元/(公里·车位),油耗动力成本为0.5元/公里,货车过路费用为0.4元/公里。
问题1:
建立数学模型考虑从某个主机厂调度货车来完成运输订单,如何安排货车,可以保证在完成运输任务的基础上运输成本最低。
请用附件1中的数据来验证你的模型,并根据你的结果给出运单方案。
允许将不同订单用同一货车运输,但是不允许将同一订单拆分用不同货车运输;一个运力货车运单的目的地城市的数量不超过3个。
说明:
车位是指一个货车最多能运输小客车的数量。
问题2:
由于小客车品牌不同,因此在运输的时候将小汽车进行了分级标识,级别最高的为1,在同一个起运地优先安排货车运输这些级别高的小汽车。
如果货车有剩余车位,则可以顺途运输其他城市的订单;如果起运地货车数量不足,可以从附近城市调运货车来运输本地订单。
请建立数学模型,考虑如何安排货车,可以保证在完成运输任务的基础上运输成本最低。
结合附件2中的数据,进行求解并给出运单。
问题3:
每辆货车对公司物流运输系统的价值和效率是不同的,通过对每一辆货车的运输汽车质损率、及时到达率、信息反馈率和服务态度等多方面进行跟踪评价,可以得到货车的评级分数,分数越高说明运输质量和效率越好。
故在安排货车运输方案的时候,首先考虑运输成本最小,其次优先安排车辆评级分数较高的货车,在问题2的基础上,利用附件3中的数据进行求解并给出新的运单。
二.基本假设
(1)不考虑天气等客观因素对货车运输的影响
(2)不考虑小客车类型的差异
(3)假设不同货车在里程数一定的情况下所用时间相同
(4)本题中所给任意两地之间均满足运输条件
(5)每一个起运地都有一个固定的供应量,所有的供应量都必须配送到各个销地
(6)每一个目的地都有一个固定的需求量,整个需求量都必须由起运地满足
三.符号说明
符号
含义
从起运地i到目的地j第k个订单的小汽车数量
编号为m的货车的车位数
从起运地i到目的地j的订单个数
货车m装载从起运地i运往目的地j的小汽车数
0-1变量1表示货车m装载从起运地i运往目的地j的第k个订单
货车m的评级分数
从起运地i到目的地j第k个订单的小汽车品牌等级
从起运地i到目的地j的里程数
从目的地s到目的地t的里程数
货车m运载小汽车的目的地个数
单位里程数运输一辆小汽车的路费
单位里程数运输途中空闲一个车位的运输成本
单位里程数的油耗成本
单位里程数货车的过路费用
起运地i到j的小汽车订单的权重
从起运地i到目的地j第k个订单小汽车优先运输
货车m优先等级的权重
L
起运地i到目的地j的成本度量
从起运地i到目的地j第k个订单小汽车优先运输的可能性
货车m在起运地的装载数
W
运输总成本
表示货车m的分级分数
M
货车优先运输的可能性
四.问题分析
对问题一,分析题意后可以看出本题属于普通的运输优化问题。
由于附件1中给出的数据较多,显然需要借助数学软件进行处理。
题目中给出几个不同的约束条件,同一货车运输到同一目的地的订单具有不确定性以及每个目的地所用的货车也具有不确定性,因此我们需建立0-1优化及多层次线性规划模型并借助于LINGO软件进行最优解的求解。
对问题二,分析附件二中的数据以及题意之后,可以看出本题属于多起运地对多目的地的物流运输问题,如果只考虑以单个起运地进行优化,效果不佳,故我们先将相邻的目的地和同一目的地的不同订单进行聚类,在保证最优解的前提下,进行近似运算。
除此之外,本题还增加了分级以及货车附近调度和顺途运输问题,显然采取简单的线性优化模型是不可行的。
因此,我们可以采取启发式算法(遗传结合模拟退火),由局部最优到全局最优,逐步递进,借助MATLAB数学软件进行最优解的求解。
对问题三,分析题意,问题三在问题二的基础上又增加了评级分数,显然需要考虑调运货车的顺序。
我们通过评级分数可以确定调运某辆货车的可能性,可近似认为是蚁群算法中的诱导因素,再结合问题二中已建好的模型加以求解。
五.模型的建立和求解
问题一在将不同订单用同一货车运输,但是不允许将同一订单拆分用不同货车运输;一个运力货车运单的目的地城市的数量不超过3个的约束条件下,求出最低成本。
模型一
根据对问题一的分析,做出的0-1优化多起运地多目的地线性规划模型如下:
约束条件:
(1)任意货车装载的小汽车总量不能超过该货车的最大车位数
m=1,2,…,
(2)
=
货车m装载从起运地i运往目的地j的第k个订单时,
=1,否则,
=0
(3)任意货车均不能完全空载
i=1,2,…
(4)货车m装载从起运地i运往目的地j的小汽车数
与从起运地i到目的地j第k个订单的小汽车数量
满足下列等式:
=
j=1,2,…
(5)货车m在起运地的装载数
与货车m装载从起运地i运往目的地j的小汽车数
满足下列等式:
i=1,2,…
目标函数:
minW=
由于起运地唯一,i就成为定值,故模型可以简化为
单起运地多目的地运输优化模型:
(1)
(2)不变
(1-1)
=
j=1,2,…(1-2)
(1-3)
目标函数minW=
为了计算方便,我们对不同的目的地和同一目的地的不同订单进行编号,生成矩阵。
下图为部分数据,细见附件1.1
订单编号
1
2
3
4
5
6
7
蒙城
3
7
0
0
0
0
0
福州
10
10
7
1
2
10
10
龙岩
4
1
0
0
0
0
0
三明
3
7
0
0
0
0
0
兰州
5
10
5
10
10
0
0
南宁
10
10
0
0
0
0
0
贵阳
10
0
0
0
0
0
0
里程数
蒙城
福州
龙岩
三明
兰州
南宁
贵阳
蒙城
0
1225
1149
1010
1161
1779
1732
福州
1225
0
392
233
2546
1636
1771
龙岩
1149
392
0
221
2334
1309
1548
三明
1010
233
221
0
2200
1304
1487
兰州
1161
2546
2334
2200
0
2265
1707
南宁
1779
1636
1309
1304
2265
0
576
贵阳
1732
1771
1548
1487
1707
576
0
蒙城
福州
龙岩
三明
兰州
南宁
贵阳
北京
884
1965
2244
1834
1630
2483
2447
编号
1
2
3
4
5
6
7
车位数
10
20
20
20
15
20
10
利用lingo编写代码(见附件1.2)计算处理好的数据(见附件1.1)。
运行结果见附件1.3。
对结果分析,得如下结论:
运费最低:
334403.3元
运单结果:
货车编号对应目的地如下表:
地点
蒙城
福州
龙岩
三明
兰州
南宁
贵阳
货车编号
1
10、14、15
5
5
16、17
19
7
地点
遵义
漯河
商丘
郑州
大庆
牡丹江
常德
货车编号
20
27、28
27、28
31
18
22
32
地点
长沙
长春
葫芦岛
盘锦
沈阳
包头
银川
货车编号
23
40
26
43
42
44
24、25
地点
东营
济南
青岛
日照
成都
达州
自贡
货车编号
34
35
37、38
37、38
3、12
45
46
地点
杭州
桐乡
金华
宁波
衢州
货车编号
9
29
41
41
30
问题二考虑小汽车的优先分级,如果起运地货车数量不足,可以从附近城市调运货车且在有剩余车位时可以顺途运输。
在完成如上运输任务的前提下,求最低运输成本。
模型二
根据对问题二的分析,显然多了汽车优先分级的约束,所以应对模型一加以改进,引进自定义分级变量,加以对模型一的约束,即单优先级多起运地多目标优化模型
建模如下:
定义
=
/
表示从起运地i到目的地j第k个订单小汽车优先运输的可能性,仅影响货车安排次序
引用模型1保持
(1)
(2)(3)(4)(5)不变
目标函数minW=
由于本问题涉及多起运地且订单过于分散,如果只考虑单个,比例太小,不便求解最优解,为了在保证最优解不变且计算方便,可以采用聚类分析思想,将数据处理如下:
起运地
终点站
小汽车数量
里程数
成都市
漯河市
14
1295
成都市
郑州市
8
1278
天津市
邯郸市
10
480
天津市
邢台市
6
432
重庆市
北京市
11
1876
芜湖市
亳州市
21
419
芜湖市
巢湖市
14
70
芜湖市
合肥市
10
135
北京市
安庆市
10
1205
北京市
合肥市
34
1038
此表仅为部分数据,详细表格见附件2-1
顺途运输的目的地间里程表
漯河
商丘
郑州
大庆
牡丹江
常德
漯河
0
201
163
2081
2299
683
商丘
201
0
226
2030
2248
875
郑州
163
226
0
2113
2255
788
大庆
2081
2030
2113
0
540
2708
牡丹江
2299
2248
2255
540
0
2923
常德
683
875
788
2708
540
0
此表仅为部分数据,详细表格见附件2-1
由于优先级制约条件,单纯依靠lingo优化达不到目的,因此需要借助matlab进行计算。
但是模型中变量较多,需要借助遗传算法进行matlab编程,现将遗传算法的思想介绍如下。
其一般性算法可以描述为:
(1)初始化进化计数器。
(2)随机产生初始种群
设定初始规模
(3)以概率α1对种群中个体进行交叉操作Crossover
,产生
(4)以概率α2对种群中个体进行变异操作Mutation
,产生
(5)以概率α3对种群进行反转操作Invertion
,产生
(6)调用模拟退火算法:
SimulatedAnnealing
,产生
(7)通过适应度函数/⑴,对中的个体适应度进行评估;
(8)将适应度最优的个体直接复制到下一代中,并按照给定概率选择其余的
个体到下一代,产生新一代
(9)重复以上步骤直到产生最优解为止。
结合上述遗传算法编写代码,见附表2-2程序运行结果见附表2-3
Ans=
0.5631457E+07
运单部分结果如下:
起运地
目的地
货车编号
起运地
目的地
货车编号
成都
郑州
192
天津
沈阳
203、204
成都
大连
193
天津
保定
206
成都
赤峰
194
天津
北京
205
成都
漯河
195
重庆
北京
236
成都
苏州
196
重庆
运城
238
成都
大连
196
重庆
广州
239
成都
洛阳
196
柳州
衡水
128
天津
阜阳
197
柳州
长治
129
天津
太原
202
柳州
邯郸
130、131
郑州
保定
151
郑州
临汾
150
注:
运单详见matlab附表2-3
问题三
问题二基础上,增加了限制条件(货车的评级分数),
也就相应需对模型二进一步限制,最终求最优解。
定义M=
/
为货车优先运输的可能性
模型三
保持模型
(1)
(2)(3)(4)(5)不变
minW=
货车分级分数数据见下表,其他数据见模型二的数据:
货车编号
车辆评级分数
1
79
0.005476223
2
56
0.00388188
3
49
0.003396645
4
99
0.006862609
5
72
0.004990988
6
62
0.004297796
7
89
0.006169416
8
63
0.004367115
9
44
0.003050049
10
25
0.001732982
11
77
0.005337585
12
70
0.00485235
13
61
0.004228476
14
18
0.001247747
15
47
0.003258006
16
92
0.006377374
17
77
0.005337585
18
75
0.005198946
19
90
0.006238736
利用matlab编码求解,matlab代码只需在原有代码基础上添加限制的限制变量即可求解。
最优解ans=0.612537E+07
求解部分运单结果如下:
起运地
目的地
货车编号
起运地
目的地
货车编号
成都
郑州
196
天津
沈阳
203
成都
大连
194
天津
保定
206、04
成都
赤峰
191
天津
北京
205
成都
漯河
195
重庆
北京
236
成都
苏州
196
重庆
运城
238
成都
大连
196
重庆
广州
239
成都
洛阳
198
柳州
衡水
129
天津
阜阳
197
柳州
长治
128
天津
太原
204
柳州
邯郸
130、131
郑州
保定
149
郑州
临汾
152
注:
matlab输出结果见3-3
六.模型的评价
优点:
在不同的约束条件下,采取了不同的数学模型,并在处理大量数据的基础上得出相应的最低成本及运单结果,基本实现了全局最优化,并且采用了MATLAB,LINGO等数学软件进行求解,使得结果更加可靠。
缺点:
1样本数据时可能不具有代表性,从而使结果产生偏差。
2.未考虑时间约束以及实际运输中存在的产销不平衡以及其他客观因素的影响。
3.在运算过程中采取了近似算法,所得结果并不完全精确。
七.参考文献
[1]徐新明,陈培友,物流调度问题的优化方法评述,商业研究,第385期:
2009年5月,107~111
[2]莫金康.智能调度系统在整车物流配送中的开发应用,技术经济,2011年05期:
36~41
[3]代红艳,李彦平,恩莉,配送问题的数学模型和遗传算法,计算机工程与应用,2005年31期:
189~192
[4]刘立波,许国银,原静,基于遗传模拟退火算法的战时物流配送路径优化研究,现代物流,29卷07期.:
2007年
[5]郭兰英,高一凡.一种运输车辆调度聚类分析模型及仿真研究,西安公路交通大学学报,第18卷第1期:
1998年1月.92~96
[6]杨启帆,数学建模,北京:
高等教育出版社,2005年
八.附录
问题一:
处理好的数据(见附件1.1)
lingo编写代码(见附件1.2)
运行结果(附件1.3)
问题二:
处理好的数据(见附件2.1)
lingo编写代码(见附件2.2)
运行结果(附件2.3)
问题三:
处理好的数据(见附件3.1)
代码(见附件3.2)
运行结果(附件3.3)
代码如下:
附件1.2
model:
sets:
YF/C1..C33/:
CI,B;
SJ/J1..J33/;
JIB(YF,SJ):
a,x;
endsets
data:
B=@ole('1.xls','bmm');
CI=@ole('1.xls','cii');
a=@ole('1.xls','aa');
enddata
min=@sum(YF(I):
((B(I)-@sum(SJ(J):
x(I,J)*a(I,J)))*f1*CI(I)+
(@sum(SJ(J):
x(I,J)*a(I,J))*f0*CI(I))+(f2+f3)*CI(I)+B(I)*CI(I)*(f1+f2+f3)));
f0=0.7;f1=0.2;f2=0.5;f3=0.4;
@for(SJ(J):
@sum(YF(I):
x(I,J))=1);
@for(YF(I):
@sum(SJ(J):
x(I,J))<=33);
@for(YF(I):
@sum(SJ(J):
x(I,J)*a(I,J))<=B(I));
@for(JIB:
@bin(x));
end
附件2.2
model:
sets:
VI/1..33/:
F;
VJ/1..33/:
JJ;
VM/1..46/:
Q;
VK/1..33/:
KK;
VC/1..33/:
CC;
VIC(VI,VC):
y,A;
VJC(VJ,VC):
z,B;
VKC(VK,VC):
m,D;
VJK(VJ,VK):
w;
VIJ(VI,VJ):
pia;
endsets
data:
F=@ole('2.xls','ffff');
w=@ole('2.xls','WW');
Q=@ole('2.xls','QQ');
A=@ole('2.xls','AA');
B=@ole('2.xls','BB');
D=@ole('2.xls','DD');
pia=@ole('2.xls','PP');
f0=0.7;
f1=0.2;
f2=0.5;
f3=0.4;
enddata
@for(VI(I):
(@sum(VC(C):
y(I,C)))<=33);
@for(VJ(J):
(@sum(VC(C):
z(J,C)))<=33);
@for(VK(K):
(@sum(VC(C):
m(K,C)))<=33);
@for(VJC(J,C):
@bin(z(J,C)));
@for(VIC(I,C):
@bin(y(I,C)));
min=@sum(VJ(J):
@sum(VK(K):
@sum(VM(S):
@sum(VI(I):
((@sum(VC(C):
y(I,C)*A(I,C))+@sum(VC(C):
z(J,C)*B(J,C))
+@sum(VC(C):
m(K,C)*D(K,C)))*F(I)*f0
+(Q(S)-(@sum(VC(C):
y(I,C)*A(I,C)))-(@sum(VC(C):
z(J,C)*B(J,C)))-(@sum(VC(C):
m(K,C)*D(K,C))))*f1*f0*F(I)
+(f2+f3)*F(I)+(@sum(VC(C):
z(J,C)*B(J,C))+@sum(VC(C):
m(K,C)*D(k,c)))*f0*pia(I,J)
+(Q(S)-(@sum(VC(C):
m(K,C)*D(K,C)))-(@sum(VC(C):
m(K,C)*D(K,C))))*f1*pia(I,J)+(f2+f3)*pia(I,J)
+(@sum(VC(C):
m(K,C)*D(K,C)))*f0*w(J,K)+(Q(S)-(@su