快递公司送货策略 完成定稿

1、-作者xxxx-日期xxxx快递公司送货策略 完成定稿【精品文档】湖北工业大学机械工程学院数学建模论文学 院： 机械工程学院专 业： 机自 题 目： 快递公司送货策略班 级： 09 创新作 者： 屠年波 0910100408 梁 晨 0910100731指导教师： 朱永松 2011 年 5月 16日快递公司送货策略摘要本文是关于快递公司送货策略的优化问题，即在给定送货地点和给定送货量和送货时间的约束条件下，确定所需业务员人数，每个业务员的运行线路，总的运行公里数，以及费用最省的策略。本文主要从最短路经和费用最省两个角度来解决该问题，建立了两个数据模型。模型一：整数规划模型结合最近插入法和最佳匹

2、配的原理，将送货点抽象为顶点，由于街道和坐标轴平行，即任意两顶点之间都有路。在此模型中，将两点之间的距离为这两点横纵坐标差的绝对值之和。并利用Lingo软件对以上结果进行了求解。模型二：根据题意，建立单目标0-1整数规划的数学模型，然后用类似于问题一的方法，建立满足题意的目标函数以及约束条件，并求得符合要求结果。最后，对所求解的方案进行优化修改。关键词快递公司送货 最优化 多目标动态规划 TSP模型 最佳匹配原理一 问题的提出：目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送

3、达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。假定所有快件在早上7点钟到达，早上9点钟开始派送，要求与当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点，每个送货点的位置和快件重量如下表所示，并且假设街道平行于坐标轴方向。1. 请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（需要多少业务员，每个业务员的运行线路，以及总的运行公里数）。2. 如果业务

4、员负重时的速度是20km/h，获得酬金是3元/km*kg；而不携带快件时的速度是30km/h，酬金是2元/km，请为公司设计一个费用最省的策略。送货点快件量T坐标(km)送货点快件量T坐标(km)xyxy1832162162151761836541811174471915126308151995311322257792221089623279910224151910140251514111732610201712146271221131312928242014101229251620714302818点的分布如下图： 二 问题分析：分析题意，由题目要求知：快递业务员是否送货到某送货点建立0-1

5、分布函数，以业务员的人数和路线总公里数为多目标函数，时间、货重等为约束条件建立数学模型，利用软件进行求解，得出最终结论。快递公司平均每天要送出总重量为184.5千克的邮件，每个人的工作时间每天不超过6小时，且每个人的最大负重是25kg，由, 可知至少需要8条路线对这些邮件进行运送。 三 模型假设： 1、假设业务员送货期间行进速度不受外界影响，且业务员的休息时间不包括在最大工作时间6个小时内。2、每个业务员每天的工作时间不超过6个小时，且送完货后必须再回公司报到。 3、假设业务员送货运行路线均为平行于坐标轴的折线。 4、业务员到某送货点后必须把该送货点的快件送完。 5、假设业务员人数不限制。6、

6、每个业务员送快递是独立的，每人之间互不影响。四 符号说明m：业务员的数量N 送货路线条数n： 业务员送货的次数k： 送货点的序号 第r个业务员送货的次数 第j个送货点的坐标五 模型的建立：(1)问题一模型:快递公司平均每天要送出总重量为184.5千克的邮件，每个人的工作时间每天不超过6小时，且每个人的最大负重是25kg，由, 可知至少需要8条路线,则最多需要八个业务员。由于第一问中只要求对快递公司提供一个合理的送货策略，而没有涉及到业务员的酬金问题，因此只需要满足两个条件： 业务员每天的工作是时间不超过6个小时； 每条路线的最大载重量不超过25千克。本题目中考虑两个目标：业务员人数最少和总的运

7、行公里数最小。可以通过以下方法实现： 假设每条路线的第一个送货点是该条路线上距离总部最远的送货点，然后以该点为基准，选择距它最近的点，加上约束条件，进行规划求解。(2)问题二模型： 由于业务员所得到的工资费用是最重要的影响因素，业务员安排、路线选择都是为了总费用的最小化提供条件，所以应该首先考虑行运路程的费用，之后再考虑业务员的安排。无论业务员怎样送货，所有业务员载货过程中所得总酬金恒定，所以只需考虑业务员空载时的总酬金，又空载时在总酬金只与每一天线路的最远点有关，所以总费用的确定就可以转化为满足一定条件下的路线最远点的选择问题。六 模型的求解与结果分析（1）问题一模型：首先，假设每一条路线上

8、由不同的业务员派送快件，即需要8个业务员同时从总部出发派送所有快件；其次，在业务员人数确定（即8个业务员）的情况下，本问题可以转化为利用0-1整数规划对总的运行公里数实施满足条件的最小化；再次，对所建立的单目标模型利用Lingo软件求解，并分析数据，列出每条路线上的时间耗费表；最后，根据上述表中的数据，利用最佳匹配的原理，对业务员的人数安排进行重新调配，得到总行运路程最小情况下，快递公司所需业务员人数最少的策略，此时即为一种合理的方案。目标函数 且 第一条路线一次经过的送货点为，因为30距原点最远，因此从30出发，29是距离30最近的送货点，而且两点的快件重量和为12.3kg小于每个人的最大负

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

10、插入法比最近邻点法得到的结果更好，由于已经构成一个子回路，但现在要将28插入，但是28送货点有3个位子可以插入：1、插入到0和30之间2、插入到30和29之间3、插入到29和0之间。分析比较，得出插入到0和30之间，增量最小。同理将23和15用最近插入法，可以得出最优化路线为。用这种方法可以依次对剩下的七条路线进行优化，进而得出所有的优化送货路：下表为由近似平均速度v=2/(1/30+1/20)=24km/h规划得结果：下表为精确计算负重和空载经历时间及路程(各量单位同上表)：下图为各条路线优化前与优化后所用时间比较下图为各条路线优化前与优化后经过路程比较由各条路线所经历的时间，结合每个业务员

11、每天工作时间不超过6小时要求，确立最佳匹配方案：第3条路线和第8条路线可由一名业务员完成；第6条路线和第7条路线可由一名业务员完成；由以上分析知最终只需要6名业务员。每个业务员相应的快递送货路线为：列表如下业务员编号过站总数所用时间（小时）总载重量（千克）总路程（千米368+284558535463+342+28总计30480(2)问题二模型： 假设业务员在送完最远点后的返回途中不送货，并假设业务员送货路线不走回头路（送货负重过程中不往横纵坐标轴的反方向走）。依据题目条件可知我们必需把业务员的酬金越少越好作为第一目标，其次再考虑总路程的多少。经分析，无论业务员怎样送货

12、，所有业务员载货过程中所得总酬金恒定，即： 因为返回过程中不送货，所以业务员返回过程中所得的酬金即为其空载的酬金，则所有业务员空载时的总酬金为： 由上知由于载货过程中所得总酬金不变，所以只需考虑业务员空载时的总酬金，又空载时在总酬金只与每一天线路的最远点有关，所以总费用的确定就可以转化为满足一定条件下的路线最远点的选择问题。所以某业务员路线的选择应遵循：近者优先，即应使尽量多的路线的最远点靠近原点，则必须同时考虑货物的重量和路程，先把货物重且近的送货点送完，依次筛选，最后送货物轻及远的，因此我们得到一优化方案，即以货物的轻重做参考由近到远依次筛选。因此，所有业务员每天的总酬金： 可建立动态规划

13、模型如下：目标： 由Lingo软件求解，分析数据，可以得出如下路线： 同样与模型一种相类似，在满足要求条件下，运用最近插入法进行优化，得出优化后的所有路线：路线编号经过站点所用时间（小时）总负载载重量（千克）负重路程空载路程总路程（千米）费用1430124225401454937333820584456248054448526354369073546449084662894合计30374186560由以上分析知，第一条路线和第二条路线可以由一名业务员来完成，其余每条路线分别由一名业务员运送，所以总共需要7名业务员。在以上方案中，公司每天付给业务员的总薪金为：13586.7。.七、模型评价与改进

14、1、模型优点1）本模型给出了业务员的调配方案，便于指导工作；2）本模型将多目标规划问题转化为单目标0-1规划问题求解，减少了运算量；3)本模型在业务员的调配中利用了最有匹配原理，减少了问题的时间复杂度；4)本模型的方法和思想对其他类型也适，便于推广到其他领域。2、模型缺点1）本模型问题二没有充分利用问题一的结论进行相关的灵敏度分析，而是重新建立相对稳定的模型求解，因此增加了问题的繁琐程度。2）模型给出的约束条件也有不太现实的地方，对街道的方向和客户的快件量的假设也有待进一步改进。3、模型的推广：1）本模型不但适合于快递公司送货问题，还是用于一般的送货以及运输问题 只需要稍微改动模型即可。 2）

15、建模的方法和思想可以推广到其他类型。参考文献【2】姜启源、谢金星、叶俊编，数学模型-3版，北京，高等教育出版社，2003.8 附录：y1=0 0 1 1 2 2 7 7 9 9 0;x1=0 1 1 2 2 3 3 4 4 5 5;y2=0 0 3 3 4 4 5 5 8 8 10 10 0;x2=0 1 1 2 2 3 3 4 4 5 5 6 6 ;y3=0 0 12 12 19 19 11 11 0;x3=0 1 1 2 2 3 3 4 4;y4=0 0 22 22 32 32 13 13 17 17 0;x4=0 1 1 2 2 3 3 4 4 5 5;y5=0 0 14 14 20 20 16 16 6 6 0;x5=0 1 1 2 2 3 3 4 4 5 5;y6=0 0 27 27 26 26 23 23 0;x6=0 1 1 2 2 3