快递公司送货策略优化模型

1、快递公司送货策略优化模型本文针对快递公司的送货策略问题，在给定送货地点及给定送货区域的条件 下，建立了人员分配和路径优化的数学模型。在这个题hl小两点z间的路线权值 赋为这两点横纵坐标z和，如此便可以用matlab求出任意两配送点间的距离。针对问题一，以某业务员是否送货到某点建立01分布苗数，以业务员总 的运行公里数为口标函数，时间、货重等为约束条件建立整数规划模型。然后我 们采用了五种分区策略，通过matlab编程求得五种策略下的最少人员和最短路 程，并给出了每个业务员每天送货的路线和所需时间等。通过对五种策略的分析 比较，得出了一个相对较优的矩形分区方法，此分区下的优化模型结果为：需要 5

2、个业务员，总行程是482km,总时间是24. 28h。针对问题二，在问题一的条件下，以给业务员的酬金最少为冃标，结合业务 员的安排和路线的选择，建立了多目标动态规划。运用matlab编程求得业务 员酬金最少的方案。结果显示第二种策略（竖条形分区）最优：共安排了 6个业 务员，跑8条路线，其屮1号业务员跑的路线为0-3-12-15-23-0, 2号业务员跑的 路线为0-27-29-30-0, 3号业务员的路线为0-16-17-24-18-0, 4号业务员的路线为 0-19-26-28-0, 5号业务员的路线为0-1-2-6-0 w 0-5-20-25-14-0, 6号业务员的路线为 0-10-2

3、2-21-11-0和047-1389-0。这样，总用时间是26.3小时,运送邮件总重184. 5kg, 总费用为14567.7 7lo针对问题三，因为所需的总时间不变，而每个业务员的工作时间增加为8 小时，所以对其工作量重新安排，可将业务员减少到4人。关键字：快递公司送货最优化整数规划分区策略一、问题重述目前，快递行业正蓬勃发展，为我们的生活带來更多方便。一般地，所有快 件到达某地后，先集屮存放在总部，然后由业务员分别进行派送；对于快递公司， 为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货， 但是，太多的业务员意味着更多的派送费用。假定所有快件在早上7点钟到达，早上9点钟

4、开始派送，要求丁当天17点 之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点 停留的时间为10分钟，途屮速度为25km/h,每次出发最多能带25千克的重量。 为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千 克，公司总部位于坐标原点处（如图2）,每个送货点的位置和快件重量见卜表, 并h假设送货运行路线均为平行于坐标轴的折线。（1）请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需 要多少业务员，每个业务员的运行线路，以及总的运行公里数）；（2）如果业务员携带快件时的速度是20km/h,获得酬金3元/km-kg；而不携带 快件时的速度

5、是30knvh,酬金2兀/km,请为公司设计一个费用最省的策略；（3）如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？二. 模型的假设1.每次业务员从一个区送货回来，再配货的时间为0,即不花时间。2业务员不会发生意外，即不会意外的花一些时间。3.业务员中途不休息。4 街道平行于坐标轴。5. 业务员在中途除了送货之外没有别的时间耽搁。6. 业务员不会屮转邮件，即不会屮途交给另一个业务员。7. 每个送货点每天的邮件量基本相同。8. 在业务员出发后到达邮局的邮件均算入第二天的邮件量9 业务员送完货后必须到公司报到。三、符号说明_ 1通过i线路/点/7 = |0不通过i线路/点$第i线

6、离公司最近的点；q第i线送完货的终点；dgb）第i线路a点到b点的距离;心第i线路送完货并返回公司的总路程;叫第i线路屮j点的快件重量；tt序号为i送货点的送货量w,业务员总负重费用巴业务员总空载费用w业务员总费用1.当第k次送货往第i点送快件时0.当第k次送货不往第i点送快件时1当第k次送货选择第i点为最远点时* 0.当第k次送货不选择i点为最远点吋问题一：运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少 业务员，每个业务员的运行线路，以及总的运行公里数）；（一）模型分析在问题一中，只要求给出一个合理的送货策略，并没有涉及到业务员的工 资问题，故只要满足要求每个业务员每天平

7、均工作时间不超过6小时且必须 从早上9点钟开始派送，到当天17点之前（即在8小时之内）派送完毕；以及 每次出发最多能带25千克的重量。由于 詈卜* ，故最少需要&条路线。如果将两点之间的路线权值赋为这两点横纵坐标之和，比如a（e，x）,（兀2，）2）两点，则权值为2 =1 %）-x2 i +1- y2 i o那么便可以用matlab求出任意两配送点间的距离，即权重（如表1,求解程序见附件一）。表1任意两配送点间的距离求得各点间的距离后，我们根据快件量，采用了五种（横条形、竖条形、矩 形、扇形、对角形）策略对30个客户进行分区，将分区的每个小区内的有限个 送货点进行组合。以人员最少和路径

8、最短为h标，考虑每个业务员的最大负重量 不超过25血和工作时间不超过6小时两个约束条件，我们建立出了一个整数规 划模型來求解。（二）模型的建立和求解经过计算，我们得到，从公司到最远点的来回时间没有超过6小时，因此， 这个问题的主要约束条件是快件的重量，于是，我们对快件量进行了不同方案的 分区，以总路程的最少为日标函数，建立了以下的模型。整数规划模型的建立:0-1整数变量1通过i线路点a=<ij o不通过i线路7点8(2)口标函数：min si=l(© = bj + q +n工 dgb)i=l约束条件:7=1<25（第i线路j送货点的巫量总和）为咲+（勺三）"（业

9、务员对1条线路送货的总时间不超过6小时） /=!冃运用这个数学模型对下面5个方案进行求解。模型求解（分区方案）方案一：横条形分区将送货地点横向划分成四个区，使得每个区的送货量基本均匀。每个区的货量大概为184.54= 46.125焰。（分区图如图1）图1横条分区图在每个分区内，要使在重量不超过25kg的前提下达到路程最近，于是乂得 出了如图2的8条优化路径图。和走的路线，但走的首尾顺序可以任意。再有上面的整数线性规划模型，用编程（见附件二），得到优化路径方案, 见表2：送货线最优路径线路路程(km)线路所花时间(h)10-1-2-6-0221. 3820-10-22-21-11-0542. 8

10、26730-4-7-13-8-9-0442.593340-3-12-15-23-0723. 546750-5-20-25-14-0582. 986760-27-29-30-0924. 1870-16-17-24-18-0683. 386780-19-26-28-0884. 02总计49824.9201根据上表的线路分析，可得最终结果：需要5个业务员，具体安排见表3送货线路总行程总耗时业务员1号2号3号4号5号0-27-29-30-0 0-1-2-6-00-19-26-28-0 0-3-12-15-23-00-4-7-13-8-9-00-16-17-24-18-00-10-22-21-11-00

11、-5-20-25-14-0线路行线路耗程时1145. 56884. 02723. 54671125. 981125.8134表2横条分区路径表49824.9201表3横条分区业务员路线分配表方案二：竖条形分区将送货地点径向划分成竖条行区域，使得每个区的送货量基本相等，在46kg 左右。(竖条形分区图如图3)竖行分区优化路径如图4：和走的路线，但走的首尾顺序可以任意。再有上曲的整数线性规划模型，用编程(见附件二)，得到优化路径方案见表4送货线最优路径线路路程(km)线路所花时间(h)10-1-3-2-0201.320-6-5-16-17-4-0502. 833330-9-12-13-8-0462

12、. 506740-7-20-18-14-0562. 906750-10-11-15-26-0743. 626760-19-25-24-0683. 2270-22-21-27-0703. 380-23-30-28-29-0984. 5867总计48224. 2801表4竖形分区路径表根据上表的线路分析，可得最终结果：需要5个业务员，具体安排见表5业务员送货线路线路行线路耗总行程总耗时程时1号0-23-30-28-29-0984.58672号0-1-3-2-00-10-11-15-26-0944.92673号0-9-12-13-8-00-22-21-27-01165. 806748224.2801

13、4号0-19-25-24-0683.225号0-6-5-16-17-4-00-7-20-18-14-01065. 74表5竖形分区业务员路线分配表方案三：矩阵分区将送货地点径向划分成儿个矩形区区域，使得每个区的送货量基本相等, 在46kg左右。(矩形分区图如图5)20181614121086420051015202530图5矩形分区图 矩阵优化路径如图6和走的路线，但走的首尾顺序可以任意。再有上面的整数线性规划模型，用编程(见附件二)，得到优化路径方案见表6送货线最优路径线路路程(km)线路所屁时间(h)10-2-4-5-6-0301.866720-1-3-7-8-9-0382. 353330

14、-10-11-12-0462. 3440-22-21-23-15-13-0723. 713350-16-17-18-20-0582. 986760-14-25-19-0582.8270-24-28-26-0884. 0280-27-29-30-0924. 18总计48224.28表6矩形分区路径表根据上表的线路分析，可得最终结果：需要5个业务员，具体安排见表7业务员1号送货线路0-27-29-30-0线路行 程 92线路耗 时4. 18总行程总耗时2号0-2-4-5-6-01180-24-28-26-05. 88673号0-22-21-23-15-13-00-16-17-18-20-0723.

15、713348224.284号0-14-25-19-00-1-9-8-7-3-01165. 80675号0-10-11-12-0844.6933表7炬形分区业务员路线分配表方案四：扇条形分区将送货地点径向划分成几个扇形区区域，使得每个区的送货量基本相等, 在46左右。(扇形分区图如图7)图7扇形分区图扇形优化路径如图8图8扇形路径优化图注釋：用线连接起来的儿个点表示一次送货可以服务的点，代表送货的先后 和走的路线，但走的首尾顺序可以任意。再有上面的整数线性规划模型，用编程(见附件二)，得到优化路径方案,见表8送货线最优路径线路路程(km)线路所花时间(h)10-2-4-5-6-0301.8667

16、20t 6-17-18-20-0582. 986730-7-14-25-0582.8240-24-28-26-0884. 0250-1-8-13-19-0542. 826760-27-29-30-0924. 1870-10-22-21-11-9-0542. 993380-3-12-15-23-0723. 5467总计50625.2401表8扇形分区路径分配图根据上表的线路分析，可得最终结果：需要5个业务员，具体安排见表9 业务员送货线路线路行线路耗总行程总耗时程时1 号0-27-29-30-0924. 1850625.24012号0-2-4-5-6-00-24-28-26-01185. 886

17、73号0-3-12-15-23-0723. 54674号0-16-17-18-20-00-7-14-25-01165. 80675号0-1-8-13-19-00-10-22-21-11-9-01085.82表9扇形分区业务员路线分配表方案五：对角分区将送货地点径向划分成几个对角行区域，使得每个区的送货量基本相等, 在46kg左右。（对角分区图如图9）图9对角形分区图对角优化路径如图10图10对角形分区路径优化图注释：用线连接起来的几个点表示一次送货可以服务的点，代表送货的先后 和走的路线，但走的首尾顺序可以任意。再有上面的整数线性规划模型，用编程(见附件二)，得到优化路径方案，见表10送货线最

18、优路径线路路程(km)线路所花时间(h)10-1-9-10-0321. 7820-2-5-4-3-0321.946730-12-13-14-0522. 5840-6-16-17-20-7-0502. 833350-22-21-15-19-0683. 386760-18-24-25-0683.2270-8-27-29-23-0864.106780-11-26-28-30-0964. 5067总计48424. 3601表10对角形分区路径分配图根据上表的线路分析，可得最终结果：需耍5个业务员，具体安排见表11业务员送货线路线路行 程线路耗 时总行程总耗时1号0-11-26-28-30-0964.

19、50672号0-1-9-10-01185.886748424. 36010-8-27-29-23-01005. 33341205.8502. 83330-2-5-4-3-00-22-21-15-19-00-12-13-14-00-25-24-18-00-6-16-17-20-7-0表11对角分区业务员路线分配表 最后将五个方案进行对比，做出表12方案对 比方案 （横形）方案二 （竖形）方案三（炬 形）方案四 （扇形）方案五（对 角形）送货总 人数55555总行程（kg）498482482506484总时间（h）24.920124.280124. 2825. 240124. 3601表12对角分

20、区业务员路线分配表综上所述：方案三最好，所用时间最短，而行程也最短。最短时间为24. 28h,最短行程为482km.问题二：如果业务员携带快件时的速度是20km/h,获得酬金3元/km kg；而不携带快件时的速度是30km/h,酬金2元/km,请为公司设计一个费用最省的策略。（-）模型的分析这个优化问题的目标是给业务员的酬金最少，业务员的安排、路线的选择都 是为了总费用的最小化提供条件。曲于模型一是在问题一中的约束条件下求解的 最优路径安排，我们可以直接根据模型一中的方案计算所需的最少费用。但是因 为业务员负载时所需的费用要比空载时高出很多，而问题一没有考虑这一点，所 以如果直接运用问题一求出

21、的最优路线针对费用來说，可能不是最佳的。又因为 每一条街道都和坐标轴平行，因此我们可以在模型一的基础上再优化每一条路线 上的送货点的顺序，利用问题二屮的速度约束条件，求出每条路径的第二时间， 最后根据第二时间对8组路线进行合理人员分配。于是我们得到了以下的整数规 划模型。（二）模型的建立和求解根据对问题的分析，我们以给业务员的酬金最少为目标函数，以每个业务 员每天平均工作时间不超过6小时和出发时的载重不超过25kg为约束条件，建 立了以下的整数模型，。30w严工 37©+”）业务员负载费用：日（5）n 30业务员空载费用:w2二工工2血（坷+兀）(7)因此，日标函数建立为口inw=w

22、l+w2应满足以下约束条件：f rvta+a±a+lycl<61 时间约束:丿tl 30206 ,=1(9)2.载重量约朿tici <25根据上面的模型，我们用matlab来进行求解（程序见附件二）。把问题 一中各方案的数据代入程序，即可以求出各线路的重量、总路线、费用，最后求 各方案的总费用。从matlab编程的结果中，可以求出各方案的费用。（见表13）方案各路线的费用总费用15081661.82891.91237.22337.81540.82621.81768.414567.72638.41588.92310.21491.32294.616973241.91988.6

23、15250.93759.1905.71865.41549.63171.225682891.91834.215545.14759.11834.22891.91489.61822.23171.21540.81274.714783.75549.410822586.415832755.81845.228702290.815562.7表13各方案的费用通过对比，我们发现方案1的费用最少，最少费用为14567.7元具体安排如下表4业务 员线路所花时间各路线的费 用10-3-12-15-23-03. 66671540.820-27-29-30-04. 33332891.930-16-17-24-1803.6

24、2337. 840-19-26-28-04. 16672621.850-1-2-6-00-5-20-25-14-04.66672276. 460-10-22-21-11-00-4-7-13-8-9-05. 8666289926.314567. 7表14问题三：如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？（一）模型分析问题三是建立在问题一的基础上的，因为每个业务员可以携带的邮件量是一 定的，即不超过25kg,当工作时间调至八小时时，无论对总公里数还是总酬金 都没有影响，只需对业务员的多少进行改进即可。（二）模型的建立和求解在问题一中已算得五个方案，方案三所需的总时间最少为24

25、. 28h,当业务员时间调至8小时时,所需的业务员至少为24 78子3个，所以业务员至少为4个。于是我们就对方案三中的表六的八个路线重新分配，分配给4个送货员，尽量给94 or业务员分配同样的工作时间。字 = 6.07/?,即每个业务员工作时间在6. 07左 4右0重新分配后得到如表15所示的方案业务员送货路线线路耗 时线路路 程10-27-29-30-06. 04671220-2-4-5-6-020-24-28-26-06. 361340-10-11-12-030-22-21-23-15-13-06. 06661100-1-9-8-7-3-040-14-25-19-05. 80671160-

26、16-17-18-20-0表15综上所述，当时间变成8小时时，业务员减为4个，具体安排为：1号业务 员跑的路线为0-27-29-30-0和0-2-4-5-6-0, 2号业务员跑的路线为 0-24-28-26-0 和 0-10-11-12-0, 3 号业务员的路线为 0-22-21-23-15-13-0 和 0-1-9-8-7-3-0, 4 号业务员的路线为 0-14-25-19-0 和 0-16-17-18-20-0。五.模型的评价1模型的优点：（1）模型通过分区的思想，让题口的复杂系数降低，在分区的同时，采用了五 种方案进行分析。系统的给出了业务员的调配方案，便于指导工作实践。（2）模型简明

27、明了，容易理解与灵活应用。（3）模型的方法和思想对其他类型也适合，易于推广到其它领域。2.模型的缺点：模型给出的约束条件可能有不太现实的，忽略了很多因素，这些因素在实际 中不可忽略。因此在实际屮应该多分配一些业务员或时间。比如每一次业务员送 完快件，回来再准备第二趟运送快件这个过程也要花时间，这个时间没有考虑到 时间范围内。六.模型的推广1. 本模型不但适合于快递公司送货问题，还可适用于一般的送货和运输调度问 题，只需要稍微改动模型即可。2. 建模的方法和思想可以推广到其他类型，如车辆调度问题等。参考文献1 姜启源 谢金星叶俊 编著，数学模型，北京：高等教育出版社，2003 年第三版；2 邓微

28、，matlab函数速查手册：人民邮电出版社，2008.3 吴建国编著，数学建模案例精编，北京：中国水利水电出版社，2005 年5月第一版.附件一：求矩阵：求任意两配送点间的距离clear clcx=03154307910141714121019261115722212715152021242528;y 二025471189620369129161817121450919141713201618;for i二1:31for j二1:31d(i, j)=abs(x(i)-x(j) +abs(y (i)-y (j); endendd附件二用matlab求各题各方案的结果：clearclcvl=20;

29、v2=30;v3=25;tm二input ('猜输入题目序号(如第一题：1)：')i f tmlfa=input('猜输入方案序号(如第一方案：1)：');elseif tn)=2fa二input ('猜输入方案序号(如第一方案：1)：');endx二3 1 543 07 910141714 1210 192 61115722 21 2715 15 20 21 242528;y=2 5 4711 8 96203 69 12 91618 17121450 9 19 14 17 1320 16 18;m=8 8. 265. 54. 537. 22.

30、31. 4 6.5 4.112. 7 5.8 3. 8 3. 4 3. 55. 8 7. 57. 8 4. 66. 26. 82.4 7.6 9.6 10126.08.1 4.2;l1 二;l2二;l3二;l4二；l5二;l6二;l7二;l8二;sm=zeros(l, 8); t=zeros(l, 8) ;l= ;d=zeros(l, 8) ;q=zeros(l, 8); jm=zeros(l, 8);px 二;py 二;s=|?lr ;，l2,l3, f ;，l5, ;，l6, ;，l7, ;'l8，;if fa=lll=l 2 6;l2二10 22 21 11; l3=4 7 13

31、 8 9; l4=3 12 15 23; l5=5 20 25 14;l6=27 29 30;l7=16 17 24 18;l8=19 26 28;elseif fa=2ll=l 3 2;l2二6 5 16 17 4;l3=9 12 13 8;l4=7 20 18 14;l5=10 11 15 26;l6=19 25 24;l7=22 21 27;l8=23 30 28 29;elseif fa=3ll=2 4 5 6;l2=l 3 7 8 9;l3=10 11 12;l4=22 21 23 15 13;l5=16 17 18 20;l6=14 25 19;l7二24 28 26;l8二27

32、29 30;elseif fa=4ll=2 456;l2=16 17 18 20; l3=7 14 25;l4二24 28 26;l5=l 8 13 19;l6=27 29 30;l7=10 22 21 11 9; l8=3 12 15 23;elseif fa5ll=l 9 10;l2=2 5 4 3;l3=12 13 14;l4二6 16 17 20 7;l5=22 21 15 19; l6=18 24 25;l7=8 27 29 23;l8=ll 26 28 30;endplot(x, y,'k*')hold onfor i=l:8if i=ll=l1;elseif i=2l=l2;elseif i=3l=l3;elseif i=4l 二 l4;e