《第16组 B题 快递公司管理系统送货策略》由会员分享，可在线阅读，更多相关《第16组 B题 快递公司管理系统送货策略（17页珍藏版）》请在装配图网上搜索。
1、word数学建模论文题目：快递公司的运送策略 学校:中原工学院信息商务学院组成员：邝光辉、魏胜伦、唐锦锦2012年8月29日快递公司送货策略摘要.本论文是关于快递公司送货策略的优化问题，就是在给定送货地点和给定送货量和送货时间的约束条件下，确定所需业务员人数，每个业务员的运行线路，总的运行公里数，以与费用最少的策略。本文主要从最短路径和费用最省两个角度来考虑问题，建立三个数学模型。 模型一：此题主要运用的的最优化线性规划中的0-1整数规划建立约束条件，将送货点抽象为一个点，且任意两点间的距离为这两点横纵坐标差的绝对值之和。先从最远点开始出发，一次查找临近点，并考虑总重量小于25kg，以此来划分
2、区域，最后利用最近插入法来寻求最优解，假设每条线路由不同的业务员来完成。模型二：运用的是图论中最小生成树的原理，在满足约束条件的前提下求的最短距离。模型三：在问题一的根底上，重新建立模型求解，得到目标结果。关键词： 快递公司送货 最优化 0-1整数规划 最近插入法 最小生成树1问题重述目前，快递行业正蓬勃开展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进展派送；对于快递公司，为了保证快件能够在指定的时间送达目的地，必须有足够的业务员进展送货，但是，太多的业务员意味着更多的派送费用。由此我们得知，确定业务员的人数和各自行走路线是此题的主要步骤。求满足
3、需求的路程最短的人员行驶路线，且使用尽量少的人数，并满足以下条件：（1） 每天的快件必须在规定的时间9：0017：008小时全部送完。（2） 每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h。（3） 每次出发业务员所携带的快件重量不超过25kg。（4） 为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克。（5） 下表所给的数据为每个送货点的位置和快件重量，并且公司总部位于坐标原点处如图2，并且假设送货运行路线均为平行于坐标轴的折线。送货点快件量T(kg)坐标(km)送货点快件量T(kg)坐标(km)xyxy1832163
4、.5216215175.86183654187.51117447197.815126308153.41995311216.222577.279226.8210896232.42799102247.61519106.5140259.61514114.11732610201712114627122113135.8129286.02420143.81012298.12516204.6714304.22818图2 送货点分布图1请你运用有关数学建模的知识，给该公司提供一个合理的送货策略即需要多少业务员，每个业务员的运行线路，以与总的运行公里数；2如果业务员携带快件时的速度是20km/h，获得酬金3元/
5、kmkg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略；3如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？在问题1中：平均每天收到的总重量为184.5千克，每个人的最大负重是25千克，即184.5/25=7.38，可知需要8条路线对这些快件进展运送。利用从最远点出发依次查找符合条件限制的各个区域，求得8条行走路线，然后根据最近插入法对路线进展优化。根据优化后得出的路线求的各条路线的路程，和在速度为25km/h的条件下得出走完每条路所需的时间。有题意知：每个业务员的工作时间不小于6小时，在此根底上将工作时间短的路线进展合并，进而求的在完成总的
6、送货量且工作时间小于6小时的条件下，所需的总的业务员数。在问题2中：业务员的速度改变，分成携带快件和不携带两种情况下的具有不同的速度，分别为20km/h,30km/h,且业务员的薪酬与其工作过程中的行走的总路程有关。以费用最省建立目标函数，建立动态规划数学模型，每人工作时间不超过6小时且每次出发最多只带25千克的重量，列出目标函数和约束条件，来找出每条路线的送货点。问题3 将业务员工作时间延长至8小时，在1的根底上将时间约束条件改为8个小时，在满足条件根底下，对问题1的路线进展合并，得出公司的送货策略。1初始模型中，假设每条路线对应不同的业务员。2每个业务员每天的工作时间不超过6个小时，且送完
7、货后必须再回公司报到。3业务员的休息时间不包括在最大工作时间6个小时。4每个业务员送快递是独立的，每人之间互不影响。5业务员到某送货点后必须把该送货点的快件送完。6假设业务员送货运行路线均为平行于坐标轴的折线。7无塞车现象，即业务员送快递途中不受任何外界因素影响，且业务员的休息时间不包括在最大工作时间6个小时。(1)(2)(3):表示第j个送货点坐标(4)：第j个送货点所需快件重量。问题1：此题中考虑一个目标：总运行公里数最短。可以用以下方法：先假设每条线路由不同的业务员来完成，即需要8名业务员来完成运送快递；然后在人数不变的情况下，此题先从最远点开始出发，依次查找临近点，并考虑总重量小于25
8、kg，以此来划分区域，最后利用最近插入法来寻求最优解，最后根据表中的时间的约束，对业务员人数安排进展重新调整。根据题意每个业务员工作时间不超过6小时，又因为184.5/25=7.38；即派送这些快件至少需要8个业务员。因此问题1只需满足两个条件即可：1. 业务员工作时间不超过6小时；2. 每条线路上最大载重不超过25kg由于快递员从公司出发最多只能载25kg，因此: (1)在每一条线路上，每一个送货点只能选择一次，因此： 2在每条线路上只有一个最远点，即： 3一条线路上至少有一个货点， 4业务员在每个货点停留10min，而业务员每天工作不超过6小时，因此： 6因此，此模型满足路程最短目标函数，
9、建立如下模型：约束条件为：因为30这个点距原点最远，因此假设先从30出发，29是距离30最近的送货点，而且两点的快件重量和为12.3kg小于每个人的最大负重，可以继续指配。接着28是距离29最近的点，此时三点的快件重量和为18.3kg仍小于25还可以继续指配，剩余送货点中23距离28最近其实距离28最近的点有23,24,26,27四个点，但是结合快递重量，将其从小到大依次排列，快递重量大者先选，但需满足总重量要求，综合考虑选择23，同理确定下一个点选择15，再继续扩大，会超出最大限载重，故返回原点，该路线总送货重量为24.1，所以第一条路线为。用该算法得到的所有路线为： 现在这五个送货点之间的
10、最优访问路径的是一个典型单回路问题。可以根据单回路运输模型TSP求解。一般而言，用比拟法求解TSP模型求解有最邻近法和最近插入法两种。由最近插入法比最近邻点法得到的结果更好，由于已经构成一个子回路，但现在要将28插入，但是28送货点有3个位子可以插入：1、插入到0和30之间2、插入到30和29之间3、插入到29和0之间。分析比拟，得出插入到0和30之间，增量最小。同理将23和15用最近插入法，可以得出最优化路线为。用这种方法可以依次对剩下的七条路线进展优化，进而得出所有的优化送货路：每个业务员所工作的具体情况如下表所示：业务员编号过站数所用时间小时总路程千米总载重量千克151002376346
11、845585454635473428328合计30480根据上述表格中的时间，可以读出每个业务员每天工作不超过6小时的最优匹配方案，又考虑每个业务员所经过工作站之间的距离，即：1） 业务员3和业务员8的工作可以合并为一个人来做；2） 业务员4和业务员7的工作可以合并为一个人来做。3） 业务员5和业务员6的工作可以合并为一个人来做。由此得出每位快递员的送货路线为：现列表如下：业务员编号过站数所用时间小时总载重量千克总路程千米15100237634+368+2845+358+4254+354+54合计301845480如下图为各条路线优化前与优化后所用时间比拟如下图为各条路线优化前与优化后经过路程
12、比拟运行路线如下：路线进展合并后每个人的行走路线：问题2：问题二中由于业务员所得的费用是最主要的，业务员安排、路线选择都是为了总费用的最小化提供条件，所以应首先考虑路费，之后再考虑业务员的安排。为了使总能够费用最少，总的思路是先送货给离快递公司最近且快件最重的送货点，以此类推，在保证时间、载重量有限的前提下，沿途把快递送完，最终让业务员最远点空载返回。根据这一思路，全部路线业务员的重载费用可表示为：某路线业务员经过的路径选择应遵循以下原如此：1近者优先原如此。某业务员最近起始送货点的选择直接关系到费用的多少，所以该业务员在沿途往送货终点站中应尽量把较近点的快件送完，不让下一条路线再把较近点作为
13、起始送货站。2少走重复路原如此。由于在路途相等的条件下，重载费用要比空载费用大得多，因此，尽量让业务员空载行走。3坐标贴近原如此。在同一条路线中，离原点较近送货点的坐标仅次于较远点的坐标。4路线较少原如此。路线多，一方面，相对最远点的选择多，跑的空路多，费用就多；另一方面，过分地强调短暂效益，出动路线多，会引起业务员的反感，不利于以后的人员控制。根据上述分析与根本假设，业务员送货的费用可以表示如下：重载费用：空载费用：根据题意可知，业务员在第i条线路运送与不运送货物，所需时间：所以总约束条件为：（1） 时间约束：（2） 载重量约束:（3） 路线约束：；问题二选货物点的方法类似于问题一，例如：第
14、一条行程中访问了节点0-1-3-4-5-0，是因为1距离原点最近，因此由1出发，3是距离1点最近的点，而且两处快件量之和为14kg，小于每个人最大负重量，可以继续指配。接着，4是距离3最近的点，而且三处快件量之和为19.5kg，仍小于25kg,还可以继续指配。在剩下的未服务送货点中，5距离4最近其实距离4最近的点有2，5，6，7四个点，然后考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但超过25kg上限的点舍去。这里2，7被舍去，应当选择了5总快件量之和为24kg。再继续扩大，发现就会超出“25kg这个上限，因此选择返回，所以0-1-3-4-5就为第一条路线所含有的送货点。并
15、且因为每个点周围的临近点中，之间距离最短，其所需路费就越少。根据路线约束条件3以与坐标知：送货点1、2首先必须作为某路线的最近起始送货点，再结合时间约束条件、载重量约束条件：每次出发不能超过25kg以与上述分析的有关容，依次选出各路线的次近点，并做统筹兼顾，一直到满足约束条件的最大值为止。因此得出八个业务员的行进路线：由此我们得知各业务员的具体路线和所得费用现列表如下：业务员编号过站总数所用时间小时总载重千克总费用元142424344455632573262083合计30由上表可知：（1） 第一条路线和第六条路线可以由一名业务员来完成；（2） 第二条路线和第三条路线可以由一名业务员来完成，所以
16、总共需要6名业务员。即最后确定行走路线为：在以上方案中，本问题得到的总费用最小值为15456.7元。每条路线行走的过程如下：问题3：由于问题将业务员的工作时间延长到8个小时，又因为业务员的工作时间加上休息时间总和不能超过8个小时，所以只需在问题一所建模型与假设的根底上，只需对问题中对时间的约束进展改变即可。、因此，此模型满足路程最短目标函数，建立如下模型：约束条件为：根据题意可知，问题三和问题一的目标函数一样，约束条件只是增加其中工作时间为8小时，不优先考虑费用，即：此问题所建立模型所得行进路线与问题一的行进路线一样，即：每个业务员所工作的具体情况如下表所示：业务员编号过站数所用时间小时总路程
17、千米总载重量千克151002376346845585454635473428328合计30480因为工作时间增为8小时，所以用类似于问题一的方法可进一步优化，但考虑到每个业务员工作时间尽量相差不大，即安排如下：1） 第一个业务员和第八个业务员可以有一个人来完成；2） 第二名业务员和第七名业务员可以有一个人来完成；3） 第三名业务员和第六名业务员可以有一个人来完成；4） 第四名业务员和第五名业务员可以有一个人来完成。每条线路的行进路线为：每个业务员的运行线路如下：业务员编号过站数所用时间小时总载重量千克总路程千米18128261183712249112合计3018454801、模型的优点 1本末
18、性问题三可以充分利用问题一的结论进展路线分析，不用重新建立模型求解。2本模型给出了业务员的调配方案，便于指导工作；3本模型将多目标规划问题转化为单目标0-1规划问题求解，减少了运算量；4本模型在业务员的调配中利用了最有匹配原理，减少了问题的时间复杂度；5本模型的方法和思想对其他类型也适，便于推广到其他领域。2、模型的缺点1本模型问题二没有充分利用问题一的结论进展相关的灵敏度分析，而是重新建立相对稳定的模型求解，因此增加了问题的繁琐程度。2模型给出的约束条件也有不太现实的地方，对街道的方向和客户的快件量的假设也有待进一步改良。参考文献（1）（2） 袁新生、邵大宏、郁时炼编，LINGO和Excel在数学建模中的应用，科学，2007.（3）（4） Lingo教程（5） 全国大学生数学建模比赛03年B题：露天矿开采的优化问题。17 / 17
第16组 B题 快递公司管理系统送货策略
