数学建模城市垃圾运输问题.docx
《数学建模城市垃圾运输问题.docx》由会员分享，可在线阅读，更多相关《数学建模城市垃圾运输问题.docx（18页珍藏版）》请在冰点文库上搜索。
数学建模城市垃圾运输问题
货运公司运输问题
数信学院14级信计班 魏琮
【摘要】
本文是针对解决某港口对某地区8个公司所需原材料A、B、C的运输调度问题提出的方案。
首先考虑在满足各个公司的需求的情况下，所需要的运输的最小运输次数，然后根据卸载顺序的约束以及载重费用尽量小的原则，提出了较为合理的优化模型，求出较为优化的调配方案。
针对问题一，在两个大的方面进行分析与优化。
第一方面是
对车次安排的优化分析，得出①~④公司顺时针送货，⑤~⑧公
司逆时针送货为最佳方案。
第二方面根据车载重相对最大化思
想使方案分为两个步骤，第一步先是使每个车次满载并运往同一
个公司，第二步采用分批次运输的方案，即在第一批次运输中，我们使A材料有优先运输权；在第二批次运输中，我们使B材料有优先运输权；在第三批次中运输剩下所需的货物。
最后得出耗时最少、费用最少的方案。
耗时为40.3333小时，费用为4864.0元。
针对问题二，加上两个定理及其推论数学模型与问题一几乎相同，只是空载路径不同。
采取与问题一相同的算法，得出耗时最少，费用最少的方案。
耗时为26.3小时，费用为4487.2元。
针对问题三的第一小问，知道货车有4吨、6吨和8吨三种型号。
经过简单的论证，排除了4吨货车的使用。
题目没有规定车
子不能变向，所以认为车辆可以掉头。
然后仍旧采取①~④公司顺时针送货，⑤~⑧公司逆时针送货的方案。
最后在满足公司需求量的条件下，采用不同吨位满载运输方案，此方案分为三个步骤：
第一，使8吨车次满载并运往同一公司；第二，6吨位车次满载并运往同一公司；第三，剩下的货物若在1~6吨内，则用6吨货车运输，若在7~8吨内用8吨货车运输。
最后得出耗时最少、费用最省的方案。
耗时为19.6833小时，费用为4403.2元。
一、问题重述
某地区有8个公司（如图一编号①至⑧），某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口（编号⑨）分别运往各个公司。
路线是唯一的双向道路（如图１）。
货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次（车辆每出动一次为一车次）。
每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时（不考虑塞车现象），每日工作不超过8小时。
运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。
一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。
卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量（见表１）。
问题：
1、货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输
途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。
2、每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？
应如何调度？
3、
（1）如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？
（2）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法（可结合实际情况深入分析）。
图１ 唯一的运输路线图和里程数
公司
材料
①
②
③
④
⑤
⑥
⑦
⑧
A
4
1
2
3
1
0
2
5
B
1
5
0
1
2
4
2
3
C
5
2
4
2
4
3
5
1
表１ 各公司所需要的货物量
二、模型假设
1）运输车正常出车。
2）假设运输车不会因天气状况，而影响其行驶速度，和装载、卸载时间。
3）运输路不会影响运输车行驶速度。
4）多辆运输车可以在港口同时装车，不必等待。
5）8个公司之间没有优先级别，货运公司只要满足他们的需求量就可以。
三、问题分析
运输过程的最大特点是三种原料重量不同，分为大小件，当大小件同车，卸货时必须先卸小件，而且不允许卸下来的材料再装上车，要区别对待运输途中是否可以调头的费用。
在问题一中，运输途中不能调头，整个送货路线是一个环形闭合回路，如果沿着某一方向同时给多家公司送货时，运输车必须为距离港口近的公司卸下小件，为距离港口远的公司运送大件；而在问题二中，运输途中可以调头，可以首先为远处公司运送小件，在返回途中为距离较近的公司卸下大件。
从表面上看，这样运输能够节省车次，降低出车费用。
但通过分析，在本题中，载重调头运输并不能降低费用。
运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成本、载重费用和空载费用。
建立模型时，要注意以下几方面的问题：
目标层：
如果将调度车数、车次以及每车次的载重和卸货点都设为变量，模型中变量过多，不易求解。
由于各辆运输车之间相互独立，可以将目标转化为：
求解车次总数和每车次的装卸方案，安排尽量少的车辆数，每车次尽量满载，使总的运费最小。
约束层：
（1）运输车可以从顺时针或者逆时针方向送货，要考虑不同方向时
的载重费用；
（2）大小件的卸车顺序要求不同原料搭配运输时，沿途必须有序卸货;
（3）每车次的送货量不能超过运输车的最大载重量；
（4）满足各公司当日需求。
四、符号说明和名词约定
表2
符号
含义
单位
备注
s1（n）
从港口到各个公司的货运最短里程集
公里
n=1、2、…、8;
s2（n）
卸载后从各公司返回港口的最短空载里程集
公里
n=1、2、…、8;
w（n）
两批次货物运至第n公司货物的总重量集
吨
n=1、2、…、8;
times（n）
两批次货物运至第n公司的总次数集
次
n=1、2、…、8;
times（j,n）
两类货车运至第n公司的次数集
次
n=1、2、…、8;
j=1、2;
yd
第d问中组合运输的费用集
元
d=1、2、3；
charge（d）
第d问中所有的运输费用集
元
d=1、2、3；
ttd
第d问中组合运输的耗时集
小时
d=1、2、3；
Time（d）
第d问中所有的运输耗时集
小时
d=1、2、3；
五、建立模型
一、问题一
i.车次规划模型的分析
在符合载重相对最大化情况下，①~④公司顺时针送货为最佳方案，⑤~⑧公司逆时针送货最佳方案。
ii.模型建立
根据车辆载重条件，可分为四种满载方案：
第1种是每个车次装载2个单位B；第2种是每个车次装载6个单位C；第3种是每个车次装载1个单位A和2个单位C；第4种是每个车次装载1个单位B和3个单位C。
但基于要使总运费最少以及满足各公司每日需求。
筛选出两种运载方案：
第1种为每个车次装载1单位A和2单位C；第2种是每个车次装载2个单位B。
并使每一车次在同一公司卸货。
具体程序见附录一。
然后，第一批次运输，我们使A材料有优先运输权，在保证满足各公司对A需求量条件下，1C与1A搭配满足载重相对最大化方法运输；第二批次运输，我们使B材料有优先运输权，在此次运输我们满足各公司尚缺B材料的量小于或等于2个单位；第三批次运输剩下所需的货物。
由此可知共出车28次。
如下表：
表3
车辆
车次数
公司
货物
时间
（小时）
运费（元）
各车工作时间（小时）
1
1
1
A,2C
1.4167
107.2
7.0835
2
1
A,2C
1.4167
107.2
3
2
A,2C
1.4167
180
4
3
A,2C
1.4167
273.6
5
3
A,2C
1.4167
273.6
2
6
4
A,2C
1.4167
325.6
7.0835
7
5
A,2C
1.4167
263.2
8
7
A,2C
1.4167
138.4
9
7
A,2C
1.4167
138.4
10
2
2B
1.4167
180
3
11
2
2B
1.4167
180
7.0835
12
5
2B
1.4167
263.2
13
6
2B
1.4167
180
14
6
2B
1.4167
180
15
7
2B
1.4167
138.4
4
16
8
2B
1.4167
76
7.0835
17
8
A,C
1.4167
67
18
8
A
1.4167
58
19
8
A
1.4167
58
20
8
A
1.4167
58
5
21
8
A
1.4167
58
6.1334
22
1
A,C
1.4167
92.8
23
1
A
1.4167
78.4
24
1，2
2B
1.5833
142.2
6
25
4
A
1.4167
221.2
6.0333
26
4
A
1.4167
221.2
27
7,6，5
6C
1.75
198.4
28
8，4
2B
1.5833
206
iii.目标分析
运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成本、载重费用和空载费用。
符号说明和名词约定见表2。
操作程序见附录二。
最后经过模型的计算,运输总费用为4864元，运输总时间为40.3333小时。
二、问题二
i.车次规划模型的分析
运载里程与空载里程相同（表四中的第28车次例外），且每次出车均不绕圈工作。
车辆载重行程是各公司到港口的最短路，且载重费用固定不变。
ii.模型建立
根据第
（1）问的分析，分为两种满载方案：
第1种为每个车次装载1单位A和2单位C；第2种是每个车次装载2个单位B。
并使每一车次在同一公司卸货。
然后，采用批次运输方案：
第一批次运输，使A材料有优先运输权，在保证满足各公司对A需求量条件下，C与A搭配满足载重相对最大化方法运输；第二批次运输，使B材料有优先运输权，在此次运输满足各公司尚缺B材料的量小于2个单位；第三批次运输剩下的货物。
最终车次运载方案如下表：
表4
车辆
车次
公司
货物
时间（小时）
运费
各车工作时间（小时）
1
1
1
A,2C
0.6834
89.6
7.2837
2
1
A,2C
0.6834
89.6
3
2
A,2C
0.9167
168
4
3
A,2C
1.2167
268.8
5
3
A,2C
1.2167
268.8
6
4
A,2C
1.3834
324.8
7
5
A,2C
1.1834
257.6
2
8
7
A,2C
0.7834
123.2
7.7838
9
7
A,2C
0.7834
123.2
10
2
2B
0.9167
168
11
2
2B
0.9167
168
12
5
2B
1.1834
257.6
13
6
2B
0.9167
168
14
6
2B
0.9167
168
15
7
2B
0.7834
123.2
16
8
2B
0.5834
56
3
17
8
A,C
0.5834
47
4.2838
18
8
A
0.5834
38
19
8
A
0.5834
38
20
8
A
0.5834
38
21
8
A
0.5834
38
22
1
A,C
0.6834
75.2
23
1
A
0.6834
60.8
4
24
1，2
2B
1.0833
130.2
6.9501
25
4
A
1.3834
220.4
26
4
A
1.3834
220.4
27
7，6，5
6C
1.5167
192.8
28
8，4
2B
1.5833
206
iii.目标分析
运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成本、载重费用和空载费用。
符号说明和名词约定见表2。
操作程序见附录三。
最后经过模型的计算,运输总费用为4487.2元，运输总时间为26.3000小时。
三、问题三
第
（1）小问：
根据第题目分析，题目中给出了3种型号的货车，4吨，6吨，8吨。
而且没有规定不能掉头，故认为可以掉头。
假设在距离港口ｘ公里的地方，需要货物Ｍ吨，则使用4吨和8吨货车运送的费用如下（因为将Ｍ吨货物运送到目的地的载重费是相同的，故只关注空载费用和出车费用）
4吨货车运送费用，M/4*（0.2*+10）；
8吨货车运送费用，M/8*（0.7*+10）；
当ｘ>33.3时，使用4吨货车运输比8吨货车更省费用。
然而在允许掉头的情况下，按之前方案进行运送，没有超过33.3公里。
所以不需要使用4吨货车，只使用6吨，8吨货车搭配运货即可。
i.模型建立
第一步，使8吨车次满载并运往同一公司；
第二步，使6吨位车次满载并运往同一公司；
运载方案如下表：
表5
车辆
车次
公司
货物
时间（小时）
运费
各车工作时间（小时）
第一辆8吨车
1
1
2A
0.6834
120.8
6.9504
2
1
2A
0.6834
120.8
3
1
B,5C
0.6834
120.8
4
2
A,B,C
0.9167
226.5
5
3
2A
1.2167
362.4
6
4
2A
1.3834
437.9
7
4
A,B,C
1.3834
437.9
第二辆8吨车
8
5
A,B,C
1.1834
347.3
5.4171
9
6
2B,2C
0.9167
226.5
10
7
2A
0.7834
166.1
11
7
2B,2C
0.7834
166.1
12
8
2A
0.5834
75.5
13
8
2A
0.5834
75.5
14
8
A,B,C
0.5834
75.5
第一辆6吨车
15
2
2B
0.9167
168
7.3169
16
2
2B
0.9167
168
17
5
B,3C
1.1834
257.6
18
6
2B
0.9167
168
19
8
2B
0.5834
56
第三步，经计算可知只剩下2,3,4,6,7公司需要C货物10吨，必须要用至少两个车次来运。
为了使费用降低，决定用2个6吨车次来运货，具体运载方案如下表：
表6
车辆
车次
公司
货物
时间
（小时）
运费
各车工作时间（小时）
第一辆6吨车
20
2，3，4
1C，4C，1C
1.7167
263.6
1.7167
21
7,6
3C,1C
1.0833
92.4
1.0833
ii.目标分析
运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成本、载重费用和空载费用。
符号说明和名词约定见表2。
操作程序见附录四。
最后经过模型的计算,运输总费用为4403.2元，运输总时间为19.6833小时。
第
（2）小问：
当部分公司接通后，对于各个车辆的运输安排并不改变，就是找到通往该公司的路径最短，使总的运输费用最少，但是由于连通了各个公司的路径变得复杂，因此我们就忽略空载时的返回路径，仅仅考虑每一吨货物以最短的路径到达目的地。
此问题就可以看作是无向图来研究路线拓扑图，将所有公司和港口看作是节点，得到各节点之间最短的距离矩阵如下，
A9*9=[a11,a12```a19;a21,a22```a29;```;a91,a92```a99]其中aij表示公司i到公司j的最短路径，当aij不存在时，记为无穷大，由Dijkstra算法得到港口九到其他公司的最短路径，按照最短路径运输货物可以将费用降到最低。
六、附录
附录一:
model:
sets:
num/1..4/:
x,a,b,c;
endsets
data:
a=0,0,1,0;
b=2,0,0,1;
c=0,6,2,3;
enddata
min=@sum（num（i）:
x（i））;
@sum（num（i）:
a（i）*x（i））>=18;!
满足A类货物总数
@sum（num（i）:
b（i）*x（i））>=18;!
满足B类货物总数
@sum（num（i）:
c（i）*x（i））>=26;!
满足C类货物总数
end
附录二：
clc
s1=[8,15,24,29,23,15,11,5];
s2=[52,45,36,31,37,45,49,55];
w=[21,18,12,14,12,12,18,27];
times=[4,3,2,3,2,2,3,6];
tt1=4.9166;
y1=576.6;
sum1=0;
sum2=0;
sum3=0;
forn=1:
8
sum1=sum1+1.8*s1（n）*w（n）;
sum2=sum2+0.4*s2（n）*times（n）;
sum3=sum3+10*times（n）;
end
change
（1）=120+y1+sum1+sum2+sum3;
disp（'问题一运输总费用：
'）;
disp（change
（1））;
tt=0;
forn=1:
8
tt=tt+times（n）*（1+5/12）;
end
Time
（1）=tt1+tt;
disp（'问题一运输总时间：
'）;
disp（Time
（1））;
结果为：
问题一运输总费用：
4.8640e+003
问题一运输总时间：
40.3333
附录三：
clc
s1=[8,15,24,29,23,15,11,5];
w=[21,18,12,14,12,12,18,27];
times=[4,3,2,3,2,2,3,6];
tt2=4.1833;
Y2=559;
sum1=0;
sum2=0;
sum3=0;
forn=1:
8
sum1=sum1+1.8*s1（n）*w（n）;
sum2=sum2+0.4*s1（n）*times（n）;
sum3=sum3+10*times（n）;
end
change
（2）=80+y2+sum1+sum2+sum3;
disp（'问题二运输总费用：
'）;
disp（change
（2））;
tt=0;
forn=1:
8
tt=tt+times（n）*（5/12+s1（n）/30）;
end
Time
（2）=tt2+tt;
disp（'问题二运输总时间：
'）;
disp（Time
（2））;
结果为：
问题二运输总费用：
4.4872e+003
问题二运输总时间：
26.3000
附录四：
clc
s1=[8,15,24,29,23,15,11,5];
w=[0,12,0,0,6,6,0,6;24,8,8,16,8,8,16,24];
times=[0,2,0,0,1,1,0,1;3,1,1,2,1,1,2,3];
tt3=2.8;
y3=376;
sum1=0;
sum2=0;
sum3=0;
forn=1:
8
sum1=sum1+1.8*s1（1,n）*（w（1,n）+w（2,n））;
sum2=sum2+0.4*s1（1,n）*times（1,n）+0.7*s1（1,n）*times（2,n）;
sum3=sum3+10*（times（1,n）+times（2,n））;
end
change（3）=60+y3+sum1+sum2+sum3;
disp（'问题三运输总费用：
'）;
disp（change（3））;
tt=0;
forn=1:
8
forj=1:
2
tt=tt+times（j,n）*（5/12+s1（n）/30）;
end
end
Time（3）=tt3+tt;
disp（'问题三运输总时间：
'）;
disp（Time（3））;
结果为：
问题三
（1）运输总费用：
4.4032e+003
问题三
（1）运输总时间：
19.6833
（注：
可编辑下载，若有不当之处，请指正，谢谢!
）
升级会员 