快递公司送货策略

1快递公司送货策略摘要本文是关于快递公司送货策略的优化设计问题，即在给定送货地点和给定的条件下，确定所需业务员人数，每个业务员的运行线路，总的运行公里数，以及费用最省的策略。本文主要从最短路经和费用最省两个角度解决该问题，建立数据模型。对于问题一：以某业务员是否送货到某送货点建立0-1分布函数，以业务员的人数和总的运行公里数为目标函数，时间、货重等为约束条件建立多目标动态规划的数学模型，根据数学模型以五种方案用Excel进行筛选，算出总公里数及需要的业务员数量，进行比较可得出最优方案。对于问题二：由于业务员空载时与载货时的费用差异较大，可假设业务回公司的途中不送货。在模型一的基础上再建立0-1分布函数，以总费用为目标函数，约束条件会考虑到货重与路程的共同作用，同样用Excel进行筛选，得出一种优化方案。对于问题三：由于业务员工作时间的调整对总的运行路线的影响并不大，只需对业务员的数量以及各业务员的安排路线进行调整即可。关键词：快递公司送货最优化分区送货策略模型多目标动态规划TSP模型一、问题的重述目前，快递行业正蓬勃发展，为我们的生活带来更多方便。对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。所以，最小化所需业务员人数及业务员总的运行公里数从而为公司节省人力和财力成为我们的研究目标。假定所有快件在早上7点钟到达，早上9点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点处，送货点的位置和每个送货点的快件重量为已知，并且假设送货运行路线均为平行于坐标轴的折线。1）给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；2）如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略；3）如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？将题中所给的数据整合成表一：表一最大载重量25kg重载时速20km/h途中的平均速度25km/h重载酬金3元/km*kg业务员工作时间上限6h空载时速30km/h每个送货点停留时间10min空载酬金2元/km2备注1、快件一律用重量来衡量2、假定街道方向均平行于坐标轴二、问题的分析通过分析题目和整理题目数据，我们认为此题为lingo优化问题。对于问题一，以某业务员是否送货到某送货点建立0-1分布函数，以业务员的人数和路线总公里数为多目标函数，时间、货重等为约束条件建立数学模型，根据数学模型用excel进行筛选，假设每个业务员只送货一次，可根据几个方案进行筛选，方案一：以任意两点的距离进行分区域排序筛选；方案二：以纵横坐标值之和由大到小进行筛选；方案三：以横坐标值由大到小进行筛选；方案四：以纵坐标值由大到小进行筛选；方案五：分别考虑横纵坐标对矩阵周长S的影响大小，以影响较大的一项作为筛选条件，由大到小依次进行筛选。此五种方案应为符合约束条件的最优方案，算出其总公里数及需要的业务员数量，进行比较，可得最优方案，最后再做适当的调整改进。对于问题二，由于业务员空载时与载货时的费用差异较大，可假设业务员回公司的途中不送货。经分析讨论，可在模型一的基础上再建立0-1分布函数，以总费用为目标函数，约束条件有所改变，其中会考虑到货重与路程总数的共同作用。与模型一的求解一样，用excel进行筛选，由于考虑到货重与路程都与费用有关，又产生一种优化方案，方案一：以货物的轻重做参考由近到远依次筛选。以此方案的费用与模型一中五种方案的费用比较，选出最小的一组，作为最优方案。问题三中业务员工作时间的调整对总的运行路线的影响并不大，只需对业务员的数量以及各业务员的安排路线进行调整即可。三、模型的假设与符号说明1）模型的假设：1.假设业务员送完货后必须再回公司报到。2.假设业务员送货期间行进速度不受外界影响，且业务员的休息时间不包括在最大工作时间6个小时内。3.假设业务员送货运行路线均为平行于坐标轴的折线。4.假设题目中送货点位置与所需货重准确无误。5.假设业务员人数不限制。6.假设业务员均能且必须把每个送货点的货物送到接受人手中。2）符号说明：符号说明单位N业务员数量人n送货路线数量\J送货点中的任意一点\3I送货路线中的任意一条\错误!未找到引用源。j点横坐标\错误!未找到引用源。j点纵坐标\错误!未找到引用源。以第i条路线中是否有j点为决策的0-1分布函数\错误!未找到引用源。以j点是否为i条线路最远点为决策的0-1分布函数\j送货点的货物重量Kg所有业务员载货时的总酬金元错误!未找到引用源。所有业务员空载时的总酬金元F所有业务员一天的总酬金元L第i点到中心点的距离\Ci第i点的横纵坐标值之和\四、模型的建立与求解1）模型准备假设有n条路线，第j点坐标为（错误!未找到引用源。建立0-1分布函数错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。2）问题一模型：对于问题一，是一个多目标动态求解问题，只需给该公司提供一个合理的送货策略，我们不考虑业务员所跑路程与报酬的关系和工作时间与报酬的关系，找出满足问题一条件的几种策略。（条件①每个业务员每天平均工作时间不超过6小时，条件②每次出发最多能带25千克的重量）对于问题一要求，首先考虑总的运行公里数。由于送货运行路线均为平行于坐标轴的折线，在此模型中，将两点之间的路线权值赋为这两点横纵坐标之和，从原点到A（x，y）点和从A点到原点距离都为x+y（不考虑回走问题，即考虑方向O→A，A→O）满足要求的路程最短而且业务员数量最少即：4nkiiiijyxp1301)(**2minNmin约束条件：①载重约束：25*301jjijTb②时间约束：6625*max*2*max*2301jijijjijibbybx距离最优：可以对送货点进行归类筛选。1.方案一：建立分区送货策略模型对送货点坐标进行不同区域的分类，以各点与中心点之间距离为分类标准，从短到远，对区域大小加以送货重量限制即各区域中所有送货点的快件量之和小于或等于kg25。用分析递推方法求解划分区域，确定离原点最远的点中中中yxA,为第一区域，找到与之距离最近的点iA，如果总快件量小于kg25，则继续找离iA最近的点，由近到远，快件量之和小于kg25的选取，直到最远的一个送货点结束。先选取第30个送货点，与30最近的L是第29个送货点，总快件量小于kg25，继续选取离29最近的点28，总快件量没有超过最大负重，继续选取离28最近的23，选取离23最近的15，此时总快件量是kg1.24，再继续选取就会超出最大负重，选择返回。中中yyxxLii得到方案一的各区域送货点、总的运行公里数、总送货时间。52.方案二：对所有送货点的坐标求和：iiiyxC用Excel对所有iC进行排序筛选，以最大的iC最为第一个送货点，确定为第一条送货路线，从剩下的点中选取最大的，如果2点总快件量小于最大负重，则放这一送货路线，如果大于最大负重kg25，则不放入这一路线，继续选取剩余数中最大的，一直到最小的一点结束。3.方案三：以送货点的横坐标由大到小进行筛选。可得出下表：路线送货点路程时间路线一15、23、28、29、30964.68路线二21、22、27703.3路线三9、11、24、26783.79路线四10、19、25582.82路线五8、12、13、14522.756路线六4、7、18、20663.31路线七1、3、5、17422.35路线八2、6、16361.94总计49824.94表中可知此方案总运行公里数为498公里，共需八次送货，由时间约束可知：路线二与路线七、路线三和路线八、路线四和路线五均可由一个业务员分两次送，所以此方案只需5个业务员。4.方案四：以送货点的纵坐标由大到小进行筛选。可得出下表：路程送货点路程时间路线一282417309964.68路线二18261614743.63路线三29202523864.11路线四27195683.22路线五7131564563.08路线六8122402.1路线七213111542.83路线八1022422.02总计51625.67表中可知此方案总运行公里数为516公里，共需八次送货，有时间约束可知：路线二与路线八、路线四与路线六、路线五与路线七均可由一个业务员分两次送，所以此方案只需5个业务员。5.方案五：对坐标x和y同时考虑，建立矩形模型，考虑矩阵周长s，当yx时，x边的变化对s影响较大，当xy时，y边的变化对s影响较大。矩阵周长s直接关系到运行路程的大小。用Excel对x和y一起排序，从最大x开始，当yx时以x为标准从大到小选取送货点，当xy时以y为标准从大到小选取送货点，当xy时，选iiyxmin，直到总快件量大于最大负重。7用模型TSP求解所有方案送货点之间最优访问路径安排，得到方案五总运行路程最短。选取方案五，安排5位业务员。得到线路：原点原点2928302311原点原点272122原点原点15262414原点原点19181716原点原点89102520原点原点12135原点原点3746原点原点21①各业务员路线安排图：8②各020406080100120一月二月三月四月123业务员人数、时间安排表：业务员经过送货点数最远送货点经历时间总路程运送重量15304.83310024.123263.547624.334243.3876822.445183.1535824.454322.8275423.663192.665420.873122.184224.28351.622820.7总计3024.2482184.53）问题二模型:假设业务员在送完最远点后的返回途中不送货，并假设业务员送货路线不走9回头路（送货工程中不往横纵坐标轴的反方向走）。依据题目条件可知我们必需把业务员的酬金越少越好作为第一目标，其次再考虑总路程的多少。经分析，无论业务员怎样送货，他们载货过程中所得总酬金不变，都为所有送货点到原点（公司坐标）的酬金。则所有业务员载货时的总酬金为：因为返回过程中不送货，所以业务员返回过程中所得的酬金即为其空载的酬金，则所有业务员空载时的总酬金为：因此，所有业务员整天的总酬金：可建立动态规划模型如下：目标：min=+约束：最远送货点约束：载重约束：总载重约束：25n184.5时间约束：6由于载货过程中所得总酬金不变，所以只需考虑业务员空载时的总酬金，又空载时在总酬金只与每一天线路的最远点有关，所以我们应使尽量多的路线的最远点靠近原点。则必须同时考虑货物的重量和路程，先把货物重且近的送货点送完，依次筛选，最后送货物轻及远的，因此我们得到一优化方案，即以货物的轻重做参考由近到远依次筛选。可得出下表：路线送货点半路程最远点到原点距离时间路线一217919162.18路线二10345825142.84路线三12191129272.82路线四2221131740273.87路线五201416626222.75路线六27262344374.52路线七25292845444.1路线八2418301547464.43总计27523327.51对上述路线进行调整，可得出如下安排：路线一：原点——1——2——7——9——原点828路线二：原点——3——4——5——8——10——原点1527.6路线三：原点——12——19——11——原点1701.210路线四：原点——22——21——13——17——原点2038路线五：原点——14——20——16——6——原点1392.4路线六：原点——27——26——23—