快递公司送货策略的优化设计

快递公司送货策略的优化设计

摘要

在快递送货过程中，合理选择送货线路是极其重要的，它不仅可以加快配送速度,提高服务质量，还可以有效的降低配送成本，增加经济效益。本文构建了送货线路的规划模型，将送货问题转化为运筹学中的旅行推销问题进行求解，但在街道平行行走中，以阶梯法求最短路程，根据运输路线优化策略中的时间的最优组法，用射线旋转法进行区域划分，以送货重量的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： 送货总重量。

Winr：在i点所卸的货的重量。

rW(max)：两条射线所夹送货点重量之和

Ax(Wr(max),px)：其中

rnW(max)表示两条射线所夹送货点重量之和

rrn pxWi1nx(max)100%

G可编辑

精品

Ax：表示两条射线所夹部分区域记为Ax。

x,y：在图（3）和图（4）中x表送货点数，y表示x送货点所卸的货重

SA(min)：Axx区域中走完所有送货点的最短距离。

SX：表示原点O到点x点最短距离。 Sxy(min)：表示点x到点y所走的最短距离。

tAx(min)：表示在Ax区域中，满足Sx(min)的所需要的时间。 n：表示Ax区域中所夹的送货点数。

SA(min)：表示第Axx区域中支出金额最少所走的距离。

t(min)的所需要的时间。 Ax(min)：表示在Ax区域中，满足SAxMAx：在Ax区域中，给业务员所支付的费用。

SAC(min)：A点与C点的最短距离。

5 模型建立及求解

5.1 模型建立 5.11射线旋转法假设

5.111 以快递公司及发货中心，平行于街道的直线为坐标建立直角坐标系。 射线旋转法进行划分依据 ：射线旋转法以送货总重量的G快递公司每个业务员的每次最多能携带的重量25kg(80~90%)为划分依据，但为了整体划分，精确模式，在此基础上可以波动。定义送货总量的G(80~90%)的依据，是考虑到克服所有送货人所携带重量的参差性和送货路线与送货人数的相关性，这样可以大幅度的个别因素对整体的影响。

记每个发货量最大不超过G，当射线旋转时与射线重合的点记：相应于该点出所卸的货的重量

WiP(Xi，Yi)。

。

可编辑

精品

以x轴为初始射线l1，以O点为圆心，按逆时针方向旋转，当遇到第一个点时，判断

W1G(80~90%)

若满足继续旋转，直临界射线l2，且

W(max)G(80~90%)ii1n

时停止，并记该区域为：

A1(Wi(max),p1)i1n

其中:

p1W(max)ii1nG100%

以l2为初始射线旋转，当遇到相应下一点M时,判断

WmG(80~90%)

l若满足继续旋转直到临界射线3，且

mi1nWnm(max)G(80~90%)

。

时停止，并记该区为：以此类推。

A2(Wm(max),p2)i1以lk做初始射线旋转，当遇到下一点R是

WrG(80~90%)

若满足继续旋转直到临界射线lk1，使满足

W(max)G(80~90%)

rr可编辑

n精品

时停止，并记该区为：Ax(Wr(max),px) 。

rn5.112 在5.111中规划区域中，当射线旋转到有两个或多个点重合时且

W(max)G时，我们应该如下：

rrn5.1121 当射线li旋转到有两个或多个点重合或时，将射线继续旋转直到li1，使满足

W(max)G

rrnW(max)2G(80~90%)

rrn时为止。

若li1同时也有两个或多个点重合或Wr(max)2G)时将射线继续旋转

rn直到li2，使满足

W(max)3G(80~90%)

rrn同理，若lij同时也有两个或多个点或Wr(max)jG时，将射线旋转直到lij1rn使满足

W(max)(j1)G(80~90%)

rrn时为止。

继续如上划分直到完毕。

5.1122 将划分出的区域有Wr(max)G的区域继续利用射线旋转再进行筛

rn选，选出符合条件的最优区域。

5.12 阶梯法模型：行走路线像阶梯一样的模型，我们定义为阶梯模型。

可编辑

精品

对于射线旋转法可以确定每条路线所经过的送货点，至于如何走最近，我们根据模型特点，证明一个“公理”。

例：例如如图（2）所示，B在A、C两点的对角线的矩形里面。从A带你出发，经过B、C两点走法

又回到A点，只能沿如图线路走，每条线段长为L。求证：阶梯法是走法最短的一种方式 。 证明：

A——C 行程路径 SAC(min)6L A——B 行程路径 SAB(min)3L B——C 行程路径 SBC(min)3L

显然，SAC(min)SAB(min)SBC(min)因此，当Ｂ在以AC为对角线的矩形里，且B在A通往C

某一条线路里，我们可直接用阶梯法走是距离最短的一条方案。 5.2 求解旋转，以射线旋转法为理论依据作图解答：

5.21如图所示：以O为原点，以x轴为l0起始射线绕O旋转。当Wi(max)25i1n时,记该区域为: A1(25,100%).

再以A1区l1为起始射线绕O逆时针旋转到l2时得到符合

W(max)G(80~90%)

ii1可编辑

n精品

记该区域为A2(18.5,74%)。

再以A1区l2为起始射线绕O旋转到k1时出现模糊地选法(即有两个或多个点重合或Wr(max)G)，故继续旋转225kg(80~90%)到射线k2时，送货点3与

rn13在同一条直线上，故继续旋转，使满足

W(max)3(80~90%)

rrn为止，记该区域为： A3(60.2,240.8%).

再以A3区l3为起始射线绕O旋转到l4时，使满足

W(max)G(80~90%)

rrn为止，记该区域为：A4(18.6,74.4%)。 再以l4为起始射线绕O旋转到l5时，使满足

W(max)G(80~90%)

ii1n记该区域为： A5(23.8,93.6%)。

最后将l5与y轴区域记为：A6(22.5,90%)。 如图（3）所示：

可编辑

精品

5.22 由以上可划分出最优选点策略A1,A2,A4A5A6区。 将A3区用射线旋转法划出最优区，作法如下： 以l3为初始射线，绕O顺时针旋转到k2时得到符合

W(max)G(80~90%)

ii1n记该区域为A31(19.8,79.2%)。

再以k2为初始射线，绕O顺时针旋转到k1时得到符合

W(max)G(80~90%)

ii1n记该区域为A32(20.3,81%)。

最后记录k2和l2之间的区为：A33(20.1,80.4%)如图（4）所示。

可编辑

精品

5.3 根据阶梯法求解行程距离最短时的优化区域的线路选择：

A1区中：

SA(min)S19(min)S119(min)S3211(min)S32(min)

128727

54km

所需时间

tA1(min)SA1(min)251n 63.0h

A2区中：

SA2(min)S12(min)S1512(min)S2315(min)S23(min)

2081636

88km

所需时间

可编辑

精品

tA2(min)SA2(min)251n 67513 2563.5h

A33区中：

SA33(min)S27(min)S2927(min)S29(min)

34741

82km

所需时间

tA33(min)SA33(min)251n 68212 2563.613h

A32区中：

SA32(min)S1(min)S81(min)S138(min)S3013(min)S30(min)

51062546

92km

所需时间

tA32(min)SA32(min)251n 69214 2564.35h

A31区中：

SA31(min)S3(min)S193(min)S2819(min)S28(min)

9181744

可编辑

精品

88km

所需时间

tA31(min)SA31(min)251n 68813 2564.02h

A4区中：

SA(min)S47(min)S147(min)S2514(min)S2425(min)S24(min)

68km 所需时间

tA4(min)SA5(min)251n 66814 2563.39h

A5区中：

SA(min)S54(min)S204(min)S1720(min)S1817(min)S18(min)

11105628

60km

所需时间

tA5(min)SA5(min)251n 66014 2563.06h

A6区中：

SAA6(min)S2(min)S52(min)S165(min)S16(min)

68618

可编辑

精品

38km

所需时间

tA(min)6SA6(min)251n 63814 2562.19h

由以上计算可得总路程、总时间分别为：

SSA1(min)SA2minSA33minSA32minSA31minSA4min

SA5minSA6min

5488829288686038

570km

ttA1(min)tA2mintA33mintA32mintA31min

tA4mintAmintAmin

5633.53.6134.354.023.393.062.1927.127h 因此平均人数

tMen

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的路线分别分派一个人去送货，每人的送货路线依次为：

第一个业务员：A1区中： 9—11—32—22—10号送货点

A2区中：12—15—23号送货点点

第二业务员：A5区中：4—20—17—18号送货点

A6区中：2—5—16—6号送货点

第三业务员：A33区中：27—29号送货点 第四业务员：A32区中：1—8—13—30号送货点 第五业务员：A31区中：3—19—28号送货点

5.4 根据送货路程价位，我们只能让离原点最远的点最后走，因此我们对每个区域再进行阶梯法预算得：

A1区中：32送货点最后走的最短路径时、支付金额和时间分别为：

SA1(min)S9(min)S109(min)S1011(min)S3211(min)S32

1266727

58kmMA1[S9(min)S109(min)S1011(min)S3211(min)]3S32min2

313272 147（元）

tA1(min)S9(min)S109(min)S1011(min)S3211(min)S32min1n

20306312715 203063.28h

A2区中：23送货点最后走的最短路径、支付金额和时间分别为：

Sin)S12(min)S1512(min)S2315(min)S23(min) A2(m可编辑

精品

2081636

88km

MA[S12(min)S1512(min)S2315(min)]3S23(min)2

2443362 204（元）

tA2(min)S12(min)S1512(min)S2315(min)S23min1n

20306443615 203064.23h

A33区中：29送货点最后走的最短路径、支付金额和时间分别为：

SA33(min)S27(min)S2927(min)S29(min)

34741

82km

MA33[S27(min)S2927(min)]3S29(min)2

413412 205（元）

tA33(min)S27(min)S2927(min)S29(min)1n

20306414112 203063.75h

A32区中：30送货点最后走的最短路径、支付金额和时间分别为：

SA32(min)S1(min)S81(min)S138(min)S3013(min)S30(min)

51062546

92km

MA32[S1(min)S81(min)S138(min)S3013(min)]3

S30(min)2

可编辑

精品

463462 230（元）

tA32(min)S1(min)S81(min)S138(min)S3013(min)S30(min)1n

20306464614 203064.5h

A31区中：28送货点最后走的最短路径、支付金额和时间分别为：

Sin)S3(min)S193(min)S2819(min)S28(min) A31(m 9181744

88km

MA31[S3(min)S193(min)S2819(min)]3

S28(min)2

443442 220（元） tA31(min)S3(min)S193(min)S2819(min)S28(min)1n

20306444413 203064.17h

A4区中：24送货点最后走的最短路径、支付金额和时间分别为：

SA4(min)S7(min)S147(min)S2514(min)S2425(min)S24(min)

68km

MA4[S7(min)S147(min)S2514(min)S2425(min)]3S24(min)2

343342

170（元）

可编辑

精品

tA4(min)S7(min)S147(min)S2514(min)S2425(min)S24(min)1n

20306343414 203063.5h

A5区中：18送货点最后走的最短路径、支付金额和时间分别为：

SA5(min)S4(min)S204(min)S1720(min)S1817(min)S18(min)

11105628

60km

MA5[S4(min)S204(min)S1720(min)S1817(min)]3S18(min)2

323282 150（元） tA5(min)S4(min)S204(min)S1720(min)S1817(min)S18(min)1n

20306322814 203063.2h

A6区中：16送货点最后走的最短路径、支付金额和时间分别为：

SA6(min)S2(min)S62(min)S56(min)S165(min)S16(min) 646618

40km

MA6[S2(min)S62(min)S56(min)S165(min)]3S16(min)2

223182 102（元）

tA6(min)S2(min)S62(min)S56(min)S165(min)S16(min)1n

20306321814 20306可编辑

精品

2.37h

综上所述：

SSin)SinSinSinSinSinA1(mA2mA33mA32mA31mA4mSinSin A5mA6m

5888829288686040

576kmttin)tinA1(mA2mtintintin AmAmAm333231tintintin A4mA5mA6m3.284.233.754.54.173.53.22.37

29h

M(min)MA1(min)MA2minMA33minMA32minMA31min MA4minMA5minMA6min

147204205230220170150102

1428（元）

所需人数

tMen

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的路线分别分派一个人去送货，每人的送货路线依次为：

第一业务员：A1区中：9—10—11—22—32号送货点 A6区中：2—6—5—16号送货点 第二业务员：A4区中： 7—14—25—24号送货点

A5区中：4—20—17—18号送货点

第三业务员：A2区中：12—15—23号送货点 第四业务员：A31区中：3—19—28号送货点 第五业务员：A32区中：1—8—13—30号送货点

6 结果分析与检验

本文主要问题是对所有送货点进行区域划分，因此我们引进了射线旋转法进

行划分，将依据G(80~90%)排除了送货路线与业务员的影响。使业务员数减少到最少，但在射线旋转法里我们有引进射线旋转法旋转满足

W(max)(j1)G(80~90%)，使局部因素内部处理更一步减少了射线旋转

rrn法带来的误差。因此射线旋转法根据大量资料可证明减少了由线路数量与业务员数相互影响的误差。

7 讨论模型

根据我们对网上查找资料和大量模拟实验表明：射线旋转G(80~90%)的

依据进行划分，大量减少了误差与优化了方案。它以一种新的思想进行了随机相连点的划分，并减少了由线路数量与业 员数相互影响的误差。但避免不了现实

当中所有点满足

W(max)G(80~90%)rr可编辑

n。因此在小模型划分中有相当大的误

精品

差。阶梯法相对误差来自射线旋转法，其本身是一种求最短路程的方法之一。

8 参考文献

[1] 沈荣芳.运筹学.上海同济大学.1999.8

[2] 刑文训 谢金星.现代优化 计算方法.北京.清华大学出版社.1999.8 [3] 汪定伟 王洪峰 张瑞友 郭哲.智能优化方法.高等教育出版社.2007.4

可编辑