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

B题快递公司送货策略摘要本文主要解决快递公司送货策略问题，研究在各种运货地点，重量的确定，业务员的运输条件和工作时间等各种约束条件下，设计最优的路线，得出最优送货策略。主要研究如下三个问题。问题一：首先考虑在时间和重量两个约束条件之下，优先考虑重量，通过对送货点的分布进行分析，将分布点按照矩形，弧形和树的理念将问题分成三种模块，从而建立三种送货方案。方案一，运用矩形，将整个区域分成5个区域，以选择的点的送货质量之和小于25kg且距离尽可能小的点的集合作为一个区域。依次来分配业务员的送货地点。方案二，运用弧形，以原点为圆心画同心圆，按照就近原则确定送货区域，依次分配业务员的送货地点。方案三，运用Dijkstra算法计算出每一个顶点到其它点的距离。分析点的分布，由此得到最小树，在最小树的基础上，向四周延伸，得到相应区域。且以送货质量小于25kg且距离尽可能小的点的集合作为一个区域。依次来分配业务员的送货地点。其次，再综合这三种方案所涉及到得时间，路程依次进行对比，画出柱形图，清晰可得出最优的方案为方案三。问题二，是解决送货总费用最小的问题。因此要求业务员的运行路线要尽量短，且尽早卸货。首先将该区域安排送货点均匀度分为三个小区域，以每个点的信件质量从小到大排列，以送货点最大点为中心，选择该点附近质量较大且距离较短原则的下一个送货点，依次类推，直到根据约束条件为每次携带的快件量不超过25kg，找到该条路线最后一个送货点。按此方法可得路线为01012110，0714270，0126280，01319250，0251617→0，0221529→30→0，062018→24→0，0438→9→21→23→0，并且利用C语言编程（见附录），算得每条路线的费用，所得总费用为14636.1元。问题三，在问题一的基础上，将业务员的工作时间延长到8小时，由此在问题一的基础上，将8小时的工作时间所需花费的费用在三个方案中进行对比，由此得到依旧是方案三的为最优。1关键字：规划模型Floyd算法最小生成树MATLAB一、问题重述：目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。假定所有快件在早上7点钟到达，早上9点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点处（如图2），每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平行于坐标轴的折线。（1）请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；（2）如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略；（3）如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？送货点快件量T(kg)坐标(km)送货点快件量T(kg)坐标(km)xyxy1832163.521628.215175.86183654187.5111745.547197.815126308153.419954.5311216.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.11732610201721212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818二、符号说明符号描述（x,y）两质点的横纵坐标KQ一次送货的最大负荷量（kg），其中1,2,...,kKit一个区域所用的时间（min）1,2,...,iiT总的所用的工作时间（min）ik一个区域经过的地方数1,2,...,iiL送货点总数iq每个送货点的快件量（kg），1,2,...,iLijd两质点之间的距离ijd0jd配送中心到送货点的运距（km）D总的路程（km）kn第k名业务员配送的送货点数，0kn表示未配送第k名业务员kR是一个集合，表示第k条路线kir表示送货点kir在路线k中的顺序为i（不包括配送中心），00kr表示配送中心v业务员每天送货的平均速度v=2560（km/min）ijb送货点i与j之间的快件密集度F快递公司一天的总费用（元）3三、模型假设（1）假设以送货运行路线均为平行于坐标轴的折线而不是直线，类似计算也可同样处理。（2）运货途中快件没有任何损坏，并且业务员的运送过程也十分安全，没有堵车、天气等问题，即送货过程非常顺利。（3）每个业务员每天的工作时间不超过6小时，第三问，则不超过8小时。（4）快件一律用重量单位千克来衡量，平均每天收到总重量为184.5千克的货物，且对体积没有影响。（5）各个业务员之间的快件运送过程是相互独立的。四、问题分析1、问题一、三：针对问题一，三，使用相同的思路，即只要在分配人员的时间上做修改。（1）对于时间和重量两个约束条件，我们优先考虑重量；（2）纵观送货点的分布，将分布点按照矩形、弧形及树的理念三种方案，将重量之和接近25千克的分布点联合起来；（3）区域数=的重量每次出发每人最多能带每天收到的总重量=25.5184=7.38，所以至少要有8个区域；（4）计算出分割好的区域内业务员完成一次任务的时间之和，最后将满足几个区域的时间之和小于6小时（问题一）或者8小时（问题三）的区域的运送任务分派给同一个业务员。（5）对于假设一说明如下：折线距离：已知两点A(1x,1y)，B(2x,2y)，距离为横坐标之差的绝对值与纵坐标之差的绝对值，即d(A,B)=|1x-2x|+|1y-2y|为AB两点之间的距离，在很多点的情况下，两点间的直线距离也同时可以使用折线距离来表示，折线距离最短也就是直线距离的最短，为了方便计算也使用折线距离来表示本题中的直线距离。41.1模型建立与求解：两质点的横纵坐标（,()iixy，,()jjxy）各自的差的绝对值的和等价于两质点之间的距离ijd，即两点间距离：||||ijijijdxxyyd都是使用用excel得到的距离,即a矩阵（见附录）一个区域所用时间为：10iiDtkv所用总时间：1030ijdTv方案一根据各个送货点的分布，以矩形把整个区域分成5个区域，在区域或区域周围找出送货质量和小于25KG且距离尽可能小的点的集合，为一个送货区域，由一位业务员负责送货。由此，画出的送货区域为下图1-1：5图1-160510152025051015202530然后连成折线距离的如下图1-2图1-2业务员的送货路线、送货区域、送货的路程及时间（通过excel可得）、如下表1-3：送货线路行进次序问题一业务员分配路程（km）时间（min）6小时8小时10-1-3-9-10-036126.4①①20-2-4-6-16-5-046146②②30-7-20-17-14-8-058191.6②①40-12-13-15-23-076227.2①③50-19-27-30-092250.8④③60-25-24-18-068169.2③④70-26-29-28-092246⑤④80-22-21-11-054159.6③②总计5221516.85个4个表1-37方案二以原点为圆心画同心圆，以一个圆内或圆周周围的点为一片，找出送货质量和小于25KG且距离尽可能小的点的集合，为一个送货区域，由一位业务员负责送货。由此，画出的送货区域为下图1-4：图1-48连成折线距离的图1-5如下图1-5则业务员的送货路线、送货区域、送货的路程及时间（通过excel可得）如下表1-6：送货线路行进次序问题一业务员分配路程（km）时间（min）6小时8小时10-1-3-2-02078①①20-6-5-4-7-8-9-034141.6②②30-12-10-11-052154.8③②40-16-17-20-14-13-060194③①50-19-25-18-064183.6②①60-27-21-22-070198④③70-15-29-30-23-094265.6①④80-24-26-28-092250.8⑤③总计4861466.45个4个05101520250510152025309表1-6方案三计算赋权图中各对顶点之间最短路径，显然可以调用Floyd算法。具体方法是：每次以不同的顶点作为起点，用Floyd算法求出从该起点到其余顶点的最短路径，反复执行n−1次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为O(3n)。第二种解决这一问题的方法是由FloydRW提出的算法，称之为Floyd算法。假设图G权的邻接矩阵为oA1112121222012nnnnnnaaaaaaAaaa其中iijijjvvaijvv权值，当之间有边时，，当之间无边时，0,1,2,.iiain对于无向图，oA是对称矩阵，ijjiaa。Floyd算法的基本思想是：递推产生一个矩阵序列1,,,,,knAAA其中矩阵kA的第i行第j列元素(,)kAij表示从顶点iv到顶点jv的路径上所经过的顶点序号不大于k的最短路径长度。计算时用迭代公式：111,min(,),(,)(,)kkkkAijAijAikAkj，10k是迭代次数，,,1,2,ijkn。最后，当k=n时，nA即是各顶点之间的最短通路值。许多应用问题都是求最小生成树问题。就像此模型中需要求解最小费用问题，该费用涉及到路程和载重量，所以如何设计优化的路程是相当重要的。因此运用最小生成树中的Floyd算法以此算出路线。以找出所有点所形成的图中找距离最小的最小树，并在最小数的基础上，向周围延伸，找出送货质量和小于25KG且距离尽可能小的点的集合，为一个送货区域，由一位业务员负责送货。最小树是由MATLAB计算得到的，可以保证是最小树。通过MATLAB得出的最小树b矩阵(见附录)，转换为图像连接在一起为转化成直角坐标系中的最小树为如图1-7：图1-711在此最小树的基础上划出的送货区域为如图1-8：0510152025051015202530图1-8则业务员的送货路线、送货区域、送货的路程及时间（通过excel可得）如下表1-9：送货线路行进次序问题一业务员分配路程（km）时间（min）6小时8小时10-1-3-4-8-034121.6①①20-2-6-5-7-038131.2②①30-10-22-21-11-9-054179.6③①40-12-13-14-052154.8③②50-20-18-17-16-058179.2②②60-19-25-24-068193.2①③70-26-28-30-23-096270.4④③80-15-27-29-082226.8⑤④总计4821456.85个4个12表1-9模型检验如表1-10：方案总路程总时间业务员人数理论上最少人数6小时8小时6小时8小时一5221516.85人4人4.2133.16二4861466.45人4人4.1673.125三4821456.85人4人4.0133.01表1-10通过用条形图进行各个方案进行比较得到如表1-11问题一中三种方案的时间路程比较02004006008001000120014001600123方案一二三方案一方案三方案二方案一方案三方案二表1-11实验结果的对比发现，用最小树理论解出来的比按几何方法划区域的解更优。对比发现，当总路程最小时，往往会使总费用最小。最终的答案为：（1）需要5个业务员，总的