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

1、2012年第九届苏北数学建模联赛承诺书我们仔细阅读了第九届苏北数学建模联赛的比赛规则。我们完整理解，在比赛开始后参赛队员不可以以任何方式（包含电话、电子邮件、网上咨询等）与本队之外的任何人（包含指导教师）研究、谈论与赛题相关的问题。我们知道，剽窃他人的成就是违反比赛规则的,假如引用他人的成就或其余公开的资料（包含网上查到的资料），一定依据规定的参照文件的表述方式在正文引用途和参照文件中明确列出。我们郑重承诺，严格遵守比赛规则，以保证比赛的公正、公正性。若有违反比赛规则的行为，我们愿意担当由此引起的全部结果。我们的参赛报名号为：2394参赛组别（研究生或本科或专科）：本科组参赛队员(署名)：队员

2、1：鞠珊队员2：夏逸凡队员3：胡思想获奖证书邮寄地址：徐州工程学院数理学院教2-5132012年第九届苏北数学建模联赛页脚内容编号专用页参赛队伍的参赛号码：（请各个参赛队提前填写好）：比赛一致编号（由比赛组委会送至评委团前编号）：比赛评阅编号（由比赛评委团评阅行进行编号）：页脚内容题目快递公司送货策略大纲本文针对快递公司送货策略的优化问题进行研究，要点放在给该快递公司供给一个合理的送货策略；在一些特别条件的限制下，给该公司供给一个花费最省的送货策略。对于问题一，我们经过运送总距离最短目标函数第一建立了模型0-1整数线性规划模型。在给定送货地址和给定送货量和送货时间的拘束条件下，结合近来插入法和

3、最正确般配的原理，将送货点抽象为一个点（极点），因为街道和坐标轴平行，即任意两极点之间都有路，且任意两点间的距离为这两点横纵坐标差的绝对值之和。如Ax1,y1,Bx2,y2两点，则权值为Dx2x1y2y1。在此基础上,运用矩形，将整个地域分成5个地域，以选择的点的送货质量之和小于25kg且距离尽可能小的点的会集作为一个地域。挨次来分配业务员的送货地址。经过我们的计算，在不考虑时间的状况下，我们求得一个人达成任务的运送路线为8条，因为工作时间的限制，求出了达成任务所需的最少业务员为5人，最短总行程为365km。对于问题二，我们借助于问题一求解出来的路线，运用图论中最小生成树的原理，以花费最省为目

4、标函数建立数学模型。经过TSP模型在满足拘束条件的前提下求出最短距离，再对所求解方案进行优化更正，从而我们求得问题二的最省花费为13586.7。要点词0-1整体线性规划近来插入法最小生成树TSP模型excel一、问题重述页脚内容1.1背景分析目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，而后由业务员分别进行派送；对于快递公司，为了保证快件可以在指定的时间内送到目的地，一定有足够的业务员进行送货，可是，太多的业务员意味着更多的派送花费。1.2问题重述假设所有快件在清早7点钟到达，清早9点钟开始派送，要求于当日17点从前一定派送到成，每个业务员每

5、天均匀工作时间不超出6小时，在每个送货点逗留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，均匀每天收到总重量为184.5千克，公司总部位于坐标原点处（如图2），每个送货点的地址和快件重量见下表，并且假设送货运转路线均为平行于坐标轴的折线。问题1：请你运用相关数学建模的知识，给该公司供给一个合理的送货策略（即需要多少业务员，每个业务员的运转线路，以及总的运转公里数）；问题2：假如业务员携带快件时的速度是20km/h，获取酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个花费最省的策略。送货

6、点快件量T坐标(km)送货点快件量T坐标(km)(kg)xy(kg)xy1832163.521628.215175.86183654187.5111745.547197.815126308153.419954.5311216.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818页脚内容点的分布以以下图：2531542015,1924,2006,182

7、8,18311,1720,1772,1625,169题157,1415,1410标21,1314轴10,1215,1217标3,11坐10147,912,919,927,9120,8104,79,614,61951,522,525,417,363,210,211014,021,015705101520253022坐标轴标题2127二、问题分析2.1对于问题一的分析问题一，我们以运送总距离最短为目标函数建立01规划数学模型。对于本问题，有时间和重量两个拘束条件，我们优先考虑重量。地域数每天收到的总重量184.57.38，所以最少要有8个地域。的重量25每次出发每人最多能带表中数据的分析最大载重量

8、25kg重驶时速20km/h地中的均匀速度25km/h重驶酬金3元/km*h业务员工作时间上限6h空驶时速30km/h每个送货点逗留时间10min空驶酬金2元/km备注1.快件一律用重量来衡量2.假设街道方向平行于坐标轴可是，从题目中我们很明显的可以得知一个业务员要运送很多次，而运送每次的路线即是我们所要确定的对于达成该任务运送路线。因为每个业务员的工作量有时间限制，于是我们又将时间考页脚内容虑在内，此时就需要增添业务员去达成任务，在此条件下所需的业务员就是达成该任务所需的最少业务员。对于运送路线的确定，我们主要分两步进行，一是每条路线上的目的地，二是经过这些目的地的先后次序。对于每条路线上的

9、目的地的确定，我们依据实质状况的需要，定义了近来插入法在满足拘束条件的前提下，在一次运送过程中，下一目标点的确定要离上一目标点近来。经过我们的分析，我们分别考虑了从近来点和最远点出发的送货路线，经过我们的求解比较可知，从近来点出发的送货路线较优，于是我们选择了从近来点出发的送货路线。在此方法下我们经过MATLAB编程，找出了每条路线所经过的目的地。对于经过每条路线中目的地的先后次序，我们采纳了TSP算法，借助于计算机辅助计算，经过MATLAB编程找出了经过它们的最短路，也就是经过他们的先后次序，使业务员用最少的时间达成一次运送，为下一次的运送节约了时间，可是业务员的工作时间最大化，从而只需较少

10、的业务员即可达成任务。2.2问题二的分析问题二，业务员的速度改变，分成携带快件和不携带两种状况下的拥有不一样的速度，分别为20km/h,30km/h,且业务员的薪酬与其工作过程中的行走的总行程相关。我们借助于第一问求解出送货路线的基础上，以运费最省为目标函数建立数学模型。因为问题一我们运送路线的安排都是最短的，而问题二不过对于速度这一拘束条件进行了改变，运转的路线是没有变化的，所以我们依据时间要求，在问题一的基础上，对业务员的送货路线进行了调整。经过我们的分析，以花费最省建立目标函数，建立动向规划数学模型，每人工作时间不超出6小时且每次出发最多只带25千克的重量，列出目标函数和拘束条件，来找出

11、每条路线的送货点。三、模型假设结合本题的实质，为了保证模型求解的正确性和合理性，我们除掉了一些地址要素的搅乱，提出以下几点假设：1、每个业务员每天的工作时间不超出6个小时，且送完货后一定再回公司报到。2、假设以送货运转路线均为平行于坐标轴的折线而不是直线。3、运货途中快件没有任何损坏，并且业务员的运送过程也十分安全，没有堵车、天气等问题，即送货过程特别顺利。4、假如离某一点近来的点不仅一个，这时我们要从快件的量出发，采纳加上此快件量最凑近25千克而不可以超出25千克的目的地。5、各个业务员之间的快件运送过程是互相独立的，互不影响。6、假设每个人的路线一旦确定，再不改正。四、符号说明为了便于问题

12、的求解，我们给出以下符号说明：符号说明x,y两质点的横纵坐标ki一个地域经过的地方数i1,2,.,i页脚内容tiTdijDvaijsijjx,jymj一个地域所用的时间（min）i1,2,.,i总的所用的工作时间（min）两质点之间的距离dij总的行程（km）25业务员每天送货的均匀速度v=（km/min）在第i条路线上业务员向第j个送货点送快件在第i条路线上业务员不向第j个送货点送快件第i条路线上选择第j个送货点是最远点0第i条路线上选择第j个送货点不是最远点第j个送货点坐标第j个送货点所需快件重量五、模型的建立与求解经过以上的分析和准备，我们将逐渐建立以下数学模型，进一步论述模型的实质建立

13、过程。5.1问题一的模型建立与求解问题一我们分两步来达成，第一将30个点进行分组，使每组总的邮件数之和尽量凑近25kg，即一个邮递员的最大载重量。分组时我们采纳先找两个可行解，而后将两可行解比较拟合获取最优解的方法。其次，确定组数以后求每组最优路线，经过计算时间，将邮递员分到相应的组内。5.1.1模型一的建立与求解两质点的横纵坐标（(xi,yi)，(xj,yj)）各自的差的绝对值的和等价于两质点之间的距离dij，即两点间距离：dij|xixj|yiyj|d都是使用用excel获取的距离,即a矩阵（见附录）一个地域所用时间为：tiD10kivdij1030所用总时间：Tv依据各个送货点的分布，以

14、矩形把整个地域分成5个地域，在地域或地域四周找出送货质量和小于25KG且距离尽可能小的点的会集，为一个送货地域，由一位业务员负责送货。由此，画出送货地域成折线距离的以以下图：页脚内容3251542024,20015,1936,1828,18711,1720,172,1625,169题157,1415,1410标1421,13轴1710,1215,12标3,1114坐107,912,919,927,9120,8104,79,614,61951,522,5265,417,33,210,21115014,021,0705101520253022坐标轴标题2127将质量大的进行分组，在不超出25KG的

15、同时将前面质量小的分摊给后边质量大的，将其不足25KG的部分补足。形成8条路线。行进次序送货路线14-5-11-20-3023-9-13-17-28310-21-22-6-847-18-24-2351-19-2962-12-15725-26827-14-16业务员的送货路线、送货地域、送货的行程及时间（经过excel可得）行进次序送货路线问题一行程（km）时间（min）14-5-11-20-307016823-9-13-17-2858139.2310-21-22-6-84198.447-18-24-2356134.451-19-293379.262-12-152867.2725-263788.

16、8827-14-1642100.8总计365876页脚内容2028,1825题2020题157,14418标3,113标15系列1轴1017轴9标4,77标10坐5坐517,328420001020300102030坐标轴标题坐标轴标题图表标题图表标题题109题2015,19标0,89,6标11,1727轴522,50轴107,927,97标014,021,014标11坐22坐0010203001020301521坐标轴标题坐标轴标题图表标题图表标题201525,1615,12310155253,2001020301019,91951,514,6101401020图表标题题20标152,162

17、1,210,轴10121310标521坐002040坐标轴标题模型二的建立与求解考虑一个目标：总运转公里数最短。可以用以下方法：先假设每条线路由不一样的业务员来达成，即需要8名业务员来达成运送快递；而后在人数不变的状况下，本题先从最远点开始出发，挨次查找周边点，并考虑总重量小于25kg，以此来划分地域，最后利用近来插入法来追求最优解，最后依据表中的时间的拘束，对业务员人数安排进行重新调整。依据题意每个业务员工作时间不超出6小时，又因为184.5/25=7.38；即派送这些快件最少需要8个业务员。所以问题一只需满足两个条件即可：页脚内容1.业务员工作时间不超出6小时；2.每条线路上最大载重不超出

18、25kg。因为快递员从公司出发最多只好载25kg，所以:30aijmj25（1）j1在每一条线路上，每一个送货点只好选择一次，所以：8（2）aij1i1在每条线路上只有一个最远点，即：30（3）bij1j1一条线路上最罕有一个货点，aijbij0（4）即aijbij业务员在每个货点逗留10min，而业务员每天工作不超出6小时，所以：2sij(jxjy)130aij6256j1且aij或0（6）1bij1或0所以，此模型满足行程最短目标函数，建立以下模型：830min2bij(jxjy)i1j1拘束条件为：30bij1j18aij1i1aijbij30staijmj25j12sij(jxjy)3

19、01aij6256j1bij或01aij1或0页脚内容因为30这个点距原点最远，所以假设先从30出发，29是距离30近来的送货点，并且两点的快件重量和为12.3kg小于每个人的最大负重，可以连续指配。接着28是距离29近来的点，此时三点的快件重量和为18.3kg仍小于25还可以连续指配，节余送货点中23距离28近来（其实距离28近来的点有23,24,26,27四个点，可是结合快递重量，将其从小到大挨次摆列，快递重量大者先选，但需满足总重量要求，综合考虑选择23），同理确定下一个点选择15，再连续扩大，会超出最大限载重，故返回原点，该路线总送货重量为24.1，所以第一条路线为0302928231

20、50。用该算法获取的所有路线一。此刻030292823150这五个送货点之间的最优接见路径的是一个典型单回路问题。可以依据单回路运输模型TSP求解。一般而言，用比较法求解TSP模型求解有最周边法和最近插入法两种。由近来插入法比近来邻点法获取的结果更好，因为030290已经构成一个子回路，但此刻要将28插入，可是28送货点有3个位子可以插入：1、插入到0和30之间2、插入到30和29之间3、插入到29和0之间。分析比较，得出插入到0和30之间，增量最小。同理将23和15用近来插入法，可以得出最优化路线为028302923150。用这类方法可以挨次对剩下的七条路线进行优化，从而得出所有的优化送货路

21、二。1)0302928231502)02627803)0242514904)018172016605)0212211100优化前6)01913707)0124308)052101)0283029231502)02627803)024251490优化后4)020181716605)01121221006)01913707)0412308)02510每个业务员每天工作不超出6小时的最正确般配方案，又考虑每个业务员所经过工作站之间的距页脚内容离，即：1、业务员3和业务员8的工作可以合并为一个人来做；2、业务员4和业务员7的工作可以合并为一个人来做。3、业务员5和业务员6的工作可以合并为一个人来做。由

22、此得出每位快递员的送货路线为：1)0283029231502)02627803)02425149025104)02018171660412305)0112122100191370所得列表以下：业务员编号过站数所用时间（小时）总载重量（千克）总行程（千米）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以下图为各条路线优化前与优化后所用时间比较时间6优化前所用4时间2优化后所用0时间12345678以下

23、图为各条路线优化前与优化后经过行程比较页脚内容行程120100优化前路80程6040优化后路程200123456785.2问题二的模型建立与求解问题一是以行程作为划分的界限，而问题二就是考虑以花费为主，花费最主要的要素就是重量和行程，依据题意，每个送货点的送货的质量是已知确定的，在确定送货路线的时候，需要考虑每个业务员每次的载重量不得超出25Kg，且每个业务员每天工作量少于6小时即满足上边论述中需要注意的一些限制条件。要使得快递公司支出花费最少，则在安排业务员的路线的时候，需要尽可能使路线短，且载重量在离原点近的时候可以卸载快件。依据问题一的模型一的求解方法，第一把快件的重量按从大到小的次序摆

24、列，将排序的前八个送货点记为重货点，其次八个为中等点，其余的记为轻货点。明显每个送货点的信件量的大小的分布是随机分布的。在此，我们考虑到它的总酬金越少则总花费越省，在考虑到重量的基础上，我们建立了以下的模型，来进行改进。所以我们转向谈论它是满载还是空载的状况。所以某业务员路线的选择应依据：近者优先，即应使尽量多的路线的最远点凑近原点，则一定同时考虑货物的重量和行程，先把货物重且近的送货点送完，挨次挑选，最后送货物轻及远的，所以我们获取优化方案，即以货物的轻重做参照由近到远挨次挑选。所以，所有业务员每天的总酬金：QQ1Q2可建立动向规划模型以下：页脚内容30TjZij25j125n184.530

25、303TjjxjyN302eijjxsteij1j1minj1i1j1jyjxmaxjyjxjy30eijmaxijijijj1zze620306我们接下来用问题一的模型进行求解可以求得以下的的路线，同时我们对路线进行进一步的优化,从而可以进行一次优化前后比较。从比较分析中我们对词的前后变动进行分析，经过简单的软件进行推测，再加入限制条件。1、近者优先原则。某业务员近来初步送货点的选择直接关系到花费的多少，所以该业务员在沿途往送货终点站中应尽量把较近点的快件送完，不让下一条路线再把较近点作为初步送货站。2、少走重复路原则。因为内行程相等的条件下，重载花费要比空载花费大得多，所以，尽量让业务员空

26、载行走。3、坐标切近原则。在同一条路线中，离原点较近送货点的坐标仅次于较远点的坐标。4、路线较少原则。路线多，一方面，相对最远点的选择多，跑的空路多，花费就多；另一方面，过分地重申短暂效益，出动路线多，会引起业务员的厌烦，不利于今后的人员控制。依据这一思路，所有路线业务员的重载花费可表示为：30M13mjjxjyj1依据上述分析及基本假设，业务员送货的花费可以表示以下：30重载花费：M13mjjxjyj1830空载花费：M22sijjxjyi1j1依据题意可知，业务员在第i条线路运送与不运送货物，所需时间：页脚内容sijjxjy;T120sijjxjyT230所以总拘束条件为：（1）sijjx

27、jysijjxjy130时间拘束：20aij6306j1（2）载重量拘束:30aijmj25j1（3）路线拘束：aijsijaij1或00；1或0sij10217902010345803121911040223213170502014166060272623070252928080241830150优化后优化前10127902034581003121911040223213170501420166060272623070252928080182430150页脚内容路线编经过所用时总负载载负空载路总路花费号站点间重量重程程（小（千克）路（千时）程米）142.566724.8301242687.6

28、253.324.8401454937333.066724.63820581659.8444.266724.65624801761.6543.133314.944852817.6634.424.45436902665.273523.74644902711.5844.922.76628942326.4合计3030.633184.5374186560135864.7由以上分析知，第一条路线和第二条路线可以由一名业务员来达成，其余每条路线分别由一名业务员运送，所以总合需要7名业务员。在以上方案中，公司每天付给业务员的总薪金为：13586.7。六、模型的谈论与改进页脚内容6.1模型的长处1、模型一给出了

29、业务员的分配方案，便于指导工作。2、两个问题中所建的模型将多目标规划问题转变成单目标0-1规划问题求解，减少了运算量。3、此模型在业务员的分配中利用了最有般配原理，减少了问题的时间复杂度。4、此模型的方法和思想对其余种类也适，便于推行到其余领域。5、问题中的模型都经过近来插入法，来进行优化，以改变其条件，从而达到最优解。6、问题一中所建两个模型，来进行比较，从而找出更加简单且更好的结果。6.2模型的弊端1、本模型问题二没有充分利用问题一的结论进行相关的矫捷度分析，而是重新建立相对稳固的模型求解，所以增添了问题的繁琐程度。2、模型给出的拘束条件也有不太现实的地方，对街道的方向和客户的快件量的假设

30、也有待进一步改进。3、各个业务员的工作时间安排不甚合理，这需要进一步改进。七、模型的推行1、本模型不仅合适于快递公司送货问题，还是用于一般的送货以及运输问题只需要略微变动模型即可。2、建模的方法和思想可以推行到其余种类。3、模型方便直观，可以在很多中实现运用。八、参照文件姜启源谢金星叶俊，数学建模（第三版），北京：高等教育第一版社，2006年基于matlab动向规划中最短路线的实现程序J电脑学习施益昌、郑贤斌、李自立。Lingo袁重生、邵大宏、郁时炼编，LINGO和Excel在数学建模中的应用，科学第一版社，2007.1页脚内容九、附录附录I问题一中TSP算法求解路线即经过目的地的先后次序：%

31、运用tsp算法求的任一回路中各点的先后次序，是总和最小；functiony=tsp(hl)an=xlsread(3.xls);页脚内容m=size(hl,2);n=hl;fori=1:m-2forj=i+1:m-1i0=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);ifan1an2n(i+1)=hl(j);n(j)=hl(i+1);n(j+1)=hl(j);endendendy=n;附录II问题二中最省花费的计算：%此程序依据用TSP算法求出的各条回路中的最短回路（共八条

32、）；%在第二问的条件下求出各条的路走完所需的时间及花费；%s_t(i)用来表示走完第i条回路所需的时间；%cost(i)用来表示走完第i条回路的花费；w=cell(8,1);w1,1=124561;k(1)=24;w2,1=1314871;k(2)=24.2;w3,1=111139101;k(3)=22.9;w4,1=1171821151;k(4)=17.7;w5,1=123222416121;k(5)=22.9;w6,1=12026251;k(6)=25;w7,1=11927291;k(7)=23.5;w8,1=12830311;k(8)=24.3;T=xlsread(1.xls,j3:j3

33、3);V=xlsread(3.xls);fori=1:8m=size(wi,1,2);an1=0;an2=0;an3=0;an=k(i);forj=1:m-2s=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;endcost(i,1)=an3+an2*2;%求得每条的