快递公司送货策略

快递公司送货策略摘要本文通过建立基于坐标变换的动态规划模型(模型一)，基于蚁群算法的TSP模型(模型二)及状态空间规划模型(模型三)对送货策略相关问题进行了探讨。

问题一模型一:考虑到送货点和所需快件量分布的无规则性，以及时间和送货量的限制，本文采用了循环平面坐标变换的方法计算路径，即从总部派遣一个人，到依照某种规则选取的一未配送的送货点，再将该人分配到距离该点最近的点，并使之满足限制条件. 继续上述指派，直到不满足限制条件，业务员返回总部并记录得到的可行路线。

对其他业务员重复上述安排，直到没有未服务的送货点。

计算得到该算法下的最佳送货策略:公司需派五个业务员，总耗时25.2333h，总路程为510km。

模型二:由于模型一的结果中每次巡回路径上的点的组合问题类似TSP问题，因而本文对这些点通过基于蚁群算法的TSP求解方法进行优化，优化解为:公司需派五个业务员，总路程为502km。

问题二:模型三:由于在时间与快件量约束下，改变后的速度的平均值接近于问题一的速度值，所以本问利用第一问得到的每条路径上的点，通过空间状态规划法得到图搜索树，借助于计算机的高速运算与逻辑判断能力,计算出一个费用最省的结果即需要9次巡回，公司需派5人，总费用为13525元。

本文的优点在于将一个复杂近似问题多角度思维，不断优化解题方法，综合运用搜索，TSP，蚁群算法，状态规划等方法，将问题简单化，可操作性强，适用范围广。

关键词: 送货策略坐标变换蚁群算法图搜索树状态空间规划1一问题的重述目前，快递行业正蓬勃发展，为我们的生活带来更多方便。

一般地，所有快件到达某地后，集中存放在总部，然后由业务员分别进行派送:对于快递公司，为了保证快件能够在制定指定的时间内送达目的地，必须有足够的业务员进行送货。

但是，太多的业务员意味着更多的派送费用。

因而在快递公司送货策略中，确定业务员人数和各自的行走路线是策略好坏的关键。

这个问题可以描述为:一中心仓库(或配送调度中心)拥有最大负重为25kg的业务员m人, 负责对30个客户进行货物分送工作, 客户()的i1,i,30货物需求为已知,求满足需求的路程最短的人员行驶路径,且使用尽量少的人数,并满足以下条件:1) 每条配送路径上各个客户的需求量之和不超过个人最大负重。

3)每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h。

问题要求解决以下问题:1 应用有关数学建模知识，给该公司提供下一个合理的送货策略(需要多少业务员，每个业务员的运行线路和总的运行公里数)。

2 如果业务员负重时的速度是20km/h，酬金是3元/km*kg，而不携带快件时的速度是30km/h，酬金是2元/km，为公司设计下一个费用最省的策略。

二模型假设1)本研究中对人的最大行程不加限制。

2)每个客户的需求必须满足,且只能由一个人送货。

3)假设每个人的送货路线一旦确定，不再更改。

4)送货期间，每个业务员相互之间互不影响。

2三符号说明符号中文说明第L个业务员第一次经过所有送货点所需时间 tiS 未配送的送货点的集合,信息素挥发系数本次循环中路径(i，j)上信息素的增量 ,,(t)ijk第k只蚂蚁在本次循环中留在路径(i j)上的信息素量 ,,(t)ijQ 信息素增加强度系数,表示轨迹的相对重要性的信息启发式因子表示能见度的相对重要性的期望启发式因子 ,启发函数 ,(t) ikD 相邻2个城市之间的距离 ijkP(t) 在t时刻蚂蚁k由元素(城市)i转移到元素(城市)j的状态ij 转移概率tabu (k=l,2,?,m) 记录蚂蚁k当前所走过的城市 klmin集合c中2个最近元素(城市)之间的距离3四. 模型的建立与求解1.问题一1.1 模型一:基于坐标变换的动态规划模型1.1.1、模型分析:本问题是快递公司分配若干个业务员到需求不同快件量的送货点，求业务员个数最小，路程最短的动态规划问题。

我们把所需要的若干个业务员看作为问题的决策者，且在不同的路径上执行相同的决策。

我们根据生活经验以及得到的不同的路径的结果比较来确定业务员最终的人数。

由于业务员路径选取的决策不同，对应整个过程就可以有一种不同的策略(当对送货过程采取某一策略时，可以得到一个确定的(或期望的)效果，采取不同的策略，就会得到不同的结果(多阶段的动态规划问题，就是要在所有可能采取的策略中间选取一个最优的策略，使在预定的标准下得到最好的效果。

所以，当我们确定某一个送货点后，若该送货过程继续，业务员则会选取距该已送货点距离最近的送货点送货。

考虑到送货点和所需快件量分布的无规则性，以及本题对时间和送货量的限制，我们采用了平面坐标变换的方法，循环把选用的送货点滤除再重复选点的方式计算路径。

又因送货量每个业务员最大负重量25kg的限制和最近的送货点可能有多个的情况，我们可以把距已送货点距离相同且最近的点做三种情况下的处理: 一，选取最近的点中所需快件量最小的点为下一个送货点。

二，选取满足负重量不超过25kg的最大快件量的点为下一个送货点。

三，选取最近的点中所需快件量最大的点为下一个送货点，若总负重量超过25kg则业务员跳过该点直接返回公司。

1.1.2、模型建立:设S为没有送货的点的集合，显然尚未送货时，S={(x,y,T)，(x,y,T)，…，111222(x,y,T)}，n为第L个业务员一次所经过的点集。

设第L个业务员第一次到达第i个送货303030i点(xi,yi,Ti)，其中Ti为第i个送货点所需的快件的重量，所用时间t=(xi+yi)/25同时验证约i束条件:niT,,25 …………………… (1) ,i,1k41xiyi，++<=6………… (2) ti625若不满足两个约束条件的任何一个，则业务员返回到公司，若满足则:坐标进行平移转换: x?=x-x yy?=y-yi i得到新的坐标点系列此时S={(x?,y?,T),(x?,y?,T),(x-1?,y-1?,T-1),(x+1?,y+1?,T+1)，…(x?,y?,T)} 111222iiiiii303030它包含有29个点，此时，则需要利用计算机算出距离(x?,y?,T)最近的点，然iii后根据上述中最所得最近的点根据情况进行不同的处理，以决定要选取的送货点。

经过上过程，业务员所在的送货点已“回到”原点，重复上述过程，知道集合S变为空集，即送货点已全部被送货，停止。

由业务员在每条路径上花费的总时间可知，一个业务员可以送多次快件，最终得到较合理的送货策略即业务员的人数，每个业务员运行的线路以及总的运行公里数。

1.1.3，模型求解:首先，由于题目中给出的送货点的排序无序，为计算描述方便起见，我们将所给送回点的顺序进行了重新编号如下图:送货点快件量T 坐标(km) 送货点快件量T 坐标X Y X Y1 8 32 16 3.5 2 162 8.2 1 5 17 5.8 6 183 6 54 18 7.5 11 174 5.5 4 7 19 7.8 15 125 3 0 8 20 3.4 19 96 4.5 3 11 21 6.2 22 57 7.2 7 9 22 6.8 21 08 2.3 9 6 23 2.4 27 99 1.4 10 2 24 7.6 15 1910 6.5 14 0 25 9.6 15 1411 4.1 17 3 26 10 20 1712 12.7 14 6 27 12 21 1313 5.8 12 9 28 6.0 24 2014 3.8 10 12 29 8.1 25 1615 4.6 7 14 30 4.2 28 185经过计算机求解，程序见附录，我们得到对最近的点在三种情况下的路径，相应的时间及业务员数，具体如下:(一)选取最近的点中所需快件量最小的点为下一个送货点公司需派出5个业务员，其各个路径及时间如下:第一个业务员:0—1—3—4—5—0，0—2—6—16—17—0，0—9—8—0花费的时间为5.9867h,该业务员的路程为108km 第二个业务员: 0—10—11—12—0，0—7—15—14—13—0，花费的时间为5.0867h,该业务员的路程为98km 第三个业务员:0—22—21—20—0，0—19—25—0，花费的时间为5.6333h,该业务员的路程为120km 第四个业务员:0—18—24—0，0—27—0花费的时间为5.94h,该业务员的路程为136km 第五个业务员:0—23—29—30—28—0花费的时间为4.6667h,该业务员的路程为100km 该情况下的总路程为562km(二)选取满足负重量不超过25kg的最大快件量的点为下一个送货点公司需派出5个业务员，其各个路径及时间如下:第一个业务员:0—1—3—4—6—0，0—2—5—7—13—0，0—9—8—0花费的时间为5.9861h，该业务员的路程为108km 第二个业务员:0—10—12—11—0，0—16—17—15—14—0花费的时间为5.2467h，该业务员的路程为92km 第三个业务员:0—22—21—20—0，0—19—25—0花费的时间为5.6333h，该业务员的路程为120km 第四个业务员:0—18—24—0，0—27—0花费的时间为5.9400h，该业务员的路程为136km 第五个业务员:0—27—29—28—30—0花费的时间为4.7467h，该业务员的路程为102km 该情况下的总路程为568km6(三)选取最近的点中所需快件量最大的点为下一个送货点，若总负重量超过25kg则业务员跳过该点直接返回公司公司需派出5个业务员，其各个路径及时间如下:第一个业务员:0—1—3—4—0，0—2—5—6—7—0，0—9—8—12—0花费的时间为5.8267h，该业务员的路程为104km 第二个业务员:0—10—11—21—22—0，0—16—17—15—14—0花费的时间为5.7333h，该业务员的路程为110km 第三个业务员:0—13—19—25—0，0—18—24—0花费的时间为5.8733h，该业务员的路程为126km 第四个业务员:0—20—27—0花费的时间为3.0533h，该业务员的路程为68km 第五个业务员:0—23—29—28—30—0花费的时间为4.7467h，该业务员的路程为102km 该情况下的总路程为510km 另外，我们把每次巡回路径的第一个点设为最远的点，然后对距已送货点最近的点按照情况三做处理得到如下结果:(四) 公司需派出6个业务员，其各个路径及时间如下:第一个业务员:0—30—29—28—0花费的时间为4.5h，该业务员的路程为100km 第二个业务员:0—26—27—0 花费的时间为3.3733h，该业务员的路程为76km 第三个业务员:0—23—20—19—25—0，花费的时间为3.9467h，该业务员的路程为82km 第四个业务员:0—24—18—17—0，0—21—22—10—0花费的时间为5.96h，该业务员的路程为124km 第五个业务员:0—14—13—12—8—0，0—15—7—4—3—0花费的时间为5.1733h，该业务员的路程为96km 第六个业务员:0—11—9—1—2—5—0，0—16—6—07花费的时间为4.7667h，该业务员的路程为90km该情况下的总路程为568km综上，经过比较各种情况下的结果，我们得到(三)的结果为该算法下的最佳的送货策略。