. . .
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小时的工作时间所需花费的费用在三个方案中进行对比，由此得到依旧是方案三的为最优。
关键字：规划模型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小时，公司的送货策略将有何变化？
二、符号说明
三、模型假设
（1）假设以送货运行路线均为平行于坐标轴的折线而不是直线，类似计算也可同样处理。
（2）运货途中快件没有任何损坏，并且业务员的运送过程也十分安全，没有堵车、天气等问题，即送货过程非常顺利。
（3）每个业务员每天的工作时间不超过6小时，第三问，则不超过8小时。 （4）快件一律用重量单位千克来衡量，平均每天收到总重量为184.5千克的货物，且对体积没有影响。
（5）各个业务员之间的快件运送过程是相互独立的。
四、问题分析
1、问题一、三：
针对问题一，三，使用相同的思路，即只要在分配人员的时间上做修改。 （1）对于时间和重量两个约束条件，我们优先考虑重量；
（2）纵观送货点的分布，将分布点按照矩形、弧形及树的理念三种方案，将重量之和接近25千克的分布点联合起来； （3）区域数=的重量每次出发每人最多能带每天收到的总重量=25
.5
184=7.38，所以至少要有8个区
域；
（4）计算出分割好的区域内业务员完成一次任务的时间之和，最后将满足几个区域的时间之和小于6小时（问题一）或者8小时（问题三）的区域的运送任务分派给同一个业务员。 （5）对于假设一说明如下：
折线距离：已知两点A(1x ,1y )，B(2x ,2y )，距离为横坐标之差的绝对值与纵坐标之差的绝对值，即d(A,B)= |1x -2x |+|1y -2y | 为AB 两点之间的距离，在很多点的情况下，两点间的直线距离也同时可以使用折线距离来表示，折线距离最短也就是直线距离的最短，为了方便计算也使用折线距离来表示本题中的直线距离。
1.1模型建立与求解：
两质点的横纵坐标（,()i i x y ，,()j j x y ）各自的差的绝对值的和等价于两质点之间的距离ij d ，
即两点间距离： ||||ij i j i j d x x y y =-+-
d 都是使用用excel 得到的距离,即a 矩阵（见附录） 一个区域所用时间为：10i i D
t k v
=+⨯ 所用总时间：1030ij d T v
=+⨯
方案一
根据各个送货点的分布，以矩形把整个区域分成5个区域，在区域或区域周围找出送货质量和小于25KG 且距离尽可能小的点的集合，为一个送货区域，由一位业务员负责送货。由此，画出的送货区域为下图1-1：
