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

井冈山大学 2011年“井冈杯”数学建模竞赛 ● 论文题目：  快递运输决策问题（B） 指导老师：王志伟 参赛队员 姓名：王祥鹿 专业：10级教技一班  学号：100915039 姓名：蒋向香 专业：10级软件二班  学号：100521037 姓名：梁 筱 专业：10级数本一班  学号：100511019 联系方式：189********，180********，151******** 2012  年   07  月 02日 快递送货策略问题 摘要 本文是关于快递公司送货策略的优化设计问题，即在给定的条件下，确定所需业务员人数，每个业务员的运行线路，总的运行公里数，以及费用最省的策略。 本文主要从最短路经和费用最省两个角度解决该问题，建立数据模型。 对于问题一：这是一个多目标动态求解问题，只需给该公司提供一个合理的送货策略，不考虑业务员所跑路程与报酬的关系以及工作时间与报酬的关系。因此先以某业务员是否送货到某送货点建立 分布函数，以业务员的人数和总的运行公里数为目标函数，时间、货重等为约束条件建立多目标动态规划的数学模型，然后根据数学模型以五种 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 用 进行筛选，算出总公里数和需要的业务员数量，最后用模型 求解所有方案送货点之间最优访问路径安排，得到方案五总运行路程最短。则问题一的最优解为方案五，安排 位业务员。 对于问题二：由于业务员空载时与载货时的费用差异较大，可假设业务员回公司的途中不送货。又由于载货过程中所得总酬金不变，所以只需考虑业务员空载时的总酬金，而空载时在总酬金只与每一天线路的最远点有关，所以应使尽量多的路线的最远点靠近原点。则必须同时考虑货物的重量和路程，先把货物重且近的送货点送完，依次筛选，最后送货物轻及远的，因此得到一优化方案，即以货物的轻重做参考由近到远依次筛选。在模型一的基础上再建立 分布函数，以总费用为目标函数，约束条件会考虑到货重与路程的共同作用，同样用 进行筛选，得出一种优化方案。另外考虑不回送的策略得到另外一种优化方案，经过比较得，第二种方案总酬金更少，总公里数和业务员皆更有优势，则问题二的最优解为第二种方案。总酬金为 元，总公里数为 公里，所需业务员为 人。 对于问题三：当工作时间调至八小时时，无论对总公里数还是总酬金都没有影响，只需对业务员的多少进行改进即可，于是我们将模型一中的最优方案（即方案五）改进，即对路线和人员的安排进行调整，得总共只需 个业务员。 最后对模型进行评价与改进，该模型可适用于一般的送货及货物运输问题，而且该模型的思想和方法可以推广到其他类问题，如车辆调度问题等。 关键词 快递公司送货   最优化   分区送货策略模型   多目标动态规划   模型 一、 问题的重述 目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。所以，最小化所需业务员人数及业务员总的运行公里数从而为公司节省人力和财力成为我们的研究目标。 假定所有快件在早上7点钟到达，早上 点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过 小时，在每个送货点停留的时间为 分钟，途中速度为 ，每次出发最多能带 的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为 ，公司总部位于坐标原点处，送货点的位置和每个送货点的快件重量为已知，并且假设送货运行路线均为平行于坐标轴的折线。 1）给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）； 2）如果业务员携带快件时的速度是 ，获得酬金 ；而不携带快件时的速度是 ，酬金 ，请为公司设计一个费用最省的策略； 3）如果可以延长业务员的工作时间到 小时，公司的送货策略将有何变化？ （图中表格和坐标图见附录1） 将题中所给的数据整合成表 ： 最大载重量 重载时速 途中的平均速度 重载酬金 业务员工作时间上限 空载时速 每个送货点停留时间 空载酬金 备注 1、快件一律用重量来衡量 2、假定街道方向均平行于坐标轴         表格 1  数据整理 二、问题的 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 快递公司平均每天要送出总重量为 的邮件，每个人的工作时间每天不超过 小时，且每个人的最大负重是 ，由 , 可知至少需要 条路线对这些邮件进行运送。 对于问题一，以某业务员是否送货到某送货点建立 分布函数，以业务员的人数和路线总公里数为多目标函数，时间、货重等为约束条件建立数学模型，根据数学模型用 进行筛选，假设每个业务员只送货一次，可根据几个方案进行筛选： 方案一：以任意两点的距离进行分区域排序筛选； 方案二：以纵横坐标值之和由大到小进行筛选； 方案三：以横坐标值由大到小进行筛选； 方案四：以纵坐标值由大到小进行筛选； 方案五：分别考虑横纵坐标对矩阵周长 的影响大小，以影响较大的一项作为筛选条件，由大到小依次进行筛选。 此五种方案应为符合约束条件的最优方案，算出其总公里数及需要的业务员数量，进行比较，可得最优方案，最后再做适当的调整改进。 对于问题二，由于业务员空载时与载货时的费用差异较大，可假设业务员回公司的途中不送货。经分析讨论，可在问题一的模型基础上再建立 分布函数，以总费用为目标函数，约束条件有所改变，其中会考虑到货重与路程总数的共同作用。 与问题一的模型求解一样，用 进行筛选，由于考虑到货重与路程都与费用有关，又产生一种优化方案：以货物的轻重做参考由近到远依次筛选。以此方案的费用与问题一中五种方案的费用比较，选出最小的一组，作为最优方案。 问题三中业务员工作时间的调整对总的运行路线的影响并不大，只需对业务员的数量以及各业务员的安排路线进行调整即可。 三、模型的假设与符号说明 1）模型的假设： 1.业务员送完货后必须再回公司报到。 2.业务员送货期间行进速度不受外界影响，且业务员的休息时间不包括在最大工作时间 个小时内。 3.业务员送货运行路线均为平行于坐标轴的折线。 4.题目中送货点位置与所需货重准确无误。 5.每个业务员送快递是独立的，每人之间互不影响。 6.业务员人数不限制。 7.业务员均能且必须把每个送货点的货物送到接受人手中。 8.业务员派送完毕，返回公司所花时间也为工作时间。 2）符号说明： :业务员数量 :送货路线数量 :送货点中的任意一点 :送货路线中的任意一条 : 点横坐标 : 点纵坐标 :以第 条路线中是否有 点为决策的0-1分布函数 :以 点是否为 条线路最远点为决策的0-1分布函数 : 送货点的货物重量 :所有业务员载货时的总酬金 :所有业务员空载时的总酬金 :所有业务员一天的总酬金 :第 点到中心点的距离 :第 点的横纵坐标值之和 四、模型的建立与求解 （一）、模型准备 假设有 条路线，第 点坐标为 ,货重 。建立0-1分布函数 、 使得：                （二）问题一模型： 对于问题一，是一个多目标动态求解问题，只需给该公司提供一个合理的送货策略，我们不考虑业务员所跑路程与报酬的关系和工作时间与报酬的关系，找出满足问题一条件的几种策略。 需满足的条件有： 条件 ：每个业务员每天平均工作时间不超过 小时。 条件 ：每次出发最多能带 的重量。 对于问题一要求，首先考虑总的运行公里数。 由于送货运行路线均为平行于坐标轴的折线，在此模型中，将两点之间的路线权值赋为这两点横纵坐标之和，从原点到 点和从 点到原点距离都为 （不考虑回走问题，即考虑方向 ） 满足要求的路程最短而且业务员数量最少即：     约束条件： 1）载重约束：         2）时间约束：    使得距离最优：可以对送货点进行归类筛选。 1. 方案一： 建立分区送货策略模型对送货点坐标进行不同区域的分类，以各点与中心点之间距离为分类标准，从短到远，对区域大小加以送货重量限制即各区域中所有送货点的快件量之和小于或等于 。 用分析递推方法求解划分区域，确定离原点最远的点 为第一区域，找到与之距离最近的点 ，如果总快件量小于 ，则继续找离 最近的点，由近到远，快件量之和小于 的选取，直到最远的一个送货点结束。 即先选取第 个送货点，与 最近的 是第 个送货点，总快件量小于 ，继续选取离 最近的点 ，总快件量没有超过最大负重，继续选取离 最近的 ，选取离 最近的 ，此时总快件量是 ，再继续选取就会超出最大负重，选择返回。 得到方案一的各区域送货点、总的运行公里数、总送货时间见表 ： 方案一 区域 送货点 路程 时间   第一区域 15、23、28、29、30 100 4.68   第二区域 8、26、27 76 3.54   第三区域 9、14、24、25 74 3.39   第四区域 6、16、17、18、20 70 3.16   第五区域 10、11、22、32 54 2.83   第六区域 7、13、19 54 2.67   第七区域 3、4、12 42 2.18   第八区域 1、2、5 28 1.62       总运行498公里 总时间24.07           表格 2  方案一路线、总路程和时间 2. 方案二： 以纵横坐标值之和由大到小进行筛选。 对所有送货点的坐标求和： 用Excel对所有 进行排序筛选，以最大的 为第一个送货点，确定为第一条送货路线，从剩下的点中选取最大的，如果2点总快件量小于最大负重，则放入这一送货路线，如果大于最大负重 ，则不放入这一路线，继续选取剩余数中最大的，一直到最小的一点结束。 得到方案二的各区域送货点、总的运行公里数、总送货时间见表 ： 方案二 路程 送货点 路程 时间   路线一 15、23、28、29、30 96 4.68   路线二 26、 27、 8 76 3.54   路线三 18、 24、 25 68 3.22   路线四 9、14、17、19、21 80 4.04   路线五 11、13、16、20、22 74 3.8   路线六 5、7、12 50 2.5   路线七 3、4、6、10 44 2.43   路线八 1、2 16 0.98       总运行504公里 总时间25.19           表格 3  方案二各路线、路程和时间 3. 方案三： 以送货点的横坐标由大到小进行筛选。 以最大的横坐标的点为第一个送货点，确定为第一条送货路线，从剩下的点中选取横坐标最大的，如果2点总快件量小于最大负重，则放入这一送货路线，如果大于最大负重 ，则不放入这一路线，继续选取剩余数中横坐标最大的，一直到横坐标最小的一点结束。 得到方案三的各区域送货点、总的运行公里数、总送货时间见表 ：  方案三 路线 送货点 路程 时间   路线一 15、23、28、29、30 96 4.68   路线二 21、22、27 70 3.3   路线三 9、11、24、26 78 3.79   路线四 10、19、25 58 2.82   路线五 8、12、13、14 52 2.75   路线六 4、7、18、20 66 3.31   路线七 1、3、5、17 42 2.35   路线 八 2、6、16 36 1.94       总运行498公里 总时间24.94           表格 4  方案三路线、路程和时间 表中可知此方案总运行公里数为 公里，共需 次送货，由时间约束可知：路线二与路线七、路线三和路线八、路线四和路线五均可由一个业务员分两次送，所以此方案只需 个业务员。 4. 方案四： 以送货点的纵坐标由大到小进行筛选。以纵坐标最大的为第一个送货点，确定为第一条送货路线，从剩下的点中选取纵坐标最大的，如果2点总快件量小于最大负重，则放入这一送货路线，如果大于最大负重 ，则不放入这一路线，继续选取剩余数中纵坐标最大的，一直到纵坐标最小的一点结束。 得到方案四的各区域送货点、总的运行公里数、总送货时间见表 ： 方案四 路程 送货点 路程 时间   路线一 28 24 17 30 9 96 4.68   路线二 18 26 16 14 74 3.63   路线三 29 20 25 23 86 4.11   路线四 27 19 5 68 3.22   路线五 7 13 15 6 4 56 3.08   路线六 8 12 2 40 2.1   路线七 21 3 11 1 54 2.83   路线八 10 22 42 2.02       总运行516公里 总时间25.67           表格 5  方案四路线、总路程和时间 表中可知此方案总运行公里数为 公里，共需 次送货，有时间约束可知：路线二与路线八、路线四与路线六、路线五与路线七均可由一个业务员分两次送，所以此方案只需 个业务员。 5. 方案五： 分别考虑横纵坐标对矩阵周长 的影响大小，以影响较大的一项作为筛选条件，由大到小依次进行筛选。 对坐标 和 同时考虑，建立矩形模型，考虑矩阵周长 ，当 时， 边的变化对 影响较大，当 时， 边的变化对 影响较大。矩阵周长 直接关系到运行路程的大小。用 对 和 一起排序，从最大 开始，当 时以 为标准从大到小选取送货点，当 时以 为标准从大到小选取送货点，当 时，选 ，直到总快件量大于最大负重。 用模型 求解所有方案送货点之间最优访问路径安排，得到方案五总运行路程最短。选取方案五，安排 位业务员。 得到线路：    路线一： 路线二： 路线三： 路线四： 路线五： 路线六： 路线七： 路线八： 得到方案五的各区域送货点、总的运行公里数、总送货时间见表 ： 方案五 路程 送货点 路程 时间   路线一 11、23、30、28、29 98 4.75   路线二 22、21、27 70 3.3   路线三 14、24、26、15 78 3.79   路线四 16、17、18、19 66 3.31   路线五 20、25、10、9、8 70 3.63   路线六 5、13、12 50 2.5   路线七 6、4、7、3 34 2.03   路线八 1、2 15 0.93       总运行481公里 总时间24.24           表格 6  方案五路线、总路程和时间 ①各业务员路线安排图见图1： 图表 1  方案五各业务员路线安排图 ②各业务员人数、时间安排表见表 ： 业务员 路线 站点编号 到个站点时间 出发时间 业务员 路线 站点编号 到个站点时间 出发时间 1号 1 11 9:48 9:00 4号 4 16   9:00 23 10:37 17   30   18   28   19   29   8 1   12:39 2号 2 22   9:00 2   21   5号 5 20   9:00 27   25   6 5   12:18 10   13   9   12   8   3号 3 14   9:00 7 6   11:22 24   4   26   7   15   3                       表格 7  方案五各业务人员人数、时间安排表 （三）问题二模型: 假设业务员在送完最远点后的返回途中不送货，并假设业务员送货路线不走回头路（送货工程中不往横纵坐标轴的反方向走）。依据题目条件可知我们必需把业务员的酬金越少越好作为第一目标，其次再考虑 总路程的多少。经分析，无论业务员怎样送货，他们载货过程中所得总酬金不变，都为所有送货点到原点（公司坐标）的酬金。则所有业务员载货时的总酬金为：        因为返回过程中不送货，所以业务员返回过程中所得的酬金即为其空载的酬金，则所有业务员空载时的总酬金为： 因此， 所有业务员整天的总酬金：  可建立动态规划模型如下： 目标：    约束： 最远送货点约束：    载重约束：          总载重约束：      时间约束：  由于载货过程中所得总酬金不变，所以只需考虑业务员空载时的总酬金，又空载时在总酬金只与每一天线路的最远点有关，所以我们应使尽量多的路线的最远点靠近原点。则必须同时考虑货物的重量和路程，先把货物重且近的送货点送完，依次筛选，最后送货物轻及远的，因此我们得到一优化方案六，即以货物的轻重做参考由近到远依次筛选。 得到该优化方案的各区域送货点、总的运行公里数、总送货时间见表 ： 路线 送货点 半路程 最远点到原点距离 时间 路线一 2 1 7 9 19 16 2.18 路线二 10 3 4 5 8 25 14 2.84 路线三 12 19 11 29 27 2.82 路线四 22 21 13 17 40 27 3.87 路线五 20 14 16 6 26 22 2.75 路线六 27 26 23 44 37 4.52 路线七 25 29 28 45 44 4.1 路线八 24 18 30 15 47 46 4.43   总计 275 233 27.51           表格 8  优化方案六各路线、路程、时间 对表7中的路线进行调整，可得出如下安排： 路线一:                   828 路线二:             1527.6 路线三：                 1701.2 路线四:                 2038 路线五：             1392.4 路线六:                   2354.8 路线七：                   2247.5 路线八:               2239.2  经计算分析得到最优路线安排如上，其总酬金为 元。总运行公里数为 ，需业务员 个。 另外，考虑不回送策略，可得到另一方案七的各区域送货点、总的运行公里数、总送货时间见表 ： 路线 送货点 路程 最远点到原点距离 时间 路线一 1 3 8 30 15 1.7 路线二 2 4 7 14 15 56 28 3.13 路线三 6 5 20 18 56 28 2.91 路线四 16 17 24 68 34 3.22 路线五 9 13 19 26 74 37 3.63 路线六 10 12 15 23 72 36 3.55 路线七 11 21 29 30 92 46 4.35 路线八 22 27 28 88 44 4.02 总计 536 268 26.51   载重总酬金 13214.7元       空载总酬金 536元 总公里数 536km   总酬金 13750.7元 业务员 6个           表格 9  方案七的各路线、路程、时间及酬金 上表 中总酬金为 元比前一种方案要少，业务员及总公里数都占优势，这就是问题二的最优方案,运行路线如下： 路线一：                   路线二：     路线三：                     路线四：           路线五：                 路线六：                       路线七：             路线八： 绘制业务员送货路线图见图 ： 图表 2  该方案业务员送货路线图 （四）问题三模型： 当工作时间调至八小时时，无论对总公里数还是总酬金都没有影响，只需对业务员的多少进行改进即可，模型一中的最优方案（即方案五）的路线一、三、八，路线二、六、七，路线四、五均可由一个以业务员分次送货，所以总共只需3个业务员。 方案五的各区域送货点、总的运行公里数、总送货时间见表 ： 方案五 路程 送货点 路程 时间   路线一 11、23、30、28、29 98 4.75   路线二 22、21、27 70 3.3   路线三 14、24、26、15 78 3.79   路线四 16、17、18、19 66 3.31   路线五 20、25、10、9、8 70 3.63   路线六 5、13、12 50 2.5   路线七 6、4、7、3 34 2.03   路线八 1、2 15 0.93       总运行481公里 总时间24.24           表格 10 方案五路线、路程及时间 五、模型的评价与改进 模型的优点： 1.问题一中只考虑总路程和业务员最优，不考虑路程与报酬以及时间与报酬的关系，建立多重假设，建立约束条件，简化了模型，更有利于求解。 2.问题一中对送货坐标按不同指标进行分类，选用多种方案求解模型，并用 制作表格进行对比，从而选取最优方案，得到方案五相对比较完善。 3.模型系统的给出了业务员的调配方案，便于指导工作实践。 4.模型简单明了，容易理解与灵活应用。 5.本模型方便、直观，易于在计算机上实现和推广。 模型的缺点： 1.街道的方向不一定严格平行于 轴和 轴，运输的线路可能刚好位于居民住宅区，则业务员必须绕过住宅区。 2.没有考虑到外界因素，如降雨降雪路面湿滑、天气炎热爆胎问题、堵车问题等。 3.未必每一份快递都能送到货主手中。 4.约束条件存在局限性。 5.邮件破损这一因素没有考虑进去。 模型的改进： 1.模型给出的约束条件可能也有不太现实的，需要考虑实际情况进行改进。（比如：快递员的速度不会是匀速。） 2.业务员送货的时候不一定是严格按照平行于 轴和 轴的折线走的，街道的方向，客户的快件量的假设有待进一步改进。 通过这两方面的改进，得到的结果会更合理、更准确。 模型的推广： 1.本模型不但适合于快递公司送货问题，还适用于一般的送货以及运输问题。 2.模型方便、直观，可以实现计算机模拟。 3.建模的方法和思想可以推广到其他类型，如车辆调度问题等。 参考文献： 【1】姜启源、谢金星、叶俊编，数学模型-3版，北京，高等教育出版社，2003.8 【2】纪崑，多维多目标模糊优选动态规划及其在资源分配中的应用，吉林大学学士学位论文，2004 【3】韩伯棠，管理运筹学-2版，北京，高等教育出版社，2005.7 【4】Excel函数应用教程276a200292eed.html 附录1： 送货点 快件量T (kg) 坐标(km) 送货点 快件量T (kg) 坐标(km) x y x Y 1 8 3 2 16 3.5 2 16 2 8.2 1 5 17 5.8 6 18 3 6 5 4 18 7.5 11 17 4 5.5 4 7 19 7.8 15 12 6 3 0 8 15 3.4 19 9 5 4.5 3 11 21 6.2 22 5 7 7.2 7 9 22 6.8 21 0 8 2.3 9 6 23 2.4 27 9 9 1.4 10 2 24 7.6 15 19 10 6.5 14 0 25 9.6 15 14 11 4.1 17 3 26 10 20 17 12 12.7 14 6 27 12 21 13 13 5.8 12 9 28 6.0 24 20 14 3.8 10 12 29 8.1 25 16 20 4.6 7 14 30 4.2 28 18                 表格 11  送货点的位置和快件重量 图表 3  送货点位置坐标点