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

页脚内容2012年第九届苏北数学建模联赛承诺书我们仔细阅读了第九届苏北数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其它公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们的参赛报名号为：2394参赛组别（研究生或本科或专科）：本科组参赛队员(签名)：队员1：鞠珊队员2：夏逸凡队员3：胡思想获奖证书邮寄地址：徐州工程学院数理学院教2--5132012年第九届苏北数学建模联赛页脚内容编号专用页参赛队伍的参赛号码：（请各个参赛队提前填写好）：竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：页脚内容题目快递公司送货策略摘要本文针对快递公司送货策略的优化问题进行研究，重点放在给该快递公司提供一个合理的送货策略；在一些特殊条件的限制下，给该公司提供一个费用最省的送货策略。对于问题一，我们通过运送总距离最短目标函数首先建立了模型——0-1整数线性规划模型。在给定送货地点和给定送货量和送货时间的约束条件下，结合最近插入法和最佳匹配的原理，将送货点抽象为一个点（顶点），由于街道和坐标轴平行，即任意两顶点之间都有路，且任意两点间的距离为这两点横纵坐标差的绝对值之和。如2211,,,yxByxA两点，则权值为1212yyxxD。在此基础上,运用矩形，将整个区域分成5个区域，以选择的点的送货质量之和小于25kg且距离尽可能小的点的集合作为一个区域。依次来分配业务员的送货地点。通过我们的计算，在不考虑时间的情况下，我们求得一个人完成任务的运送路线为8条，由于工作时间的限制，求出了完成任务所需的最少业务员为5人，最短总路程为km365。对于问题二，我们借助于问题一求解出来的路线，运用图论中最小生成树的原理，以费用最省为目标函数建立数学模型。通过TSP模型在满足约束条件的前提下求出最短距离，再对所求解方案进行优化修改，从而我们求得问题二的最省费用为7.13586。关键词0-1整体线性规划最近插入法最小生成树TSP模型excel一、问题重述页脚内容1.1背景分析目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。1.2问题重述假定所有快件在早上7点钟到达，早上9点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点处（如图2），每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平行于坐标轴的折线。问题1：请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；问题2：如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略。送货点快件量T(kg)坐标(km)送货点快件量T(kg)坐标(km)xyxy1832163.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页脚内容点的分布如下图：3,21,55,44,70,83,117,99,610,214,017,314,612,910,1219,92,166,1811,1715,127,1422,521,027,915,1915,1420,1721,1324,2025,1628,180510152025051015202530坐标轴标题坐标轴标题3154037910141714121019261115722212715二、问题分析2.1对于问题一的分析问题一，我们以运送总距离最短为目标函数建立0—1规划数学模型。对于本问题，有时间和重量两个约束条件，我们优先考虑重量。区域数的重量每次出发每人最多能带每天收到的总重量25.518438.7，所以至少要有8个区域。表中数据的分析最大载重量kg25重驶时速hkm/20地中的平均速度hkm/25重驶酬金hkm*/3元业务员工作时间上限h6空驶时速hkm/30每个送货点停留时间min10空驶酬金km/2元备注1.快件一律用重量来衡量2.假定街道方向平行于坐标轴然而，从题目中我们很明显的能够得知一个业务员要运送很多次，而运送每次的路线即是我们所要确立的对于完成该任务运送路线。由于每个业务员的工作量有时间限制，于是我们又将时间考页脚内容虑在内，此时就需要增加业务员去完成任务，在此条件下所需的业务员就是完成该任务所需的最少业务员。对于运送路线的确定，我们主要分两步进行，一是每条路线上的目的地，二是经过这些目的地的先后顺序。对于每条路线上的目的地的确定，我们根据实际情况的需要，定义了最近插入法——在满足约束条件的前提下，在一次运送过程中，下一目标点的确定要离上一目标点最近。经过我们的分析，我们分别考虑了从最近点和最远点出发的送货路线，经过我们的求解比较可知，从最近点出发的送货路线较优，于是我们选择了从最近点出发的送货路线。在此方法下我们通过MATLAB编程，找出了每条路线所经过的目的地。对于经过每条路线中目的地的先后顺序，我们采用了TSP算法，借助于计算机辅助计算，通过MATLAB编程找出了经过它们的最短路，也就是经过他们的先后顺序，使业务员用最少的时间完成一次运送，为下一次的运送节约了时间，可是业务员的工作时间最大化，从而只需较少的业务员即可完成任务。2.2问题二的分析问题二，业务员的速度改变，分成携带快件和不携带两种情况下的具有不同的速度，分别为20km/h,30km/h,且业务员的薪酬与其工作过程中的行走的总路程有关。我们借助于第一问求解出送货路线的基础上，以运费最省为目标函数建立数学模型。由于问题一我们运送路线的安排都是最短的，而问题二只是对于速度这一约束条件进行了改变，运行的路线是没有变化的，所以我们根据时间要求，在问题一的基础上，对业务员的送货路线进行了调整。经过我们的分析，以费用最省建立目标函数，建立动态规划数学模型，每人工作时间不超过6小时且每次出发最多只带25千克的重量，列出目标函数和约束条件，来找出每条路线的送货点。三、模型假设结合本题的实际，为了确保模型求解的准确性和合理性，我们排除了一些位置因素的干扰，提出以下几点假设：1、每个业务员每天的工作时间不超过6个小时，且送完货后必须再回公司报到。2、假设以送货运行路线均为平行于坐标轴的折线而不是直线。3、运货途中快件没有任何损坏，并且业务员的运送过程也十分安全，没有堵车、天气等问题，即送货过程非常顺利。4、如果离某一点最近的点不止一个，这时我们要从快件的量出发，选取加上此快件量最接近25千克而不能超过25千克的目的地。5、各个业务员之间的快件运送过程是相互独立的，互不影响。6、假设每个人的路线一旦确定，再不更改。四、符号说明为了便于问题的求解，我们给出以下符号说明：符号说明yx,两质点的横纵坐标ik一个区域经过的地方数1,2,...,ii页脚内容it一个区域所用的时间（min）1,2,...,iiT总的所用的工作时间（min）ijd两质点之间的距离ijdD总的路程（km）v业务员每天送货的平均速度v=2560（km/min）ija1在第i条路线上业务员向第j个送货点送快件0在第i条路线上业务员不向第j个送货点送快件ijs1第i条路线上选择第j个送货点是最远点0第i条路线上选择第j个送货点不是最远点yxjj,第j个送货点坐标jm第j个送货点所需快件重量五、模型的建立与求解经过以上的分析和准备，我们将逐步建立以下数学模型，进一步阐述模型的实际建立过程。5.1问题一的模型建立与求解问题一我们分两步来完成，首先将30个点进行分组，使每组总的邮件数之和尽量接近25kg，即一个邮递员的最大载重量。分组时我们采用先找两个可行解，然后将两可行解比较拟合得到最优解的方法。其次，确立组数之后求每组最优路线，通过计算时间，将邮递员分到相应的组内。5.1.1模型一的建立与求解两质点的横纵坐标（,()iixy，,()jjxy）各自的差的绝对值的和等价于两质点之间的距离ijd，即两点间距离：||||ijijijdxxyyd都是使用用excel得到的距离,即a矩阵（见附录）一个区域所用时间为：10iiDtkv所用总时间：1030ijdTv根据各个送货点的分布，以矩形把整个区域分成5个区域，在区域或区域周围找出送货质量和小于25KG且距离尽可能小的点的集合，为一个送货区域，由一位业务员负责送货。由此，画出送货区域成折线距离的如下图：页脚内容将质量大的进行分组，在不超过25KG的同时将前面质量小的分摊给后面质量大的，将其不足25KG的部分补足。形成8条路线。行进次序送货路线130-20-11-5-4228-17-13-9-338-6-22-21-10423-24-18-7529-19-1615-12-2726-25816-14-27业务员的送货路线、送货区域、送货的路程及时间（通过excel可得）行进次序送货路线问题一路程（km）时间（min）130-20-11-5-470168228-17-13-9-358139.238-6-22-21-104198.4423-24-18-756134.4529-19-13379.2615-12-22867.2726-253788.8816-14-2742100.8总计36587628,1825,1624,2021,1320,1715,1415,1927,921,022,57,1415,1211,176,182,1619,910,1212,914,617,314,010,29,67,93,110,84,75,41,53,20510152025051015202530坐标轴标题坐标轴标题3154037910141714121019261115722212715页脚内容4,73,1117,37,1428,18051015200102030坐标轴标题坐标轴标题4317728491820205101520250102030坐标轴标题坐标轴标题系列1图表标题9,60,814,022,521,005100102030坐标轴标题坐标轴标题90142221图表标题27,97,911,1715,19010200102030坐标轴标题坐标轴标题2771115图表标题3,215,1225,1605101520010203031525图表标题19,91,514,605100102019114图表标题2,1610,1221,130510152002040坐标轴标题坐标轴标题210215.1.2模型二的建立与求解考虑一个目标：总运行公里数最短。可以用以下方法：先假设每条线路由不同的业务员来完成，即需要8名业务员来完成运送快递；然后在人数不变的情况下，本题先从最远点开始出发，依次查找临近点，并考虑总重量小于25kg，以此来划分区