快递公司送货策略数学模型论文

1、精品快递公司送货策可编辑精品略可编辑精品快递公司送货策略模型摘要本文是关于快递公司送货策略的优化设计问题，即在给定送货地点和给定设计规划的前提下，确定所需的业务员人数，每个业务员的行程路线，总的运行公里数及费用最省的策略。在问题一中，在考虑业务员工作时间及载重限制的两方面因素的情况下，寻求路程最短的路线优化组合，建立TSP（旅行商问题）模型，采用最近邻算法，以原点（配送中心）为起点，通过距离矩阵依次寻找距离最近的未服务送货点，运用MATLAB 软件求解出最优的路线组合。并根据遗传算法的思想，提出了模型优化的方案，得到了一个相对较优的策略，模型结果为：共需6 名送货员，所需总路程为536 千米，

2、所需总时间为 26.44 小时。对于问题二，以业务员酬金最少为目标， 选取最优路线时应尽量避免快件回送现象，同样建立 TSP（旅行商问题）模型，依次寻找费用最小的点的组合，由此寻找最优路线组合，优化模型结果为：总路程是620 千米，所花总时间是31.43 小时，共需要送货员 8 人，所需最少费用为16189.9 元。对于问题三，业务员工作时间增加2 小时，以寻找业务员人数最小的路线分配为目标，并尽量保证时间和路程的相对均衡。由于业务员工作时间对总的运行路线影响较小，所以只需对业务员数量和各业务员送货线路进行调整，调整后将业务员人数减少到4 人。关键字： TSP （旅行商问题）最近邻法交叉算子可

3、编辑精品一、问题重述目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。假定所有快件在早上7 点钟到达，早上9 点钟开始派送，要求于当天17 点之前必须派送完毕， 每个业务员每天平均工作时间不超过6 小时，在每个送货点停留的时间为10 分钟，途中速度为25km/h ，每次出发最多能带25 千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5 千克，公司总部位于坐标原点处

4、（如图 2 ），每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平可编辑精品行于坐标轴的折线。（1）请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；（2）如果业务员携带快件时的速度是20km/h ，获得酬金 3 元 /kmkg ；而不携带快件时的速度是30km/h ，酬金 2 元/km ，请为公司设计一个费用最省的策略；（3）如果可以延长业务员的工作时间到8 小时，公司的送货策略将有何变化？二、模型假设1.假设每个快递员由派送中心出发，可连续工作6 小时，中途不休息，且送货完毕后必须返回派送中心报到；2.假设每

5、个快递员独立工作，送货过程相互不影响；3.假设每个送货点只能由一个业务员送货且只需经过一次，路线确定后不再更改；4.若一个业务员需运送多条路线，中间返回总部取快件所花时间不计；5.假设快递员送货的公路均平行于所建立的坐标轴；6.假设快递员在送货途中不出现堵车现象，且没有其他的事情耽搁；可编辑符号LiAijCciSi ( j 1)SijTvtiKkikijR iPpApBv1v2G（ a, b, c）精品三、符号说明说明任意一条路线（ i1,2n ）任意一条路线上具体某一送货点（j1,2m ）总的运行公里数每一条最优送货路线的公里数每条路线上两个送货点之间的距离快件全部送完所花总时间业务员运送途

6、中的速度每一条送货路线的时间总的送货点重量之和每一条路线送货的重量每一条路线上每一个送货点的重量任意一位送货员总的送货需要多少钱送货员携带快件时的酬金送货员未携带快件时的酬金业务员携带快件时途中的运行速度业务员未携带快件时途中的运行速度三角距离函数可编辑精品四、问题分析本题属于资源分配优化问题， 要求根据资源限制和约束条件来建立一个合理的邮件派送模型。在问题一中，要求我们根据时间和重量等方面的约束条件，建立合理的邮件派送路径，使得运行线路最短且使用尽可能少的业务员。分析题目条件知道影响模型的主要因素有：1.业务员每天工作不可超过6 小时；2.业务员每次出发至多可带25 千克的快件；3.公司需在

7、 9:00-17:00间将 184.5 千克的货物分送到杂乱无序的30 个送货点。因此，我们需要建立最短送货路径的数学模型，首先，应用Dijkstra算法求解出坐标原点（公司总部）到各送货点的最短路距离矩阵D1 ；利用 TSP 模型中的最近邻法确定满足条件的 8 条最短路径并依据各线路送货时间进行送货人员的分配； 利用顺序插入交叉算子对模型一提出优化方案。问题二中，题目增加了业务员空载和重载的酬金以及速度的条件，要求公司设计一个费用最省的策略。因业务员重载的费用高于空载费用，而模型一仅给出路线最短，不能满足问题二需求，所以对问题二提出费用优化方案，即根据费用计算方式，运用最近邻法寻找离原点（配

8、送中心）费用最少的点，依次类推，找出费用最省的路径组合并计算出所需费用；根据路径组合和运送时间，在满足问题一约束条件的基础上重新分配送货人员。问题三中，将业务员的工作时间延长到每天 8 小时，求解公司的运送策略将如何改可编辑精品变。业务员工作时间的调整对于总的运行路线的影响并不大，只需对业务员的数量已及各业务员的安排路线进行调整即可。五、模型建立与求解5.1 问题一模型建立与求解5.1.2 模型的建立在问题一中，要求在每个业务员每天平均工作时间不超过6 小时且必须从早上9 点开始到当日 17 点（ 8 小时内）全部派送完毕 ;平均每天送货总重量为184.5 千克，每人每次出发最多可带25 千克

9、。如果将两点之间的路线距离附为这两点横纵坐标之和，比如 Ai ( xi , yi ) ， Aj ( xj , y j )这两点，则次两点间的距离为：Sij | xi xj | yiy j |（ 5.1.1 ）用此方法结合 MATLAB求出任意两配送点的距离矩阵如下（图5.1 ）：可编辑精品图 5.1 距离矩阵 D该问题为规划模型，根据题意，结合距离矩阵D ，设定目标函数为：nm -1（ 5.1.2 ）min C ( Si ( j 1) S ij ) ( Sim Si 1 )i 1j 1即为送货总路线的最短路程。其约束条件为：1、每条线路上个需求点需求量之和不超过业务员的最大负荷量：mkij k

10、i（5.1.3 ）j12、每个业务员所有配送路径来回的时间不能超过业务员一天最长的工作时间：可编辑精品m-1Si1 ) v 1 (m 1) ti（5.1.4 ） (Si ( j 1) Sij ) (Simj 163、每一条送货路线上送货点数不超过总送货点数：0m31（5.1.5 ）4、所有点都能够被配送到：nki K（5.1.6 ）i 15、总的送货路线不超过每人送一个一个地点：0n30（5.1.7 ）综上：最终模型建立如下nm -1min C ( Si ( j 1 ) Sij ) ( Sim Si 1 )（5.1.8 ）i 1j 1mkij25j 1m-1S) (SS ) v1 (m 1)

11、t (Sii ( j 1)ijimi16j1nki KSt（ 5.1.9 ）i 10m310n30为方便快件公司进行人员分配和路线选择，需计算每天路径的送货时间ti 及派送完可编辑精品所有快件所花总时间 TmSi1 ) v 1 (m 1)ti (Si( j 1) Sij ) (Sim（5.1.10 ）j 16T t1 t2 . tn（5.1.11 ）5.1.2 利用最近邻法求最短送货路径组合经过分析，本题属于业务员路径问题，即VRP 问题，从本质上说， TSP（旅行商问题）是 VRP 的基本问题，因此，本文以TSP 思想中的一种最近邻算法为根据，结合题目约束条件，利用MATLAB 求解出业务员

12、工作的最短路径。TSP 问题是典型的组合优化问题，问题要求求得一条遍历所有城市的最短路径，是一个易于描述但难于处理的NP-HARD问题。 TSP 问题在交通运输、 计算机网络、 电路设计以及物流配送等领域内有着广泛的应用，目前，其主要算法主要有遗传算法、贪婪算法、模拟退火法及最近邻法等诸多方法。最近邻算法是TSP 近似算法中最简单直观的一种，其主要思想为：任取一点作为出发点，每次取最近的一个点加入到最优解中，一直到所有点皆已进入解中。首先根据距离矩阵 D 找到距离送货中心最近的一个未服务送货点 A1 ，则分配一条路线 c1 ，再找出距离 A1 最近的另外一个未服务的送货点 A2 ，对每一个服务

13、店同理依次寻找出 A3, A4.Ai ，同时，每经过一个服务点对该服务点邮件的重量k i j 进行累加，即 kiki1ki 2 . kij ，直到此路线 ci 中所经过的所有送货点的邮件累计重量 k i25，则以上包含的点的组合即为该路线的路径。依据上述原理，运用MATLAB 软件（程序详见附件一）可得到8 条最短路径，由此分析配送路线及分配表如下表：表一：模型一路线分配表可编辑路线 i路径10-1-3-4-520-2-6-7-8-9-2330-10-11-1240-16-17-20-14-1350-22-21-15-1960-18-24-2570-27-2680-29-28-30合计精品总时

14、间 (h)总路程 (km)总重量 (kg)注1.953224.0：04.528824.5为配2.344623.3送3.236023.5中3.396824.2心将3.226824.7以3.377622.0上4.429818.3模型26.44536184.5求解得到的路线射线图可用网络图象表达，如下（图5.2 ）：可编辑精品图 5.2模型一路线射线图则每条路径的具体路线如下（图5.3 ）：可编辑精品图 5.3 模型一路线图在保证所有快件准时送达各个送货点的情况下，合理安排路线及送货员，使得所需送货员的人数最少，线路及人员安排情况如下表：表二：模型一人员分配表送货员R123456合计路线 L2468

15、1 、 53 、 7-总时间 (h)4.53.233.224.425.345.7126.442可编辑精品总重量 (kg)24.23.524.718.348.245.3184.55总路程 (km)88606898100122536综上，可得该模型所构建的路线共需6 名送货员，快件完全送完所需总路程为 536千米，所需总时间为 26.44 小时。该模型较简单直观，但也存在不足。在路径选择时，当其中某一点A被路线 Li 选ij定后，该点将不作为接下来的任意一条路线的备选送货点，每一条路线均为当前条件下的最优路线，将所有路线组合后不一定是整体送货点的最优路线，即局部最优并非整体最优。为提高工作效率，使

16、所走总路程更短、时间更少，我们对上述模型进行了优化。5.1.3 利用顺序插入交叉算子（OIC）优化模型一顺序插入交叉算子是针对TSP 问题的特点，在遗传算法的交叉运算过程中设计的三角距离差函数作为评价标准，运用贪婪策略思想，提出的一种新的交叉算子，该算子有效的利用了局部信息，并且能很好的继承父代优秀的基因。顺序插入交叉算子的基本思想是：对于两个待交叉的染色体，将一个作为基本染色体，另一个作为参考染色体，按照在参考染色体中的送货点间的邻接顺序，利用三角距离差函数作为评价标准，运用贪婪策略思想，逐步改变基本染色体的编码顺序，从而使经过交叉得到的两个子代染色体的适应度最高。优化思想：利用顺序插入交叉

17、算子，我们将模型一中每一条进行染色体编码定义，如 Li ( A1 , A2 ,., Ai ) ，将上述染色体看成一个环， 染色体 Ai 的下一个送货点是 A1 。可编辑精品定义，设有 3 个送货点 Aa , Ab , Ac ，定义三角距离函数G(a,b,c) 如下：G(a,b,c)S(a,b)S(b,c) - S(a,c)（ 5.1.12 ）其中， S(x, y) 表示送货点 Ax 到送货点 Ay 的距离。设待交叉的双亲为 LA ( A1 , A2 ,., Am ) 和 LB (B1, B2 ,., Bn ) ,设计交叉算子其求解步骤如下：1. 将父体 LA 作为基本染色体，父体 LB 作为参

18、考染色体，在 LB 中随机找到一个参考城市 B j ；2. 在染色体 LA中找到城市 AiBj ， AmBi 1，然后对函数值进行比较， 若：G（ Aj , Ai 1 , Aj1） G( Am 1 , Am , Am 1 )（ 5.1.13 ）则染色体 LA 保持不变，否则，在染色体 LA 中删除城市Am ，然后再 Aj 与 Aj 1 之间插入 Bj 1 ，得到新染色体 LA3.依次在参考染色体LB 中取参考城市，重复步骤 2 ，直至生成子代个体。4.再将 LB 作为基本染色体， 将 LA 作为参考染色体， 重复上述步骤直至得到最优搭配方案。5.2 问题二模型建立与求解5.2.1 模型的建立问

19、题二要求根据题给空载和重载的速度与价格条件，优化送货路线使得送货费用最小。根据条件，任意一条送货路线的费用Pi 可分为两部分组成：重载情况下到达最后一个送货点通过该路线将快件从原点送到该路线上任意一点Aij 所需要的路程为：可编辑精品j 1(si ( z 1)siz )z 1则所需要的费用为j 1pA ki(si ( z 1) siz )z 1由此得到重载情况下到达最后一个送货点的费用为m 1j 1（pA ki(si ( z 1)siz )）j 1z 12.空载情况下由最后一个送货点返回配送中心：P返回pB (sijsi 1 )综合 1 、2 两步，得到任意一条送货路线的费用为m 1j1Pi（

20、pAki(si ( z 1)siz )） pB (simsi1 )j1z 1n则将货物送达完毕的费用为 minPPii 1可设定目标函数为：nm 1j 1min P(j 1pA ki (z 1si ( z 1)siz ) pB (simsi 1 )（ 5.2.1 ）i 1上式即为送货总费用的最省的线路。1、每条线路上的需求点需求量之和不超过业务员的最大负荷量，即：mkij 25（5.2.2 ）j 12、每个业务员所有配送路径来回的时间不能超过业务员一天最长的工作时间：m 11(m 1) ti(si ( j 1)sij ) v1 (sim si1) v2（ 5.2.3 ）j 16可编辑精品3、所

21、有点都能够被配送到：nkiK（5.2.4 ）i 14、每一条送货路线上送货点数不超过总送货点数：0m31（ 5.2.5 ）5、总的送货路线不超过每人送一个地点：0n30（ 5.2.6 ）综上：最终模型建立如下nm 1j 1min P(pA ki (si ( z 1)i 1j 1z 1mkij25j 1m 1(si ( j 1)sij ) v1j 1nstkiKi 1siz ) pB (sim si 1 ) .（5.2.7 ）(simsi1 ) v21(m 1) ti（5.2.8 ）60m310n30为方便快件公司进行人员分配和路线选择，需计算每条路径的送货时间ti 和派送完所有快件所花总时间

22、T ，以及总的费用 P5.2.2 模型的求解可编辑精品根据题意，本题目属于求解费用最小的组合优化模型，同样利用问题一种的最近邻法，结合送货时间及重量的约束条件，利用路线费用计算公式来寻找费用最小的优化模型。首先找到距离送货中心送货费用最少的一个未服务送货点 A1 ，则分配一条路线 c1 ，再找出距离 A1 送货费用最小的另外一个未服务的送货点 A2 ，对每一个服务店同理依次寻找出 A3, A4 .Ai ，同时，每经过一个服务点对该服务点邮件的重量k i j 进行累加，即 kiki1ki 2.kij ，直到此路线 ci 中所经过的所有送货点的邮件累计重量 k i25，则以上包含的点的组合即为该路

23、线的路径。依据上述原理，运用MATLAB 软件（程序详见附件）可得到9 条最短路径，由此分析配送路线及分配表如下表：表三：模型二路线分配图路线 i路径总时间总路程总重量总费用(h)(km)(kg)10-9-8-14-20-16-5-65623.1002234.53.83-0020-11-10-22-21-06623.6002205.63.52030-2-7-13-23-07223.6001189.83.670可编辑精品40-1-3-4-15-05822.900858.53.10050-26-07410.00011843.25060-12-27-06824.70020563.17070-30-2

24、8-29-09818.3002955.14.72080-19-25-05817.40015252.75090-17-18-24-07020.9001981.43.430合计620184.5016189.31.4309每条路径的路线图如下（图5.4 ）所示：可编辑精品图 5.4模型二路线图根据送货路线分配表，合理安排送货员如下表：表四：模型二业务员分配表送货员R12345678合计路线 L1234，85679-总时间 (h)3.833.523.675.853.253.174.723.4331.43可编辑精品总重量 (kg)23.10023.60023.600040.30010.00024.700

25、18.30020.900184.5000000000总路程 (km)56667211674689870620总费用（元）2234.52234.52234.52042.52056205620562056综上，模型二所建立的优化模型的总路程是620 千米，所花总时间是 31.43 小时，共需要送货员 8 人，所需最少费用为16189.9 元5.3 问题三模型建立与求解5.3.1 模型的建立与求解由于业务员的日常工作时间由6 小时增加到 8 小时，因此，需要根据每天路径的运送时间 t i 对模型一的路线重新分配业务员。模型三人员分配表如下：表五：模型三业务员分配表送货员 R1234合计路线 L1 ，

26、 82 ，34 ，56 ， 7-总时间 (h)6.376.866.626.5926 44总重量 (kg)42.347.847.746.7184.5总路程 (km)130134128144536可编辑精品综上，业务员工作时间调整后，共需业务员4 人。六、模型的评价与改进6.1 模型的评价6.1.1 模型的优点在模型建立的过程当中，我们将具体问题抽象成一个数学目标函数，一方面在结果上具体分配出了送货策略，另一方面模型的整个求解过程简单清晰，便于理解和推广。在求解分析中将有序路径问题引入到矩阵中，并很好的融合了TSP 模型中求最短路径的思想设计出自己的算法，模型的建立简单明确，具有针对性，模型的计算

27、结果经过仿真测试，具有较高的准确度。最终得出了较为合理的送货策略并对模型一提出了基于遗传算法思想的优化理论。6.1.2 模型的缺点该模型主要采用 TSP（旅行商问题）思想中的最近邻算法，仅在现有条件内实现了局部最优，并没有达到整体最优的效果，优化方案模型不成熟。该模型选择配送线路不能对客户的需求进行灵活多变的处理。由于线代的消费者的需求倾向于个性化，引起企业的生产、销售和配送也愈来愈倾向于小批量、多品种、多批次，而该模型更适合需求稳定的环境。参考文献1 孙海雷，刘琼荪，胡上尉。 TSP 问题的顺序插入交叉算子 J。计算机工程与应用， 2007,43 （8）。2 张辉。 TSP 问题的算法与应用

28、的研究 J。计算机应用与软件， 2009 ，26（4 ）。可编辑精品附录附录 1.模型求解相关 matlab程序关键字：tsp 模型邻近算法状态选择模型求解的相关数据文件文件说明数据类文件：Point.xls文件存入的是以送货配发点为原点所建成的坐标体系上的各个点的相对坐标集合st.xls文件存入的内容为各个配送点的所需货物的重量以及货物送达的状态可编辑精品Dis2.xls文件存入的内容为各个配送点的距离矩阵表gres.xls由问题模型一结果构成的路线矩阵Dis3.xls由距离矩阵和单价表构成的距离单价矩阵（用于问题二的模型）程序类文件getallDis.m文件（工具类程序文件）表现： fun

29、ction s = getallDis()主要功能：求出各个送货点的距离举证，并存入dis.txt源代码 ：function s = getallDis()%UNTITLED1 Summary of this function goes here% Detailed explanation goes here% author:managerx=xlsread('point.xls','b3:b33');y=xlsread('point.xls','c3:c33');可编辑精品for i=1:31for j=1:31a(i,j)=a

30、bs(x(i)-x(j)+abs(y(i)-y(j);endendfile=fopen('dis.txt','w');for i=1:31for j=1:31% fprintf(file,',');fprintf(file,',%d',a(i,j);if mod(j,31)=0fprintf(file,'n');endendendfclose(file);可编辑精品getDis.m文件（工具类程序文件）表现： function k = getDis(i)主要功能：获取返还距离；源代码 ：function k = g

31、etDis(i)%UNTITLED1 Summary of this function goes here% Detailed explanation goes hereif i=1 k=xlsread('dis2.xls','a1:a1');endif i=2 k=xlsread('dis2.xls','a2:a2');endif i=3 k=xlsread('dis2.xls','a3:a3');endif i=4 k=xlsread('dis2.xls','a4:a4&

32、#39;);endif i=5 k=xlsread('dis2.xls','a5:a5');endif i=6 k=xlsread('dis2.xls','a6:a6');endif i=7 k=xlsread('dis2.xls','a7:a7');endif i=8 k=xlsread('dis2.xls','a8:a8');endif i=9 k=xlsread('dis2.xls','a9:a9');endif i=10 k=x

33、lsread('dis2.xls','a10:a10');end可编辑精品if i=11 k=xlsread('dis2.xls','a11:a11');endif i=12 k=xlsread('dis2.xls','a12:a12');endif i=13 k=xlsread('dis2.xls','a13:a13');endif i=14 k=xlsread('dis2.xls','a14:a14');endif i=15 k=x

34、lsread('dis2.xls','a15:a15');endif i=16 k=xlsread('dis2.xls','a16:a16');endif i=17 k=xlsread('dis2.xls','a17:a17');endif i=18 k=xlsread('dis2.xls','a18:a18');endif i=19 k=xlsread('dis2.xls','a19:a19');endif i=20 k=xlsrea

35、d('dis2.xls','a20:a20');endif i=21 k=xlsread('dis2.xls','a21:a21');endif i=22 k=xlsread('dis2.xls','a22:a22');endif i=23 k=xlsread('dis2.xls','a23:a23');endif i=24 k=xlsread('dis2.xls','a24:a24');endif i=25 k=xlsread(

36、9;dis2.xls','a25:a25');endif i=26 k=xlsread('dis2.xls','a26:a26');endif i=27 k=xlsread('dis2.xls','a27:a27');end可编辑精品if i=28 k=xlsread('dis2.xls','a28:a28');endif i=29 k=xlsread('dis2.xls','a29:a29');endif i=30 k=xlsread(

37、9;dis2.xls','a30:a30');endif i=31 k=xlsread('dis2.xls','a31:a31');endcaldis.m文件（工具类程序文件）表现： function ans = caldis(s,m,n)主要功能：计算矩阵的整体路径源代码 ：function ans = caldis(s,m,n)%UNTITLED1 Summary of this function goes here% Detailed explanation goes heredis=;tempdis=0;for i=1:mtemp

38、dis=0;for j=1:n-1m=j+1;可编辑精品if s(i,m)>0tempdis=tempdis+GgetbothDis(s(i,j),s(i,m);dismy=GgetbothDis(s(i,j),s(i,m);tempdiselsebreak;endendif s(i,j+1)=0tempdis=tempdis+GgetbothDis(s(i,j),s(i,1)elsetempdis=tempdis+GgetbothDis(s(i,j+1),s(i,1)enddis(i)=tempdis;endans=dis;gets.m文件（工具类程序文件）可编辑精品表现： funct

39、ion n = gets(i)主要功能：获取i 到各点的距离矩阵源代码 ：function n = gets(i)% 获取 i 到个点的各个点的距离举证ifi=1s=xlsread('dis2.xls','a1:a31'); endifi=2s=xlsread('dis2.xls','b1:b31'); endifi=3s=xlsread('dis2.xls','c1:c31'); endifi=4s=xlsread('dis2.xls','d1:d31'); end

40、ifi=5s=xlsread('dis2.xls','e1:e31'); endifi=6s=xlsread('dis2.xls','f1:f31'); endifi=7s=xlsread('dis2.xls','g1:g31'); endifi=8s=xlsread('dis2.xls','h1:h31'); endifi=9s=xlsread('dis2.xls','i1:i31'); endifi=10s=xlsread('dis2.xls','j1:j31'); endifi=11s=xlsread('dis2.xls','k1:k31'); endifi=12s=xlsread('dis2.xls','l1:l31'); end可编辑精品ifi=13s=xlsread('dis2.xls','m1:m31'); endifi=14s=xlsread('dis2.xls','n1:n31'); endifi=15s=xlsread('di