快递公司送货策略数学模型_数学建模论文.docx

《快递公司送货策略数学模型_数学建模论文.docx》由会员分享，可在线阅读，更多相关《快递公司送货策略数学模型_数学建模论文.docx（44页珍藏版）》请在三一文库上搜索。

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

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

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

4、轴的折线。（1）请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；（2）如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略；（3）如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？二、模型假设1.假设每个快递员由派送中心出发，可连续工作6小时，中途不休息，且送货完毕后必须返回派送中心报到；2.假设每个快递员独立工作，送货过程相互不影响；3.假设每个送货点只能由一个业务员送货且只需经过一次，路线确定后不再更改；4.

5、若一个业务员需运送多条路线，中间返回总部取快件所花时间不计；5.假设快递员送货的公路均平行于所建立的坐标轴；6.假设快递员在送货途中不出现堵车现象，且没有其他的事情耽搁；三、符号说明符号说明任意一条路线（1,2n）任意一条路线上具体某一送货点（1,2m）总的运行公里数每一条最优送货路线的公里数每条路线上两个送货点之间的距离快件全部送完所花总时间业务员运送途中的速度每一条送货路线的时间总的送货点重量之和每一条路线送货的重量每一条路线上每一个送货点的重量任意一位送货员总的送货需要多少钱送货员携带快件时的酬金送货员未携带快件时的酬金业务员携带快件时途中的运行速度业务员未携带快件时途中的运行速度三角距

6、离函数四、问题分析本题属于资源分配优化问题，要求根据资源限制和约束条件来建立一个合理的邮件派送模型。在问题一中，要求我们根据时间和重量等方面的约束条件，建立合理的邮件派送路径，使得运行线路最短且使用尽可能少的业务员。分析题目条件知道影响模型的主要因素有：1.业务员每天工作不可超过6小时；2.业务员每次出发至多可带25千克的快件；3.公司需在9:00-17:00间将184.5千克的货物分送到杂乱无序的30个送货点。因此，我们需要建立最短送货路径的数学模型，首先，应用Dijkstra算法求解出坐标原点（公司总部）到各送货点的最短路距离矩阵D1；利用TSP模型中的最近邻法确定满足条件的8条最短路径并

7、依据各线路送货时间进行送货人员的分配；利用顺序插入交叉算子对模型一提出优化方案。问题二中，题目增加了业务员空载和重载的酬金以及速度的条件，要求公司设计一个费用最省的策略。因业务员重载的费用高于空载费用，而模型一仅给出路线最短，不能满足问题二需求，所以对问题二提出费用优化方案，即根据费用计算方式，运用最近邻法寻找离原点（配送中心）费用最少的点，依次类推，找出费用最省的路径组合并计算出所需费用；根据路径组合和运送时间，在满足问题一约束条件的基础上重新分配送货人员。问题三中，将业务员的工作时间延长到每天8小时，求解公司的运送策略将如何改变。业务员工作时间的调整对于总的运行路线的影响并不大，只需对业务

8、员的数量已及各业务员的安排路线进行调整即可。五、模型建立与求解5.1问题一模型建立与求解5.1.2模型的建立在问题一中，要求在每个业务员每天平均工作时间不超过6小时且必须从早上9点开始到当日17点（8小时内）全部派送完毕;平均每天送货总重量为184.5千克，每人每次出发最多可带25千克。如果将两点之间的路线距离附为这两点横纵坐标之和，比如， 这两点，则次两点间的距离为： （5.1.1）用此方法结合MATLAB求出任意两配送点的距离矩阵如下（图5.1）：图5.1 距离矩阵D该问题为规划模型，根据题意，结合距离矩阵D，设定目标函数为： （5.1.2）即为送货总路线的最短路程。其约束条件为：1、每条

9、线路上个需求点需求量之和不超过业务员的最大负荷量： （5.1.3）2、每个业务员所有配送路径来回的时间不能超过业务员一天最长的工作时间： （5.1.4）3、每一条送货路线上送货点数不超过总送货点数： （5.1.5）4、所有点都能够被配送到： （5.1.6）5、总的送货路线不超过每人送一个一个地点： （5.1.7）综上：最终模型建立如下 （5.1.8） （5.1.9） 为方便快件公司进行人员分配和路线选择，需计算每天路径的送货时间及派送完所有快件所花总时间 （5.1.10） （5.1.11）5.1.2利用最近邻法求最短送货路径组合经过分析，本题属于业务员路径问题，即VRP问题，从本质上说，TSP

10、（旅行商问题）是VRP的基本问题，因此，本文以TSP思想中的一种最近邻算法为根据，结合题目约束条件，利用MATLAB求解出业务员工作的最短路径。TSP问题是典型的组合优化问题，问题要求求得一条遍历所有城市的最短路径，是一个易于描述但难于处理的NP-HARD问题。TSP问题在交通运输、计算机网络、电路设计以及物流配送等领域内有着广泛的应用，目前，其主要算法主要有遗传算法、贪婪算法、模拟退火法及最近邻法等诸多方法。最近邻算法是TSP近似算法中最简单直观的一种，其主要思想为：任取一点作为出发点，每次取最近的一个点加入到最优解中，一直到所有点皆已进入解中。首先根据距离矩阵D找到距离送货中心最近的一个未

11、服务送货点，则分配一条路线，再找出距离最近的另外一个未服务的送货点，对每一个服务店同理依次寻找出，同时，每经过一个服务点对该服务点邮件的重量进行累加，即，直到此路线中所经过的所有送货点的邮件累计重量，则以上包含的点的组合即为该路线的路径。依据上述原理，运用MATLAB软件（程序详见附件一）可得到8条最短路径，由此分析配送路线及分配表如下表：表一：模型一路线分配表路线i路径总时间(h)总路程(km)总重量(kg)10-1-3-4-51.95 3224.020-2-6-7-8-9-234.52 8824.530-10-11-122.34 4623.340-16-17-20-14-133.23 60

12、23.550-22-21-15-193.39 6824.260-18-24-253.22 6824.770-27-263.37 7622.080-29-28-304.42 9818.3合计26.44536184.5注：0为配送中心将以上模型求解得到的路线射线图可用网络图象表达，如下（图5.2）：图5.2 模型一路线射线图 则每条路径的具体路线如下（图5.3）：图5.3 模型一路线图在保证所有快件准时送达各个送货点的情况下，合理安排路线及送货员，使得所需送货员的人数最少，线路及人员安排情况如下表：表二：模型一人员分配表送货员R123456合计路线L24681、53、7-总时间(h)4.523.2

13、33.224.425.345.7126.44总重量(kg)24.523.524.718.348.245.3184.5总路程(km)88606898100122536综上，可得该模型所构建的路线共需6名送货员，快件完全送完所需总路程为536千米，所需总时间为26.44小时。该模型较简单直观，但也存在不足。在路径选择时，当其中某一点被路线选定后，该点将不作为接下来的任意一条路线的备选送货点，每一条路线均为当前条件下的最优路线，将所有路线组合后不一定是整体送货点的最优路线，即局部最优并非整体最优。为提高工作效率，使所走总路程更短、时间更少，我们对上述模型进行了优化。5.1.3利用顺序插入交叉算子（O

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

15、货点是。定义，设有3个送货点,，定义三角距离函数G(a,b,c)如下： （5.1.12）其中，表示送货点到送货点的距离。设待交叉的双亲为和,设计交叉算子其求解步骤如下：1. 将父体作为基本染色体，父体作为参考染色体，在中随机找到一个参考城市；2. 在染色体中找到城市，然后对函数值进行比较，若： （5.1.13）则染色体保持不变，否则，在染色体中删除城市，然后再与之间插入，得到新染色体3.依次在参考染色体中取参考城市，重复步骤2，直至生成子代个体。4.再将作为基本染色体，将作为参考染色体，重复上述步骤直至得到最优搭配方案。5.2问题二模型建立与求解5.2.1模型的建立问题二要求根据题给空载和重载

16、的速度与价格条件，优化送货路线使得送货费用最小。根据条件，任意一条送货路线的费用可分为两部分组成：重载情况下到达最后一个送货点通过该路线将快件从原点送到该路线上任意一点所需要的路程为： 则所需要的费用为 由此得到重载情况下到达最后一个送货点的费用为 2.空载情况下由最后一个送货点返回配送中心： 综合1、2两步，得到任意一条送货路线的费用为 则将货物送达完毕的费用为 可设定目标函数为： （5.2.1）上式即为送货总费用的最省的线路。1、每条线路上的需求点需求量之和不超过业务员的最大负荷量，即： （5.2.2）2、每个业务员所有配送路径来回的时间不能超过业务员一天最长的工作时间： （5.2.3）3

17、、所有点都能够被配送到： （5.2.4）4、每一条送货路线上送货点数不超过总送货点数： （5.2.5）5、总的送货路线不超过每人送一个地点： （5.2.6）综上：最终模型建立如下. （5.2.7） （5.2.8） 为方便快件公司进行人员分配和路线选择，需计算每条路径的送货时间和派送完所有快件所花总时间，以及总的费用5.2.2模型的求解根据题意，本题目属于求解费用最小的组合优化模型，同样利用问题一种的最近邻法，结合送货时间及重量的约束条件，利用路线费用计算公式来寻找费用最小的优化模型。首先找到距离送货中心送货费用最少的一个未服务送货点，则分配一条路线，再找出距离送货费用最小的另外一个未服务的送货

18、点，对每一个服务店同理依次寻找出，同时，每经过一个服务点对该服务点邮件的重量进行累加，即，直到此路线中所经过的所有送货点的邮件累计重量，则以上包含的点的组合即为该路线的路径。依据上述原理，运用MATLAB软件（程序详见附件）可得到9条最短路径，由此分析配送路线及分配表如下表：表三：模型二路线分配图路线i路径总时间(h)总路程(km)总重量(kg)总费用10-9-8-14-20-16-5-6-03.835623.10002234.520-11-10-22-21-03.526623.60002205.630-2-7-13-23-03.67 7223.60001189.8 40-1-3-4-15-0

19、3.10 5822.9000858.550-26-03.25 7410.0000118460-12-27-03.17 6824.7000205670-30-28-29-04.72 9818.30002955.180-19-25-02.75 5817.4000152590-17-18-24-03.43 70 20.90001981.4合计31.43 620184.50016189.9每条路径的路线图如下（图5.4）所示：图5.4 模型二路线图根据送货路线分配表，合理安排送货员如下表：表四：模型二业务员分配表送货员R12345678合计路线L1234，85679-总时间(h)3.833.523.6

20、7 5.853.253.174.723.4331.43 总重量(kg)23.100023.600023.600040.300010.000024.700018.300020.9000184.500总路程(km)56667211674689870 620总费用（元）2234.52234.52234.52042.52056205620562056综上，模型二所建立的优化模型的总路程是620千米，所花总时间是31.43小时，共需要送货员8人，所需最少费用为16189.9元5.3问题三模型建立与求解5.3.1模型的建立与求解由于业务员的日常工作时间由6小时增加到8小时，因此，需要根据每天路径的运送时间

21、对模型一的路线重新分配业务员。模型三人员分配表如下：表五：模型三业务员分配表送货员R1234合计路线L1，82，34，56，7-总时间(h)6.376.866.626.592644总重量(kg)42.347.847.746.7184.5总路程(km)130134128144536综上，业务员工作时间调整后，共需业务员4人。六、模型的评价与改进6.1模型的评价6.1.1模型的优点在模型建立的过程当中，我们将具体问题抽象成一个数学目标函数，一方面在结果上具体分配出了送货策略，另一方面模型的整个求解过程简单清晰，便于理解和推广。在求解分析中将有序路径问题引入到矩阵中，并很好的融合了TSP模型中求最短

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

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

24、工具类程序文件） 表现：function 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:31 for j=1:31 a(i,j)=abs(x(i)-x(j)+abs(y(i)-y(j); e

25、ndendfile=fopen(dis.txt,w); for i=1:31 for j=1:31 % fprintf(file,); fprintf(file,%d,a(i,j); if mod(j,31)=0 fprintf(file,n); end end end fclose(file);getDis.m文件（工具类程序文件） 表现：function k = getDis(i)主要功能：获取返还距离；源代码：function k = getDis(i)%UNTITLED1 Summary of this function goes here% Detailed explanation

26、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);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

27、i=9 k=xlsread(dis2.xls,a9:a9);endif i=10 k=xlsread(dis2.xls,a10:a10);endif 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=xlsread(dis2.xls,a15:a15);endif i=16 k=xlsread(dis2.xls,a16:a1

28、6);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=xlsread(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(dis

29、2.xls,a24:a24);endif i=25 k=xlsread(dis2.xls,a25:a25);endif i=26 k=xlsread(dis2.xls,a26:a26);endif i=27 k=xlsread(dis2.xls,a27:a27);endif i=28 k=xlsread(dis2.xls,a28:a28);endif i=29 k=xlsread(dis2.xls,a29:a29);endif i=30 k=xlsread(dis2.xls,a30:a30);endif i=31 k=xlsread(dis2.xls,a31:a31);endcaldis.m文

30、件（工具类程序文件） 表现：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:m tempdis=0; for j=1:n-1 m=j+1; if s(i,m)0 tempdis=tempdis+GgetbothDis(s(i,j),s(i,m); dismy=GgetbothDis(s(i,j),s

31、(i,m); tempdis else break; end end if s(i,j+1)=0 tempdis=tempdis+GgetbothDis(s(i,j),s(i,1) else tempdis=tempdis+GgetbothDis(s(i,j+1),s(i,1) end dis(i)=tempdis;end ans=dis; gets.m文件（工具类程序文件） 表现：function n = gets(i)主要功能：获取i到各点的距离矩阵源代码： function n = gets(i)%获取i到个点的各个点的距离举证if i=1 s=xlsread(dis2.xls,a1:a

32、31); endif i=2 s=xlsread(dis2.xls,b1:b31); endif i=3 s=xlsread(dis2.xls,c1:c31); endif i=4 s=xlsread(dis2.xls,d1:d31); endif i=5 s=xlsread(dis2.xls,e1:e31); endif i=6 s=xlsread(dis2.xls,f1:f31); endif i=7 s=xlsread(dis2.xls,g1:g31); endif i=8 s=xlsread(dis2.xls,h1:h31); endif i=9 s=xlsread(dis2.xls,

33、i1:i31); endif i=10 s=xlsread(dis2.xls,j1:j31); endif i=11 s=xlsread(dis2.xls,k1:k31); endif i=12 s=xlsread(dis2.xls,l1:l31); endif i=13 s=xlsread(dis2.xls,m1:m31); endif i=14 s=xlsread(dis2.xls,n1:n31); endif i=15 s=xlsread(dis2.xls,o1:o31); endif i=16 s=xlsread(dis2.xls,p1:p31); endif i=17 s=xlsre

34、ad(dis2.xls,q1:q31); endif i=18 s=xlsread(dis2.xls,r1:r31); endif i=19 s=xlsread(dis2.xls,s1:s31); endif i=20 s=xlsread(dis2.xls,t1:t31); endif i=21 s=xlsread(dis2.xls,u1:u31); endif i=22 s=xlsread(dis2.xls,v1:v31); endif i=23 s=xlsread(dis2.xls,w1:w31); endif i=24 s=xlsread(dis2.xls,x1:x31); endif

35、i=25 s=xlsread(dis2.xls,y1:y31); endif i=26 s=xlsread(dis2.xls,z1:z31); endif i=27 s=xlsread(dis2.xls,aa1:aa31); endif i=28 s=xlsread(dis2.xls,ab1:ab31); endif i=29 s=xlsread(dis2.xls,ac1:ac31); endif i=30 s=xlsread(dis2.xls,ad1:ad31); endif i=31 s=xlsread(dis2.xls,ae1:ae31); endCloseDis.m文件 （问题一基本模

36、型核心文件） 表现：function n = closeDis(i,st,status)主要功能：在选择状态和货物重量的限制下，求出与参数i点距离最近的点n并返回；源代码：%用于计算和i点距离最近的点，并返回点的下标function n = closeDis(i,st,status)%UNTITLED1 Summary of this function goes here% Detailed explanation goes here% i表示要寻找的点% st表示当前累计重量% status:所有货物点的接受状态%step1:寻找与i点距离最近的点且累计重量不超过25kg%获得所有货物点的坐

37、标和标号x=xlsread(point.xls,b3:b33);y=xlsread(point.xls,c3:c33);%获取所有货物点的重量k=xlsread(st.xls,b1:b31);a=xlsread(st.xls,a1:a31);%获取i到个点的各个点的距离举证if i=1 s=0,5,6,9,11,8,14,16,15,12,14,20,20,21,22,21,18,24,28,27,28,27,21,36,34,29,37,34,44,41,46; endif i=2 s=5,0,5,4,6,9,9,11,10,7,13,15,15,16,17,16,15,19,23,22,2

38、3,22,20,31,29,24,32,29,39,36,41; endif i=3 s=6,5,0,5,5,4,8,10,9,12,18,18,14,15,16,15,12,18,22,21,22,21,25,30,28,23,31,28,38,35,40; endif i=4 s=9,4,5,0,4,9,9,7,6,7,13,13,11,12,13,12,15,15,19,18,19,18,20,27,25,20,28,25,35,32,37; endif i=5 s=11,6,5,4,0,5,5,5,6,11,17,17,11,10,11,10,11,13,17,16,17,20,24,

39、25,23,18,26,23,33,30,35; endif i=6 s=8,9,4,9,5,0,6,8,11,16,22,22,16,13,14,13,10,16,20,19,20,25,29,28,26,21,29,26,36,33,38; endif i=7 s=14,9,8,9,5,6,0,6,11,16,22,22,16,11,8,7,6,10,14,13,18,25,29,26,20,15,23,20,30,27,32; endif i=8 s=16,11,10,7,5,8,6,0,5,10,16,16,10,5,6,5,12,10,12,11,12,19,23,20,18,13,21,18,28,25,30; endif i=9 s=15,10,9,6,6,11,11,5,0,5,11,11,5,6,7,10,17,15,13,12,13,14,18,21,19,14,22,19,29,26,31; endif i=10 s=12,7,12,7,11,16,16,10,5,0,6,8,8,9,10,15,22,20,16,15,16,15,13,24,22,17,25,2