快递公司送货策略一摘要：本文是关于快递公司送货策略的优化设计问题，即在给定送货地点和给定设计规范的条件下，确定所需业务员人数，每个业务员的运行线路,总的运行公里数,以及费用最省的策略。

本文主要从最短路经和费用最省两个角度解决该问题,建立了两个数据模型。

模型一:利用“图”的知识，将送货点抽象为“图”中是顶点，由于街道和坐标轴平行，即任意两顶点之间都有路。

在此模型中,将两点之间的路线权值赋为这两点横纵坐标之和。

如A(x１，y1),Ｂ(x2，y2）两点，则权值为D=｜x２—x1|+|ｙ2—y１｜。

并利用计算机程序对以上结果进行了校核。

模型二:根据题意，建立动态规划的数学模型。

然后用动态规划的知识求得最优化结果。

根据所建立的两个数学模型，对满足设计要求的送货策略和费用最省策略进行了模拟，在有标尺的坐标系中得到了能够反映运送最佳路线的模拟图。

最后，对设计规范的合理性进行了充分和必要的论证.二关键词:快递公司送货最优化图模型多目标动态规划TSP模型三问题重述:在快递公司送货策略中，确定业务员人数和各自的行走路线是本题的关键。

这个问题可以描述为:一中心仓库（或配送调度中心）拥有最大负重为２5kｇ的业务员ｍ人，负责对30个客户进行货物分送工作，客户ｉ的快件量为已知 , 求满足需求的路程最短的人员行驶路径，且使用尽量少的人数,并满足以下条件:1) 每条送快件的路径上各个客户的需求量之和不超过个人最大负重。

2）每个客户的需求必须满足, 且只能由一个人送货。

3)每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为１0分钟，途中速度为２5km/ｈ。

4）为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为1８４．5千克。

表一为题中所给的数据：表一处于实际情况的考虑, 本研究中对人的最大行程不加限制。

本论文试图从最优化的角度，建立起满足设计要求的送货的数学模型,借助于计算机的高速运算与逻辑判断能力，求出满足题意要求的结果。

四 问题分析：从公司总部配出一个人，到任意未配送的送货点,然后将这个人配到最近的未服务的送货点范围之内的邻居,并使送货时间小于6小时，各送货点总重量不超过25kg 。

继续上述指派，直到各点总重量超过25kg,或者送货时间大于６小时。

最后业务员返回总部,记录得到的可行行程（即路线)。

对另一个业务员重复上述安排，直到没有未服务的送货点.对得到的可行的行程安排解中的每一条路径，求解一个旅行商问题，决定访问指派给每一条行程的业务员的顺序，最小化运输总距离。

得到可行解的行程安排解后退出. 根据题意的要求，每个人的工作时间不超过6小时,且必须从早上9点钟开始派送,到当天17点之前(即在8小时之内）派送完毕。

且8255.184=⎥⎥⎤⎢⎢⎡kg kg ,故至少需要8条路线。

表二列出了题中任意两配送点间的距离.表二:任意两点间的距离矩阵因为距离是对称的,即从送货点i 到送货点ｊ的距离等于从ｊ到i 的距离。

记作：ｄij ．表三给出了客户的需求，为了完成送快递的任务，每个人在工作时间范围内,可以承担两条甚至更多的线路。

表中给出了送货点序号，送货点编号，快件量Ｔ,以及送货点的直角坐标。

表三五模型假设：（１)街道方向均平行于坐标轴，且在该前提下,业务员可以任意选择路线.（２)无塞车现象，即业务员送快递途中不受任何外界因素影响，且业务员的休息时间不包括在最大工作时间6个小时内。

(3）业务员人数不限制。

（４）每个业务员的路线一旦确定，便不再更改。

(5）每个业务员送快递是独立的，每人之间互不影响.（6)业务员到某送货点后必须把该送货点的快件送完。

(7）每个业务员每天的工作时间不超过6个小时。

（8）业务员回到快递公司后停留一个小时。

六 主要符号说明：Ti ：序号为i 的送货点的快件重量 （xi ,ｙｉ）序号为i 的送货点的坐标 M 重:业务员送货总重载费用 M 空:业务员送货总空载费用 M 总:业务员送货总费用 N ：业务员送货的总次数 m:业务员人数mj:第j 个业务员送货的次数⎩⎨⎧=的送货点没有送快件，业务员在序号为的送货点送快件业务员在序号为i 0i ,1ai 1,k i 0k i bi ⎧=⎨⎩第条路线选择序号为的送货点是最远点，第条路线选择序号为的送货点不是最远点七 模型建立与求解： 7.1问题一模型本模型考虑用多目标动态规划求解。

由于问题一中只要求给出一个合理的方案，且未涉及到业务员工资问题,故只要满足条件——业务员的工作时间上限是6个小时以及每条路线的最大载重量不大于25kg 即可,本模型中追加两个目标-—路程最短和人员最少.可以通过以下两种方法实现:（1)每一个行程的第一个送货点是距离总部最近的未服务的送货点。

用这种方法，即可得到一组运行路线，总的运行公里数,以及总费用。

（2)每一个行程的第一个送货点是距离总部最远的未服务的送货点.然后以该点为基准，选择距它最近的点,加上约束条件，也可得到一组数据.然后比较两组结果,通过函数拟合即可得到最优化结果.本模型中以满足需求的路程最短的人员行驶路径，且使用尽量少的人数,即N30k 1i 1min (2*bi*(xi+yi))==∑∑且minm约束条件为：① 时间约束：∑∑==≤++mj1j 3016)6125)(2(i ai yi xi② 载重量约束:25* ai Ti方法一:每一个行程的第一个送货点是距离总部最近的未服务的送货点.ﻩ第一条行程中访问了节点０-1-３－4-５—0,是因为1距离原点最近,因此由1出发,３是距离１点最近的点,而且两处快件量之和为14ｋg ，小于每个人最大负重量，可以继续指配。

接着，4是距离3最近的点,而且三处快件量之和为19.５kg ，仍小于2５ｋg ，还可以继续指配.在剩下的未服务送货点中，5距离4最近（其实距离４最近的点有2，5，６，7四个点,然后考虑该点需求的快件量，将其从大到小依次排列,快件量需求大者优先，但超过25kg 上限的点舍去.这里２，７被舍去,故选择了5)总快件量之和为24ｋg.再继续扩充,发现就会超出“25ｋg ”这个上限，因此选择返回，所以0-1—3-4－5就为第一条路线所含有的送货点. 用该算法得到的各路线为：(1）0 1 3ﻩ４ 5（２）０２ 6 7 13 0（3）０9 8 １2 10 0(4）0 1６ 1７ 20 １4 1５ 23 0(5）0 11 22 3２ 19 ０（６)0 ２7 2６０（7）0 １８ 24 25 0（8）0 ２9 28 3０ 0现在０－1—3—4—5这四个送货点之间的最优访问路径安排就是一个典型的单回路问题.可以通过单回路运输模型—TSＰ模型求解。

一般而言，比较简单的启发式算法求解TSP模型求解有最邻近法和最近插入法两种.由RoｓenｋrantzＳtearns等人在1９77年提出的最近插入法，能够比最近邻点法,取得更满意的解。

由于０－1-３-0 已经先构成了一个子回路,现在要将节点４插入，但是客户4有三个位置可以插入,现在分析将客户4插入到哪里比较合适:1．插入到(0，1)间，C总= 7+４＋5+１＋４+9=3０.2.插入到（1,3）间，C总=5+6+4+9=24。

3。

插入到（３，0）间,C总=5+4+4+１1=24。

比较上述三种情况的增量，插入到（３,０）间和(１,3)间增量最小,考虑到下一节点插入时路程最小问题,所以应当将４插入到送货点3和总部0之间。

接下来,用同样的方法，将5插到4和0之间,能使该条路线总路程最小,该路线总路程为３2ｋm，历时1。

9467ｈ。

结果子回路为T={0—1—3—4—5－0｝.因为街道平行于坐标轴方向,所以它就是最优化路线。

第二条行程这中，由于所剩下节点中，２距离0点最近，因此由2出发,就可以找到最近点６，接着是7，然后1３。

这样，第二条优化路线0-2-６－７—13—0就确定了。

用这种方法，依次可确定以下剩余六条路线。

得到总的送货路线为：ﻩ４5ﻩ0（１）0ﻩ１ﻩ3（2）0 ２ 6 7 1３０（3）０10 1２ 8 9 0(４）０ 16 17 20 １４ 1５ ２3 0 （5）0 １９ １1 32 22 0 (６）０ 1８ 24 2５ ０ （７)0 ２7 26 0 （８）0 29 3０ ８ 0改进前和改进后的路程，时间比较如下：路程比较12345时间比较然后，根据所经历的时间进行划分,确定运送人数。

在工作时间小于6小时的前提下,最终只需要六名运输员，第一条线路和第二条线路有一人完成,第三条和第七条线路由一人完成,则各运输员到达各站点时间的情况如下：2131２：４81１:586241０：319：0０7１３:1０２510:５3613:3972713：451２：23310９:349:０02６1４：071２９：5882910:3８9：00８10：２03011：０091０:442８１1:2441６9:439：00１７１0:072010：291410:5115１1:３0231１：59路径为:方法二：每一个行程的第一个送货点是距离总部最远的未服务的送货点。

分析方法如一：得到的路径为：（1）0 30 29 28 2３ 15 0（2)0 ２6 27 8 0（3)０24 25 14 9 ０（４)0 １８ 1７ 20 1６ 6 0（5）0 32 ２2 11 10 0（６)0 1９ 1３ 7 0(7)０ 12 4 3 0（8)0 5 2 1 ０同方法一，用最近插入法修改路径可以得到更优的解，改进后的路径为:29ﻩﻩ23 15 02830（１） 0ﻩﻩ(2) 0 26 27 8 0(３) 0 24 25 1４ 9 0（4）０ 2０18 1７１6 6 0（５）０ 11 ３2 ２２10 0(６） 0 １9 13 ７ 0(7） 0 4 １２ 3 ０（8） 0 2 ５ 1 ０改进前后路程和时间的比较如下：线路一线路二线路三线路四线路五线路六线路七线路八路程比较时间比较然后，根据所经历的时间进行划分，确定运送人数。

在工作时间小于6小时的前提下,最终只需要五名运输员，第三条线路和第八条线路由一人完成第四条线路和第七条线路由一人完成,第五条线路和第六条线路由一人完成，则各运输员到达各站点时间的情况如下：路径图为：由上面得图表知改进后的方法二的路线的总的距离为480km，时间为24。

1９9７;比改进后的方法一的距离短，时间短,所以若是只考虑时间和路程，改进后的方法二为最优解。

7.２问题二模型问题二中由于业务员所得的费用是最主要的,业务员安排、路线选择都是为了总费用的最小化提供条件，所以应首先考虑路费，之后再考虑业务员的安排。

为了使总能够费用最少,总的思路是先送货给离快递公司最近切块间最重的送货点，以此类推,在保证时间、载重量有限的前提下,沿途把快递送完，最终让业务员最远点空载返回。