快递公司送货策略

快递公司送货策略摘要此题属于多旅行商问题〔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模型一、问题重述目前，快递行业正蓬勃开展，为我们的生活带来更多方便。一般地，所有快件到达*地后，先集中存放在总部，然后由业务员分别进展派送；对于快递公司，为了保证快件能够在指定的时间送达目的地，必须有足够的业务员进展送货，但是，太多的业务员意味着更多的派送费用。假定所有快件在早上7点钟到达，早上9点钟开场派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克〔1〕请你运用有关数学建模的知识，给该公司提供一个合理的送货策略〔即需要多少业务员，每个业务员的运行线路，以及总的运行公里数〕；〔2〕如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km〔3〕如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？二、模型假设1、假设业务员送货期间的速度不受外界的影响；2、假设业务员的休息时间不包含在6小时中；3、假设每个派送点只经过一次，每名业务员的行进路线决定后就不得改变；4、假设假设其中一个业务员跑多条路线时，中间返回总部后取快件〔将快件装上车〕所花费的时间不计；5、假设各业务员之间的快件运送过程是相互独立的。三、符号说明符号符号意义符号符号意义旅行商经过对应弧度所花的费用初始种群规模遗传算法的一代种群穿插概率每条线路的完成时间变异概率配送点与配送点之间的实际距离从派送点到派送点再返程的最省费用费用目标函数派送点所需货物的重量四、问题分析4.1问题一的分析首先，此题要求用最少的业务员，最少的时间，派送完所有的快件所走的路程最短，并给出每个业务员的运行路线。且，故至少需要8条路线；考虑到求解最短路径，我们采用了两种方法：模型一是用遗传算法中的一个回路的TSP模型算出所有点最短的路线，并根据每个业务员的所用时间，携带质量，按照要求进展分段，得到一种送货方案并改良了遗传算法最终结果为业务员5个,业务员行走总路程为484km,工作的总时间为24.36h；模型二是用基于遗传算法的MTSP模型进展求解，也即在不考虑重量和时间的约束下，将MTSP问题转化为增加个结点的单旅行商问题，然后采用遗传算法，使算法能以较大的概率获得全局的最优解：业务员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做出了多条路径后，计算出每条路径经派送所需要的时间，在题目所给的限制每个派送员一天最多工作时间以，对路径分配到各个派送员的身上，固以此思路对派送员的人数进展确定，调整公司送货策略。五、模型的建立与求解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〕，可以作为问题近似最优解或满意解。遗传算法的具体步骤如下：(初始化)确定种群规模、穿插概率、变异概率；设置终止进化准则；随即生成个体作为初始种群；置；(个体评价)计算或估计中各个个体的适应度；(种群进化)〔1〕选择〔母体〕从中运用选择算子选择出对母体；〔2〕穿插对所选择出对母体，依概率执行穿插，形成个中间个体；〔3〕变异对个中间个体分别独立依概率执行变异，形成个候选个体；〔4〕选择〔子代〕从上述所形成的个候选个体中依适应度选择出个个体组成新一代种群；(终止检验)如已满足终止准则，则输出中具有最大适应度的个体作为最优解，终止计算；否则置并转；由上一代种群生成新一代种群的过程可以用以下矩阵的形式表示〔其中表示单位阵〕：.我们把随机产生的路径作为初始种群，进展编码转化成二进制数串，数串的长度由我们定的精度来控制；接下来评价染色体数串的适应度，由适应度评价函数来作为环境的角色，进展自然选择，接着依照染色体的适应度值进展新种群的复制，依照轮盘选择法，把染色体条数的数目设定为转动轮盘的次数，得到新种群的染色体组成；之后进展新种群的交配，结合突变概率得到最终新种群的染色体组成和新一代的相对实际值和适应度值，至此，已完成遗传算法的第一代流程，依次迭代，直至满足迭代次数得到最大目标函数值对应的染色体。求解此题具体算法流程如图1：图1遗传算法流程图5.1.2模型一：模型的建立和求解旅行商问题〔TSP〕简称为TSP问题，是最根本的路线问题，该问题的本质是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径本钱。TSP问题的描述十分简单,简言之,就是寻找一条最短的遍历n个城市的最短路径,或者说搜索自然数子集*={1,2,.,n}(*的元素表示对n个城市的编号)的一个排列π(*)={V1,V2,.,Vn},使len=Σd(Vi,Vi+1)+d(V1,Vn)取最小值,式中的d(Vi,Vi+1)表示城市Vi到城市Vi+1的距离.考虑到求解最短路径，我们采用遗传算法的TSP模型进展求解，也即在不考虑重量和时间的约束下，根据题目给出的坐标建立距离矩阵，调用遗传算法求出该问题的最短路径，然后根据每次出发最多能带25千克的重量，将所得的最短路径分成最少的分段路线，即可构成业务员的运行线路，再根据每个人的工作时间不超过6小时，对业务员进展合并求解出最少业务员数。最短路径求解首先我们在模型准备阶段得到了距离矩阵，采用一个业务员携带快件从总部出发，运用遗传算法实现所有的快件到达送货点。用MATLAB软件编程来求解，程序见附录1.针对题目，我们将遗传算法初始化群体，遗传算法的总设计如图2所示：图2TSP问题的遗传算法总体设计设定计算群体上每个个体的适应度值，由个体适应度值所决定的*个规则选择将进入下一代个体，随后进展穿插操作和变异操作，穿插概率=0.80，变异概率=0.01，经过500次迭代后得到一个业务员携带快件派送完所有送货点最短路径如图3所示。图3一个业务员的派送快件的TSP示意图带入程序得出优化结果最短路线为：0-2-6-5-16-17-18-24-25-19-27-26-29-28-30-23-15-21-22-11-10-9-8-12-13-14-20-7-4-3-1-0。其总路程长度为174km。然后按照量小于或等于25kg将它分为9段，即最多分派9个业务员完成派送问题，9条派送线路如图4所示：图430点具体派送分段图对于问题一，虽然我们采用遗传算法找到了一个业务员派送完所有送货点的最优的TSP回路，对上面的派送分段图进展解析，先安排9名业务员从总部出发，完成每条派送任务后返回本部，每个业务员途中速度为25km/h，计算每个分段的路径长度为：〔1〕为每条分段图的路径和从原点出发到第一个送货点与完成最后一个点的送货任务后返回原点的路径；为每条分段图的路径；为业务员从原点出发到第一个送货点的路径；为业务员完成最后一个点的送货任务后返回原点的路径。则每条线路的完成的时间为：〔2〕其中，为每个送货员在送货点送货出现的次数。则业务员经过的站号、时间、携带的总重量以及总路程一览表如表1所示表1业务员送货路线、所用时间、携带重量和最短路径业务员经过的站号所用时间〔h〕总重量〔kg〕总路程〔km〕10-2-6-5-16-17-02.91255220-18-24-25-03.2224.76830-19-27-03.0519.86840-26-29-28-04.1824.19250-30-23-15-21-22-04.75239860-11-10-9-8-02.7514.35270-12-13-14-02.5822.35280-20-7-4-3-02.4323.34490-1-00.57810总计26.44184.5536减少业务员通过表1进展分析发现每个业务员时间都远小于总共的6小时，局部并非是最优化的，且本文所考虑的车辆由第三方运输效劳商提供，且对所使用的每辆车都要缴纳一定的发车费用，所以在整个优化分销网络的过程中，尽可能减少发车车辆所需的费用是本文需要考虑的另一个方面，所以将分成的9段按分析中的方法进展再优化，具体优化步骤：按照派送最少的业务员完成派送任务原则，先将30点的派送分段图进展编号，按照从何总部出发，完成任务后返回总部的各个业务员的时间进展合理组合，选取时间和均缺乏6小时的假设干业务员合并成一个业务员；为了尽量节省时间，对局部的路径进展调整，到达用最少的业务员，在规定的时间和满足自己的最大承受快件质量为条件，跑最短的路径，完成派送任务。经过局部的调整之后，得到每个业务员的送货路线，所用时间，总量和总路程如表2：表2优化后的业务员数和具体路线业务员经过的站号所用时间〔h〕总路程〔km〕10-2-6-5-16-17-0和0-19-27-05.9612020-18-24-25-0和0-11-10-9-8-05.9712030-9-12-10-11-0和0-1-04.7510240-30-23-15-21-22-04.759850-12-13-14-0和0-20-7-4-3-05.0196总计26.44536对表2中数据分析可知，原线路1和线路3，原线路2和线路6，原线路4和线路4以及原线路7和线路8的时间和均缺乏6小时，故可合二为一，派给一个业务员送，这样只需要业务员5名即可完成每天的任务。改良遗传算法在对数据的进一步分析之后发现，用遗传算法得到的30个点的总路线虽然是最优的，分段后随做了一定优化处理，但仍不一定是最优的数据。特别是在距原点较远的地方业务员带的费用较高，对第二问并没有帮助，于是我们进一步用遗传算法在VRP问题中的应用进展探讨，改良了遗传算法，以寻求最优解。由于原先将路径分为9段，分别派送5名业务员，为减少来回路途，我们进一步将其局部调整为8段。按照这一解题思路，采用改良遗传算法的Matlab程序得出优化结果最短路线为：0-1-2-6-5-16-17-18-24-25-19-27-26-29-28-30-23-15-21-22-11-10-9-8-12-13-14-20-7-4-3-0。有了一个业务员携带快件将所有的快件派送到送货点，然后按照量小于或等于25kg将它分为8段，即最多分派8个业务员完成派送问题，也就是有8条派送线路，现30点具体派送分段图5所示：图530点具体派送分段图对于此题的改良算法，我们找到了一个业务员派送完所有送货点的最优的TSP回路，对上面的派送分段图进展解析，先安排8名业务员从总部出发，完成每条派送任务后返回本部，每个业务员途中速度为25km/h，计算每个分段的路径长度同上，计算时间也采用上述方法则通过合理计算得到业务员经过的站号、时间、携带的总重量以及总路程一览表如表3所示：表3业务员送货路线、所用时间、携带重量和最短路径业务员经过的站号所用时间〔h〕总重量〔kg〕总路程〔km〕10-1-2-6-01.3819.22220-5-16-17-18-03.0721.36030-24-25-19-03.22256840-27-26-03.37227650-29-28-30-23-15-04.7524.19860-21-22-11-10-9-03.39256470-8-12-13-14-02.7524.65280-20-7-4-3-02.4323.344总计24.36184.5484通过上表进展分析发现每个业务员时间都远小于总共的6小时，局部并非是最优化的，所以将分成的8段按分析中的方法进展再优化，将表2中线路1和线路4，线路2和线路7，线路3和线路8的时间和均缺乏6小时，故可合二为一，派给一个业务员送，这样也只需要业务员5名即可完成每天的任务。具体优化后的业务员数和具体路线见表4；表4改良算法优化后的业务员数和具体路线业务员经过的站号所用时间〔h〕总路程〔km〕10-1-2-6-0和0-27-26-04.759820-5-16-17-18-0和0-8-12-13-14-05.8211230-24-25-19-0和0-20-7-4-3-05.6511240-29-28-30-23-15-04.759850-21-22-11-10-9-03.3964总计24.36484结论：从遗传算法所得的结果来看，在题目要求的条件下，需要5名业务员，业务员行走总路程为536km,工作总时间为26.44h；而从改良后的遗传算法所得的结果来看，题目要求不变的情况下，也需要5名业务员，业务员行走总路程为484km,工作的总时间为24.36h.通过比拟，发现改良后的遗传算法更适宜解决业务员路径优化问题。5.1.3模型二：模型的建立和求解1、模型的建立和转换本文提出了一种求解MTSP问题的遗传算法，引入虚拟结点将MTSP转换成标准的TSP，然后采用遗传算法进展求解。MTSP通常可以描述如下：M个旅行商从同一个城市或不同城市〔此题是同一个城市〕出发，分别走一条旅行路线，每个城市有且有一个旅行商经过〔处出发城市外〕，使得总旅行最短。以点0表示旅行商的出发城市，称为源点，点表示个旅行商需访问的城市。MTSP问题的数学模型可以表示为：令模型表示如下：式中：为增广费用。假设用表示旅行商经过对应弧度所花的费用，如时间、距离、花费等，则给增加行和列，每一新的行或列是的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用。一般MTSP中，旅行商访问个城市必须满足以下2个条件。条件1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。条件2：一条有效路径严格由条非平凡子路径(NontrivialSubtours)组成。所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。用遗传算法求解MTSP，可通过附加虚拟城市的方法把MTSP转化为TSP。将另外个旅行商理解为个虚拟城市，这个虚拟城市标号分别为，它们与城市0具有一样的坐标(即一样位置)。在旅行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP中一个旅行商的旅行路径。需注意的是，为了防止出现平凡子路径，必须假设个虚拟城市到原点的距离为为一无穷大的正数〔即永远不能到达〕，到其他各点距离与原点一致，这样遗传算法就不会出现0-0-0的途径。将源点0复制个，个源点编号为每一个同源点0一样与其他点相连，而个源点互相不连接，这样在结点集上，可得到TSP线路，然后各源点合并成一个点。这样MTSP线路就分解成个分线路。2、模型的遗传算法求解流程〔1〕随机产生初始种群〔2〕将初始种群平均分为a个子种群〔3〕主循环开场对每一个子种群,执行〔a〕~〔g〕〔a〕染色体解码〔b〕计算每个染色体的适应度函数值〔c〕随机选择两个个体作为父染色体〔d〕对父染色体进展穿插，产生新的后代〔e〕对新的后代进展变异操作〔f〕最优个体代替邻子种群的最差个体，实现子种群间的信息交换〔g〕从每个子种群中提取要迁移的个体〔4〕完毕子循环〔5〕进化完毕判断(是否到达最大进化代数):假设满足,则循环完毕〔6〕进化完毕后对较优种群进展排序，最终得到最优解其中，a是路径条数。5.1.3基于遗传算法的模型和求解我们采用基于混合遗传算法的MTSP模型进展求解，同时在考虑重量和时间的约束下，通过附加虚拟城市的方法把MTSP转化为TSP，用MATLAB软件编程来求解，实现了所有的快件到达送货点的最短路径，程序见附录2.开场全局最优解的搜索过程，它先通过选择、穿插、变异等遗传操作来产生一组新的个体，这个运行过程反复迭代地进展，直到满足*个终止条件为止。经过4601次迭代，30个送货点最终被分为总路程最短的8段路径，具体路径为：0-7-13-19-14-0,0-21-29-30-23-11-0,0-9-28-26-20-6-0,0-1-3-2-0,0-16-17-5-4-0，0-22-27-15-0，0-18-24-25-0，0-10-12-8-0。其总路径长度为480km,工作的总时间为24.2h.图68个业务员的派送快件的MTSP示意图分派8个业务员完成派送问题，8条派送线路如图7所示：图730点具体派送分段图则业务员经过的站号、时间、携带的总重量以及总路程一览表如表5所示表5业务员送货路线、所用时间、携带重量和最短路径业务员经过的站号所用时间〔h〕总重量〔kg〕总路程〔km〕10-7-13-19-14-02.8324.65420-21-29-30-23-11-04.51259230-9-28-26-20-6-04.35258840-1-3-2-01.322.22050-16-17-5-4-02.6719.35060-22-27-15-03.2222.26870-18-24-25-03.2224.76880-10-12-8-02.121.540总计24.2184.5480通过表5进展分析发现每个业务员时间都远小于总共的6小时，局部并非是最优化的，且本文所考虑的车辆由第三方运输效劳商提供，且对所使用的每辆车都要缴纳一定的发车费用，所以在整个优化分销网络的过程中，尽可能减少发车车辆所需的费用是本文需要考虑的另一个方面，所以将分成的8段按分析中的方法进展再优化，按照派送最少的业务员完成派送任务原则，先将30点的派送分段图进展编号，按照从何总部出发，完成任务后返回总部的各个业务员的时间进展合理组合，选取时间和均缺乏6小时的假设干业务员合并成一个业务员；路径局部调整后，到达用最少的业务员，在规定的时间和满足自己的最大承受快件质量为条件，跑最短的路径，完成派送任务。经过局部的调整之后，得到每个业务员的送货路线，所用时间，总量和总路程如表6：表6优化后的业务员数和具体路线业务员经过的站号所用时间〔h〕总路程〔km〕10-7-13-19-14-02.835420-21-29-30-23-11-04.519230-9-28-26-20-6-0和0-1-3-2-05.6510840-16-17-5-4-0和0-22-27-15-05.9811850-18-24-25-0和0-10-12-8-05.32108总计24.2480对表6中数据分析可知，原线路3和线路4，原线路5和线路6，原线路7和线路8的时间和均缺乏6小时，故可合二为一，派给一个业务员送，这样只需要业务员5名即可完成每天的任务。总路径长度480km，总工作时间为24.2h.5.1.4两个模型的比拟分析第一问我们通过分析题意分别建立两种切实可行的的模型：MTSP模型和TSP模型。MTSP模型的总路径长度为480km,工作的总时间为24.2h，而TSP模型业务员行走总路程为484km,工作的总时间为24.36，经比拟不难发现，MTSP模型无论在业务员行走的总路径上还是所花总时间上都比TSP模型更为适宜。TSP模型所得数据用遗传算法得到的30个点的总路线虽然是最优的，分段后随做了一定优化处理，仍不一定是最优的数据，而MTSP模型恰恰解决了这一问题。综上所述，我们得到的最优路径总长480km,工作的总时间为24.2h。5.2问题二模型的建立与求解问题二要求如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km这个优化问题的目标是给业务员的酬金最少，业务员的安排、路线的选择都是为了总费用的最小化提供条件。由于MTSP模型是在问题一中的约束条件下求解的最优路径安排，我们可以直接根据MTSP模型中的方案计算所需的最少费用。但是因为业务员负载时所需的费用要比空载时高出很多，而问题一没有考虑这一点，所以如果直接运用问题一求出的最优路线针对费用来说，可能不是最正确的，对于问题二我们引入了一种费用优化方案，增加酬费目标函数，根据列出的优化方案对问题一得出的最短路径进展局部调整，即在问题一确定最短路径的根底上利用酬费距离矩阵对经过路径上各个派送点的顺序进展调整，得到最省费用策略。5.2.1建立酬费目标函数与问题一中确定总路程最短类似，问题二中的目标函数由总距离最小变为酬费最少，基于问题一MTSP模型中确定的最优的送货策略，共八条送货路径，对每条路径的派送点进展单独优化调整，使各条路径派送费用最省。且遗传算法涉及到个体选择，淘汰适应性差的个体，因此，需要建立目标函数来评价个体好坏。目标函数酬金P的计算公式为：其中，表示配送点与配送点之间的实际距离，表示配送点到配送点之间所需运送的货物重量，表示送货完毕回来无任何负载是配送点与原点之间的实际距离。目标函数中考虑了为携带货物时，派送点两两之间的酬费，也考虑了在送完货物返程时不携带货物的情况，计算出空载时的酬费，费用计算完毕后得出该条路径的实际最省酬费。算法依然是基于改良的遗传算法进展求解，寻找费用最省的MTSP费用最短路径。5.2.2基于MTSP模型求解最省费用5.2.2.1模型思路根据问题一中的处理方法，采用基于遗传算法的MTSP模型求解业务员的酬金最少路径，所得路径表示酬费距离最短，即费用最省。具体模型为〔5〕表示从派送点到派送点再返程的最省费用表示携带货物从派送点到派送点的最省费用；表示从派送点到派送点0空载时的费用；〔6〕表示从派送点到派送点之间的路程；表示派送点所需货物的重量；5.2.2.2遗传算法的求解按照问题一的解题思路采用基于遗传算法的MTSP模型的Matlab程序〔程序见附录〕，将遗传算法的参数设定如下：目标函数为，5个送货点的坐标作为参数，经过3263次迭代次，得到两种路径：方案一是分为费用最省的10条业务路线，分10次经过所有送货点；方案二是分为在尽可能减少费用的情况下最省业务员数的8条业务路线，分8次经过所有送货点。用Matlab绘出两种酬金费用路线如图7、图8所示。1、方案一图810条最短酬金费用路线据图7得出9段最短酬金费用路径为：0-19-25-24-0,0-10-11-21-0,0-2-4-7-0,0-22-29-30-0,0-13-27-28-0,0-12-15-23-0,0-5-20-18-0,0-6-16-17-0,0-9-14-26-0,0-1-3-8-0，最省费用为13873.7元，其总最省费用、时间、路径长度见表7：表710条分布路线的最省费用分配路线重量〔kg〕距离〔km〕时间〔h〕具体费用值(元)0-19-25-24-025683.332310.20-10-11-21-016.8542.751075.20-2-4-7-020.9321.83706.70-22-29-30-019.1924.332096.30-13-27-28-023.8884.172469.40-12-15-23-018.5723.51378.80-5-20-18-015.1562.831209.80-6-16-17-013.8482.5726.60-9-14-26-015.2743.581485.20-1-3-8-016.3301.75415.5总计184.561430.5713873.7从上表数据分析，经过遗传算法后得到了目标函数费用最省的10条新路线，在该路线的根底上，根据每条路线所花时间将路线合并，从而到达缩减业务员数量的目的。合并过后的数据见表8：表810条路线分配方法业务员经过的站号所用时间〔h〕总路程〔km〕总费用〔元〕10-22-29-30-04.33922096.320-2-4-7-0和0-13-27-28-061203176.130-12-15-23-0和0-6-16-17-061202105.440-9-14-26-0和0-1-3-8-05.331041900.750-19-25-24-03.33682310.260-10-11-21-0和0-5-20-18-05.851102285总计30.5761413873.7以上是费用最为低廉的的10条路径，需要6名业务员完成任务，总费用为13873.7元，下面我们将提供另一种方案。1、方案二在保证费用增幅不大的情况下，减少业务员数量，通过基于遗传算法的MTSP模型，将其分为8条路径，分派5名业务员完成任务，得到的路径为：0-8-12-21-23-0，0-3-7-20-17-0，0-10-22-28-30-0，0-11-27-29-0，0-6-5-14-25-0，0-1-9-18-24-0，0-4-13-19-15-0，0-2-16-26-0.得到的总费用为14429.8元。具体路线派送图如图8所示：图98条最短酬金费用路线采用上面的模型求解出在8条路线上的费用值见表9表98条分布路线的最省费用分配路线重量〔kg〕距离〔km〕时间〔h〕具体费用值(元)0-8-12-21-23-023.6743.11750.50-3-7-20-17-023.6502.11297.80-10-22-28-30-023.5964.032215.40-11-27-29-024.2823.422897.80-6-5-14-25-020.9582.4214050-1-9-18-24-024.5682.831658.60-4-13-19-15-022.5702.931684.10-2-16-26-021.7743.081520.6总计184.557223.9114429.8从上表分析可知，在遗传算法调整后得到的8条新路线的费用最省值为14429.8元。在该路线的根底上，根据每条路线所花时间将路线合并，从而到达缩减业务员数量的目的。合并过后的数据见表10：表108条路线分配方法业务员经过的站号所用时间〔h〕总路程〔km〕总费用〔元〕10-8-12-21-23-0和0-1-9-18-24-05.931423409.120-3-7-20-17-0和0-11-27-29-05.521324195.630-10-22-28-30-04.03962215.440-6-5-14-25-0和0-2-16-26-05.51322925.650-4-13-19-15-02.93701684.1总计223.9157214429.8以上是费用较为低廉的的8条路径，需要5名业务员完成任务，总费用为14429.8元3、两种方案的比拟通过数据分析两种方案各有优劣。第一种方案总体费用最为低廉，但至少需要6名业务员完成，第二种方案中价钱虽然较高但是只需要5名业务员即可完成任务。快递公司可以根据资金和人员调度来为了进一步确定使用哪种方案更为优化。考虑到公司费用最省，如公司予以派送员根本工资〔派送费以外工资〕大于14429.8-13873.7=556.1，则选择8条路径时表10的派送方案；如公司予以派送员根本工资小于556.1，则选择10条路径时表8的派送方案。5.3问题三模型的建立与求解基于问题一与问题二的结果，将原来派送员工作时间6个小时改为派送时间为8个小时。问题一与问题二的结果不变，最短距离不变，最少费用不变，所需时间与分配路径不变。仅改变派送方案，进而减少派送人员。5.3.1距离最短新派送方案第一问中遗传算法的目标函数控制为总距离最短，我们采用了基于TSP算法和基于MTSP算法的两种方法，最终选取了MTSP算法的结果。在MTSP算法结果的根底上，将派送人员每天工作6个小时改为派送员每天工作小时为8小时后，结合每条路径所需时间，对表1中的数据，依照每个派送人员所用时间之和小于8个小时，而且派送时间、路程、货物质量尽量平均的原则，重新进展人员分配。结果如下表11：表11：基于问题一的新派送情况派送人员派送路径经过的站号10-7-13-19-14-0，0-16-17-5-4-0，0-10-12-8-020-21-29-30-23-11-0，0-22-27-15-030-9-28-26-20-6-0，0-18-24-25-040-1-3-2-0 由上表可知，总共仅需4名派送员便能完成任务。第一名派送员经过路径1,5,8走完3个来回，共行程144km，费时7.6h。4名派送员所消耗总时间与总路程如表12所示：表12：基于问题一的新派送消耗情况派送员编号所用时间〔h〕总路程〔km〕17.614427.7316037.5715641.320 派送员工作时间由6小时变为8小时后，所需总路程不变仍为480km，总时间不变，仍为24.2h。但是派送人员能减少到4个。5.3.2费用最少新派送方案5.3.2.1不考虑派送人员根本工资的费用最少新派送方案同样，基于问题二的结果，在不考虑公司予以派送员根本工资的情况下，将10条路径费用最少的派送结果进展优化。把派送员工作时间由6小时变为8小时后，基于每个派送员所用时间、总路程、携带货物总质量尽量平均的原则，得到新的派送方案如表13所示。表13：基于问题二的十条路径新的派送情况派送人员编号经过的站号10-2-4-7-0，0-12-15-23-0，0-6-16-17-020-10-11-21-0，0-5-20-18-0，0-1-3-8-030-19-25-24-0，0-22-29-30-040-13-27-28-0，0-9-14-26-0由上表可知，在总费用不变的情况下，我们将派送人员由原来的6个缩减为现在的4个，大大节约了人力资源本钱，又不影响公司利益。5.3.2.2考虑派送人员根本工资的费用最少新派送方案于是，我们再考虑对公司予以派送员根本工资的情况，将8条路径费用最少的派送结果进展优化。考虑派送人员工作时间由6小时变为8小时后，每个派送人员所用总时间、总路程以及携带货物总量尽量平均，得到新的派送方案如表14所示。表14：问题二中八条路径派送情况派送人员编号经过的站号10-3-7-20-17，0-10-22-28-3020-11-27-29-0，0-6-5-14-25-030-8-12-21-23-0，0-1-9-18-24-040-4-13-19-15-0，0-2-16-26-0由上表可知，在选择8条路径的费用最少派送结果中，如果派送人员工作时间增加2个小时，则可以将原来的5名派送人员缩减为4名派送人员。5.3.2.3费用最少新派送方案由于派送人员工作时间的改变，导致派送方案的变化。原本10条路径所需人员由6人变为了4人，8条路径派送人员由5人变为了4人，现在两种方案所需派送人员一样，只需考虑其因路程与货物重量造成的费用即可得到最少费用方案。10条路径与8条路径所需费用如表16所示。表16：路径数为10和8时所需的费用路径数费用〔元〕1013873.7814429.8由表16可明显看出，路径数为10时所需费用最少。最终选择路径数为10的方案。最少费用为13873.7元。六、模型的评价与推广6.1模型的优点本文第一问从单旅行商问题出发，把从原点出发的一条遍历所有城市的路径依据载重限制进展分割，并结合所分割出点之间的远近和所要派送的重量进展搭配重组，分配给各个派送员；之后自然而然过渡到多旅行商问题，由一至多，发现更优化的解决方法。第二问保持了和上一问的连贯性和算法的连续性，修改目标函数为总花费，得出不同路径数目设置对仅考虑路径走法的花费，之后结合时间限制算出不同路径所需人数，给公司提出了是否考虑派送员根底工资的方案，考虑更为细致全面，层次上也更加清楚。第三问考虑修改了派送员每天的工作时间后分别在最短路径和最少花费的情况下对人员分配进展了说明，分类更为细致。6.2模型的缺点本文因第一问在由单旅行商路线进展拆分给各个派送员时，单条遍历所有城市的路径最短不代表拆分过后总路径最短，带来了一定误差，好在我们之后采用了多旅行商思路，弥补了这一缺乏，也进一步说明了多旅行商思路的优越之处。第二问由TSP分出的路径均衡度与花费最省不能同时满足，所以就给公司提出来方案以供选择。

6.3模型的推广本模型设计在考虑各个因素限制的情况下的人员分配及路线划分问题，适用于多种情况，如蜜蜂采蜜模型，水流分配等，且有很广泛应用领域如：规划最合理高效的道路交通，以减少拥堵；更好地规划物流，以减少运营本钱；在互联网环境中更好地设置节点，以更好地让信息流动等。七、参考文献[1]熊翠,吴慧萍，多旅行商问题遗传算法求解及其改良[J]，华中师大学,,24(5):9-11，2005。[2]维维，静，基于混合遗传算法的MTSP问题研究[J].农业大学,2010(1):39-46.[3]震东，唐加福，带货物权重的车辆路径问题及遗传算法[J]，东北大学系统工程研究所,33(3):250-252，2012。[4]俞庆生，多旅行商问题研究综述[J]，科学技术学院信息与教育技术中心，(1):54-56，1999。[5]霞,齐欢.车辆路径问题的研究[J].华中科技大学,2008,34(7):34-36.[6]冰洁，遗传算法及其应用实例[J]，理工大学学报,28(1):66-69，2008。[7]周明,树栋，遗传算法原理与应用[J]，国防工业，26(2):72-75，2003。[8]林家恒,国峰，长有，一种求解MTSP的遗传算法[J]，工业大学,18(3):25-29，1999。[9]明,琳度，多旅行商问题求解的一类新遗传算法[J]，东南大学系统工程研究所,17(8):33-37，2010。[10]静,但琦，数学建模与数学实验[M]，:高等教育出社,2008:254-281.[11]FrankR.Giordano等，AFirstCourseinMathematicalModeling[M]，:机械工业,2010:161-163.[12]卓金武.MATLAB在数学建模中的应用[M]，:航空航天大学,2010:5-9。附录附录一：基于遗传算法的TSP算法matlab代码主程序：clc;clearall;closeall;global*y*=[03154037910141714121019261115722212715152021242528];y=[025478119620369129161817121450919141713201618];a=[88.265.534.57.22.31.46.54.112.75.83.83.43.55.87.57.84.66.26.82.47.69.6101268.14.2];h=0:30;t=31+1;%送货点数s=1500;%初始中群数G=500;%最大迭代次数c=25;%一次选取25个样本pc=0.80;%交配率pm=0.01;%变异率pop=zeros(s,t);fori=1:spop(i,1:t-1)=randperm(t-1);%初始化种群endfork=1:1:G%GA开场¼ifmod(k,50)==1kendpop=distance1(pop);%调用距离函数pop=select(pop,c);%调用选择函数p1=rand;ifp1>=pcpop=cross(pop);%调用交配函数endp2=rand;ifp2>=pmpop=mutate(pop);%调用变异函数endend%GA完毕%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%bestL=min(pop(:,t))J=pop(:,t);fi=1./J;[Oderfi,Inde*fi]=sort(fi);%对fi进展排序BestS=pop(Inde*fi(s),:);%得到最短路径I=BestS;fori=1:1:t-1*1(i)=*(I(i));y1(i)=y(I(i));end*1(t)=*(I(1));y1(t)=y(I(1));cities_new=[*1;y1];disp('BestRouteis:');disp(cities_new);pos=[cities_newcities_new(:,1)];lentemp=0;fori=1:1:t-1temp=(abs(pos(1,i)-pos(1,i+1))+abs(pos(2,i)-pos(2,i+1)));lentemp=lentemp+temp;enddisp('ShortestLengthis:');disp(lentemp);plot(*1,y1,'-or');*label('*a*is'),ylabel('Ya*is'),title('最短路径');a*is([0,1,0,1]);a*is([0,30,0,20]);a*ison距离函数matlab代码：function[pop]=distance1(pop)global*y[s,t]=size(pop);fori=1:1:sdd=0;pos=pop(i,1:t-1);pos=[pospos(:,1)];forj=1:1:t-1m=pos(j);n=pos(j+1);dd=dd+(abs(*(m)-*(n))+abs(y(m)-y(n)));endpop(i,t)=dd;end选择函数matlab代码：function[pop]=select(pop,c)[s,t]=size(pop);m11=(pop(:,t));m11=m11';mma*=zeros(1,c);mmin=zeros(1,c);num=1;whilenum<c+1%取距离大的C个样本[a,mma*(num)]=ma*(m11);m11(mma*(num))=0;num=num+1;endnum=1;whilenum<c+1%取距离小的C个样本[b,mmin(num)]=min(m11);m11(mmin(num))=a;num=num+1;endfori=1:cpop(mma*(i),:)=pop(mmin(i),:);end交配函数matlab代码：function[pop]=cross(pop)[s,t]=size(pop);pop_1=pop;n=randperm(s);%将种群随机排序fori=1:2:s%随机选择两个穿插点m=randperm(t-3)+1;crosspoint(1)=min(m(1),m(2));crosspoint(2)=ma*(m(1),m(2));%任意两行穿插*1=n(i);*2=n(i+1);%将*1左边与*2的左边互换middle=pop(*1,1:crosspoint(1));pop(*1,1:crosspoint(1))=pop(*2,1:crosspoint(1));pop(*2,1:crosspoint(1))=middle;%将*1右边与*2的右边互换middle=pop(*1,crosspoint(2)+1:t);pop(*1,crosspoint(2)+1:t)=pop(*2,crosspoint(2)+1:t);pop(*2,crosspoint(2)+1:t)=middle;forj=1:crosspoint(1)whilefind(pop(*1,crosspoint(1)+1:crosspoint(2))==pop(*1,j))zhi=find(pop(*1,crosspoint(1)+1:crosspoint(2))==pop(*1,j));temp=pop(*2,crosspoint(1)+zhi);pop(*1,j)=temp;endendforj=crosspoint(2)+1:t-1whilefind(pop(*1,crosspoint(1)+1:crosspoint(2))==pop(*1,j))zhi=find(pop(*1,crosspoint(1)+1:crosspoint(2))==pop(*1,j));temp=pop(*2,crosspoint(1)+zhi);pop(*1,j)=temp;endendforj=1:crosspoint(1)whilefind(pop(*2,crosspoint(1)+1:crosspoint(2))==pop(*2,j))zhi=find(pop(*2,crosspoint(1)+1:crosspoint(2))==pop(*2,j));temp=pop(*1,crosspoint(1)+zhi);pop(*2,j)=temp;endendforj=crosspoint(2)+1:t-1whilefind(pop(*2,crosspoint(1)+1:crosspoint(2))==pop(*2,j))zhi=find(pop(*2,crosspoint(1)+1:crosspoint(2))==pop(*2,j));temp=pop(*1,crosspoint(1)+zhi);pop(*2,j)=temp;endendend%生成新的种群与穿插前相比拟[pop]=distance1(pop);fori=1:sifpop_1(i,t)<pop(i,t)pop(i,:)=pop_1(i,:);endend变异函数matlab代码：function[pop]=mutate(pop)[s,t]=size(pop);pop_1=pop;fori=1:2:sm=randperm(t-3)+1;%随机选取两个点mutatepoint(1)=min(m(1),m(2));mutatepoint(2)=ma*(m(1),m(2));%用倒置变异的方法倒置两个点中间局部的位置mutate=round((mutatepoint(2)-mutatepoint(1))/2-0.5);forj=1:mutatezhong=pop(i,mutatepoint(1)+j);pop(i,mutatepoint(1)+j)=pop(i,mutatepoint(2)-j);pop(i,mutatepoint(2)-j)=zhong;endend[pop]=distance1(pop);fori=1:sifpop_1(i,t)<pop(i,t)pop(i,:)=pop_1(i,:);endend附录二：遗传算法MTSPmatlab代码程序一：functionvarargout=mtspf_ga(*y,dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res)%*y各个送货点坐标%dmat送货点之间距离%salesmen路径数%min_tour派送员最少到底派送点数%pop_size种群个体数%num_iter迭代代数%show_prog,show_res显示参数设定a=[088.265.534.57.22.31.46.54.112.75.83.83.43.55.87.57.84.66.26.82.47.69.6101268.14.2];[nr,nc]=size(dmat);ifnr~=ncerror('Invalid*YorDMATinputs!')endn=nr-1;%送货点数%输入参数检查salesmen=ma*(1,min(n,round(real(salesmen(1)))));min_tour=ma*(1,min(floor(n/salesmen),round(real(min_tour(1)))));pop_size=ma*(8,8*ceil(pop_size(1)/8));num_iter=ma*(1,round(real(num_iter(1))));show_prog=logical(show_prog(1));show_res=logical(show_res(1));%初始化路线，断点num_brks=salesmen-1;dof=n-min_tour*salesmen;addto=ones(1,dof+1);fork=2:num_brksaddto=cumsum(addto);endcum_prob=cumsum(addto)/sum(addto);%初始化种群pop_rte=zeros(pop_size,n);%路径集合的种群pop_brk=zeros(pop_size,num_brks);%断点集合的种群fork=1:pop_sizepop_rte(k,:)=randperm(n)+1;pop_brk(k,:)=randbreaks();endclr=[100;001;0.6701;010;10.50];ifsalesmen>5clr=hsv(salesmen);end%开场遗传算法global_min=Inf;%初始化最短路径total_dist=zeros(1,pop_size);dist_history=zeros(1,num_iter);tmp_pop_rte=zeros(8,n);%当前的路径设置tmp_pop_brk=zeros(8,num_brks);%当前的断点设置new_pop_rte=zeros(pop_size,n);%更新的路径设置new_pop_brk=zeros(pop_size,num_brks);%更新的断点设置ifshow_progpfig=figure('Name','MTSPF_GA|CurrentBestSolution','Numbertitle','off');endforiter=1:num_iter%评价每一代的种群适应情况并作出选择forp=1:pop_sizep_rte=pop_rte(p,:);p_brk=pop_brk(p,:);rng=[[1p_brk+1];[p_brkn]]';w=0;fors=1:salesmenh=0;d=0;d=d+dmat(1,p_rte(rng(s,1)));w=w+dmat(1,p_rte(rng(s,1)))*a(p_rte(rng(s,1)))*3;%添加初始路径fork=rng(s,1):rng(s,2)-1d=d+dmat(p_rte(k),p_rte(k+1));w=w+d*a(p_rte(k+1))*3;h=h+a(p_rte(1+k));endh=h+a(p_rte(k+1));d=d+(dmat(p_rte(rng(s,2)),1));w=w+(dmat(p_rte(rng(s,2)),1))*2;%添加完毕路径ifh>25w=inf;endendtotal_dist(p)=w;end%在每代种群中找到最好路径[min_dist,inde*]=min(total_dist);dist_history(iter)=min_dist;ifmin_dist<global_minglobal_min=min_dist;opt_rte=pop_rte(inde*,:);opt_brk=pop_brk(inde*,:);rng=[[1opt_brk+1];[opt_brkn]]';ifshow_prog%PlottheBestRoutefigure(pfig);fors=1:salesmenrte=[1opt_rte(rng(s,1):rng(s,2))1];plot(*y(rte,1),*y(rte,2),'.-','Color',clr(s,:));title(sprintf('TotalDistance=%1.4f,Iteration=%d',min_dist,iter));holdonendplot(*y(1,1),*y(1,2),'ko');holdoffendend%遗传算法操作集合rand_grouping=randperm(pop_size);forp=8:8:pop_sizertes=pop_rte(rand_grouping(p-7:p),:);brks=pop_brk(rand_grouping(p-7:p),:);dists=total_dist(rand_grouping(p-7:p));[ignore,id*]=min(dists);best_of_8_rte=rtes(id*,:);best_of_8_brk=brks(id*,:);rte_ins_pts=sort(ceil(n*rand(1,2)));I=rte_ins_pts(1);J=rte_ins_pts(2);fork=1:8%产生新方案tmp_pop_rte(k,:)=best_of_8_rte;tmp_pop_brk(k,:)=best_of_8_brk;switchkcase2%倒置操作tmp_pop_rte(k,I:J)=fliplr(tmp_pop_rte(k,I:J));case3%互换操作tmp_pop_rte(k,[IJ])=tmp_pop_rte(k,[JI]);case4%滑动平移操作tmp_pop_rte(k,I:J)=tmp_pop_rte(k,[I+1:JI]);case5%更新断点tmp_pop_brk(k,:)=randbreaks();case6%倒置并更新断点tmp_pop_rte(k,I:J)=fliplr(tmp_pop_rte(k,I:J));tmp_pop_brk(k,:)=randbreaks();case7%互换并更新断点tmp_pop_rte(k,[IJ])=tmp_pop_rte(k,[JI]);tmp_pop_brk(k,:)=randbreaks();case8%评议并更新断点tmp_pop_rte(k,I:J)=tmp_pop_rte(k,[I+1:JI]);tmp_pop_brk(k,:)=randbreaks();otherwiseendendnew_pop_rte(p-7:p,:)=tmp_pop_rte;new_pop_brk(p-7:p,:)=tmp_pop_brk;endpop_rte=new_pop_rte;pop_brk=new_pop_brk;end%返回结果rng=[[1opt_brk+1];[opt_brkn]]';dis_e=zeros(1,