数学建模：快递公司送货策略

1、-PAGE . z.2012年第九届北数学建模联赛承 诺 书我们仔细阅读了第九届北数学建模联赛的竞赛规则。我们完全明白，在竞赛开场后参赛队员不能以任何方式包括、电子、网上咨询等与本队以外的任何人包括指导教师研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其它公开的资料包括网上查到的资料，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承当由此引起的一切后果。我们的参赛报名号为： 2394参赛组别研究生或本科或专科：本科组参赛队员 (签名) ：队员

2、1：鞠珊队员2：夏逸凡队员3：胡思想获奖证书邮寄地址：工程学院数理学院教2-5132012年第九届北数学建模联赛编 号 专 用 页参赛队伍的参赛：请各个参赛队提前填写好：竞赛统一编号由竞赛组委会送至评委团前编号：竞赛评阅编号由竞赛评委团评阅前进展编号：题目 快递公司送货策略摘要本文针对快递公司送货策略的优化问题进展研究，重点放在给该快递公司提供一个合理的送货策略；在一些特殊条件的限制下，给该公司提供一个费用最省的送货策略。对于问题一，我们通过运送总距离最短目标函数首先建立了模型0-1整数线性规划模型。在给定送货地点和给定送货量和送货时间的约束条件下，结合最近插入法和最正确匹配的原理，将送货点抽

3、象为一个点顶点，由于街道和坐标轴平行，即任意两顶点之间都有路，且任意两点间的距离为这两点横纵坐标差的绝对值之和。如两点，则权值为。在此根底上,运用矩形，将整个区域分成5个区域，以选择的点的送货质量之和小于25kg且距离尽可能小的点的集合作为一个区域。依次来分配业务员的送货地点。通过我们的计算，在不考虑时间的情况下，我们求得一个人完成任务的运送路线为8条，由于工作时间的限制，求出了完成任务所需的最少业务员为5人，最短总路程为。对于问题二，我们借助于问题一求解出来的路线，运用图论中最小生成树的原理，以费用最省为目标函数建立数学模型。通过TSP模型在满足约束条件的前提下求出最短距离，再对所求解方案进

4、展优化修改，从而我们求得问题二的最省费用为。关键词 0-1整体线性规划 最近插入法 最小生成树TSP模型 e*cel一、问题重述1.1背景分析目前，快递行业正蓬勃开展，为我们的生活带来更多方便。一般地，所有快件到达*地后，先集中存放在总部，然后由业务员分别进展派送；对于快递公司，为了保证快件能够在指定的时间送达目的地，必须有足够的业务员进展送货，但是，太多的业务员意味着更多的派送费用。1.2问题重述假定所有快件在早上7点钟到达，早上9点钟开场派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带

5、25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点处如图2，每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平行于坐标轴的折线。问题1：请你运用有关数学建模的知识，给该公司提供一个合理的送货策略即需要多少业务员，每个业务员的运行线路，以及总的运行公里数；问题2：如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略。送货点快件量T(kg)坐标(km)送货点快件量T(kg)坐标(km)*y*y1832163.521628.2151

6、75.86183654187.5111745.547197.815126308153.419954.5311216.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818点的分布如下列图：二、问题分析2.1对于问题一的分析问题一，我们以运送总距离最短为目标函数建立01规划数学模型。对于本问题，有时间和重量两个约束条件，我们优先考虑重量。，所以至少要有8

7、个区域。表中数据的分析最大载重量重驶时速地中的平均速度重驶酬金业务员工作时间上限空驶时速每个送货点停留时间空驶酬金备注1.快件一律用重量来衡量2.假定街道方向平行于坐标轴然而，从题目中我们很明显的能够得知一个业务员要运送很屡次，而运送每次的路线即是我们所要确立的对于完成该任务运送路线。由于每个业务员的工作量有时间限制，于是我们又将时间考虑在，此时就需要增加业务员去完成任务，在此条件下所需的业务员就是完成该任务所需的最少业务员。对于运送路线确实定，我们主要分两步进展，一是每条路线上的目的地，二是经过这些目的地的先后顺序。对于每条路线上的目的地确实定，我们根据实际情况的需要，定义了最近插入法在满足

8、约束条件的前提下，在一次运送过程中，下一目标点确实定要离上一目标点最近。经过我们的分析，我们分别考虑了从最近点和最远点出发的送货路线，经过我们的求解比拟可知，从最近点出发的送货路线较优，于是我们选择了从最近点出发的送货路线。在此方法下我们通过MATLAB编程，找出了每条路线所经过的目的地。对于经过每条路线中目的地的先后顺序，我们采用了TSP算法，借助于计算机辅助计算，通过MATLAB编程找出了经过它们的最短路，也就是经过他们的先后顺序，使业务员用最少的时间完成一次运送，为下一次的运送节约了时间，可是业务员的工作时间最大化，从而只需较少的业务员即可完成任务。2.2问题二的分析问题二，业务员的速度

9、改变，分成携带快件和不携带两种情况下的具有不同的速度，分别为20km/h,30km/h,且业务员的薪酬与其工作过程中的行走的总路程有关。我们借助于第一问求解出送货路线的根底上，以运费最省为目标函数建立数学模型。由于问题一我们运送路线的安排都是最短的，而问题二只是对于速度这一约束条件进展了改变，运行的路线是没有变化的，所以我们根据时间要求，在问题一的根底上，对业务员的送货路线进展了调整。经过我们的分析，以费用最省建立目标函数，建立动态规划数学模型，每人工作时间不超过6小时且每次出发最多只带25千克的重量，列出目标函数和约束条件，来找出每条路线的送货点。三、模型假设结合此题的实际，为了确保模型求解

10、的准确性和合理性，我们排除了一些位置因素的干扰，提出以下几点假设：1、每个业务员每天的工作时间不超过6个小时，且送完货后必须再回公司报到。2、假设以送货运行路线均为平行于坐标轴的折线而不是直线。3、运货途中快件没有任何损坏，并且业务员的运送过程也十分平安，没有堵车、天气等问题，即送货过程非常顺利。4、如果离*一点最近的点不止一个，这时我们要从快件的量出发，选取加上此快件量最接近25千克而不能超过25千克的目的地。5、各个业务员之间的快件运送过程是相互独立的，互不影响。6、假设每个人的路线一旦确定，再不更改。四、符号说明为了便于问题的求解，我们给出以下符号说明：符号说明两质点的横纵坐标一个区域经

11、过的地方数一个区域所用的时间min总的所用的工作时间min两质点之间的距离总的路程km业务员每天送货的平均速度v=km/min1 在第i条路线上业务员向第j个送货点送快件0 在第i条路线上业务员不向第j个送货点送快件1 第i条路线上选择第j个送货点是最远点0 第i条路线上选择第j个送货点不是最远点第j个送货点坐标第j个送货点所需快件重量五、模型的建立与求解经过以上的分析和准备，我们将逐步建立以下数学模型，进一步阐述模型的实际建立过程。5.1问题一的模型建立与求解问题一我们分两步来完成，首先将30个点进展分组，使每组总的数之和尽量接近25kg，即一个邮递员的最大载重量。分组时我们采用先找两个可行

12、解，然后将两可行解比拟拟合得到最优解的方法。其次，确立组数之后求每组最优路线，通过计算时间，将邮递员分到相应的组。模型一的建立与求解两质点的横纵坐标，各自的差的绝对值的和等价于两质点之间的距离，即两点间距离： d都是使用用e*cel得到的距离,即a矩阵见附录一个区域所用时间为：所用总时间：根据各个送货点的分布，以矩形把整个区域分成5个区域，在区域或区域周围找出送货质量和小于25KG且距离尽可能小的点的集合，为一个送货区域，由一位业务员负责送货。由此，画出送货区域成折线距离的如下列图：将质量大的进展分组，在不超过25KG的同时将前面质量小的分摊给后面质量大的，将其缺乏25KG的局部补足。形成8条

13、路线。行进次序送货路线12345678业务员的送货路线、送货区域、送货的路程及时间通过e*cel可得行进次序送货路线问题一路程km时间min170168258139.234198.4456134.453379.262867.273788.8842100.8总计365876模型二的建立与求解考虑一个目标：总运行公里数最短。可以用以下方法：先假设每条线路由不同的业务员来完成，即需要8名业务员来完成运送快递；然后在人数不变的情况下，此题先从最远点开场出发，依次查找临近点，并考虑总重量小于25kg，以此来划分区域，最后利用最近插入法来寻求最优解，最后根据表中的时间的约束，对业务员人数安排进展重新调整。

14、根据题意每个业务员工作时间不超过6小时，又因为184.5/25=7.38；即派送这些快件至少需要8个业务员。因此问题一只需满足两个条件即可：业务员工作时间不超过6小时；每条线路上最大载重不超过25kg。由于快递员从公司出发最多只能载25kg，因此: 1 在每一条线路上，每一个送货点只能选择一次，因此： 2在每条线路上只有一个最远点，即： 3一条线路上至少有一个货点， 4业务员在每个货点停留10min，而业务员每天工作不超过6小时，因此： 6因此，此模型满足路程最短目标函数，建立如下模型：约束条件为：因为30这个点距原点最远，因此假设先从30出发，29是距离30最近的送货点，而且两点的快件重量和

15、为12.3kg小于每个人的最大负重，可以继续指配。接着28是距离29最近的点，此时三点的快件重量和为18.3kg仍小于25还可以继续指配，剩余送货点中23距离28最近其实距离28最近的点有23,24,26,27四个点，但是结合快递重量，将其从小到大依次排列，快递重量大者先选，但需满足总重量要求，综合考虑选择23，同理确定下一个点选择15，再继续扩大，会超出最大限载重，故返回原点，该路线总送货重量为24.1，所以第一条路线为。用该算法得到的所有路线一。现在这五个送货点之间的最优访问路径的是一个典型单回路问题。可以根据单回路运输模型TSP求解。一般而言，用比拟法求解TSP模型求解有最邻近法和最近插

16、入法两种。由最近插入法比最近邻点法得到的结果更好，由于已经构成一个子回路，但现在要将28插入，但是28送货点有3个位子可以插入：1、插入到0和30之间2、插入到30和29之间3、插入到29和0之间。分析比拟，得出插入到0和30之间，增量最小。同理将23和15用最近插入法，可以得出最优化路线为。用这种方法可以依次对剩下的七条路线进展优化，进而得出所有的优化送货路二。优化后优化前每个业务员每天工作不超过6小时的最正确匹配方案，又考虑每个业务员所经过工作站之间的距离，即：业务员3和业务员8的工作可以合并为一个人来做；业务员4和业务员7的工作可以合并为一个人来做。业务员5和业务员6的工作可以合并为一个

17、人来做。由此得出每位快递员的送货路线为：所得列表如下：业务员编号过站数所用时间小时总载重量千克总路程千米154.8324.1100233.5424.37634+33.39+1.6322.4+20.768+2845+33.15+2.1824.4+24.258+4254+32.83+2.6623.6+20.854+54合计3024.211845480下列图为各条路线优化前与优化后所用时间比拟下列图为各条路线优化前与优化后经过路程比拟5.2问题二的模型建立与求解问题一是以路程作为划分的界限，而问题二就是考虑以费用为主，费用最主要的因素就是重量和路程，根据题意，每个送货点的送货的质量是确定的，在确定送

18、货路线的时候，需要考虑每个业务员每次的载重量不得超过25Kg，且每个业务员每天工作量少于6小时即满足上面论述中需要注意的一些限制条件。要使得快递公司支出费用最少，则在安排业务员的路线的时候，需要尽可能使路线短，且载重量在离原点近的时候可以卸载快件。根据问题一的模型一的求解方法，首先把快件的重量按从大到小的顺序排列，将排序的前八个送货点记为重货点，其次八个为中等点，其余的记为轻货点。显然每个送货点的信件量的大小的分布是随机分布的。在此，我们考虑到它的总酬金越少则总费用越省，在考虑到重量的根底上，我们建立了以下的模型，来进展改良。因此我们转向讨论它是满载还是空载的情况。所以*业务员路线的选择应遵循

19、：近者优先，即应使尽量多的路线的最远点靠近原点，则必须同时考虑货物的重量和路程，先把货物重且近的送货点送完，依次筛选，最后送货物轻及远的，因此我们得到优化方案，即以货物的轻重做参考由近到远依次筛选。因此，所有业务员每天的总酬金：可建立动态规划模型如下：我们接下来用问题一的模型进展求解可以求得以下的的路线，同时我们对路线进展进一步的优化, 从而可以进展一次优化前后比照。从比照分析中我们对词的前后变动进展分析，通过简单的软件进展推断，再参加限制条件。1、近者优先原则。*业务员最近起始送货点的选择直接关系到费用的多少，所以该业务员在沿途往送货终点站中应尽量把较近点的快件送完，不让下一条路线再把较近点

20、作为起始送货站。2、少走重复路原则。由于在路途相等的条件下，重载费用要比空载费用大得多，因此，尽量让业务员空载行走。3、坐标贴近原则。在同一条路线中，离原点较近送货点的坐标仅次于较远点的坐标。4、路线较少原则。路线多，一方面，相对最远点的选择多，跑的空路多，费用就多；另一方面，过分地强调短暂效益，出动路线多，会引起业务员的反感，不利于以后的人员控制。根据这一思路，全部路线业务员的重载费用可表示为：根据上述分析及根本假设，业务员送货的费用可以表示如下：重载费用：空载费用：根据题意可知，业务员在第i条线路运送与不运送货物，所需时间：所以总约束条件为：时间约束：载重量约束:路线约束：；优化前优化后路

21、线编号经过站点所用时间小时总负载载重量千克负重路程空载路程总路程千米费用142.566724.8301242687.6253.324.8401454937333.066724.63820581659.8444.266724.65624801761.6543.133314.944852817.6634.424.45436902665.273523.74644902711.5844.922.76628942326.4合计30 = sum(C2:C9) * MERGEFORMAT 30.6334 = sum(D2:D9) * MERGEFORMAT 184.5 = sum(E2:E9) * MERG

22、EFORMAT 374 = sum(F2:F9) * MERGEFORMAT 186560 = sum(H2:H9) * MERGEFORMAT 13586.7由以上分析知，第一条路线和第二条路线可以由一名业务员来完成，其余每条路线分别由一名业务员运送，所以总共需要7名业务员。在以上方案中，公司每天付给业务员的总薪金为：13586.7。六、模型的评价与改良6.1模型的优点1、模型一给出了业务员的调配方案，便于指导工作。2、两个问题中所建的模型将多目标规划问题转化为单目标0-1规划问题求解，减少了运算量。3、此模型在业务员的调配中利用了最有匹配原理，减少了问题的时间复杂度。4、此模型的方法和思想

23、对其他类型也适，便于推广到其他领域。5、问题中的模型都通过最近插入法，来进展优化，以改变其条件，从而到达最优解。6、问题一中所建两个模型，来进展比照，从而找出更加简单且更好的结果。6.2模型的缺点1、本模型问题二没有充分利用问题一的结论进展相关的灵敏度分析，而是重新建立相对稳定的模型求解，因此增加了问题的繁琐程度。2、模型给出的约束条件也有不太现实的地方，对街道的方向和客户的快件量的假设也有待进一步改良。3、各个业务员的工作时间安排不甚合理，这需要进一步改良。七、模型的推广1、本模型不但适合于快递公司送货问题，还是用于一般的送货以及运输问题只需要稍微改动模型即可。 2、建模的方法和思想可以推广

24、到其他类型。3、模型方便直观，可以在很多中实现运用。八、参考文献1启源 金星 叶俊，数学建模第三版，：高等教育，2006年2 基于matlab 动态规划中最短路线的实现程序J电脑学习施益昌、贤斌、自立。3 Lingowenku.baidu./view/3bef9888d0d233d4b14e697e.html4 袁新生、邵大宏、郁时炼编，LINGO和E*cel在数学建模中的应用，科学，2007.1九、附录附录问题一中TSP算法求解路线即经过目的地的先后顺序：%运用tsp算法求的任一回路中各点的先后顺序，是总和最小；function y=tsp(hl)an=*lsread(3.*ls);m=si

25、ze(hl,2); n=hl;for i=1:m-2for j=i+1:m-1 i0=hl(i);j0=hl(j);i1=hl(i+1);j1=hl(j+1); an1=an(i0,j0)+an(i1,j1); an2=an(i0,i1)+an(j0,j1);if an1an2 n(i+1)=hl(j); n(j)=hl(i+1);n(j+1)=hl(j);endendendy=n;附录问题二中最省费用的计算：%此程序根据用TSP算法求出的各条回路中的最短回路共八条；%在第二问的条件下求出各条的路走完所需的时间及费用；%s_t(i)用来表示走完第i条回路所需的时间；%cost(i)用来表示走完

26、第i条回路的费用；w=cell(8,1);w1,1=1 2 4 5 6 1;k(1)=24;w2,1=1 3 14 8 7 1;k(2)=24.2;w3,1=1 11 13 9 10 1 ;k(3)=22.9;w4,1=1 17 18 21 15 1;k(4)=17.7;w5,1=1 23 22 24 16 12 1;k(5)=22.9;w6,1=1 20 26 25 1;k(6)=25;w7,1=1 19 27 29 1;k(7)=23.5;w8,1=1 28 30 31 1;k(8)=24.3;T=*lsread(1.*ls,j3:j33);V=*lsread(3.*ls);for i=1

27、:8 m=size(wi,1,2);an1=0;an2=0;an3=0;an=k(i);for j=1:m-2 s=wi,1(j);t=wi,1(j+1); an1=an1+V(s,t); an2=V(wi,1(1,(m-1),1); t1=1/6*(m-2); t2=an1/20;t3=an2/30; s_t(i,1)=t1+t2+t3; %求得每条的时间； an=an-T(wi,1(1,j); an3=an3+(an)*3*V(wi,1(1,j),wi,1(1,j+1); s_s(i,1)=an1+an2;end cost(i,1)=an3+an2*2; %求得每条的花费；endfor i=1:8 disp (第,num2str(i),条回路为：,num2str(wi,1), 时间为：,num2str(s_t(i,1), 花费为：,num2str(cost(i,1); disp(.);endss_t=sum(s_t);s_c=sum(cost);ss_s=sum(s_s);disp (这八条路线的总时间为：,num2str(ss_t), 总费用为：,num2str(s_c), 总路程为：,num2str(ss_s);送货点快件量T坐标(km)*Y91.4102*82.396*19.8232.4279*6308*153.4199163.5216143.81012