快递运输决策问题建模论文

1井冈山大学2011年“井冈杯”数学建模竞赛论文题目：快递运输决策问题（B）指导老师：王志伟参赛队员姓名：王祥鹿专业：10级教技一班学号：100915039姓名：蒋向香专业：10级软件二班学号：100521037姓名：梁筱专业：10级数本一班学号：100511019联系方式：18970672155，18079605389，151708654682012年07月02日2快递送货策略问题摘要本文是关于快递公司送货策略的优化设计问题，即在给定的条件下，确定所需业务员人数，每个业务员的运行线路，总的运行公里数，以及费用最省的策略。本文主要从最短路经和费用最省两个角度解决该问题，建立数据模型。对于问题一：这是一个多目标动态求解问题，只需给该公司提供一个合理的送货策略，不考虑业务员所跑路程与报酬的关系以及工作时间与报酬的关系。因此先以某业务员是否送货到某送货点建立10分布函数，以业务员的人数和总的运行公里数为目标函数，时间、货重等为约束条件建立多目标动态规划的数学模型，然后根据数学模型以五种方案用Excel进行筛选，算出总公里数和需要的业务员数量，最后用模型TSP求解所有方案送货点之间最优访问路径安排，得到方案五总运行路程最短。则问题一的最优解为方案五，安排5位业务员。对于问题二：由于业务员空载时与载货时的费用差异较大，可假设业务员回公司的途中不送货。又由于载货过程中所得总酬金不变，所以只需考虑业务员空载时的总酬金，而空载时在总酬金只与每一天线路的最远点有关，所以应使尽量多的路线的最远点靠近原点。则必须同时考虑货物的重量和路程，先把货物重且近的送货点送完，依次筛选，最后送货物轻及远的，因此得到一优化方案，即以货物的轻重做参考由近到远依次筛选。在模型一的基础上再建立10分布函数，以总费用为目标函数，约束条件会考虑到货重与路程的共同作用，同样用Excel进行筛选，得出一种优化方案。另外考虑不回送的策略得到另外一种优化方案，经过比较得，第二种方案总酬金更少，总公里数和业务员皆更有优势，则问题二的最优解为第二种方案。总酬金为7.13750元，总公里数为536公里，所需业务员为6人。对于问题三：当工作时间调至八小时时，无论对总公里数还是总酬金都没有影响，只需对业务员的多少进行改进即可，于是我们将模型一中的最优方案（即方案五）改进，即对路线和人员的安排进行调整，得总共只需3个业务员。最后对模型进行评价与改进，该模型可适用于一般的送货及货物运输问题，而且该模型的思想和方法可以推广到其他类问题，如车辆调度问题等。关键词快递公司送货最优化分区送货策略模型多目标动态规划TSP模型3一、问题的重述目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。所以，最小化所需业务员人数及业务员总的运行公里数从而为公司节省人力和财力成为我们的研究目标。假定所有快件在早上7点钟到达，早上9点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为hkm/25，每次出发最多能带kg25的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为kg5.184，公司总部位于坐标原点处，送货点的位置和每个送货点的快件重量为已知，并且假设送货运行路线均为平行于坐标轴的折线。1）给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；2）如果业务员携带快件时的速度是hkm/20，获得酬金kgkm/3元；而不携带快件时的速度是hkm/30，酬金km/2元，请为公司设计一个费用最省的策略；3）如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？（图中表格和坐标图见附录1）将题中所给的数据整合成表1：最大载重量kg25重载时速hkm/20途中的平均速度hkm/25重载酬金kgkm/3元业务员工作时间上限h6空载时速hkm/30每个送货点停留时间min10空载酬金km/2元备注1、快件一律用重量来衡量2、假定街道方向均平行于坐标轴表格1数据整理4二、问题的分析快递公司平均每天要送出总重量为kg5.184的邮件，每个人的工作时间每天不超过6小时，且每个人的最大负重是kg25，由38.7255.184,可知至少需要8条路线对这些邮件进行运送。对于问题一，以某业务员是否送货到某送货点建立10分布函数，以业务员的人数和路线总公里数为多目标函数，时间、货重等为约束条件建立数学模型，根据数学模型用Excel进行筛选，假设每个业务员只送货一次，可根据几个方案进行筛选：方案一：以任意两点的距离进行分区域排序筛选；方案二：以纵横坐标值之和由大到小进行筛选；方案三：以横坐标值由大到小进行筛选；方案四：以纵坐标值由大到小进行筛选；方案五：分别考虑横纵坐标对矩阵周长S的影响大小，以影响较大的一项作为筛选条件，由大到小依次进行筛选。此五种方案应为符合约束条件的最优方案，算出其总公里数及需要的业务员数量，进行比较，可得最优方案，最后再做适当的调整改进。对于问题二，由于业务员空载时与载货时的费用差异较大，可假设业务员回公司的途中不送货。经分析讨论，可在问题一的模型基础上再建立10分布函数，以总费用为目标函数，约束条件有所改变，其中会考虑到货重与路程总数的共同作用。与问题一的模型求解一样，用Excel进行筛选，由于考虑到货重与路程都与费用有关，又产生一种优化方案：以货物的轻重做参考由近到远依次筛选。以此方案的费用与问题一中五种方案的费用比较，选出最小的一组，作为最优方案。问题三中业务员工作时间的调整对总的运行路线的影响并不大，只需对业务员的数量以及各业务员的安排路线进行调整即可。三、模型的假设与符号说明1）模型的假设：1.业务员送完货后必须再回公司报到。2.业务员送货期间行进速度不受外界影响，且业务员的休息时间不包括在最大工作时间6个小时内。3.业务员送货运行路线均为平行于坐标轴的折线。4.题目中送货点位置与所需货重准确无误。5.每个业务员送快递是独立的，每人之间互不影响。6.业务员人数不限制。7.业务员均能且必须把每个送货点的货物送到接受人手中。8.业务员派送完毕，返回公司所花时间也为工作时间。52）符号说明：N:业务员数量n:送货路线数量J:送货点中的任意一点I:送货路线中的任意一条ix:j点横坐标iy:j点纵坐标ijb:以第i条路线中是否有j点为决策的0-1分布函数ijp:以j点是否为i条线路最远点为决策的0-1分布函数jT:J送货点的货物重量1F:所有业务员载货时的总酬金2F:所有业务员空载时的总酬金F:所有业务员一天的总酬金L:第i点到中心点的距离iC:第i点的横纵坐标值之和四、模型的建立与求解（一）、模型准备假设有n条路线，第i点坐标为jiyx,,货重jT。建立0-1分布函数ijb、ijp使得：点点即业务员送货到达条路线中有第点点即业务员送货不到条路线中没有第ijiijibij10点条业务员送货路线最远点是第第点条业务员送货路线最远点不是第第ijijpij106（二）问题一模型：对于问题一，是一个多目标动态求解问题，只需给该公司提供一个合理的送货策略，我们不考虑业务员所跑路程与报酬的关系和工作时间与报酬的关系，找出满足问题一条件的几种策略。需满足的条件有：条件1：每个业务员每天平均工作时间不超过6小时。条件2：每次出发最多能带kg25的重量。对于问题一要求，首先考虑总的运行公里数。由于送货运行路线均为平行于坐标轴的折线，在此模型中，将两点之间的路线权值赋为这两点横纵坐标之和，从原点到),(yxA点和从A点到原点距离都为yx（不考虑回走问题，即考虑方向0,0AA）满足要求的路程最短而且业务员数量最少即：njiiiijyxp1301)(**2minNmin约束条件：1）载重约束：25*301jjijTb2）时间约束：6625*max*2*max*2301jijijjijibbybx使得距离最优：可以对送货点进行归类筛选。1.方案一：建立分区送货策略模型对送货点坐标进行不同区域的分类，以各点与中心点之间距离为分类标准，从短到远，对区域大小加以送货重量限制即各区域中所有送货点的快件量之和小于或等于kg25。用分析递推方法求解划分区域，确定离原点最远的点中中中yxA,为第一区域，找到与之距离最近的点iA，如果总快件量小于kg25，则继续找离iA最近的7点，由近到远，快件量之和小于kg25的选取，直到最远的一个送货点结束。即先选取第30个送货点，与30最近的L是第29个送货点，总快件量小于kg25，继续选取离29最近的点28，总快件量没有超过最大负重，继续选取离28最近的23，选取离23最近的15，此时总快件量是kg1.24，再继续选取就会超出最大负重，选择返回。中中yyxxLii得到方案一的各区域送货点、总的运行公里数、总送货时间见表2：方案一区域送货点路程时间第一区域15、23、28、29、301004.68第二区域8、26、27763.54第三区域9、14、24、25743.39第四区域6、16、17、18、20703.16第五区域10、11、22、32542.83第六区域7、13、19542.67第七区域3、4、12422.18第八区域1、2、5281.62总运行498公里总时间24.07表格2方案一路线、总路程和时间2.方案二：以纵横坐标值之和由大到小进行筛选。对所有送货点的坐标求和：iiiyxC用Excel对所有iC进行排序筛选，以最大的iC为第一个送货点，确定为第一条送货路线，从剩下的点中选取最大的，如果2点总快件量小于最大负重，则放入这一送货路线，如果大于最大负重kg25，则不放入这一路线，继续选取剩余数中最大的，一直到最小的一点结束。8得到方案二的各区域送货点、总的运行公里数、总送货时间见表3：方案二路程送货点路程时间路线一15、23、28、29、30964.68路线二26、27、8763.54路线三18、24、25683.22路线四9、14、17、19、21804.04路线五11、13、16、20、22743.8路线六5、7、12502.5路线七3、4、6、10442.43路线八1、2160.98总运行504公里总时间25.19表格3方案二各路线、路程和时间3.方案三：以送货点的横坐标由大到小进行筛选。以最大的横坐标的点为第一个送货点，确定为第一条送货路线，从剩下的点中选取横坐标最大的，如果2点总快件量小于最大负重，则放入这一送货路线，如果大于最大负重kg25，则不放入这一路线，继续选取剩余数中横坐标最大的，一直到横坐标最小的一点结束。得到方案三的各区域送货点、总的运行公里数、总送货时间见表4：方案三路线送货点路程时间路线一15、23、28、29、30964.68路线二21、22、27703.3路线三9、11、24、26783.79路线四10、19、25582.82路线五8、12、13、14522.75路线六4、7、18、20663.31路线七1、3、5、17422.35路线八2、6、16361.94总运行498公里总时间24.94表格4方案三路线、路程和时间9表中可知此方案总运行公里数为498公里，共需8次送货，由时间约束可知：路线二与路线七、路线三和路线八、路线四和路线五均可由一个业务员分两次送，所以此方案只需5个业务员。4.方案四：以送货点的纵坐标由大到小进行筛选。以纵坐标最大的为第一个送货点，确定为第一条送货路线，从剩下的点中选取纵坐标最大的，如果2点总快件量小于最大负重，则放入这一送货路线，如果大于最大负重kg25，则不放入这一路线，继续选取剩余数中纵坐标最大的，一直到纵坐标最小的一点结束。得到方案四的各区域送货点、总的运行公里数、总送货时间见