数学建模论文物资调度问题精选文档.docx
《数学建模论文物资调度问题精选文档.docx》由会员分享，可在线阅读，更多相关《数学建模论文物资调度问题精选文档.docx（32页珍藏版）》请在冰点文库上搜索。
数学建模论文物资调度问题精选文档
物资调度问题
摘要
“运输调度”数学模型是通过运输车运输路线的确定以及运输车调配方案的确定来使运输的花费最小.本文首先分析了物资调度中运费、载重量及各站点需求量间相互关系。
而后，紧抓住总运营费用最小这个目标，找出最短路径,最后完成了每辆运输车的最优调度具体方案.
问题一：
根据题目及实际经验得出运输车运输物资与其载重量及其行驶的路程成正比例关系，又运输的价格一定,再结合题目给出的条件“运输车重载运费2元/吨公里"，其重载运费的单位“元/吨公里"给我们的启发。
于是结合题目给定的表，我们将两个决策变量（载重量，路程）化零为整为一个花费因素来考虑，即从经济的角度来考虑.同理我们将多辆车也化零为整，即用一辆“超大运输车”来运输物资。
根据这样从经济的角度来考虑,于是我们将需求点的需求量乘入需求点的坐标得到一个新的表，即花费经济表，我们再运用数学软件作出一个新的坐标，这样可以得到一个花费坐标.于是按照从经济花费最少的角度，根据我们所掌握的最短路径及算法再结合数学软件，可求得经济花费坐标上的最短路径。
具体求法上，采用了算法结合“最优化原理”，先保证每个站点的运营费用最小，从而找出所有站点的总运营费用最小,即找出了一条总费用最低的最短路径。
用我们的“超大运输车"走这条最小花费的路线,我们发现时间这个因素不能满足且计算结果与实际的经验偏差较大。
于是我们重新分配路线，并且同时满足运输车工作时间这个因素的限制，重新对该方案综合考虑，作出了合理的调整.此处我们运用了“化整为零"的思想，将该路线分为八条路径。
同时也将超大车进行分解，于是派八辆运输车向29个需求点运送物资.同样的道理我们也将运输车运送物资从经济的角度看，即将运量乘以其速度，又因运输的价格一定,因此便可以将运输车在整体上从经济考虑。
于是便可以将整体从经济上来考虑。
将运输最小花费转化从经济方面来考虑比较合理。
由此可求解出运输车全程的最低费用：
结合各约束条件求得最低费用为1980。
16元。
问题二：
由题目知运输车的载重量不同,但由于我们从整体的经济上来考虑运输物资的花费最少问题,因此花费坐标的最短路径仍然不变.因此结合运输车工作时间的这个因素,我们仍用问题一的思路,运用“化零为整”,“化整为零"的思想来考虑第二问。
按照这样的的思路我们制定了八条路线，派了七辆运输车来运送物资。
同样在整体上对问题从经济上来考虑比较合理。
结合各约束条件求得最低费用为1969.66元，需要7辆车
关键词：
物资调度最短路线最优化原理Dijkstra算法0—1规划
一、问题重述
1。
1.背景资料与条件
某城区有29个物资需求点，需求点的地理坐标和每天物资的需求量见如下表一.（表一为原表截取的一部分,原表其余部分见附录一）。
每天凌晨都要从仓库（第30号站点）出发将物资运至每个需求点.现有已知一种运输车,载重6吨，运输车平均速度为40公里／小时，每台车每日工作4小时,每个需求点需要用10分钟的时间下货。
运输车重载运费2元/吨公里,空载费用0。
5元/公里；并且街道方向均平行于坐标轴.
29个需求点物资需求量及地理坐标
站点编号
需求量T
坐标（km）
站点编号
需求量T
坐标（km）
x
y
x
y
1
2.50
3
2
16
1.50
2
16
2
1.00
1
5
17
0。
80
6
18
3
1.50
5
4
18
1。
50
11
17
4
1.20
4
7
19
0。
90
15
12
5
0。
85
0
8
20
1。
40
19
9
6
1.30
3
11
21
1。
20
22
5
下图为29个需求点的地理坐标示意图:
图一：
各需求点地理坐标图
1.2.需要解决的问题
问题一：
在运输车的载重固定为6吨的情况下，为使运输费用最小，怎样调动运输车（包括运输车的数量，每台车的运营路线及费用）.
问题二：
在运输车的载重分为三类（四吨，六吨，八吨）的情况下，为使运输费用最小，怎样调动运输车（包括运输车的数量,每台车的运营路线及费用）。
二、问题分析
2.1。
问题的重要性分析（社会背景）
现代社会经济高速发展,各种信息物资交流频繁,特别是当今，对如何优化物资分配，降低经济成本，时间成本的要求十分迫切。
研究在使费用最小情况下的物资调度问题，对于满足各地物资需求，优化资源配置，促进经济社会发展具有十分重要的意义。
2.2.有关方面在这个问题上做过的研究
［2］物流配送车辆优化调度问题最早是由学者Dantzig和Ramser于1959年首次提出的，国外一般称之为vehicleroutingproblem或vehicleschedulingproblem。
一般以为，不考虑时间要求，仅根据空间位置安排线路时称为车辆线路安排问题VRP;考虑时间要求，安排线路时称为车辆调度问题VSP。
目前针对车辆优化调度问题的求解算法可以说是相当丰富,根据对这些算法本质的分类研究,基本上可以分为精确算法和启发式算法两大类。
精确算法指可求出最优解的算法，主要有分枝定界法、割平面法、网络流算法和动态规划法。
精确算法的计算量一般随问题规模的增大而呈指数增长，所以多用于规模较小的问题。
启发式算法是指一种基于直观或经验构造的算法，目标是在可接受的花费（计算时间、占用空间等）下得出待解决问题的满意解,而不是最优解。
考虑到VRP是强NP难题,而启发式方法能够比较快地得到满意解，这对解决NP难题来说有着不可估量的作用.因此大部分文献中专家们主要是在构造各种高质量的启发式算法.
2。
3.问题的思路分析
仓库物资由运输车进行调运。
每辆车的工作时间不超过4小时，并且每辆车的载重不能超过6吨。
若调运的需求地点已经明确,为了使运费最小，必须用最少的车在允许的工作时间内把需要运送的物资运送到需求地点，因此选择什么样的调运路线和派遣多少车辆显得尤为重要。
本论文试图从最短路程和最小花费的角度，建立起满足调运费用最少且调用车辆最少的数学模型,求出仓库派遣的车辆的数量和运送路线。
问题一的分析:
2.3。
1。
“化零为整”，求最短路
本题要求在使总运输费用最小的情况下，安排这29个运输点的车辆调度方案。
先考虑运输车运往各个需求地的总运输最小费用。
假设从仓库（0，0）点开始，车先运往地，此时运费最小；再运往地,保证从地到地的总运费也是最小的；车再运往地,保证此时地与地的运费仍是最小;即若每两地之间的运输费用都是最小的，那么将所有联通的两个需求地的运费求和仍是最少的运费。
即假设为地和地的最小运输费用，为0-1变量，即两地与若联通，则为1,若两地不连通，则为0。
在运输车运往个需求点的过程中,总运输最小费用为：
针对地，根据实际情况，其运输费用与该地的需求量及地到地的距离均成正比,故将地的需求量和地理位置合成一个新量（），仓库（0,0）到各个需求点的最短路径即为总运输费用最小的路径。
2。
3。
2求总最小运输费用
在运输车从各个需求点回到仓库的过程中,由于最短路已经确定,因而返回时按每条运输路线上终止需求点到仓库的最短路径，就可求出整个运输车运送物资与返回全过程的最小费用.
即在运输车往返需求点的全过程中的最小费用为
2.3.3。
化整为零，调度车辆，分配每辆车运输线路
根据本文前部分的求解，能求出从仓库到29个需求点的最短物资调度线路，则调度车辆要考虑的因素是使总运费最小及使用的车辆尽量少。
因为在实际物资调度过程中，派出一辆车的固定费用远高于一辆车的行驶费用,因此调度的车辆尽可能少也是优化车辆调度的一个重要考虑因素。
本文在此提供两种方案。
第一种方案：
假设每辆运输车满载,即载重均为6吨，假设运输车在运到第个运输点时，将6吨货全部卸完，此时运输到地的物资小于地的需求量，则车返回，车继续往地送货,满足地的需求量后继续前进，按此种运输方式运输往各个需求地的需求量，直至第29个需求点。
即在此过程中,假设有一辆“超级大车”，载重了29个需求点的全部物资，每到一个需求点,就
卸下一部分物资,直至最后一个需求点。
第二种方案:
假设每辆运输车不一定满载，车在运送完最短路上指定的几个需求点后，即空载返回，车沿着最短路线，继续运送物资.即在此种方案下，每个需求点只有一辆车来运送物资。
问题二的分析：
在第一问已求出最短路的前提下，第二问中提供了三种载重不同的运输车。
即在这种条件下,能够继续优化调度方案，使载重大的车（8吨的车），运送离仓库较近的需求地的物资，使这几个需求地的物资总和尽量接近于8吨.载重越小的车，运往的需求地离仓库越远。
因为大车的运营成本最高。
（大车载重多，因而每公里的运输费用最高）.
思路图：
三、基本假设
结合本题的实际，为了确保模型求解的准确性和合理性，我们排除了一些位置因素的干扰，提出以下几点假设：
3。
1．问题一的假设
1.每辆车载重不同时速度均相等.
2。
忽略运输车加速和制动的速度变化及时间的影响。
3。
不考虑汽车在红绿灯，堵车，恶劣天气状况时的延误时间。
4.每辆车派出的人工成本,装卸货等固定成本忽略不计。
5。
供应物资的公司能够提供足够多的车辆。
6.假设不考虑其他因素，第j个需求点的运费与第j个需求点的需求量及仓库到第j个需求点的位置均成正比.
3。
2．问题二的假设
1.本题求解最小费用不考虑实际情况中三种载重不同的运输车的固定成本的差异.
2、不考虑三种载重不同的运输车速度的不同。
3。
3。
本文引用的数据、资料均真实可靠。
四、符号说明
为了便于问题的求解，我们给出以下符号说明：
（其他未说明的符号在文中第一次出现时会做详细的说明。
）
符号
意义
第i辆车
需求点
需求点和需求点之间的距离
需求点的物资需求量
需求量乘位置后需求点的合成坐标
0—1变量
需求点和需求点之间的费用
第辆车的总运输费用
：
注一:
注二：
，其中、均为题中所给的第个需求点的横纵坐标.
五、模型的建立与求解
5.1.问题一的求解
5。
1.1模型一概述
算法[3]：
算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。
主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止.算法能得出最短路径的最优解.
算法描述：
（这里描述的是从节点1开始到各点的算法，其中表示的边的权值，即为最短路径值）
1．置集合数组,（1,之间存在边）or+无穷大（1.之间不存在边）
2．在中，令，令，若为空集则算法结束,否则转3
3．对全部属于,如果存在边,那么,转2
算法思想为：
设是一个带权有向图，把图中顶点集合分成两组,第一组为已求出最短路径的顶点集合（用表示,初始时中只有一个源点，以后每求得一条最短路径,就将加入到集合中，直到全部顶点都加入到中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用表示），按最短路径长度的递增次序依次把第二组的顶点加入中。
在加入的过程中，总保持从源点到中各顶点的最短路径长度不大于从源点到中任何顶点的最短路径长度.此外,每个顶点对应一个距离，中的顶点的距离就是从到此顶点的最短路径长度，中的顶点的距离，是从到此顶点只包括中的顶点为中间顶点的当前最短路径长度.
算法具体步骤
（1）初始时，只包含源点,即＝的距离为0。
包含除外的其他顶点，中顶点距离为边上的权（若与有边）或）（若不是的出边邻接点）.
（2）从中选取一个距离最小的顶点，把加入中（该选定的距离就是到的最短路径长度）.
（3）以为新考虑的中间点,修改中各顶点的距离；若从源点到顶点（）的距离（经过顶点）比原来距离（不经过顶点）短，则修改顶点的距离值，修改后的距离值的顶点k的距离加上边上的权。
（4）重复步骤
（2）和（3）直到所有顶点都包含在中。
最优化原理：
作为整个过程的最优策略，它满足相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”.一个问题满足最优化原理也称其拥有最优子结构性质。
5.1.2．模型一的运用与求解
（1）运用整体思想，最短路思想的由来
从仓库开出任一辆运输车对物资进行调运，到任意的未配送的需求点。
要求运输车的工作时间小于等于4小时，各运输车的载重量不超过6吨.且运输车重载运费2元/吨公里，空载费用0。
5元/公里。
为使总费用最小，则应使运输车从每一个需求点运往下一个需求点的费用最少。
现先采用“化零为整”的思想，假设有一辆“超级运输车”，装载了29个需求地的所有所需物资之和,即首先，使运输车从仓库运往地的运输费用最少，再从地运往地的运输费用最小，如此类推,若运输车从每一个需求地运往下一个需求地的都是费用最少的最优路径，则29个需求地的运输费用之和就是最少的费用。
即运输车走的29个需求地的路径即为总费用最少的路径。
再采用“化整为零”的思想,使所有运输车均排成一条长队,依次经过最短路径，当第一辆车运完所装载物资后,即空载撤回,第二辆车接着向下一个需求点运送物资，在经过最短路上相应需求点运送完所装载物资后，也空载撤回，如此类推，直至最后一辆运输车运送完全部所需物资。
再次，我们假设运输车行驶的速度与其载重无关（假设1）。
（2）由每个需求点的最小费用转化为求最短路
设运往需求点的费用为，代表与相连接,且为连向的费用最少的需求点。
即在最短路径上，“超大运输车”先经过,再经过.
运输的费用与该点的物资需求量及该点的地理坐标=成正比例关系。
对此我们将二者化零为整,将每个需求点的需求量乘以其坐标得到新的坐标。
同时也将运输车的载重量乘以它的速度.将二者同时放在花费的角度上（金钱的角度上）进行求解。
如此我们求了花费上的最短距离,同时我们设所有的运输车都载重6吨.对得到的最短行程做解，以得到最小的花费。
由上，，，设比例系数分别为。
则可表示为：
=
=
=
=
即此处,将需求点的地理坐标与需求量合成为一个新的坐标，该坐标表示的是需求点的运输费用坐标。
则题目转化为求一条最短路,将所有的29个需求点连接，使总运输费用最小。
我们根据原始数据表（表1）,将需求量乘入各个需求点的坐标建立一张新的表2.
表二各站点花费坐标表
站点编号
需求量T
地理坐标（km）
花费坐标（km*t）
站点编号
需求量T
地理坐标（km）
花费坐标（km＊t）
x
y
x
y
1
2。
5
3
2
12.5
16
1。
5
2
16
27
2
1
1
5
6
17
0。
8
6
18
19。
2
3
1。
5
5
4
13.5
18
1。
5
11
17
42
4
1.2
4
7
13。
2
19
0。
9
15
12
24.3
5
0.85
0
8
6。
8
20
1。
4
19
9
39。
2
6
1.3
3
11
18.2
21
1.2
22
5
32.4
7
1.2
7
0。
9
9.48
22
1。
8
21
0
37。
8
8
2。
3
9
6
34.5
23
1.4
27
9
50。
4
9
1.4
10
2
16。
8
24
1.6
15
19
54.4
10
1.8
14
0
25.2
25
1.9
15
14
55.1
11
1。
1
17
3
22
26
1
20
17
37
12
2.7
14
6
54
27
2
21
13
68
13
1.8
12
9
37.8
28
1
24
20
44
14
1.8
10
12
39。
6
29
2。
1
25
16
86。
1
15
0.6
7
14
12.6
30
0
0
0
0
我们又用Mathematica作出一张坐标图（程序见附录二）：
图二:
各需求点花费坐标图
（3）最短路的求法
根据最小生成树及Dijkstra算法可求得花费位置的最短路径（其中数据表，及Mathematica程序见附录）。
流程图如下：
图三：
花费最短路径算法流程图
最后求得使总费用最少的最短路径示意图如下（最短路上两相邻需求点的具体距离见附录四）：
图四：
最短路径示意图
（4）将合成坐标转化为地理坐标，确定具体调度方案
根据上文,我们找出了运输物资的最短路径，同时求解出了总运营的最低费用。
这样便为我们具体分配调度运输车扫清障碍。
但问题一中各需求点的坐标并非为各需求点的地理坐标，而是求最小费用的需求量与地理位置的合成坐标，即坐标是各需求点的费用坐标。
因而，根据花费最少的最小路径，首先将合成坐标回归为地理坐标.
在如何装载的问题上，显然有两种情况：
情况一:
若每量车均为满载,即每量发出的车均承载6吨货物。
根据最短路径经过的各站点依次发货，当第一辆货车所装载物资发完，第二辆继续前进，发货到下一个站点,而此时第一辆便空载撤回，为下一次的运输做好准备。
也即是我们的”超大运输车"假想思路。
在这里需要提出的是，有几辆车应该重复使用的（只需保证用时不大于4小时）,因为根据实际情况,派出一辆车的固定费用远高于一辆车的行驶费用.具体的调度方案见如下表一：
表一运输车满载调配物资情况表
车次
1
2
3
4
5
6
7
8
调配路线
3—6-16—5-4-2
8—20—10—12
11—22—21—9
14-27—15—19
25-26-29—13
24—23—28
30—17—7
18
装载吨数
6
6
6
6
6
6
6
1.15
里程数
41
86
125
168
218
262
298
308
注:
此处里程数仅为各运输车走完各自调配物资线路的里程数，不包括空载返回的里程数.
具体车辆调配见下图五：
图五：
满载车辆调配图
图例：
此图例也适用于图六、图七
注:
考虑此种方案,目的是简化对车辆的调度.使得可以假想为所有的车辆排成一条长队，当车到地时恰好运完所有货物，空载返回,车接着补充,满足地的需求量，以此类推，直至满足完第29个需求地的需求量。
情况二:
若各辆车按具体需求量装载货物（可以满载,可以非满载）,比如根据最短路径的连接站点，如果前3个站点需要总物资为m吨（m<6），而前四个站点需要总物资为M吨（M〉6），这样的情况我们可以把第一辆车装载m吨物资，那么第一辆车Ｖ１运货到第三个站点恰好运完货物，此时Ｖ１就可以空载撤回，第二辆Ｖ２也再通过计算下几个站点需要的具体物资去装载具体的物资量，完全发配．以此类推,直到最后一个站点运输完毕，即最后一辆车恰好运完，空载撤回．具体的调度方案见如下表二:
表二各辆车非满载调配物资情况表
车次
1
2
3
4
5
6
7
8
调配路线
3-6-16—5—4
2-8-20-10
12-11—22-21
9-14-27
15-19—25
26—29—13
24—23—28
30-17—7—18
装载吨数
5。
15
6
5.5
5.1
4.9
5。
6
5.2
5。
7
里程数
37
78
112
147
174
218
262
308
费用
246.8
319.6
547
601.2
654.2
991
1065.6
1352.5
注:
此处里程数仅为各运输车走完各自调配物资线路的里程数，不包括空载返回的里程数。
图六:
非满载车辆调配图
由表一和表二的对比，可以看出虽然满载和非满载两种情况下调配车辆辆数一样,但非满载情况下总运输费用远小于满载情况下总运输费用。
原因是满载情况下，当运输车在运完第个需求点，此时运输总量小于6，即使很小,小于最小路线上下一个需求点的需求量,但必须前往下一个需求点将余下物资卸完,因而会多出行进（需求点与需求点之间的距离），多运送
吨物资所需的耗费。
（5）问题一进一步的优化
在前面两种情况中,考虑的均是让所有运输车沿着同一条线路运送物资，即花费最短路。
事实上,可以让各运输车按最近路径从仓库到达各调配路线的初始需求点,而不是沿花费最短路，使得开往各初始需求点的费用大大减少。
返回时则由各调配路线终止点按最近路径返回仓库，而不是按花费最少路径.
根据上述思路，由题意知：
运输车的速度为40公里/小时,最大载重量为6吨，
可得车一次最在可运（40公里/小时）×6吨，即对车有最大运量240吨公里/小时.
我们重新定义每个需求点的需求为:
（需求量）*（该需求点的坐标和）。
数据见表二（见附录2）.
如此我们可求得总需求量为：
，
由表二我们可求得:
=939。
08吨公里
对图六非满载车辆调配图作如下运输车辆调配方案：
非满载最优车辆调配图
车次
1
2
3
4
5
6
7
8
调配路线
3-6-16—5—4
2—8—20—10
12-11-22-21
9-14—27
15—19—25
26—29—13
24—23—28
30—17—7—18
装载吨数
5.15
6
5.5
5。
1
4。
9
5。
6
5。
2
5.7
里程数
34
46
54
50
49
73
80
87
对于该方案：
我们派出去八辆车，分别开往3,2，12，9,15，26，24,30这八个站点。
第一条路线有：
车载重为5.15吨，其行程为34km，返回时行驶了11km。
，停留了40分钟,
共用时约为2小时；
花费为:
2×（）+0。
5×11；
第二条路线有：
车载重为6吨，其行程为46km，返回时行驶了14km，停留了40分钟，
共用时约为2.5小时了；
花费为：
2×（）+0.5×14；
第三条路线有:
车载重为5。
5吨,其行程为54km,返回时行驶了27km，停留了40分钟,
共用时约为3小时了;
花费为：
2×（）+0。
52×7
第四条路线有:
车载重为5。
1吨,其行程为50km,返回时行驶了34km,停留了30分钟,
共用时约为2.5小时了；
花费为：
2×（）+0.5×34
第五条路线有：
车载重为4。
9吨,其行程为49km，返回时行驶了29km，停留了30分钟，
共用时约为2。
5小时了；
花费为：
2×（）+0.5×29
第六条路线有：
车载重为5。
6吨,其行程为73km,返回时行驶了21km，停留了30分钟,
共用时约为3小时了;
花费为:
2×（）+0。
5×21
第七条路线有：
车载重为5。
2吨，其行程为80km，返回时行驶了44km，停留了30分钟，
共用时约为3.5小时了；
花费为:
2×（）+0。
5×44
第八条路线有：
车载重为5.7吨,其行程为87km，返回时行驶了24km，停留了40分钟,
共用时约为3.5小时了；
花费为：
2×（）+0.5×24
综上:
对第一到第八条路线有总花费P（总）=
2×（）+0。
5×11++（）+0.5×24
即：
花费P（总）=
+0.5×（11+14+27+34+29+21+44+24）
求解得:
花费P（总）=1980.16元
5。
2。
问题二的求解
由问题一的求解已找出使总费用最小的最短路径，因此在问题二中，只需沿着最小路径，具体分配载重量不同的运输车辆。
考虑到一辆载重大的运输车每公里的运营费用远大于载重小的运输车，因为在每吨物资每公里均为2元的情况下，载重
升级会员 