快递公司送货策略
快递公司送货策略
摘要
本文是关于快递公司送货策略的优化设计问题,即在给定送货地点和给定的条件下,确定所需业务员人数,每个业务员的运行线路,总的运行公里数,以及费用最省的策略。 本文主要从最短路经和费用最省两个角度解决该问题,建立数据模型。对于问题一:以某业务员是否送货到某送货点建立0-1分布函数,以业务员的人数和总的运行公里数为目标函数,时间、货重等为约束条件建立多目标动态规划的数学模型,根据数学模型以五种方案用Excel进行筛选,算出总公里数及需要的业务员数量,进行比较可得出最优方案。对于问题二:由于业务员空载时与载货时的费用差异较大,可假设业务回公司的途中不送货。在模型一的基础上再建立0-1分布函数,以总费用为目标函数,约束条件会考虑到货重与路程的共同作用,同样用Excel进行筛选,得出一种优化方案。对于问题三:由于业务员工作时间的调整对总的运行路线的影响并不大,只需对业务员的数量以及各业务员的安排路线进行调整即可。
关键词:快递公司送货 最优化 分区送货策略模型 多目标动态规划 TSP模型
一、 问题的重述
目前,快递行业正蓬勃发展,为我们的生活带来更多方便。对于快递公司,为了保证快件能够在指定的时间内送达目的地,必须有足够的业务员进行送货,但是,太多的业务员意味着更多的派送费用。所以,最小化所需业务员人数及业务员总的运行公里数从而为公司节省人力和财力成为我们的研究目标。
假定所有快件在早上7点钟到达,早上9点钟开始派送,要求于当天17点之前必须派送完毕,每个业务员每天平均工作时间不超过6小时,在每个送货点停留的时间为10分钟,途中速度为25km/h,每次出发最多能带25千克的重量。为了计算方便,我们将快件一律用重量来衡量,平均每天收到总重量为千克,公司总部位于坐标原点处,送货点的位置和每个送货点的快件重量为已知,并且假设送货运行路线均为平行于坐标轴的折线。
1)给该公司提供一个合理的送货策略(即需要多少业务员,每个业务员的运行线路,以及总的运行公里数);
2)如果业务员携带快件时的速度是20km/h,获得酬金3元/kmkg;而不携带快件时的速度是30km/h,酬金2元/km,请为公司设计一个费用最省的策略;
3)如果可以延长业务员的工作时间到8小时,公司的送货策略将有何变化
将题中所给的数据整合成表一:
表一
最大载重量 | 25kg | 重载时速 | 20km/h |
途中的平均速度 | 25km/h | 重载酬金 | 3元/km*kg |
业务员工作时间上限 | 6h | 空载时速 | 30km/h |
每个送货点停留时间 | 10min | 空载酬金 | 2元/km |
备注 | 1、快件一律用重量来衡量 2、假定街道方向均平行于坐标轴 | ||
二、问题的分析
通过分析题目和整理题目数据,我们认为此题为lingo优化问题。
对于问题一,以某业务员是否送货到某送货点建立0-1分布函数,以业务员的人数和路线总公里数为多目标函数,时间、货重等为约束条件建立数学模型,根据数学模型用excel进行筛选,假设每个业务员只送货一次,可根据几个方案进行筛选,方案一:以任意两点的距离进行分区域排序筛选;方案二:以纵横坐标值之和由大到小进行筛选;方案三:以横坐标值由大到小进行筛选;方案四:以纵坐标值由大到小进行筛选;方案五:分别考虑横纵坐标对矩阵周长S的影响大小,以影响较大的一项作为筛选条件,由大到小依次进行筛选。此五种方案应为符合约束条件的最优方案,算出其总公里数及需要的业务员数量,进行比较,可得最优方案,最后再做适当的调整改进。
对于问题二,由于业务员空载时与载货时的费用差异较大,可假设业务员回公司的途中不送货。经分析讨论,可在模型一的基础上再建立0-1分布函数,以总费用为目标函数,约束条件有所改变,其中会考虑到货重与路程总数的共同作用。与模型一的求解一样,用excel进行筛选,由于考虑到货重与路程都与费用有关,又产生一种优化方案,方案一:以货物的轻重做参考由近到远依次筛选。以此方案的费用与模型一中五种方案的费用比较,选出最小的一组,作为最优方案。问题三中业务员工作时间的调整对总的运行路线的影响并不大,只需对业务员的数量以及各业务员的安排路线进行调整即可。
三、模型的假设与符号说明
1)模型的假设:
1.假设业务员送完货后必须再回公司报到。
2.假设业务员送货期间行进速度不受外界影响,且业务员的休息时间不包括在最大工作时间6个小时内。
3.假设业务员送货运行路线均为平行于坐标轴的折线。
4.假设题目中送货点位置与所需货重准确无误。
5.假设业务员人数不限制。
6.假设业务员均能且必须把每个送货点的货物送到接受人手中。
2)符号说明:
符号 | 说明 | 单位 |
N | 业务员数量 | 人 |
n | 送货路线数量 | \ |
J | 送货点中的任意一点 | \ |
I | 送货路线中的任意一条 | \ |
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)
满足要求的路程最短而且业务员数量最少即:
约束条件:
①载重约束:
②时间约束:
距离最优:可以对送货点进行归类筛选。
1.方案一:
建立分区送货策略模型对送货点坐标进行不同区域的分类,以各点与中心点之间距离为分类标准,从短到远,对区域大小加以送货重量限制即各区域中所有送货点的快件量之和小于或等于
用分析递推方法求解划分区域,确定离原点最远的点
先选取第
得到方案一的各区域送货点、总的运行公里数、总送货时间。
2.方案二:
对所有送货点的坐标求和:
用Excel对所有
3.方案三:
以送货点的横坐标由大到小进行筛选。可得出下表:
路线 | 送货点 | 路程 | 时间 |
路线一 | 15、23、28、29、30 | 96 | |
路线二 | 21、22、27 | 70 | |
路线三 | 9、11、24、26 | 78 | |
路线四 | 10、19、25 | 58 | |
路线五 | 8、12、13、14 | 52 | |
路线六 | 4、7、18、20 | 66 | |
路线七 | 1、3、5、17 | 42 | |
路线 八 | 2、6、16 | 36 | |
总计 | 498 | ||
表中可知此方案总运行公里数为498公里,共需八次送货,由时间约束可知:路线二与路线七、路线三和路线八、路线四和路线五均可由一个业务员分两次送,所以此方案只需5个业务员。
4.方案四:
以送货点的纵坐标由大到小进行筛选。可得出下表:
路程 | 送货点 | 路程 | 时间 |
路线一 | 28 24 17 30 9 | 96 | |
路线二 | 18 26 16 14 | 74 | |
路线三 | 29 20 25 23 | 86 | |
路线四 | 27 19 5 | 68 | |
路线五 | 7 13 15 6 4 | 56 | |
路线六 | 8 12 2 | 40 | |
路线七 | 21 3 11 1 | 54 | |
路线八 | 10 22 | 42 | |
总计 | 516 | ||
表中可知此方案总运行公里数为516公里,共需八次送货,有时间约束可知:路线二与路线八、路线四与路线六、路线五与路线七均可由一个业务员分两次送,所以此方案只需5个业务员。
5.方案五:
对坐标
用模型TSP求解所有方案送货点之间最优访问路径安排,得到方案五总运行路程最短。选取方案五,安排5位业务员。
得到线路:
①各业务员路线安排图:
②各业务员人数、时间安排表:
3)问题二模型:
假设业务员在送完最远点后的返回途中不送货,并假设业务员送货路线不走回头路(送货工程中不往横纵坐标轴的反方向走)。依据题目条件可知我们必需把业务员的酬金越少越好作为第一目标,其次再考虑总路程的多少。经分析,无论业务员怎样送货,他们载货过程中所得总酬金不变,都为所有送货点到原点(公司坐标)的酬金。则所有业务员载货时的总酬金为:
因为返回过程中不送货,所以业务员返回过程中所得的酬金即为其空载的酬金,则所有业务员空载时的总酬金为:
因此,所有业务员整天的总酬金:
可建立动态规划模型如下:
目标: min = +
约束:
最远送货点约束:
载重约束:
总载重约束: 25n>
时间约束: <6
由于载货过程中所得总酬金不变,所以只需考虑业务员空载时的总酬金,又空载时在总酬金只与每一天线路的最远点有关,所以我们应使尽量多的路线的最远点靠近原点。则必须同时考虑货物的重量和路程,先把货物重且近的送货点送完,依次筛选,最后送货物轻及远的,因此我们得到一优化方案,即以货物的轻重做参考由近到远依次筛选。可得出下表:
路线 | 送货点 | 半路程 | 最远点到原点距离 | 时间 |
路线一 | 2 1 7 9 | 19 | 16 | |
路线二 | 10 3 4 5 8 | 25 | 14 | |
路线三 | 12 19 11 | 29 | 27 | |
路线四 | 22 21 13 17 | 40 | 27 | |
路线五 | 20 14 16 6 | 26 | 22 | |
路线六 | 27 26 23 | 44 | 37 | |
路线七 | 25 29 28 | 45 | 44 | |
路线八 | 24 18 30 15 | 47 | 46 | |
总计 | 275 | 233 | ||
对上述路线进行调整,可得出如下安排:
路线一:原点——1——2——7——9——原点 828
路线二:原点——3——4——5——8——10——原点
路线三:原点——12——19——11——原点
路线四:原点——22——21——13——17——原点 2038
路线五:原点——14——20——16——6——原点
路线六:原点——27——26——23——原点
路线七:原点——2 5——29——28——原点
路线八:原点——18——24——30——15——原点
经计算分析得到最优路线安排如上,其总酬金为元。总运行公里数为550km,需业务员6个。
另外,考虑不回送策略,可得到一方案如下:
路线 | 送货点 | 路程 | 最远点到原点距离 | 时间 |
路线一 | 1 3 8 | 30 | 15 | |
路线二 | 2 4 7 14 15 | 56 | 28 | |
路线三 | 6 5 20 18 | 56 | 28 | |
路线四 | 16 17 24 | 68 | 34 | |
路线五 | 9 13 19 26 | 74 | 37 | |
路线六 | 10 12 15 23 | 72 | 36 | |
路线七 | 11 21 29 30 | 92 | 46 | |
路线八 | 22 27 28 | 88 | 44 | |
| 总计 | 536 | 268 | |
载重总酬金 | 元 | |||
空载总酬金 | 536元 | 总公里数 | 536km | |
总酬金 | 元 | 业务员 | 6个 | |
上表中总酬金为元比前一种方案要少,业务员及总公里数都占优势,这就是问题二的最优方案,运行路线如下:
路线一:原点——1——3——8——原点
路线二:原点——2——4——7——14——15——原点
路线三:原点——6——5——20——18——原点
路线四:原点——16——17——24——原点
路线五:原点——9——13——19——26——原点
路线六:原点——10——12——15——23——原点
路线七:原点——11——21——29——30——原点
路线八:原点——22——27——28——原点
下图为业务员送货路线图:
4)问题三模型:
当工作时间调至八小时时,无论对总公里数还是总酬金都没有影响,只需对业务员的多少进行改进即可,模型一中的最优方案(即方案五)的路线一、三、八,路线二、六、七,路线四、五 均可由一个以业务员分次送货,所以总共只需3个业务员。
五、模型的评价与改进
1)模型的优点:
1.模型系统的给出了业务员的调配方案,便于指导工作实践。
2.模型简单明了,容易理解与灵活应用。
3.模型的方法和思想对其他类型也适合,易于推广到其他领域。
2)模型的缺点:
1.模型给出的约束条件可能也有不太现实的。
2.对街道的方向,客户的快件量的假设有待进一步改进。
3)模型的推广:
1.本模型不但适合于快递公司送货问题,还是用于一般的送货以及运输问题,只需要稍
微改动模型即可。
2.建模的方法和思想可以推广到其他类型,如车辆调度问题等。
参考文献:
【1】姜启源、谢金星、叶俊编,数学模型-3版,北京,高等教育出版社,
【4】Excel函数应用教程
本文来源:https://www.2haoxitong.net/k/doc/ba6f35d6657d27284b73f242336c1eb91b3733b5.html
文档为doc格式