物流毕业论文设计快递公司送货策略优化模型.doc

快递公司送货策略优化模型

摘 要
本文讨论了快递公司送货路线的优化设计问题，即在给定送货地点和给定设计规范的条件下，综合考虑最大载重范围、以及各快递员工作时限，建立了人员分配和路径优化的数学模型。在这个题目中两点之间的路线权值赋为这两点横纵坐标之和，如此便可以用MATLAB求出任意两配送点间的距离。
针对问题一，我们以路程最短为目标 ，使公司获得最大效益并且快递员工作时间和每次出发的快件量越接近临界值越好，使其利用率最高。我们用以下方法：即每一个行程的第一个送货点是距离总部最近的未服务的送货点，可得到一组运行路线，总的运行公里数，以及总费用。通过用TSP模型对每条路线的最短路处理，在之前的路线上进行修正，得到优化模型结果为：最短时间为28.2699h，最短行程为506km，需要6个业务员。
针对问题二，在问题一的条件下，以给业务员的酬金最少为目标，结合业务员的安排和路线的选择，结果显示最优：共安排了8业务员，跑9路线，其中1号业务员跑的路线为0-1-3-8-13-0和0-2-4-7-14-0，2号业务员跑的路线为0-6-5-20-18-30-0，3号业务员的路线为0-9-12-19-0，4号业务员的路线为0-10-11-32-23-0，5号业务员的路线为0-16-17-24-28-0，6号业务员的路线为0-22-29-0，7号业务员的路线为0-15-27-0，8号业务员的路线为0-25-26-0，时间为30.7668h，用为13830.7元
针对问题三，因为所需的总时间不变，而每个业务员的工作时间增加为8小时，所以对其工作量重新安排，可将业务员减少到4人。
关键字：快递公司送货 欧拉回路模型 0-1规划 TSP模型

一、 问题重述
目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。
假定所有快件在早上7点钟到达，早上9点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点处（如图2），每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平行于坐标轴的折线。
（1）请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；
（2）如果业务员携带快件时的速度是20km/h，获得酬金3元/km×kg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略；
（3）如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？

送货点
快件量T
坐标(km)
送货点
快件量T
坐标(km)
x
y
x
y
1
8
3
2
16
3.5
2
16
2
8.2
1
5
17
5.8
6
18
3
6
5
4
18
7.5
11
17
4
5.5
4
7

19
7.8
15
12
6
3
0
8
15
3.4
19
9
5
4.5
3
11
32
6.2
22
5
7
7.2
7
9
22
6.8
21
0
8
2.3
9
6
23
2.4
27
9
9
1.4
10
2
24
7.6
15
19
10
6.5
14
0
25
9.6
15
14
11
4.1
17
3
26
10
20
17
12
12.7
14
6
27
12
21
13
13
5.8
12
9
28
6.0
24
20
14
3.8
10
12
29
8.1
25
16
20
4.6
7
14
30
4.2
28
18

点的分布如下图：

根据题意，得到运输情况及业务员工作信息如表1所示

表1 运输情况及业务员工作信息
运输车载重量
25kg
平均每天收到总重量
184.5kg
运输车途中平均速度
25km/h
每个业务员每天平均工作时间
<=6h
每个送货点停留的时间
10min
携带快件时速度
20km/h
携带快件时酬金
3元/km.kg
不携带快件速度
30km/h
不携带快件酬金
2元/km.kg
备注
1.公司总部位于坐标原点处 2.送货运行路线均为平行于坐标轴的折线
处于实际情况的考虑, 本研究中对人的最大行程不加限制.本论文试图从最优化的角度，建立起满足设计要求的送货的数学模型，求出满足题意要求的结果。

二． 模型的假设
1.无塞车现象,且车辆技术良好
2.车辆使用无限制
3.业务员到某送货点后必须把该送货点的快件送完
4．每次业务员从一个区送货回来，再配货的时间为0，即不花时间。
5．业务员中途不休息。
6．街道平行于坐标轴，且在保证该前提下，车辆可任意选择路径
7．业务员在中途除了送货之外没有别的时间耽搁。
8．每个送货点每天的快件量基本相同。
9．在业务员出发后到达快递公司的快件量均算入第二天的快件量
10．业务员送完货后必须到公司报到。
11.每个业务员只在自己送货的点有等待时间，路过送货点但不送货的没有等待时间。

三、符号说明
Ti：序号为i的送货点的快件重量
（xi ，yi）序号为i的送货点的坐标
dij:两点之间的距离
W1：业务员送货总重载费用
W2：业务员送货总空载费用
W：业务员送货总费用
N：业务员送货的总次数

第i线送完货的终点；

四、模型的分析、建立和求解
问题一：
运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）
（一） 模型分析
在问题一中，只要求给出一个合理的送货策略，并没有涉及到业务员的工资问题，故只要满足要求——每个业务员每天平均工作时间不超过6小时且必须从早上9点钟开始派送，到当天17点之前（即在8小时之内）派送完毕；以及每次出发最多能带25千克的重量。
由于，故最少需要8条路线。
如果将两点之间的路线权值赋为这两点横纵坐标之和，比如，两点，则权值为。那么便可以用MATLAB求出任意两配送点间的距离，即权重（如表1，求解程序见附件一）。
得到距离矩阵

因为距离是对称的，即从送货点i到送货点j的距离等于从j到i的距离。记作：

（二） 模型的建立和求解
可以通过以下方法实现：每一个行程的第一个送货点是距离总部最近的未服务的送货点。
本模型中以满足需求的路程最短的人员行驶路径,且使用尽量少的人数，即不走冤枉路原则（即只能向上或者向右走）。一方面，离原点（快递公司）较远的送货点坐标应分别大于离原点较近送货点的 坐标，在各个坐标上均不走回头路。
用这种方法，即可得到一组运行路线，总的运行公里数。
且
约束条件为：
① 时间约束：
② 载重量约束：
方法如下：
寻找每一个行程的第一个送货点是距离总部最近的未服务的送货点。
用该算法得到的各路线为：
第一条路线：
快递公司
1（3，2）
3（5，4）
4（4，7）
5（3，11）
出发线
返回线

第二条路线：
快递公司
2（1，5）
6（0，8）
7（7，9）
13（12,9）
出发线
返回线

第三条路线：
快递公司
9（10，2）
8（9，6）
12（14，6）
出发线
返回线
10（14，0）

第四条路线：
快递公司
16（2，,16）
17（6,18）
20（7,14）
14（10,12）
15（19,9）
23（27,9）
出发线
返回线

第五条路线：
快递公司
11（17，3）
22（21，0）
21（22，5）
19（15，12）
出发线
返回线

第六条路线：
快递公司
27（21，13）
26（20，17）
出发线
返回线

第七条路线：
快递公司
18（11，17）
24（15，19）
25（15，14）
出发线
返回线

第八条路线：
快递公司
29（25，16）
28（24，20）
30（28，18）
出发线
返回线

得到的路线图如下：

图1
注释：用线连接起来的几个点表示一次送货可以服务的点，代表送货的先后和走的路线，但走的首尾顺序可以任意。

每条线路的所用时间和载重量如下：
表一

以上8条路线，我们分别对每条回路利用TSP模型求得该回路的最短路，使得路程和时间得到改善，提高工作效率。我们把快递员送货问题转化为0-1规划，然后用LINGO来求解。
引入0-1整数变量 (且i≠j): =1表示路线从i到j，即边i-j在旅行路线中，而
＝0则表示不走i-j路线。
目标函数：
首先必须满足约束条件：对每个送货点访问一次且仅一次。从送货点i出发一次(到其它送货点去),表示为

从某个送货点到达j一次且仅一次，表示为

以上建立的模型类似于指派问题的模型，对快递员送货问题只是必要条件，并不充分。
例如，用图示路线连接六个点，满足以上两个约束条件，但这样的路线出现了两个子回路，两者之间不通，不构成整体巡回路线
3
1
2
6
5
4

为此需要考虑增加充分的约束条件以避免产生子巡回
增加变量,i=2,3,…,n，（它的大小可以取整数：例如从起点出发所达到的投递点u=2,依此类推）。

综上所述，该约束条件只限止子巡回，不影响其它，于是快递员送货问题转化成了一个混合整数线性规划问题。
快递员送货问题可以表示为规划：

利用LINGO求解，依次可求得每天回路的最短路线：
修改后得到总的送货路线为：
第一条路线：
快递公司
1（3，2）
3（5，4）
4（4，7）
5（3，11）
出发线
返回线

第二条路线：
快递公司
2（1，5）
6（0，8）
7（7，9）
13（12，9）
出发线
返回线

第三条路线：
快递公司
10（14，0）8）
12(14,6)
8（9，6）
9（10，2）
出发线
返回线

第四条路线：
快递公司
16（2，,16）
17（6,18）
20（7,14）
14（10,12）
15（19,9）
23（27,9）
出发线
返回线

第五条路线：
快递公司
19（15，12）
11（17，3）
21（22，5）
22（21，0）
出发线
返回线

第六条路线：
快递公司
18（11，17）
24（15，19）
出发线
返回线
25（15,14）

第七条路线：
快递公司
27（21，13）
26（20，17）
出发线
返回线

第八条路线：
快递公司
29（25，16）
30（28，18）
出发线
返回线
28（11,17）

修改后得到的路线图如下：

注释：用线连接起来的几个点表示一次送货可以服务的点，代表送货的先后和走的路线，但走的首尾顺序可以任意。

修改后每条线路的所用时间和载重量如下：
表二
运输员序号
所经站数
最近点
所用时间
(小时)
总载重（kg）
总路程（km）
1
4
1（3，2）
1.9467
24
32
2
4
2（1，5）
2.5067
24.2
46
3
4
9（10，2）
1.8664
22.9
30
4
6
16（2，16）
4.6000
23.5
90
5
4
11（17，3）
4.2134
24.9
72
6
3
18（11，17）
3.7500
24.7
68
7
2
27（21，13）
3.7067
22
76
8
3
29（25，16）
4.8400
18.3
96
合计
30

28.2699
184.5
506

改进前和改进后的路程，时间比较如下：

根据所经历的时间进行划分，确定运送人数。在工作时间小于6小时的前提下，最终只需要六名运输员，第一条线路和第二条线路有一人完成，第三条和第七条线路由一人完成，则各运输员到达各站点时间的情况如下：
路线
站点
编号
到各站
点时间
出发时间
路线
站点
编号
到各站点时间
出发时间

1
1
9：12

9：00

5
19
10：05

9：00
3
9：32
11
10：41
4
9：52
32
11：08
5
10：14
22
11：32

2
2
12：02

11：58

6
18
10：07

9：00
13
12：48
24
10：31
7
13：10
25
10：53
6
13：39
7
27
13：45
12：23

3
10
9：34

9：00
26
14：07
12
9：58

8
29
10：38

9：00
8
10：20
30
11：00
9
10：44
28
11：24

4
16
9：43

9：00

问题二：如果业务员携带快件时的速度是20km/h，获得酬金3元/km×kg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略。
（一） 模型的分析
问题二中由于业务员所得的费用是最主要的，业务员安排、路线选择都是为了总费用的最小化提供条件，所以应首先考虑路费，之后再考虑业务员的安排。为了使总能够费用最少，总的思路是先送货给离快递公司最近切块间最重的送货点，以此类推，在保证时间、载重量有限的前提下，沿途把快递送完，最终让业务员最远点空载返回。
（二） 模型的建立和求解
总费用为重载与空载费用之和，所以总费用的确定就可以转化为满足一定条件下的各路线的最远点的选择问题。某路线业务员经过的路径选择应遵循以下原则：一是，近者优先原则。某业务员最近起始送货点的选择直接关系到费用的多少，所以该业务员在沿途往送货终点站中应尽量把较近点的快件送完，不让下一条路线再把较近点作为起始送货站。二是，不走冤枉路原则（即只能向上或者向右走）。一方面，离原点（快递公司）较远的送货点坐标应分别大于离原点较近送货点的 坐标，在各个坐标上均不走回头路。
另一方面，由于在路途相等的条件下，重载费用要比空载费用大得多，因此，尽量让业务员空载行走。
根据上述分析及基本假设，业务员送货的费用可以表示如下：
业务员负载费用：
业务员空载费用：
总费用:
因此，目标函数建立为
应满足以下约束条件:
1．时间约束:
2．载重量约束25
据路线约束条件以及问题一中的表二知：送货点1（3，2）、2（1，5）首先必须作为某路线的最近起始送货点，再结合时间约束条件①、载重量约束条件②以及上述分析的有关内容，依次选出各路线的次近点，并做统筹兼顾，一直到满足约束条件的最大值为止。随后又选出6（0，8）、9（10，2）、10（14，0）、16（2，16）、22（21，0）、15（19，9）、25（15，14）为某条路线的最近点，分别确定次近点等，最后确定各路线如下所示：
第一条路线：
快递公司
1（3，2）
3（5，4）
8（9，6）
13（12，9）
出发线
返回线

第二条路线：
快递公司
2（1，5）
4（4，7）
7（7，9）
14（10，12）
出发线
返回线

第三条路线：
快递公司
6（0，8）
5（3，11）
20（7，14）
18（11，17）
出发线
返回线
30（28，18）

第四条路线：
快递公司
9（10，2）
12（14，6）
19（15，12）
出发线
返回线

第五条路线：
快递公司
10（14，0）
11（17，3）
32（22，5）
23（27，9）
出发线
返回线

第六条路线：
快递公司
16（2，16）
17（6，18）
24（15，19）
28（24，20）
出发线
返回线

第七条路线：
快递公司
22（21，0）
29（25，16）
出发线
返回线

第八条路线：
快递公司
15（19，9）
27（21，13）
出发线
返回线

第九条路线：
快递公司
25（15，14）
26（20，17）
出发线
返回线

根据上面确定的路线，把个业务员所经过的送货点数、最近点、所用时间、总载重量进行归纳，求出各业务员送货所得费用以及总费用，如下表：
路线号
所经送货点数
最近送货点
所用时间（小时）
总载重量（kg）
费用（元）
1
4
1（3，2）
2.41667
22.1
792.9
2
4
2（1，5）
2.5
24.7
969.5
3
5
6（0，8）
4.66667
23.8
1852.4
4
3
9（10，2）
2.75
21.9
1498.2
5
4
10（14，0）
3.66667
19.2
1352.4
6
4
16（2，16）
4.33333
22.9
2261.8
7
2
22（21，0）
3.75
14.9
1506.7
8
2
15（19，9）
3.16667
15.4
1577.6
9
2
25（15，14）
3.42667
19.6
2019.2
合计
30

30.7668
184.5
13830.7
根据时间约束，最少要8个业务员送快件，其中把路线1和2合并，让业务员A执行任务，其余的分别由其他7个业务员送货。同时，为了便于统筹业务员，可以得出各业务员到各送货点的时间（各业务员的出发时间为0）以及各路线从快递公司出发的参考时间（从9：00开始工作）。

第一个人：0-1-3-8-13-0和0-2-4-7-14-0
第二个人：0-6-520-18-30-0
第三个人：0-9-12-19-0
第四个人：0-10-11-32-23-0
第五个人：0-16-17-24-28-0
第六个人：0-22-29-0
第七个人：0-15-27-0
第八个人：0-25-26-0

问题三：如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？
（一）模型分析
问题三是建立在问题一的基础上的，因为每个业务员可以携带的邮件量是一定的，即不超过25kg，当工作时间调至八小时时，无论对总公里数还是总酬金都没有影响，只需对业务员的多少进行改进即可。
（二） 模型的建立和求解
在问题一中已算得，修改前的方案所需的总时间最少为27.69h，当业务员时间调至8小时时，所需的业务员至少为个,所以业务员至少为4个。于是我们就对修改前的方案的表一的八个路线重新分配，分配给4个送货员，尽量给业务员分配同样的工作时间，即，即每个业务员工作时间在6.07左右。
重新分配后得到如表15所示的方案
业务员
送货路线
线路耗时
线路路程
1
0-16-17-20-14-15-23-0
6.55
122
0-1-3-4-5-0
2
0-29-28-30-0
6.93
144
0-2-6-7-13-0
3
0-11-22-21-19-0
6.76
119
0-9-8-12-10-0
4
027-26-0
7.46
144
0-18-24-25-0
表15
综上所述，当时间变成8小时时，业务员减为4个，具体安排为：1号业务员跑的路线为0-16-17-20-14-15-23-0和0-1-3-4-5-0，2号业务员跑的路线为0-29-28-30-0和0-2-6-7-13-0，3号业务员的路线为0-11-22-21-19-0和0-9-8-12-10-0，4号业务员的路线为0-27-26-0和0-18-24-25-0。
五．模型的评价
1.模型的优点：
(1）模型系统的给出了业务员的调配方案，便于指导工作实践。
(2）模型简明明了，容易理解与灵活应用。
(3)本论文模型的建立从实际问题出发,对于解决其它问题也具有一定的实用性, 具 有较强的推广价值。
(4)成功运用matlab和LINGO等软件，减少计算量
（5）充分利用0-1规划、欧拉回路模型和TSP模型，使方案更具有可行性
2． 模型的缺点：
(1) 本模型求解复杂程度太大，当送货点个数增加一个，求解复杂度就会成级数增加，由于受各种条件的限制，送货员的送货线路只能逐条去求，增加了劳动量。
(2） 模型给出的约束条件有些不太现实，忽略了很多因素，比如快递员休息时间等，这些因素在实际中不可忽略。
(3）对街道的方向，客户的快件量的假设有待进一步改进。

六．模型的推广
（1）本模型不但适合于快递公司送货问题，还是用于一般的送货以及运输问题， 只需要稍微改动模型即可。
（2）模型方便、直观，可以实现计算机模拟。
（3）建模的方法和思想可以推广到其他类型，如车辆调度问题等。

七、 结果分析
通过以上模型我们解决了快递公司在实际中所面临的送货员聘用问题，我们帮他们找出了聘用的最少送货员人数，以及每个送货员运送路线的安排，线路的产生是我们通过对实际问题中可能遇到的结果进行比较，从中选择出了最优结果。
对于问题一和问题二的分析，我们可以将问题二看成是问题一约束条件的增加，问题一的结果适用于问题二，只是因需要满足时间要求而进行调整。
本问题的求解具有一般性对实际问题的解决具有一定的指导意义。

八、参考文献
[1]姜启源 谢金星 叶俊 编著，《数学模型》，北京：高等教育出版社，2003年第三版；
[2]邓微，MATLAB函数速查手册：人民邮电出版社，2008.
[3]吴建国 编著，《数学建模案例精编》，北京：中国水利水电出版社，2005年5月第一版.
[4]数学建模案例精编（超星阅览器）
[5]中国邮递员模型案例

九、附录

附件一：
求矩阵：求任意两配送点间的距离

clear
clc
x=[0 3 1 5 4 3 0 7 9 10 14 17 14 12 10 19 2 6 11 15 7 22 21 27 15 15 20 21 24 25 28];
y=[0 2 5 4 7 11 8 9 6 2 0 3 6 9 12 9 16 18 17 12 14 5 0 9 19 14 17 13 20 16 18];
for i=1:31
for j=1:31
d(i,j)=abs(x(i)-x(j))+abs(y(i)-y(j));
end
end

运行结果:
Columns 1 through 10

0 5 4 6 9 9 11 10 7 13
5 0 5 5 4 8 10 9 12 18
4 5 0 4 9 9 7 6 7 13
6 5 4 0 5 5 5 6 11 17
9 4 9 5 0 6 8 11 16 22
9 8 9 5 6 0 6 11 16 22
11 10 7 5 8 6 0 5 10 16
10 9 6 6 11 11 5 0 5 11
7 12 7 11 16 16 10 5 0 6
13 18 13 17 22 22 16 11 6 0
15 18 13 17 22 22 16 11 8 6
15 14 11 11 16 16 10 5 8 6
16 15 12 10 13 11 5 6 9 11
17 16 13 11 14 8 6 7 10 16
16 15 12 10 13 7 5 10 15 21
15 12 15 11 10 6 12 17 22 28
19 18 15 13 16 10 10 15 20 26
23 22 19 17 20 14 12 13 16 20
22 21 18 16 19 13 11 12 15 13
23 22 19 17 20 18 12 13 16 14
22 21 18 20 25 25 19 14 15 13
20 25 20 24 29 29 23 18 13 7
31 30 27 25 28 26 20 21 24 22
29 28 25 23 26 20 18 19 22 20
24 23 20 18 21 15 13 14 17 15
32 31 28 26 29 23 21 22 25 23
29 28 25 23 26 20 18 19 22 20
39 38 35 33 36 30 28 29 32 30
36 35 32 30 33 27 25 26 29 27
41 40 37 35 38 32 30 31 34 32

Columns 11 through 20

15 15 16 17 16 15 19 23 22 23
18 14 15 16 15 12 18 22 21 22
13 11 12 13 12 15 15 19 18 19
17 11 10 11 10 11 13 17 16 17
22 16 13 14 13 10 16 20 19 20
22 16 11 8 7 6 10 14 13 18
16 10 5 6 5 12 10 12 11 12
11 5 6 7 10 17 15 13 12 13
8 8 9 10 15 22 20 16 15 16
6 6 11 16 21 28 26 20 13 14
0 6 11 16 21 28 26 20 11 8
6 0 5 10 15 22 20 14 7 8
11 5 0 5 10 17 15 9 6 7
16 10 5 0 5 12 10 6 5 12
21 15 10 5 0 7 5 7 10 17
28 22 17 12 7 0 6 10 17 24
26 20 15 10 5 6 0 6 15 22
20 14 9 6 7 10 6 0 9 16
11 7 6 5 10 17 15 9 0 7
8 8 7 12 17 24 22 16 7 0
7 9 14 19 24 31 29 23 14 7
7 13 18 23 28 35 33 27 18 11
16 16 15 20 25 32 30 24 15 8
18 14 13 12 13 16 10 6 7 14
13 9 8 7 8 15 13 7 2 9
17 17 16 15 16 19 15 9 10 9
14 14 13 12 15 22 20 14 7 6
24 24 23 22 23 26 20 16 17 16
21 21 20 19 20 23 21 15 14 13
26 26 25 24 25 28 22 18 19 18

Columns 21 through 30

22 20 31 29 24 32 29 39 36 41
21 25 30 28 23 31 28 38 35 40
18 20 27 25 20 28 25 35 32 37
20 24 25 23 18 26 23 33 30 35
25 29 28 26 21 29 26 36 33 38
25 29 26 20 15 23 20 30 27 32
19 23 20 18 13 21 18 28 25 30
14 18 21 19 14 22 19 29 26 31
15 13 24 22 17 25 22 32 29 34
13 7 22 20 15 23 20 30 27 32
7 7 16 18 13 17 14 24 21 26
9 13 16 14 9 17 14 24 21 26
14 18 15 13 8 16 13 23 20 25
19 23 20 12 7 15 12 22 19 24
2