快递公司送货策略

-1-快递公司送货策略摘要本题属于多旅行商问题（MTSP），研究在固定的送货地点，派送员在运输重量限制和工作时间等各种约束条件下，设计出最优的送货路线，得出最优送货策略。本文建立了基于遗传算法的MTSP模型，依次回答了题目提出的三个问题。针对问题一，首先采用基于遗传算法的TSP模型求解，不限制送货时间与派送员携带货物质量上限，遍历30个送货点计算出一条送货路径。再依照每个派送员携带货物不超过25kg的限制条件，将求出的TSP路线分为总距离最短的8条。进而得到8条路径，总距离数为484km，共需5名派送人员的方案，派送方案如表4所示。再用基于遗传算法的MTSP模型求解，由于派送员每次携带货物不能超过25kg，而每天收到的平均总货物重量为184.5kg，因此选择184.5/25进位取整等于8条派送路径，即视为多旅行商问题中旅行商数为8。由于选择8条路径，每条路径派送完成时间明显小于6个小时，所以计算时暂不考虑派送时间因素，在最后派送人员分配上再考虑时间限制。于是将8条路径总距离数设为目标函数，加入每条路径携带货物总质量不能超过25kg的限制条件，使用基于遗传算法的MTSP模型。求解得出8条路径最短距离为480km，共需5名派送人员，派送方案如表2所示。比较TSP得出方案与MTSP得出方案，发现MTSP得出方案明显优于TSP得出方案。于是采用最短路径为480km，共需5人，派送方案如表2所示的方案。针对问题二，仍然采用基于遗传算法的MTSP模型，将所有路径总花费设为目标函数，仍将时间限制放在派送方案选取时考虑。计算出8条路径时总距离数为572km，所需人数为5人，总花费为14429.8，派送方案如表10所示。将路径数增加，发现当派送人员有10条路径时，总距离数为614km，所需人数为6人，总花费为13873.7元，派送方案如表8所示。9条路径以及10条以上路径在花费和所需人数安排上都劣于10条路径。考虑到公司费用最省，如公司予以派送员基本工资（派送费以外工资）大于14429.8-13873.7=556.1，则选择8条路径时表10的派送方案；如公司予以派送员基本工资小于556.1，则选择10条路径时表8的派送方案。针对问题三，在问题一与问题二的基础上，将派送员的派送时间由6h增加到8h，设计出新的派送方案。分别得出距离最短派送新派送方案所需人数为4人，距离仍为480km，新派送方案如表11所示；费用最少10条路径所需人数为4人，总费用仍为13873.7元，新派送方案如表13所示。关键词：多旅行商问题遗传算法MTSP模型TSP模型-2-一、问题重述目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。假定所有快件在早上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、假设业务员的休息时间不包含在6小时中；3、假设每个派送点只经过一次，每名业务员的行进路线决定后就不得改变；4、假设若其中一个业务员跑多条路线时，中间返回总部后取快件（将快件装上车）所花费的时间不计；5、假设各业务员之间的快件运送过程是相互独立的。三、符号说明符号符号意义符号符号意义ijc旅行商经过对应弧度(,)ij所花的费用N初始种群规模()Xt遗传算法的一代种群cp交叉概率t每条线路的完成时间mp变异概率ijd配送点i与配送点j之间的实际距离qnS从派送点0到派送点n再返程的最省费用ijP费用目标函数im派送点i所需货物的重量-3-四、问题分析4.1问题一的分析首先，本题要求用最少的业务员，最少的时间，派送完所有的快件所走的路程最短，并给出每个业务员的运行路线。且184.5825kgkg，故至少需要8条路线；考虑到求解最短路径，我们采用了两种方法：模型一是用遗传算法中的一个回路的TSP模型算出所有点最短的路线，并根据每个业务员的所用时间，携带邮件质量，按照要求进行分段，得到一种送货方案并改进了遗传算法最终结果为业务员5个,业务员行走总路程为484km,工作的总时间为24.36h；模型二是用基于遗传算法的MTSP模型进行求解，也即在不考虑重量和时间的约束下，将MTSP问题转化为增加(1)m个结点的单旅行商问题，然后采用遗传算法，使算法能以较大的概率获得全局的最优解：业务员5个，总路径长度480km，总工作时间为24.2h.4.2问题二的分析本题在加了速度和费用的前提下，要求花费最省的一种方案。固在MTSP问题的基础上，把目标函数设置为公司派送的总花费，且总花费为每点所要求业务员送达快件的质量与该点到路径上的前一些点直到原点的折线距离和3元/km×kg的乘积，加上路径中最后一个点到原点的乘积与2元/km的乘积，其中的距离为平行与坐标轴的总距离。由问题一的分析，先设置MTSP的路径数为8,9,10发现路径数为8时费用较高，所需要的派送员为5人；路径数为9时花费较大；路径数为10费用最少但所需派送人数为6人。而在10条路径以上时，花费明显增加，固此时就给公司提出了一个选择，是更侧重于考虑派送员们的基础工资减少派送员的个数还是考虑由于运送路程和载重不同造成的花费最省。4.3问题三的分析本题条件上将前面所限定的每个业务员每天最多工作6小时改成了8小时。经过对问题一与问题二的研究，我们将会发现，这一条件的改变，对送货路径并没有太多影响，只是业务员工作的分配会发生变化，因为在解决前两问时由MTSP做出了多条路径后，计算出每条路径经派送所需要的时间，在题目所给的限制每个派送员一天最多工作时间以内，对路径分配到各个派送员的身上，固以此思路对派送员的人数进行确定，调整公司送货策略。-4-五、模型的建立与求解5.1问题一模型的建立与求解在问题一中，要求在每个业务员每天平均工作时间不超过6小时且必须从早上9点钟开始派送，到当天17点之前（即在8小时之内）派送完毕；以及每次出发最多能带25千克的重量。要求给该公司提供一个合理的送货策略,即当业务员数量最少且送货总距离最小时可得到比较合理的送货策略。由于平均每天收到总重量为184.5千克，而业务员每次最多只能带25千克的重量，便可以确定出最少需要[184.5/25]=8条路线。据此，我们分别建立了TSP模型和MTSP模型，并采用遗传算法求得最终路径。5.1.1遗传算法设计遗传算法（GeneticAlgorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》，GA这个名称才逐渐为人所知。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解或满意解。遗传算法的具体步骤如下：1step(初始化)确定种群规模N、交叉概率cp、变异概率mp；设置终止进化准则；随即生成N个体作为初始种群；置0t；2step(个体评价)计算或估计Xt中各个个体的适应度；3step(种群进化)（1）选择（母体）1::NMLLSHH从()Xt中运用选择算子选择出2M对母体MN；（2）交叉::NMLLCHH对所选择出2M对母体，依概率cp执行交-5-叉，形成M个中间个体；（3）变异::NMLLMHH对M个中间个体分别独立依概率执行变异，形成M个候选个体；（4）选择（子代）2::NMLLSHH从上述所形成的M个候选个体中依适应度选择出N个个体组成新一代种群1Xt；4step(终止检验)如已满足终止准则，则输出1Xt中具有最大适应度的个体作为最优解，终止计算；否则置1tt并转3step；由上一代种群()Xt生成新一代种群1Xt的过程可以用以下矩阵的形式表示（其中I表示单位阵）：12010SMCXtXtIS.我们把随机产生的路径作为初始种群，进行编码转化成二进制数串，数串的长度由我们定的精度来控制；接下来评价染色体数串的适应度，由适应度评价函数来作为环境的角色，进行自然选择，接着依照染色体的适应度值进行新种群的复制，依照轮盘选择法，把染色体条数的数目设定为转动轮盘的次数，得到新种群的染色体组成；之后进行新种群的交配，结合突变概率得到最终新种群的染色体组成和新一代的相对实际值和适应度值，至此，已完成遗传算法的第一代流程，依次迭代，直至满足迭代次数得到最大目标函数值对应的染色体。求解本题具体算法流程如图1：初始化路径矩阵D确定实际问题参数对参数进行编码(0)X初始化群体适应度评估满足停止准则结束遗传操作（选择、交叉、变异）是否进行代数加1图1遗传算法流程图5.1.2模型一：TSP模型的建立和求解-6-旅行商问题（TSP）简称为TSP问题，是最基本的路线问题，该问题的本质是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。TSP问题的描述十分简单,简言之,就是寻找一条最短的遍历n个城市的最短路径,或者说搜索自然数子集X={1,2,.,n}(X的元素表示对n个城市的编号)的一个排列π(X)={V1,V2,.,Vn},使len=Σd(Vi,Vi+1)+d(V1,Vn)取最小值,式中的d(Vi,Vi+1)表示城市Vi到城市Vi+1的距离.考虑到求解最短路径，我们采用遗传算法的TSP模型进行求解，也即在不考虑重量和时间的约束下，根据题目给出的坐标建立距离矩阵，调用遗传算法求出该问题的最短路径，然后根据每次出发最多能带25千克的重量，将所得的最短路径分成最少的分段路线，即可构成业务员的运行线路，再根据每个人的工作时间不超过6小时，对业务员进行合并求解出最少业务员数。1、最短路径求解首先我们在模型准备阶段得到了距离矩阵，采用一个业务员携带快件从总部出发，运用遗传算法实现所有的