快递公司送货策略
摘要
快递是快递公司快速收集、运输和递送客户文件、物品或货物的一种服务.
合理选择送货线路并制定业务员分派方案是极其重要的,它不仅可以加快配送速
度,提高服务质量,还可以有效的降低配送成本,增加经济效益.
本文是关于快递公司送货策略的优化设计问题，即在给定送货地点和给定设
计规划的前提下，确定所需的业务员人数，每个业务员的行程路线，总的运行公
里数及费用最省的策略。对此,本文重点讨论的问题是快递公司如何雇佣多少业
务员送货,如何确定每个业务员的运行线路以达到费用最省的目的。
在问题一中，由于不要考虑业务员费用，所以我们以业务员所走路程最短为
目标函数：
先假定将送货点划分为 N 个区域，然后用 LINGO 软件进行求解，得出最短
送货距离，然后引入路径矩阵 D，用 MATLAB 编程求解得出业务员的最佳行走
路径及所需要的业务员个数 5 人。
在问题二中，主要考虑业务员的费用，通过对载货费用与空载费用求和得到
所需总费用。所以，我们以总费用最小为目标建立动态规划模型：
通过运用 LINGO 和 MATLAB 软件求解得出最优送货路线及送货费用。
在问题三中，我们沿用问题一的模型，并将其中每趟送货不超过 6 个小时的
约束条件改为不超过 8 个小时，得出最有送货路线及业务员人数 4 人。
关键字：路程矩阵 动态规划 遗传算法
1
0 01 11 1
[ ) ]min (
N k
R R R Rjm jm j jkj m j
d d d
1
0 01 11 1 1
min (3 ( ) ( ) 2 )
N k m
jmR R R Rjn jn j jkj m n
d d G R d
一、问题重述
目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快
件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，
为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，
但是，太多的业务员意味着更多的派送费用。
假定所有快件在早上 7 点钟到达，早上 9 点钟开始派送，要求于当天 17 点
之前必须派送完毕，每个业务员每天平均工作时间不超过 6 小时，在每个送货点
停留的时间为 10 分钟，途中速度为 25km/h，每次出发最多能带 25 千克的重量。
为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为 千
克，公司总部位于坐标原点处（如图 2），每个送货点的位置和快件重量见下表，
并且假设送货运行路线均为平行于坐标轴的折线。
（1）请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需
要多少业务员，每个业务员的运行线路，以及总的运行公里数）；
（2）如果业务员携带快件时的速度是 20km/h，获得酬金 3 元/km①kg；而不携
带快件时的速度是 30km/h，酬金 2 元/km，请为公司设计一个费用最省的策略；
（3）如果可以延长业务员的工作时间到 8 小时，公司的送货策略将有何变化？
二、问题假设与符号说明
模型的假设
假设 1：每天每个送货点只由一个业务员送一次货
假设 2：业务员在送货区域内只走最短路径
假设 3：各个业务员相互独立，互不影响
假设 4：送货运行路线均为平行于坐标轴的折线
假设 5：各业务员在中途除了送货之外没有其它时间耽搁
符号说明
符号 符号说明
用 0、1 表示第 i 个送货点是否属于第 j 个送货区
第 i 个送货点的邮件+重量
wij
G
i
mnd 两送货点之间的最短折线距离
jmR j第 个送货区内的k个送货点之间的有序线路解集
D 路径矩阵
三、问题分析
此题是一个典型的中国邮递员问题，要求我们根据各种约束条件为快递公司
建立出比较合理的送货策略。
针对问题一：要求我们根据时间和重量等方面的约束来建立一个合理的邮件
配送模型。模型以邮递员数量最少且送货总距离最小为最佳送货策略。考虑到送
货时间由送货行驶距离和行驶速度来决定（送货点个数和位置确定的情况下），
所以当送货所需的总行驶距离为最小时，所需的送货时间和所需的邮递员个数都
将最少。因此我们考虑建立以送货总行驶距离最小为目标函数的数学模型。以此
为基础将送货点分到若干区内，然后确定由多少邮递员分别给哪几个区送货。
针对问题二：此问给出了具体的运输费用，要求我们求解费用最省的送货策
略，因此我们根据运费和送货行程的关系建立费用最省模型，并结合各种约束条
件来计算求解。
针对问题三：此问即在问题一的基础上将约束条件中每个业务员平均每天的
工作时间从不超过 6 个小时改为了不超过 8 个小时，因此我们可以沿用第一问的
模型，改变时间约束条件来进行求解计算。
四、模型的建立与求解
问题一：建立一个合理的送货模型
（一）模型分析建立
此问要求我们根据时间和重量等方面的约束来建立一个合理的邮件配送模
型。当邮递员数量最少且送货总距离最小时可得到比较合理的送货策略。
当送货所需的总行驶距离为最小时，所需的送货时间和所需的邮递员都将最
少。因此我们考虑建立以送货总行驶距离最小为目标函数的数学模型。为了得到
简化的数学模型，我们首先假定将所有送货点分为 N 个送货区，在最优化总体
送货总距离的基础上为 N 个送货区分得一些送货点，并得出此区域内的送货具
体线路（即顺序），然后再根据时间的约束为每位邮递员分配送货区域，以此来
得到一个较优的合理的送货方案。
先设立如下变量：
：
：第 i 个送货点的邮件重量
0 1R j
d 表示原点和第j 个送货区内第一个送货点之间的距离
0R jk j
d
表示原点和第j 个送货区内最后一个送货点之间的距离
jiw
0 i j
i j
{jiw
表示第 个送货点不属于第 个送货区
1表示第 个送货点属于第 个送货区
jjmR ：第 个送货区内的k个送货点之间的有序线路解集
mnd : 两送货点之间的最短折线距离
iG
以总行驶距离最小为目标函数：
约束条件：
每天每个送货点只由一个邮递员送一次货:
（二）模型求解
（1）定义路径矩阵
由于有序解集R的难以确定性，为了方便求解我们引入一新变量路径矩阵D：
设 的矩阵D是所求的一条解路径, 它满足每行每列有且仅有一个元素为1,
其余为0。 表示路径 中存在从送货点 到送货点 的边 , 显然, 当
时必有 。这是一种基于边的路径编码方法, 如图1（a）所示的矩阵
是四个送货点的一个解, 它表示如图1( b) 所示的一条解路径。
（a） (b)
图1
因此可由路径矩阵D得到有序解集R：
当矩阵D满足 时可得到唯一的有序
1
0 01 11 1
[ ) ]min (
N k
R R R Rjm jm j jkj m j
d d d
1
1
N
ijj
w
1 2 3... 0i 3
k每个送货区的送货点个数等于相应的 值：
30
1 ij ji
w k
1 2 3... 0j 3
25每个邮递员每次出发带邮件不超过 千克：
30
1
25ij i
i
w G
1 2 3... 0j 3
6每趟送货不能超过 小时：
1
0 030 1 11
1
)
( )
(
1
6 25
k
R R R Rjm jm j jkm
ij
i
d d d
w
6
k*k
( , ) 1D i j D ic jc ije
i j ( , ) 0D i j
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
1 3 4 2 1c c c c c
( , ) 1& ( , ) 1&... ( , ) 1)...D i j D j k D n n d
解集R：
其中
（2）确定算法
送货路径问题是物流送的核心问题,对于此类多变量，多可行性的问题，一般
难以由LINGO等软件直接求得最优解。本题我们采用一种基于路径问题的遗传
算法，通过在MATLAB中编程求得了较优解。
遗传算法( Genetic Algorithm, 简称为GA) 是基于“适者生存”的一种高度并行、
随机和自适应化的优化算法, 它将问题的求解表示成“染色体”的适者生存过程,
通过“染色体”群的一代代不断进化, 最终收敛到“最适应环境”的个体, 从而寻求
得到问题的最优解或满意解。
求解本题具体算法流程如下：
（3）计算结果
针对题目中所给数据用 MATLAB 软件对该模型进行编程求解得到最短送货
总距离为 528km。
由解得到每个送货区的划分，并根据题中所给数据信息可得其区内一组最短
路线以及送货一趟所需总时间：
[ , , .. , ..]R i j k n n d , , .. , ..i j k n n d N
初始化路径矩阵 D
进化代数加 1
交叉、变异
内部扰动
此群体能进化
满足终止条件
结束算法
外部扰动
送货区序号 每个送货区包含的送货点及
其一组最短路线
给每个区送货的总时间
1
2
3
4
5
6
7
8
由上图得所有送货总时间约为 小时，题中要求每个业务员每天平均
工作时间不超过 6 小时。由 5*6=30>，所以只需 5 个业务员便可达到要
求，如果出现某些送货任务超过 6 小时而有些不到 6 小时的时候，只需 5 个业务
员进行轮流换班送货即可。据此用 MATLAB 软件编程对 8 个送货区进行分组，
分为 5 个组，使每个组的送货总时间为接近 6 的最优解：
组号 每个组所含送货区 送货时间（小时）
① 7
① 2
① 5 8
① 1 3
① 4 6
据此需要的业务员数量为 5 个，无需轮流换班，如果考虑每个业务员之间的
公平性则可让每个业务员按天轮流给每个组送货，总的运送公里为 528km。
问题二： 为公司设计一个费用最省的策略
模型的分析建立
在这一问中由于业务员送货行程及其邮件重量决定了主要的费用，与邮递员的安
排无关，所以我们以运费总费用最小为目标函数建立模型：
式中 表示第 j 个送货区的第 m 个送货点的邮件重量。
约束条件：
每天每个送货点只由一个邮递员送一次货:
15 25 24 14
23 18 17 20
22 11 9 2
6 7 13 19
3 12 4
1 5 16 2
10 29 30 28
8 27 26
1
0 01 11 1 1
min (3 ( ) ( ) 2 )
N k m
jmR R R Rjn jn j jkj m n
d d G R d
( )jmG R
1
1
N
ijj
w
1 2 3... 0i 3
k每个送货区的送货点个数等于相应的 值：
30
1 ij ji
w k
1 2 3... 0j 3
模型的求解
针对题目中所给数据用 MATLAB 软件采用问题一所述的遗传算法对该模型
进行编程求解得到最小费用为 15742 元。
由解得到每个送货区的划分，并根据题中所给数据信息可得其区内一组最短
路线以及送货一趟所需总时间：
送货区序号 每个送货区包含的送货点及
其一组最短路线
所需费用（元）
1 +003
2 +003
3 +003
4 +003
5 +003
6 1122
7 +003
8 +003
问题三：在平均每天工作时间允许延长为 8 小时后建立送货策略
此问要求我们如果可以延长业务员的工作时间到 8 小时，求公司的送货策略。
这里我们可以沿用问题一的模型，并将其中每趟送货不超过 6 个小时的约束条件
改为不超过 8 个小时，再用 MATLAB 软件求得最优送货区的划分：
送货区序号 每个送货区包含的送货点及
其一组最短路线
给每个区送货的总时间
1
2
3
4
5
6
25每个邮递员每次出发带邮件不超过 千克：
30
1
25ij i
i
w G
1 2 3... 0j 3
6每趟送货不能超过 小时：
1
0 030 1 11
1
)
( )
20 30
(
1
6
k
R R R Rjm jm j jkm
ij
i
d d d
w
6
14 25 24 15
20 17 18 23
2 9 11 22
6 7 13 19
3 4 12
1 2 5 16
10 29 30 28
8 27 26
15 25 24 14
23 18 17 20
22 11 9 2
6 7 13 19
3 12 4
1 5 16 2
7
8
再在工作时间变为 8 小时的基础上，为每位邮递员分配送货区域，以此来得
到一个较优的合理的送货方案。
由上表得所有送货总时间与问题一的结果一样约为 小时，题中要求
每个业务员每天平均工作时间不超过 8 时。由 4*8=32>，得只需 4 个业
务员即可，如果出现某些送货任务超过 8 小时而有些不到 8 小时的时候，只需 4
个业务员进行轮流换班送货即可达到要求。据此用 MATLAB 软件编程对 8 个送
货区进行分组，分为 4 个组，使每个组的送货总时间为接近 8 的最优解：
组号 每个组所含送货区 送货时间（小时）
① 1 2 7
① 3 4
① 5 8
① 6 7
据此需要的业务员数量为 4 个，业务员无需换班，如要考虑每个业务员之间
的公平性的话，亦可轮流换班送货。总的运送公里为 528km。
五、模型评价与推广
模型的优点
在建立模型时我们都是将问题转换为一个数学目标函数，模型结果一方面具
体分配出了送货策略，另一方面模型简单清晰，便于理解和推广。
在求解分析中灵活的将有序路径问题引入到矩阵中，以求解变量路径矩阵的
方式进行分区路线的求解；另外在求解过程中用 MATLAB 并结合运用遗传算法
得出了比较理想的送货策略。
模型的缺点
由于实际中送货问题与许多变量有关，而我们模型中为了使其简化只考虑了
少量主要变量，像业务员来回送货时要用时间，还有可能实践中遇到堵车等耗时
现象，这些问题都可能使实际结果偏离具体的送货策略。
另外我们模型完全依靠软件求解，在多变量的情况下数据计算量很大，因此
在计算机条件有限的情况下求得最优解比较困难。
模型的推广
此模型不但能应用于送货策略，也可推广到各种物流分配，车辆运输、城市网络
布线等方面。
10 29 30 28
8 27 26
