《快递公司送货策略__数模论文(17页).doc》由会员分享，可在线阅读，更多相关《快递公司送货策略__数模论文(17页).doc（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-快递公司送货策略_数模论文-第 16 页承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C中选择一项填写）： C 我们的参赛报名号为（如果赛区设置
2、报名号的话）： 所属学院（请填写完整的全名）： 自动化 参赛队员 (打印并签名) ：1. 2. 3. 日期： 2013 年 8 月 23 日评阅编号(教师评阅时填写)：快递公司送货策略摘要： 本文是关于如何优化快递公司送货策略的问题,即在给定送货地点和给定设计规范的条件下，确定所需业务员人数，每个业务员的运行线路，总的运行公里数，以及费用最省的策略。 本文主要从最短路经和费用最省两个角度解决该问题。针对问题一，利用单目标0-1规划模型和最佳匹配的原理，将送货点抽象为顶点，由于街道和坐标轴平行，即任意两顶点之间都有路。在此模型中，将两点之间的距离为这两点横纵坐标差的绝对值之和。比如A（x1，y1
3、），B（x2，y2）两点，则两点之间距离为d=|x2-x1|+|y2-y1|。通过多目标动态规划找出初步路径，再通过lingo软件对各路径进行优化。通过分析，其模型结果为：共需要5名快递员。快递员1： 0-29-28-30-23-15-0；快递员2： 0-8-26-27-0；快递员3： 0-19-24-25-0-1-6-5-2-0；快递员4：0-16-17-18-20-0-3-7-4-0；快递员5：0-9-11-21-22-10-0-12-13-14-0路程为461km，所需总的时间为23.44h。针对问题二,根据题意，建立单目标0-1整数规划的数学模型，然后用类似于问题一的方法，建立满足题意
4、的目标函数以及约束条件，并求得最优结果。最后，对所求解的方案进行修改。所得结果为：快递员1走0-1-3-8-13-0-25-26-0；快递员2走0-2-4-7-14-0；快递员3走：0-6-5-20-18-30；快递员4走：0-10-11-21-23-0；快递员5走：0-16-17-24-28；快递员6走：0-22-29-0；快递员7走：0-9-12-19-0-15-27-0；所走路程为616km,最少费用为13830.7元。针对问题三，在问题二的模型基础上，改变时间的条件约束，因为所需要的总时间不变，而每个业务员的工作时间增加为8小时，所以对其工作量重新进行安排，得到结果为：需要4个快递员，
5、快递员1走：0-6-5-20-18-30-0-15-27-0；快递员2走：0-16-17-24-28-0-25-26；快递员3走：0-10-11-21-23-0-0-22-29-0；快递员4走：0-1-3-8-13-0-2-4-7-14-0-9-12-19-0；最后对论文所建模型进行了评价与推广。关键词：快递公司送货 最优化 分区送货策略模型 TSP模型一、问题重述1.1问题背景：目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太
6、多的业务员意味着更多的派送费用。1.2问题提出：假定所有快件在早上7点钟到达，早上9点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点处（如图2），每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平行于坐标轴的折线。图一送货点快件量T坐标(km)送货点快件量T坐标(km)xyXy1832163.521628.215175.86183654187.5111745.
7、547197.815126308153.419954.5311326.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818（1）请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；（2）如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km
8、/h，酬金2元/km，请为公司设计一个费用最省的策略；（3）如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？图二二、基本假设(1) 假设送货运行路线均为平行于坐标轴的折线(2) 无塞车现象，即业务员送快递途中不受任何外界因素影响，且业务员的休息时间不包括在最大工作时间6个小时内。（3）假设在问题一中若其中一个业务员跑多条路线时，中间返回总部后取快（将快件装上车）所花费的时间不计(4) 在问题一中假设空载时的速度和有货物时的速度是相同的都是（5）每个业务员送快递是独立的，每人之间互不影响。（6）不走冤枉路原则（即送货时只能向上或者向右走）。三、符号说明符号说明单位第j个送货点的所
9、需的快件重量kg业务员携带快件时，按第i条路线派送快件所需时间h业务员不携带快件时，按第i条路线派送快件所需时间h业务员按第i条路线所花费的总时间h业务员送货的总次数四、问题分析问题要求给出快递公司送货的策略，要求我们根据不同情况和要求为快递公司提供合理的送货策略，题中给出了实际送货点的位置和快件重量表，并且抽象到一个平面的二维坐标系中，题中假设送货运行路线均为平行于坐标轴的折线，则我们可以用平行于坐标轴的折线连接两个送货点，它们之间的距离为两坐标差的绝对值.题中还给出了几个已知条件和限制条件：1.每个业务员平均工作时间不超过6小时；2.在每个送货点停留的时间为10分钟；3.途中速度为5.每次
10、出发时带的重量不超过；4.平均每天收到的货物总重量为。送货问题的难点在于当运输能力和送货点一定的情况下，如何选择最优的送货路线，而最优的目标有多个:送货总路程最短,运输时间最短,所需业务员人数最少或运输成本最低。在大多数情况下，由于送货总路程与运输时间正相关 与运输成本负相关。因此，为了便于叙述和推导，我们直接选取送货总路程最短和所需业务员最少作为我们优化送货线路的最终目标由题意可知，平均每天收到总重量为184.5千克，每个人的最大负重是25kg，即,则可知至少需要8条路线对这些邮件进行运送。对于问题一的要求，给该公司提供一个合理的送货策略。其中所谓“合理”，我们可以理解为业务员尽量少，每个业
11、务员的运行路线尽量短，完成任务的时间尽量短。再以这个要求为原则进行方案设计。对于问题二只是业务员的携带快件时的速度与不携带时的不同,并且提到了业务员的酬金并且要求费用最省,其他条件没变,我们可以在解决问题一后利用它得到的结果，对问题二的最优策略进行设计与安排。对于问题三，将前面所限定的每个业务员每天最多工作6小时改成了8小时。这一条件的改变，对送货路径并没有太多影响，只是业务员工作的分配会发生改变，事实上问题三是问题一和二的衍生。 根据实际要求，建立出单目标0-1规划模型，分别针对三个问题列出目标函数和约束条件，然后利用软件进行求解，得出最终结论，并进行相关的模型评价与推广。五、模型的建立与求
12、解5.1问题15.1.1模型的建立本模型考虑用多目标动态规划求解。由于问题一中只要求给出一个合理的方案，且未涉及到业务员工资问题，故只要满足条件业务员的工作时间上限是6个小时以及每条路线的最大载重量不大于25kg即可，本模型中追加两个目标路程最短 和人员最少。可以通过以下两种方法实现：（1）每一个行程的第一个送货点是距离总部最近的未服务的送货点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。（2）每一个行程的第一个送货点是距离总部最远的未服务的送货点。然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。然后比较两组结果，通过函数拟合即可得到最优化结果。5.1.2
13、模型的求解由题意可知，平均每天收到总重量为184.5千克，每个人的最大负重是25kg，即,则可知至少需要8条路线对这些邮件进行运送。可以通过以下两种方法实现：（1）每一个行程的第一个送货点是距离总部最近的未服务的送货点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。（2）每一个行程的第一个送货点是距离总部最远的未服务的送货点确定业务员的送货路线，采取多目标动态规划法，根据送货点的位置和快件的质量，我们进行送货点的划分，划分时遵循以下的准则：1、 两个送货点间距最近；2、 尽量沿这实际道路的方向选取送货点；3、 使区域经过尽量多的点4、 经过的送货点快件的总质量不超过25kg即：
14、目标函数： 约束条件为：方案一：每一个行程的第一个送货点是距离总部最近的未服务的送货点。开始找离原该点最近的点v，且该点的访问标志设为被访问，该点快递重量为w，输出该点。找点v最近的点，快递重量为w1，且w1+w25，当其不成立时找次远点。NY找不到符合条件的点 时找到符合条件的点，且不止一个时选择快递重量最重的那个点，访问标志设为被访问，并输出该点，赋值给v，且w=w+w1；取原点为0 点，离最近的送货点是1点，离1点最近的时3点，离3点最近的4点 ，离 4点最近的是5点，这时我们发现离5点最近的是2点，但根据条件2 点的快件总量为8.2kg，加上1、2、3、4、5点的重量已经超过了25kg
15、。而这时的1，3，4，5 的重量之和为24kg，所以将 1，3，4，5点划分为一个区域 ，同理我们可以按照上面的方法划分区域，可以得到如下的送货路线线路编号送货路线路程（公里）负重站点数时间（小时）线路10-1-3-4-5-0322441.946线路20-2-6-7-13-04424.242.4267线路30-9-8-12-10-04222.942.3467线路40-16-17-20-14-15-23-09023.564.6线路50-11-22-21-19-07424.933.46线路60-27-26-0762223.7067线路70-18-24-25-06824.733.75线路80-29-
16、28-30-09818.334.42总计524184.53026.6561 现在对路线进行优化：由于论文格式问题，举例选取第一条路线，现在0-1-3-4-5这四个送货点之间的最优访问路径安排就是一个典型的单回路问题。可以通过单回路运输模型-TSP模型求解。通过lingo程序（附录2）解决路线的选择。得到第一条路线优化后的路线为0-1-3-4-5-0。 用以上方法可以得到其它的路线（1）013450（2）0 2 13 7 6 0（3）0 10 12 8 9 0（4）0 16 17 20 14 15 23 0（5）0 11 19 2 1 22 0（6）0 27 26 0（7）0 18 24 25
17、0（8）0 29 30 28 0则站点数，所用时间，总载重（kg），总路程（km）如下：线路编号送货路线路程（公里）负重（千克）站点数时间（小时）线路10-1-3-4-5-0322441.9467线路20-2-6-7-13-04324.242.3866线路30-9-8-12-10-04222.942.3467线路40-16-17-20-14-15-23-09023.564.6线路50-11-22-21-19-07224.933.38线路60-27-26-0762223.7067线路70-18-24-25-06824.733.75线路80-29-28-30-09618.334.34总计52218
18、4.53027.4299优化前后的路程和时间的比较如下 ：时间比较 由表共有八条路线，其中线路1和线路6累计时间不足6小时，可选派一名快递员分两次运送。同理，线路2 和3也可以由一名快递员运送。所以整个过程只需要6名快递员。快递员1:线路1，线路6；快递员2:线路2，线路3；快递员3:线路 4 ；快递员4:线路5；快递员5:线路7；快递员6: 线路8；方案二：每一个行程的第一个送货点是距离总部最远的未服务的送货点。分析方法和方案一相似，只不过是从离原点的最远端开始优化前线路编号送货路线路程（公里）负重站点数时间（小时）线路10-30-29-28-23-15-09624.154.673线路20-
19、26-27-8-07524.333.500线路30-24-25-19-0682533.220线路40-18-17-20-16-06421.443.227线路50-21-22-11-10-9-0522554.673线路60-14-13-12-05222.332.580线路70-7-4-3-03418.731.860线路80-5-6-2-1-03423.742.027总计475184.53025.76同方案一，进行优化。优化后的路线：线路编号送货路线路程（公里）负重站点数时间（小时）线路10-29-28-30-23-15-09124.154.473线路20-8-26-27-07624.333.54
20、0线路30-19-24-25-0682533.22线路40-16-17-18-20-05821.442.987线路50-9-11-21-22-10-0542552.993线路60-12-13-14-05222.332.58线路70-3-7-4-03218.731.78线路80-1-6-5-2-03023.741.867总计461184.53023.44优化前后比较：同样共有八条路线，根据所经历的时间进行划分，确定运送人数。在工作时间小于6小时的前提下，最终只需要五名快递员，第三条线路和第八条线路由一人完成 第四条线路和第七条线路由一人完成，第五条线路和第六条线路由一人完成。快递员1：线路1；快
21、递员2：线路2；快递员3：线路3，线路8快递员4：线路4，线路7快递员5：线路5，线路6；通过以上两种方法的比较，考虑时间和路程因素我们可以得出：方案路程（km）时间（h）方案一52227.4299方案二46123.44方法二更优其最优路程为461km，所需的总的时间为23.44h。5.2问题25.2.1模型建立在业务员送货次数为N的情况下，本问题可以转化为利用0-1整数规划对总的费用实施满足条件的最小化；再次，对所建立的单目标模型利用Lingo软件求解，并分析数据，列出每条路线上的时间耗费表；最后，根据上述表中的数据，利用最佳匹配的原理，对业务员的人数安排进行重新调配，得到总行运路程最小情况
22、下，快递公司所需业务员人数最少的策略，此时即为一种合理的方案。类似于问题一的研究方法，可以将本问题的方法分析如下：问题中由于业务员所得的费用是最主要的，业务员安排、路线选择都是为了总费用的最小化提供条件，所以应首先考虑路费，之后再考虑业务员的安排。为了使总能够费用最少，总的思路是先送货给离快递公司最近切块间最重的送货点，以此类推，在保证时间、载重量有限的前提下，沿途把快递送完，最终让业务员最远点空载返回。根据这一思路，全部路线业务员的重载费用可表示为：从上式可以看出，业务员的重载费用是恒定的，又由于总费用为重载与空载费用之和，所以总费用的确定就可以转化为满足一定条件下的各路线的最远点的选择问题
23、。某路线业务员经过的路径选择应遵循以下原则：（1）近者优先原则。某业务员最近起始送货点的选择直接关系到费用的多少，所以该业务员在沿途往送货终点站中应尽量把较近点的快件送完，不让下一条路线再把较近点作为起始送货站。（2）不走冤枉路原则（即只能向上或者向右走）。一方面，离原点（快递公司）较远的送货点坐标应分别大于离原点较近送货点的坐标，在各个坐标上均不走回头路，即按图（a）中的路线前进，而不按路线前进：另一方面，由于在路途相等的条件下，重载费用要比空载费用大得多，因此，尽量让业务员空载行走（3）坐标贴近原则。在同一条路线中，离原点较近送货点的坐标仅次于较远点的坐标。四是，路线较少原则。路线多，一方
24、面，相对最远点的选择多，跑的空路多，费用就多；另一方面，过分地强调短暂效益，出动路线多，会引起业务员的反感，不利于以后的人员控制。根据上述分析及基本假设，业务员送货的费用可以表示如下：业务员携带快件时公司应付费用为：由于业务员不携带快件时的速度是30千米/小时，酬金2元/千米，因此，业务员不携带快件时，公司应付费用为：根据题意，业务员携带与不携带快件时，按第i条路线派送快件所需时间分别为因此，本问题的时间约束可以列为 根据上述分析及基本假设，本问题的模型可表示为目标函数：约束条件： 根据模型，通过C+编程（程序见附录）可得结果如下表：线路编号送货线路时间（小时）路程（公里）费用负重（千克）10
25、-1-3-8-13-02.4166742792.922.120-2-4-7-14-02.544969.524.730-6-5-20-18-30-04.66667921852.423.840-9-12-19-02.75541498.221.950-10-11-21-23-03.66667721352.419.260-16-17-24-28-04.33333882261.822.970-22-29-03.75821506.714.980-15-27-03.16667681577.615.490-25-26-03.41667742019.219.661613830.7线路1和线路9累计时间不足6小时
26、，可选派一名快递员分两次运送。同理，线路4 和8也可以由一名快递员运送。所以整个过程只需要7名快递员。快递员1: 线路1，线路9，快递员2:线路2；快递员3:线路 3 ；快递员4:线路5；快递员5:线路6；快递员6: 线路7；快递员7，线路4，85.3问题3模型及其求解由于问题三为问题一和问题二的衍生，所以该模型在问题二的基础上重新考虑时间这个约束条件。因此由问题二的模型即可求得问题三的结果。该模型条件为: 通过C+语言编程（程序见附录）可得结果如下表： 路线时间路程 费用线路10-1-3-8-13-02.41642792.9线路20-2-4-7-14-02.544969.5线路30-6-5-
27、20-18-30-04.66667921852.4线路40-9-12-19-02.75541498.2线路50-10-11-21-23-03.66667721352.4线路60-16-17-24-28-04.33333882261.8线路70-22-29-03.75821506.7线路80-15-27-03.16667681577.6线路90-25-26-03.41667742019.2由表共有九条路线，其中线路3和线路8累计时间不足8小时，可选派一名快递员分两次运送。同理，线路6 和9也可以由一名快递员运送，线路5和线路7选一名快递员，线路1和线路4、线路2派一名快递员。所以整个过程只需要4
28、名快递员。每个快递员负责的路线分别为：快递员1: 线路3，线路8，快递员2:线路6、线路9；快递员3:线路5、线路7 ；快递员4:线路1、线路2、线路4。六、 模型的评价与推广6.1模型的优点（1）模型系统的给出了业务员的调配方案，便于指导工作实践。（2）模型简单明了，容易理解与灵活应用。（3）模型的方法和思想对其他类型也适合，比如灾情考察、邮局递送、车辆运输等，易于推广到其他领域。（4）本模型方便、直观，易于在计算机上实现和推广。比如灾情考察、邮局递送、6.2模型的缺点（1）模型给出的约束条件可能也有不太现实的。（2）对街道的方向，客户的快件量的假设有待进一步改进。6.3模型的推广（1）本模
29、型不但适合于快递公司送货问题，还是用于一般的送货以及运输题，只需要稍微改动模型即可。（2）模型方便、直观，可以实现计算机模拟。（3）建模的方法和思想可以推广到其他类型，如车辆调度问题等。七、参考文献1姜启源，谢金星数学模 型 .北京:高等教育出版社 2003.2唐焕文，贺明峰编，数学模型引论-3版，北京，高等教育出版社，2005.3 .3快递公司送货策略, 2013.8.16.八、附录附录1：各送货点之间的距离（含原点）附录2：问题1路线优化:model:sets:city / 1. 5/: u; link( city, city): dist, ! 距离矩阵; x;endsets n = s
30、ize( city);data: !距离矩阵，它并不需要是对称的; dist=0 70 115 90 95 70 0 46 21 50 115 46 0 30 32 90 21 30 0 48 95 50 32 48 0;enddata !目标函数; min = sum( link: dist * x); FOR( city( K): !进入城市K; sum( city( I)| I #ne# K: x( I, K) = 1; !离开城市K; sum( city( J)| J #ne# K: x( K, J) = 1; !保证不出现子圈; for(city(I)|I #gt# 1: for(
31、city( J)| J#gt#1 #and# I #ne# J: u(I)-u(J)+n*x(I,J)=n-1); !限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解;for(city(I) | I #gt# 1: u(I)=n-2 ); !定义X为01变量; for( link: bin( x);End附录3：问题2，3路线求解：#include#include#include#define M 1000using namespace std;struct nodeint x;int y;int num;float weight;node v31;int mindis3
32、1;bool vd31;void create(ifstream &in,int n)int i;for(i=0;ivi.numvi.xvi.yvi.weight; coutvi.num(vi.x,vi.y) vi.weightt;int d(node a,node b)return (abs(a.x-b.x)+abs(a.y-b.y);void dis()int i,j;for(i=0;i31;i+)coutvi.num到各点的距离：n;for(j=0;j31;j+) coutd(vi,vj) ;coutendlendl;int next1()int k,min=M,tag=0;float
33、w;for(int i=1;i31;i+)if(vdi=false&d(v0,vi)w) k=i; w=vi.weight;tag=1; if(tag) return k;else return 0;int next2(int k,float w)int min=M,tag=0,m,i; for(i=1;i31;i+)if(vdi=false&d(vk,vi)min&w+vi.weightvk.x&vi.yvk.y) min=d(vk,vi); m=i; tag=1; if(vdi=false&d(vk,vi)=min&w+vi.weightvm.weight&vi.xvk.x&vi.yvk.
34、y)m=i;tag=1;if(tag) return m;else return 0;void way()int k;float w;k=next1(); while(k!=0)float time,money;int num_of_station=0,distance,tag; vdk=true;w=vk.weight;distance=vk.x+vk.y;money=3.0*w*distance;time=(vk.x+vk.y)/20.0;cout0vk.num;tag=next2(k,w);while(tag!=0)num_of_station+;vdtag=true;coutvtag.
35、num;w=w+vtag.weight;time=time+(d(vk,vtag)/20.0;if(time+(vtag.x+vtag.y)/20.0+(num_of_station+1)/6.0=8)distance=distance+d(vk,vtag);money=money+3.0*distance*vtag.weight;k=tag;tag=next2(tag,w);else time=time-(fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y)/20.0;break;time=time+(vk.x+vk.y)/30.0+(num_of_station+1)/6
36、.0;distance=distance+vk.x+vk.y;money=money+(vk.x+vk.y)*2.0;cout0 time distancekm money wendl;k=next1();int main()ifstream infile(C:UsersAdministratorDesktop1.txt);create(infile,31);coutendlendl;way();system(PAUSE);return 0;附录4：问题2，3所应用的文档1.txt0 0 0 0 1 3 2 82 1 5 8.23 5 4 6 4 4 7 5.5 5 3 11 4.5 6 0 8 3 7 7 9 7.28 9 6 2.3 9 10 2 1.4 10 14 0 6.511 17 3 4.112 14 6 12.713 12 9 5.814 10 12 3.815 19 9 3.416 2 16 3.517 6 18 5.8 18 11 17 7.519 15 12 7.820 7 14 4.621 22 5 6.222 21 0 6.823 27 9 2.424 15 19 7.625 15 14 9.626 20 17 1027 21 13 1228 24 20 629 25 16 8.1 30 28 18 4.2