快递公司送货策略的优化设计
摘要
在快递送货过程中，合理选择送货线路是极其重要的，它不仅可以加快配送速度, 提高服务质量，还可以有效的降低配送成本，增加经济效益。本文构建了送货线路的规划模型，将送货问题转化为运筹学中的旅行推销问题进行求解，但在街道平行行走中，以阶梯法求最短路程，根据运输路线优化策略中的时间的最优组法，用射线旋转法进行区域划分，以送货重量的80~90%为划分依据，利用整数规划对每一个区域进行线路规划，从而得到最优线路。该模型对物流企业合理安排送货线路, 提升运送效率有着很强的理论指导作用，因而有着重大的实用价值。
1 问题的提出：
在快递传递工程中，所有快件在早上7点钟到达，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km /h ，每次出发最多能带25kg 重量，公司平均每天接受到总重量为184. 5kg 的快件。
1.1 每天接收到的总重量是否全部送至30个送货点？
1.2 每个业务员工作时间不超过8小时，每个业务员的平均工作时间不超过6小时。假如某一业务员每天送完第一线路后是否再有下一次线路？ 1.3 如何使用射线旋转法与旅行推销问题中特殊的“阶梯法”求解。
2 问题的分析：
2.1 对于现实问题当中，每个送货点每天的送货量有一定的波动，对某些送货点就单独某天是否送货，有一定的概率。根据题意，结合所有30个送货点总重量184. 5kg 约等于每天接受的重量，因此我们不考虑其他因素。直接对个送货点配备送货策略。
2.2 送货线路与业务员有间接关系，但送货路线数不等于业务员数。我们根据最优送货线路的最短时间的关系组合来确定业务员的数量，因此为了消除送货路线与业务员数的误差，我们提出以所携带总重量的(80~90%)的依据。 2.3 我们提出射线旋转法，将随机的、不确定的、无规律的点进行区域划分，再对每个线路又进行线路规划。这样可有效减少线路重复问题，他是解决旅游途中如何经过旅游单中的城市而不重复旅游过的城市却要行程距离最短。其中两点直线走法，涉及到现实生活中很多实际的问题。而“快递转送”是旅游推销问题中的特殊问题。
它以街道平行的轴进行两直角边行走。例如图（1）所示，
A —B —C —直线走最短，但在平行街道当中，以①-②-③-④-⑤-⑥如上阶梯法走最短。
3 模型假设：
根据30个送货点所处的位置的随机性及送货过程中行走路程的重复性和行程最短问题，我们“射线旋转法和阶梯法”的模型假设。其中射线旋转中依据所携带总重量的(80~90%)以整个区域划分为主，个别小区域等不符合区域以单独进行射线旋转法划分，以做到整数规划，再对每一个区域进行线路规划。然后用阶梯法进行求最短问题。
4 符号说明
G ： 送货总重量。
W i ：在i 点所卸的货的重量。
∑W (max ) ：两条射线所夹送货点重量之和
r r
n
A x (∑W r (max ) , p x ) ：其中
r
n
∑W (max ) 表示两条射线所夹送货点重量之和
r r
n
p x =
∑W
i =1
n
x
(max )
⨯100%
G
A x ：表示两条射线所夹部分区域记为A x 。
(x , y )：在图（3）和图（4）中x 表送货点数，y 表示x 送货点所卸的货重
S A (min)：A
x
x
区域中走完所有送货点的最短距离。
S X ：表示原点O 到点x 点最短距离。
S x -y (min)：表示点x 到点y 所走的最短距离。
t A x (min)：表示在A x 区域中，满足S x (min)的所需要的时间。
n ：表示A x 区域中所夹的送货点数。
S 'A (min)：表示第A
x
x
区域中支出金额最少所走的距离。
(min)的所需要的时间。 t 'A x (min)：表示在A x 区域中，满足S 'A
x
M A x ：在A x 区域中，给业务员所支付的费用。
S AC (m in ) ：A 点与C 点的最短距离。
5 模型建立及求解
5.1 模型建立 5.11射线旋转法假设
5.111 以快递公司及发货中心，平行于街道的直线为坐标建立直角坐标系。 射线旋转法进行划分依据 ：射线旋转法以送货总重量的G 快递公司每个业务员的每次最多能携带的重量25kg ⨯(80~90%)为划分依据，但为了整体划分，精确模式，在此基础上可以波动。定义送货总量的G ⨯(80~90%)的依据，是考虑到克服所有送货人所携带重量的参差性和送货路线与送货人数的相关性，这样可以大幅度的个别因素对整体的影响。
记每个发货量最大不超过G ，当射线旋转时与射线重合的点记：P (X i ，Y i ) 。相应于该点出所卸的货的重量W i 。
以x 轴为初始射线l 1，以O 点为圆心，按逆时针方向旋转，当遇到第一个点时，判断
W 1≤G (80~90%)
若满足继续旋转，直临界射线l 2，且
∑W (max ) ≤G (80~90%)
i i =1
n
时停止，并记该区域为：
A 1(∑W i (max ) , p 1)
i =1
n
其中:
p 1=
∑W (max )
i i =1
n
G
⨯100%
以l 2为初始射线旋转，当遇到相应下一点M 时, 判断
W m ≤G (80~90%)
若满足继续旋转直到临界射线l 3，且
m =i +1n
∑W
n
m
(max ) ≤G (80~90%)
时停止，并记该区为：以此类推。
A 2(∑W m (max ) , p 2)
i =1
。
以l k 做初始射线旋转，当遇到下一点R 是
W r ≤G (80~90%)
若满足继续旋转直到临界射线l k +1，使满足
∑W (max ) ≤G (80~90%)
r r
n
时停止，并记该区为：A x (∑W r (max ) , p x ) 。
r
n
5.112 在5.111中规划区域中，当射线旋转到有两个或多个点重合时且
∑W (max ) >G 时，我们应该如下：
r r
n
5.1121 当射线l i 旋转到有两个或多个点重合或时，将射线继续旋转直到l i +1，使满足
∑W (max ) >G
r r
n
∑W (max ) ≤2⨯G (80~90%)
r r
n
时为止。
若l i +1同时也有两个或多个点重合或∑W r (max ) >2⨯G ) 时将射线继续旋转
r n
直到l i +2，使满足
∑W (max ) ≤3⨯G (80~90%)
r r
n
同理，若l i +j 同时也有两个或多个点或∑W r (max ) >j ⨯G 时，将射线旋转直到l i +j +1
r
n
使满足
∑W (max ) ≤(j +1) ⨯G (80~90%)
r r
n
时为止。
继续如上划分直到完毕。
5.1122 将划分出的区域有∑W r (max ) >G 的区域继续利用射线旋转再进行筛
r n
选，选出符合条件的最优区域。
5.12 阶梯法模型：行走路线像阶梯一样的模型，我们定义为阶梯模型。 对于射线旋转法可以确定每条路线所经过的送货点，至于如何走最近，我们根据模型特点，证明一个“公理”。
例：例如如图（2）所示，B 在A 、C 两点的对角线的矩形里面。从A 带你出发，经过B 、C 两点走法又回到A 点，只能沿如图线路走，每条线段长为L 。求证：阶梯法是走法最短的一种方式 。 证明：
A ——C 行程路径 S AC (m in ) =
6L
A ——B 行程路径 S AB (m in ) =3L B ——C 行程路径 S BC (m in ) =3L
显然，S AC (m in ) =S AB (m in ) +S BC (m in ) 因此，当Ｂ在以AC 为对角线的矩形里，且B 在A 通往C
某一条线路里，我们可直接用阶梯法走是距离最短的一条方案。 5.2 求解旋转，以射线旋转法为理论依据作图解答：
5.21如图所示：以O 为原点，以x 轴为l 0起始射线绕O 旋转。当∑W i (max ) =25
i =1n
时, 记该区域为: A 1(25, 100%).
再以A 1区l 1为起始射线绕O 逆时针旋转到l 2时得到符合
∑W (max ) ≤G (80~90%)
i i =1
n
记该区域为A 2(18. 5, 74%)。
再以A 1区l 2为起始射线绕O 旋转到k 1时出现模糊地选法(即有两个或多个点重合或∑W r (max ) >G ) ，故继续旋转2⨯25kg (80~90%)到射线k 2时，送货点3与
r n
13在同一条直线上，故继续旋转，使满足
∑W (max ) ≤3⨯(80~90%)
r r
n
为止，记该区域为： A 3(60. 2, 240. 8%).
再以A 3区l 3为起始射线绕O 旋转到l 4时，使满足
∑W (max ) ≤G (80~90%)
r r
n
为止，记该区域为：A 4(18. 6, 74. 4%)。 再以l 4为起始射线绕O 旋转到l 5时，使满足
∑W (max ) ≤G (80~90%)
i i =1
n
记该区域为： A 5(23. 8, 93. 6%)。
最后将l 5与y 轴区域记为：A 6(22. 5, 90%)。 如图（3）所示：
5.22 由以上可划分出最优选点策略A 1, A 2, A 4A 5A 6区。 将A 3区用射线旋转法划出最优区，作法如下： 以l 3为初始射线，绕O 顺时针旋转到k 2时得到符合
∑W (max ) ≤G (80~90%)
i i =1
n
记该区域为A 31(19. 8, 79. 2%)。
再以k 2为初始射线，绕O 顺时针旋转到k 1时得到符合
∑W (max ) ≤G (80~90%)
i i =1
n
记该区域为A 32(20. 3, 81%)。
最后记录k 2和l 2之间的区为：A 33(20. 1, 80. 4%)如图（4）所示。
5.3 根据阶梯法求解行程距离最短时的优化区域的线路选择：
A 1区中：
S A (min)=S
1
9
(min)+S 11-9(min)+S 32-11(min)+S 32(min)
=12+8+7+27
=54km
所需时间
S A 1(min)1
+⨯n t A 1(min)=
256
≈3. 0h
A 2区中：
S
A 2
(min)=S 12(min)+S 15-12(min)+S 23-15(min)+S 23(min)
=20+8+16+36
=88km
所需时间
S A 2(min)1
t A 2(min)=+⨯n
256
=
751+⨯3 256
≈3. 5h
A 33区中：
S
A 33
(min)=S 27(min)+S 29-27(min)+S 29(min)
=34+7+41
=82km
所需时间
S A 33(min)1
t A 33(min)=+⨯n
256
=
821+⨯2 256
≈3. 613h
A 32区中：
S
A 32
(min)=S 1(min)+S 8-1(min)+S 13-8(min)+S 30-13(min)+S 30(min)
=5+10+6+25+46
=92km
所需时间
t A 32(min)=
=
S A 32(min)1
+⨯n 256921+⨯4 256
≈4. 35h
A 31区中：
S
A 31
(m i n =) S 3(m i n +) S 19-3(m i n +) S 28-19(m i n +) S 28(m i n )
=9+18+17+44
=88km
所需时间
S A 31(min)1
t A 31(min)=+⨯n
256
=
881+⨯3 256
≈4. 02h
A 4区中：
S A (min)=S
4
7
(min)+S 14-7(min)+S 25-14(min)+S 24-25(min)+S 24(min)
=68km 所需时间
S A 5(min)1
t A 4(min)=+⨯n
256
=
681+⨯4 256
≈3. 39h
A 5区中：
S A (min)=S
5
4
(min)+S 20-4(min)+S 17-20(min)+S 18-17(min)+S 18(min)
=11+10+5+6+28
=60km
所需时间
t A 5(min)=
=
S A 5(min)1
+⨯n 256601+⨯4 256
≈3. 06h
A 6区中：
S
A A 6
(min)=S 2(min)+S 5-2(min)+S 16-5(min)+S 16(min)
=6+8+6+18
=38km
所需时间
t A (min)=
6
S A 6(min)1
+⨯n 256
=
381+⨯4 256
≈2. 19h
由以上计算可得总路程、总时间分别为：
S
)+S A 33(m i n )+S A 32(m i n )+S A 31(m i n )+S A 4(m i n ) =S A 1(m i n +) S A 2(m i n
)+S A 6(m i n ) +S A 5(m i n
=54+88+82+92+88+68+60+38
=570km
t
=t A 1(min)+t A 2(min )+t A 33(min )+t A 32(min )+t A 31(min )
+t A 4(min )+t A 5(min )+t A 6(min )
=3+3. 5+3. 613+4. 35+4. 02+3. 39+3. 06+2. 19=27. 127h
因此平均人数
Men =
____
t
6
=4. 52
所以需要5个业务员，总的运行公里数为570km 。
为了减少每个人所携带重量的相对参差性，我们将时间最短的四组组合，使其按大小排序，第一个和第三个组合，第二个和底四的个组合。 即：最小四个为：3.5 3.06 3 2.19 可得到时间为2.19与3.06、3与3.5的路线各一人送货。 综上所述
时间为2.19与3、3.06与3.5、3.613、4.35、4.02的路线分别分派一个人去送货，每人的送货路线依次为：
第一个业务员：A 1区中： 9—11—32—22—10号送货点
A 2区中：12—15—23号送货点点
第二业务员：A 5区中：4—20—17—18号送货点
A 6区中：2—5—16—6号送货点
第三业务员：A 33区中：27—29号送货点 第四业务员：A 32区中：1—8—13—30号送货点 第五业务员：A 31区中：3—19—28号送货点
5.4 根据送货路程价位，我们只能让离原点最远的点最后走，因此我们对每个区域再进行阶梯法预算得：
A 1区中：32送货点最后走的最短路径时、支付金额和时间分别为：
S 'A 1(min)=S 9(min)+S 10-9(min)+S 10-11(min)+S 32-11(min)+S 32
=12+6+6+7+27
=58km
M A 1=[S 9(min)+S 10-9(min)+S 10-11(min)+S 32-11(min)]⨯3+S 32(min )⨯2
=31⨯3+27⨯2 =147（元）
t 'A 1(min)=
=
S 9(min)+S 10-9(min)+S 10-11(min)+S 32-11(min)S 32(min )1
++⨯n
2030631271
++⨯5 20306
≈3. 28h
A 2区中：23送货点最后走的最短路径、支付金额和时间分别为：
S 'A 2(min)=S 12(min)+S 15-12(min)+S 23-15(min)+S 23(min)
=20+8+16+36
=88km
M A 2=[S 12(min)+S 15-12(min)+S 23-15(min)]⨯3+S 23(min)⨯2
=44⨯3+36⨯2
=204（元）
t 'A 2(min)=
=
S 12(min)+S 15-12(min)+S 23-15(min)S 23(min )1
++⨯n
2030644361
++⨯5 20306
≈4. 23h
A 33区中：29送货点最后走的最短路径、支付金额和时间分别为：
S 'A 33(min)=S 27(min)+S 29-27(min)+S 29(min)
=34+7+41
=82km
M A 33=[S 27(min)+S 29-27(min)]⨯3+S 29(min)⨯2
=41⨯3+41⨯2 =205（元）
t 'A 33(min)=
=
S 27(min)+S 29-27(min)S 29(min)1
++⨯n
2030641411++⨯2 20306
≈3. 75h
A 32区中：30送货点最后走的最短路径、支付金额和时间分别为：
S 'A 32(min)=S 1(min)+S 8-1(min)+S 13-8(min)+S 30-13(min)+S 30(min)
=5+10+6+25+46
=92km
M A 32=[S 1(m i n ) +S 8-1(m i n +) S 13-8(m i n +) S 30-13(m i n ⨯) 3] +S 30(m i n ⨯) 2
=46⨯3+46⨯2 =230（元）
t 'A 32(min)=
S 1(min)+S 8-1(min)+S 13-8(min)+S 30-13(min)S 30(min)1
++⨯n
20306
=
46461++⨯4 20306
≈4. 5h
A 31区中：28送货点最后走的最短路径、支付金额和时间分别为：
) S '=) S 3(m i n +) S 19-3(m i n +) S 28-19(m i n +) S 28(m i n A 31(m i n
=9+18+17+44
=88km
M A 31=[S 3(min)+S 19-3(min)+S 28-19(min)]⨯3
+S 28(min)⨯2
=44⨯3+44⨯2 =220（元）
t 'A 31(min)=
=
S 3(min)+S 19-3(min)+S 28-19(min)S 28(min)1
++⨯n
2030644441
++⨯3 20306
≈4. 17h
A 4区中：24送货点最后走的最短路径、支付金额和时间分别为：
S 'A 4(min)=S 7(min)+S 14-7(min)+S 25-14(min)+S 24-25(min)+S 24(min)
=68km
M A 4=[S 7(min)+S 14-7(min)+S 25-14(min)+S 24-25(min)]⨯3+S 24(min)⨯2
=34⨯3+34⨯2
=170（元）
t 'A 4(min)=
=
S 7(min)+S 14-7(min)+S 25-14(min)+S 24-25(min)S 24(min)1
++⨯n
2030634341
++⨯4 20306
≈3. 5h
A 5区中：18送货点最后走的最短路径、支付金额和时间分别为：
S 'A 5(min)=S 4(min)+S 20-4(min)+S 17-20(min)+S 18-17(min)+S 18(min)
=11+10+5+6+28
=60km
M A 5=[S 4(min)+S 20-4(min)+S 17-20(min)+S 18-17(min)]⨯3+S 18(min)⨯2
=32⨯3+28⨯2 =150（元）
t 'A 5(min)=
=
S 4(min)+S 20-4(min)+S 17-20(min)+S 18-17(min)S 18(min)1
++⨯n
2030632281
++⨯4 20306
≈3. 2h
A 6区中：16送货点最后走的最短路径、支付金额和时间分别为： S ' ) =) S 2(m i n +) S 6-2(m i n +) S 5-6(m i n +) S 16-5(m i n +) S 16(m i n A 6(m i n =6+4+6+6+18
=40km
M A 6=[S 2(min)+S 6-2(min)+S 5-6(min)+S 16-5(min)]⨯3+S 16(min)⨯2
=22⨯3+18⨯2 =102（元）
t 'A 6(min)=
=
S 2(min)+S 6-2(min)+S 5-6(min)+S 16-5(min)S 16(min)1
++⨯n
2030632181
++⨯4 20306
≈2. 37h
综上所述：
''''S '=S '(min)+S 'A A 2(min )+S A 33(min )+S A 32(min )+S A 31(min )+S A 4(min )1
)+S ') +S 'A 5(m i n A 6(m i n
=58+88+82+92+88+68+60+40
=576km
''' t '=t '(min)+t 'A A 2(min )+t A 33(min )+t A 32(min )+t A 31(min )1
)+t ')+t ') +t 'A 4(m i n A 5(m i n A 6(m i n
=3. 28+4. 23+3. 75+4. 5+4. 17+3. 5+3. 2+2. 37
=29h
)+M A 33(m i n )+M A 32(m i n )+M A 31(m i n )M (m i n =) M A 1(m i n +) M A 2(m i n
)+M A 5(m i n )+M A 6(m i n ) +M A 4(m i n
=147+204+205+230+220+170+150+102
=1428（元） 所需人数
M e n
____
=
=
t 6
29
6
=4. 83
因此需要5个业务员最省钱，公司将最少支出1428元。 将送货路线中时间最短的组合可得 即 3.5 3.28 3.2 2.37
可得到时间为2.37与3.28、3.2与3.5的路线各一人送货
时间为2.37与3.28、3.2与3.5、4.23、4.17、4.5的路线分别分派一个人去送货，每人的送货路线依次为：
第一业务员：A 1区中：9—10—11—22—32号送货点 A 6区中：2—6—5—16号送货点 第二业务员：A 4区中： 7—14—25—24号送货点
A 5区中：4—20—17—18号送货点
第三业务员：A 2区中：12—15—23号送货点 第四业务员：A 31区中：3—19—28号送货点
第五业务员：A 32区中：1—8—13—30号送货点
6 结果分析与检验
本文主要问题是对所有送货点进行区域划分，因此我们引进了射线旋转法进
行划分，将依据G ⨯(80~90%)排除了送货路线与业务员的影响。使业务员数减少到最少，但在射线旋转法里我们有引进射线旋转法旋转满足
∑W (max ) ≤(j +1) ⨯G (80~90%)，使局部因素内部处理更一步减少了射线旋转
r r
n
法带来的误差。因此射线旋转法根据大量资料可证明减少了由线路数量与业务员数相互影响的误差。
7 讨论模型
根据我们对网上查找资料和大量模拟实验表明：射线旋转G ⨯(80~90%)的
依据进行划分，大量减少了误差与优化了方案。它以一种新的思想进行了随机相连点的划分，并减少了由线路数量与业 员数相互影响的误差。但避免不了现实
当中所有点满足
∑W (max ) ≤G (80~90%)
r r
n
。因此在小模型划分中有相当大的误
差。阶梯法相对误差来自射线旋转法，其本身是一种求最短路程的方法之一。
8 参考文献
[1] 沈荣芳. 运筹学. 上海同济大学.1999.8
[2] 刑文训 谢金星. 现代优化 计算方法. 北京. 清华大学出版社.1999.8 [3] 汪定伟 王洪峰 张瑞友 郭哲. 智能优化方法. 高等教育出版社.2007.4