《快递公司管理系统送货策略》由会员分享，可在线阅读，更多相关《快递公司管理系统送货策略（31页珍藏版）》请在金锄头文库上搜索。
1、word快递公司送货策略摘要此题属于多旅行商问题MTSP，研究在固定的送货地点，派送员在运输重量限制和工作时间等各种约束条件下，设计出最优的送货路线，得出最优送货策略。本文建立了基于遗传算法的MTSP模型，依次回答了题目提出的三个问题。针对问题一，首先采用基于遗传算法的TSP模型求解，不限制送货时间与派送员携带货物质量上限，遍历30个送货点计算出一条送货路径。再依照每个派送员携带货物不超过25kg的限制条件，将求出的TSP路线分为总距离最短的8条。进而得到8条路径，总距离数为484km，共需5名派送人员的方案，派送方案如表4所示。再用基于遗传算法的MTSP模型求解，由于派送员每次携带货物不能超
2、过25kgkg，因此选择184.5/25进位取整等于8条派送路径，即视为多旅行商问题中旅行商数为8。由于选择8条路径，每条路径派送完成时间明显小于6个小时，所以计算时暂不考虑派送时间因素，在最后派送人员分配上再考虑时间限制。于是将8条路径总距离数设为目标函数，参加每条路径携带货物总质量不能超过25kg的限制条件，使用基于遗传算法的MTSP模型。求解得出8条路径最短距离为480km，共需5名派送人员，派送方案如表2所示。比拟TSP得出方案与MTSP得出方案，发现MTSP得出方案明显优于TSP得出方案。于是采用最短路径为480km，共需5人，派送方案如表2所示的方案。针对问题二，仍然采用基于遗传算
3、法的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的派送方案。针对
4、问题三，在问题一与问题二的根底上，将派送员的派送时间由6h增加到8h，设计出新的派送方案。分别得出距离最短派送新派送方案所需人数为4人，距离仍为480km，新派送方案如表11所示；费用最少10条路径所需人数为4人，总费用仍为13873.7元，新派送方案如表13所示。关键词：多旅行商问题 遗传算法 MTSP模型 TSP模型一、问题重述目前，快递行业正蓬勃开展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进展派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进展送货，但是，太多的业务员意味着更多的派送费用。假定所有快件在早上
5、7点钟到达，早上9点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点处如图2，每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平行于坐标轴的折线。1请你运用有关数学建模的知识，给该公司提供一个合理的送货策略即需要多少业务员，每个业务员的运行线路，以与总的运行公里数；2如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km
6、/h，酬金2元/km，请为公司设计一个费用最省的策略；3如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？二、模型假设1、假设业务员送货期间的速度不受外界的影响；2、假设业务员的休息时间不包含在6小时中；3、假设每个派送点只经过一次，每名业务员的行进路线决定后就不得改变；4、假设假如其中一个业务员跑多条路线时，中间返回总部后取快件将快件装上车所花费的时间不计；5、假设各业务员之间的快件运送过程是相互独立的。三、符号说明符号符号意义符号符号意义旅行商经过对应弧度所花的费用初始种群规模遗传算法的一代种群交叉概率每条线路的完成时间变异概率配送点与配送点之间的实际距离从派送点到派送点再返
7、程的最省费用费用目标函数派送点所需货物的重量四、问题分析首先，此题要求用最少的业务员，最少的时间，派送完所有的快件所走的路程最短，并给出每个业务员的运行路线。且，故至少需要8条路线；考虑到求解最短路径，我们采用了两种方法：模型一是用遗传算法中的一个回路的TSP模型算出所有点最短的路线，并根据每个业务员的所用时间，携带质量，按照要求进展分段，得到一种送货方案并改良了遗传算法最终结果为业务员5个,业务员行走总路程为484kmh；模型二是用基于遗传算法的MTSP模型进展求解，也即在不考虑重量和时间的约束下，将MTSP问题转化为增加个结点的单旅行商问题，然后采用遗传算法，使算法能以较大的概率获得全局的
8、最优解：业务员5个，总路径长度480 km h.此题在加了速度和费用的前提下，要求花费最省的一种方案。固在MTSP问题的根底上，把目标函数设置为公司派送的总花费，且总花费为每点所要求业务员送达快件的质量与该点到路径上的前一些点直到原点的折线距离和3元/kmkg的乘积，加上路径中最后一个点到原点的乘积与2元/km的乘积，其中的距离为平行与坐标轴的总距离。由问题一的分析，先设置MTSP的路径数为8,9,10发现路径数为8时费用较高，所需要的派送员为5人；路径数为9时花费较大；路径数为10费用最少但所需派送人数为6人。而在10条路径以上时，花费明显增加，固此时就给公司提出了一个选择，是更侧重于考虑派
9、送员们的根底工资减少派送员的个数还是考虑由于运送路程和载重不同造成的花费最省。 此题条件上将前面所限定的每个业务员每天最多工作6小时改成了8小时。经过对问题一与问题二的研究，我们将会发现，这一条件的改变，对送货路径并没有太多影响，只是业务员工作的分配会发生变化，因为在解决前两问时由MTSP做出了多条路径后，计算出每条路径经派送所需要的时间，在题目所给的限制每个派送员一天最多工作时间以内，对路径分配到各个派送员的身上，固以此思路对派送员的人数进展确定，调整公司送货策略。五、模型的建立与求解在问题一中，要求在每个业务员每天平均工作时间不超过6小时且必须从早上9点钟开始派送，到当天17点之前即在8小
10、时之内派送完毕；以与每次出发最多能带25千克的重量。要求给该公司提供一个合理的送货策略,即当业务员数量最少且送货总距离最小时可得到比拟合理的送货策略。由于平均每天收到总重量为184.5千克，而业务员每次最多只能带25千克的重量，便可以确定出最少需要184.5/25=8条路线。据此，我们分别建立了TSP模型和MTSP模型，并采用遗传算法求得最终路径。5.1.1 遗传算法设计遗传算法Genetic Algorithm是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是由美国Michigan大学教授于1975年首先提出来的，并出版了颇有影响的专著
11、Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知。遗传算法是从代表问题可能潜在的解集的一个种群population开始的，而一个种群如此由经过基因gene编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现即基因型是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往
12、进展简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代generation演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度fitness大小选择selection个体，并借助于自然遗传学的遗传算子genetic operators进展组合交叉crossover和变异mutation，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码decoding，可以作为问题近似最优解或满意解。遗传算法的具体步骤如下：(初始化)确定种群规模、交叉概率、变异概率；设置终止进化准如此；随即生成个体作为初始种
13、群；置；(个体评价)计算或估计中各个个体的适应度；(种群进化) 1选择母体从中运用选择算子选择出对母体； 2交叉对所选择出对母体 ，依概率执行交叉，形成个中间个体； 3变异对个中间个体分别独立依概率执行变异，形成个候选个体； 4选择子代从上述所形成的个候选个体中依适应度选择出个个体组成新一代种群； (终止检验)如已满足终止准如此，如此输出中具有最大适应度的个体作为最优解，终止计算；否如此置并转； 由上一代种群生成新一代种群的过程可以用以下矩阵的形式表示其中表示单位阵：.我们把随机产生的路径作为初始种群，进展编码转化成二进制数串，数串的长度由我们定的精度来控制；接下来评价染色体数串的适应度，由适
14、应度评价函数来作为环境的角色，进展自然选择，接着依照染色体的适应度值进展新种群的复制，依照轮盘选择法，把染色体条数的数目设定为转动轮盘的次数，得到新种群的染色体组成；之后进展新种群的交配，结合突变概率得到最终新种群的染色体组成和新一代的相对实际值和适应度值，至此，已完成遗传算法的第一代流程，依次迭代，直至满足迭代次数得到最大目标函数值对应的染色体。 求解此题具体算法流程如图1：图1 遗传算法流程图5.1.2 模型一：模型的建立和求解旅行商问题TSP简称为TSP问题，是最根本的路线问题，该问题的本质是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径本钱。TSP问题的
15、描述十分简单, 简言之, 就是寻找一条最短的遍历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、 最短路径求解首先我们在模型准备阶段得到了距离矩阵，采用一个业务员携带快件从总部出发，运用遗传算法实现所有的快件到达送货点。用MATLAB软件编程来求解，程序见附录1.针对题目，我们将遗传算法初始化群体，遗传算法的总设计如图2所示：图2 TSP问题的遗传算法总体设计设定计算群体上每个个体的适
