快递公司送货策略数学模型_数学建模论文Word文档格式.docx
《快递公司送货策略数学模型_数学建模论文Word文档格式.docx》由会员分享，可在线阅读，更多相关《快递公司送货策略数学模型_数学建模论文Word文档格式.docx（41页珍藏版）》请在冰点文库上搜索。
任意一条路线上具体某一送货点（1,2……m）
总的运行公里数
每一条最优送货路线的公里数
每条路线上两个送货点之间的距离
快件全部送完所花总时间
业务员运送途中的速度
每一条送货路线的时间
总的送货点重量之和
每一条路线送货的重量
每一条路线上每一个送货点的重量
任意一位送货员
总的送货需要多少钱
送货员携带快件时的酬金
送货员未携带快件时的酬金
业务员携带快件时途中的运行速度
业务员未携带快件时途中的运行速度
三角距离函数
四、问题分析
本题属于资源分配优化问题，要求根据资源限制和约束条件来建立一个合理的邮件派送模型。
在问题一中，要求我们根据时间和重量等方面的约束条件，建立合理的邮件派送路径，使得运行线路最短且使用尽可能少的业务员。
分析题目条件知道影响模型的主要因素有：
1.业务员每天工作不可超过6小时；
2.业务员每次出发至多可带25千克的快件；
3.公司需在9:
00-17:
00间将184.5千克的货物分送到杂乱无序的30个送货点。
因此，我们需要建立最短送货路径的数学模型，首先，应用Dijkstra算法求解出坐标原点（公司总部）到各送货点的最短路距离矩阵D1；
利用TSP模型中的最近邻法确定满足条件的8条最短路径并依据各线路送货时间进行送货人员的分配；
利用顺序插入交叉算子对模型一提出优化方案。
问题二中，题目增加了业务员空载和重载的酬金以及速度的条件，要求公司设计一个费用最省的策略。
因业务员重载的费用高于空载费用，而模型一仅给出路线最短，不能满足问题二需求，所以对问题二提出费用优化方案，即根据费用计算方式，运用最近邻法寻找离原点（配送中心）费用最少的点，依次类推，找出费用最省的路径组合并计算出所需费用；
根据路径组合和运送时间，在满足问题一约束条件的基础上重新分配送货人员。
问题三中，将业务员的工作时间延长到每天8小时，求解公司的运送策略将如何改变。
业务员工作时间的调整对于总的运行路线的影响并不大，只需对业务员的数量已及各业务员的安排路线进行调整即可。
五、模型建立与求解
5.1问题一模型建立与求解
5.1.2模型的建立
在问题一中，要求在每个业务员每天平均工作时间不超过6小时且必须从早上9点开始到当日17点（8小时内）全部派送完毕;
平均每天送货总重量为184.5千克，每人每次出发最多可带25千克。
如果将两点之间的路线距离附为这两点横纵坐标之和，比如，这两点，则次两点间的距离为：
（5.1.1）
用此方法结合MATLAB求出任意两配送点的距离矩阵如下（图5.1）：
图5.1距离矩阵D
该问题为规划模型，根据题意，结合距离矩阵D，设定目标函数为：
（5.1.2）
即为送货总路线的最短路程。
其约束条件为：
1、每条线路上个需求点需求量之和不超过业务员的最大负荷量：
（5.1.3）
2、每个业务员所有配送路径来回的时间不能超过业务员一天最长的工作时间：
（5.1.4）
3、每一条送货路线上送货点数不超过总送货点数：
（5.1.5）
4、所有点都能够被配送到：
（5.1.6）
5、总的送货路线不超过每人送一个一个地点：
（5.1.7）
综上：
最终模型建立如下
（5.1.8）
（5.1.9）
为方便快件公司进行人员分配和路线选择，需计算每天路径的送货时间及派送完所有快件所花总时间
（5.1.10）
（5.1.11）
5.1.2利用最近邻法求最短送货路径组合
经过分析，本题属于业务员路径问题，即VRP问题，从本质上说，TSP（旅行商问题）是VRP的基本问题，因此，本文以TSP思想中的一种最近邻算法为根据，结合题目约束条件，利用MATLAB求解出业务员工作的最短路径。
TSP问题是典型的组合优化问题，问题要求求得一条遍历所有城市的最短路径，是一个易于描述但难于处理的NP-HARD问题。
TSP问题在交通运输、计算机网络、电路设计以及物流配送等领域内有着广泛的应用，目前，其主要算法主要有遗传算法、贪婪算法、模拟退火法及最近邻法等诸多方法。
最近邻算法是TSP近似算法中最简单直观的一种，其主要思想为：
任取一点作为出发点，每次取最近的一个点加入到最优解中，一直到所有点皆已进入解中。
首先根据距离矩阵D找到距离送货中心最近的一个未服务送货点，则分配一条路线，再找出距离最近的另外一个未服务的送货点，对每一个服务店同理依次寻找出，同时，每经过一个服务点对该服务点邮件的重量进行累加，即，直到此路线中所经过的所有送货点的邮件累计重量，则以上包含的点的组合即为该路线的路径。
依据上述原理，运用MATLAB软件（程序详见附件一）可得到8条最短路径，由此分析配送路线及分配表如下表：
表一：
模型一路线分配表
路线i
路径
总时间（h）
总路程（km）
总重量（kg）
1
0-1-3-4-5
1.95
32
24.0
2
0-2-6-7-8-9-23
4.52
88
24.5
3
0-10-11-12
2.34
46
23.3
4
0-16-17-20-14-13
3.23
60
23.5
5
0-22-21-15-19
3.39
68
24.2
6
0-18-24-25
3.22
24.7
7
0-27-26
3.37
76
22.0
8
0-29-28-30
4.42
98
18.3
合计
26.44
536
184.5
注：
0为配送中心
将以上模型求解得到的路线射线图可用网络图象表达，如下（图5.2）：
图5.2模型一路线射线图
则每条路径的具体路线如下（图5.3）：
图5.3模型一路线图
在保证所有快件准时送达各个送货点的情况下，合理安排路线及送货员，使得所需送货员的人数最少，线路及人员安排情况如下表：
表二：
模型一人员分配表
送货员R
路线L
1、5
3、7
---------
4.52
3.23
3.22
4.42
5.34
5.71
48.2
45.3
100
122
综上，可得该模型所构建的路线共需6名送货员，快件完全送完所需总路程为536千米，所需总时间为26.44小时。
该模型较简单直观，但也存在不足。
在路径选择时，当其中某一点被路线选定后，该点将不作为接下来的任意一条路线的备选送货点，每一条路线均为当前条件下的最优路线，将所有路线组合后不一定是整体送货点的最优路线，即局部最优并非整体最优。
为提高工作效率，使所走总路程更短、时间更少，我们对上述模型进行了优化。
5.1.3利用顺序插入交叉算子（OIC）优化模型一
顺序插入交叉算子是针对TSP问题的特点，在遗传算法的交叉运算过程中设计的三角距离差函数作为评价标准，运用贪婪策略思想，提出的一种新的交叉算子，该算子有效的利用了局部信息，并且能很好的继承父代优秀的基因。
顺序插入交叉算子的基本思想是：
对于两个待交叉的染色体，将一个作为基本染色体，另一个作为参考染色体，按照在参考染色体中的送货点间的邻接顺序，利用三角距离差函数作为评价标准，运用贪婪策略思想，逐步改变基本染色体的编码顺序，从而使经过交叉得到的两个子代染色体的适应度最高。
优化思想：
利用顺序插入交叉算子，我们将模型一中每一条进行染色体编码定义，如，将上述染色体看成一个环，染色体的下一个送货点是。
定义，设有3个送货点,,，定义三角距离函数G（a,b,c）如下：
（5.1.12）
其中，表示送货点到送货点的距离。
设待交叉的双亲为和,设计交叉算子其求解步骤如下：
1.将父体作为基本染色体，父体作为参考染色体，在中随机找到一个参考城市；
2.在染色体中找到城市，，然后对函数值进行比较，若：
（5.1.13）
则染色体保持不变，否则，在染色体中删除城市，然后再与之间插入，得到新染色体
3.依次在参考染色体中取参考城市，重复步骤2，直至生成子代个体。
4.再将作为基本染色体，将作为参考染色体，重复上述步骤直至得到最优搭配方案。
5.2问题二模型建立与求解
5.2.1模型的建立
问题二要求根据题给空载和重载的速度与价格条件，优化送货路线使得送货费用最小。
根据条件，任意一条送货路线的费用可分为两部分组成：
重载情况下到达最后一个送货点
通过该路线将快件从原点送到该路线上任意一点所需要的路程为：
则所需要的费用为
由此得到重载情况下到达最后一个送货点的费用为
2.空载情况下由最后一个送货点返回配送中心：
综合1、2两步，得到任意一条送货路线的费用为
则将货物送达完毕的费用为
可设定目标函数为：
（5.2.1）
上式即为送货总费用的最省的线路。
1、每条线路上的需求点需求量之和不超过业务员的最大负荷量，即：
（5.2.2）
（5.2.3）
3、所有点都能够被配送到：
（5.2.4）
4、每一条送货路线上送货点数不超过总送货点数：
（5.2.5）
5、总的送货路线不超过每人送一个地点：
（5.2.6）
.（5.2.7）
（5.2.8）
为方便快件公司进行人员分配和路线选择，需计算每条路径的送货时间和派送完所有快件所花总时间，以及总的费用
5.2.2模型的求解
根据题意，本题目属于求解费用最小的组合优化模型，同样利用问题一种的最近邻法，结合送货时间及重量的约束条件，利用路线费用计算公式来寻找费用最小的优化模型。
首先找到距离送货中心送货费用最少的一个未服务送货点，则分配一条路线，再找出距离送货费用最小的另外一个未服务的送货点，对每一个服务店同理依次寻找出，同时，每经过一个服务点对该服务点邮件的重量进行累加，即，直到此路线中所经过的所有送货点的邮件累计重量，则以上包含的点的组合即为该路线的路径。
依据上述原理，运用MATLAB软件（程序详见附件）可得到9条最短路径，由此分析配送路线及分配表如下表：
表三：
模型二路线分配图
总费用
0-9-8-14-20-16-5-6-0
3.83
56
23.1000
2234.5
0-11-10-22-21-0
3.52
66
23.6000
2205.6
0-2-7-13-23-0
3.67
72
1189.8
0-1-3-4-15-0
3.10
58
22.9000
858.5
0-26-0
3.25
74
10.0000
1184
0-12-27-0
3.17
24.7000
2056
0-30-28-29-0
4.72
18.3000
2955.1
0-19-25-0
2.75
17.4000
1525
9
0-17-18-24-0
3.43
70
20.9000
1981.4
31.43
620
184.500
16189.9
每条路径的路线图如下（图5.4）所示：
图5.4模型二路线图
根据送货路线分配表，合理安排送货员如下表：
表四：
模型二业务员分配表
4，8
5.85
3.25
3.17
4.72
3.43
40.3000
116
总费用（元）
2042.5
综上，模型二所建立的优化模型的总路程是620千米，所花总时间是31.43小时，共需要送货员8人，所需最少费用为16189.9元
5.3问题三模型建立与求解
5.3.1模型的建立与求解
由于业务员的日常工作时间由6小时增加到8小时，因此，需要根据每天路径的运送时间对模型一的路线重新分配业务员。
模型三人员分配表如下：
表五：
模型三业务员分配表
1，8
2，3
4，5
6，7
6.37
6.86
6.62
6.59
26．44
42.3
47.8
47.7
46.7
130
134
128
144
综上，业务员工作时间调整后，共需业务员4人。
六、模型的评价与改进
6.1模型的评价
6.1.1模型的优点
在模型建立的过程当中，我们将具体问题抽象成一个数学目标函数，一方面在结果上具体分配出了送货策略，另一方面模型的整个求解过程简单清晰，便于理解和推广。
在求解分析中将有序路径问题引入到矩阵中，并很好的融合了TSP模型中求最短路径的思想设计出自己的算法，模型的建立简单明确，具有针对性，模型的计算结果经过仿真测试，具有较高的准确度。
最终得出了较为合理的送货策略并对模型一提出了基于遗传算法思想的优化理论。
6.1.2模型的缺点
该模型主要采用TSP（旅行商问题）思想中的最近邻算法，仅在现有条件内实现了局部最优，并没有达到整体最优的效果，优化方案模型不成熟。
该模型选择配送线路不能对客户的需求进行灵活多变的处理。
由于线代的消费者的需求倾向于个性化，引起企业的生产、销售和配送也愈来愈倾向于小批量、多品种、多批次，而该模型更适合需求稳定的环境。
参考文献
[1]孙海雷，刘琼荪，胡上尉。
TSP问题的顺序插入交叉算子[J]。
计算机工程与应用，2007,43（8）。
[2]张辉。
TSP问题的算法与应用的研究[J]。
计算机应用与软件，2009，26（4）。
附录
附录1.模型求解相关matlab程序
tsp模型邻近算法状态选择
模型求解的相关数据文件
文件说明
数据类文件：
Point.xls
文件存入的是以送货配发点为原点所建成的坐标体系上的各个点的相对坐标集合
st.xls
文件存入的内容为各个配送点的所需货物的重量以及货物送达的状态
Dis2.xls
文件存入的内容为各个配送点的距离矩阵表
gres.xls
由问题模型一结果构成的路线矩阵
Dis3.xls
由距离矩阵和单价表构成的距离单价矩阵（用于问题二的模型）
程序类文件
getallDis.m文件（工具类程序文件）
表现：
functions=getallDis（）
主要功能：
求出各个送货点的距离举证，并存入dis.txt
源代码：
%UNTITLED1Summaryofthisfunctiongoeshere
%Detailedexplanationgoeshere
%author:
manager
x=xlsread（'
point.xls'
'
b3:
b33'
）;
y=xlsread（'
c3:
c33'
fori=1:
31
forj=1:
a（i,j）=abs（x（i）-x（j））+abs（y（i）-y（j））;
end
end
file=fopen（'
dis.txt'
w'
fori=1:
forj=1:
%fprintf（file,'
fprintf（file,'
%d'
a（i,j））;
ifmod（j,31）==0
fprintf（file,'
\n'
end
end
end
fclose（file）;
getDis.m文件（工具类程序文件）
functionk=getDis（i）
获取返还距离；
functionk=getDis（i）
%Detailedexplanationgoeshere
ifi==1k=xlsread（'
dis2.xls'
a1:
a1'
ifi==2k=xlsread（'
a2:
a2'
ifi==3k=xlsread（'
a3:
a3'
ifi==4k=xlsread（'
a4:
a4'
ifi==5k=xlsread（'
a5:
a5'
ifi==6k=xls
升级会员 