数学建模之快递公司送货策略.doc

快递公司送货策略一摘要:本文是关于快递公司送货策略的优化设计问题，即在给定送货地点和给定设计规范的条件下，确定 所需业务员人数，每个业务员的运行线路，总的运行公里数，以及费用最省的策略本文主要从 最短路经和费用最省两个角度解决该问题，建立了两个数据模型模型一：利用“图”的知识，将 送货点抽象为“图”中是顶点，由于街道和坐标轴平行，即任意两顶点之间都有路在此模型中， 将两点之间的路线权值赋为这两点横纵处标之和如A （xl, yl） , B （x2, y2）两点，则权值为 D=|x2-xl| + |y2-ylb并利用计算机程序对以上结果进行了校核模型二 根据题意，建立动态规 划的数学模型然后用动态规划的知识求得最优化结果根据所建立的两个数学模型，对满足设计 要求的送货策略和费川最省策略进行了模拟，在有标尺的坐标系中得到了能够反映运送最住路线的 模拟图最后，对设计规范的合理性进行了充分和必要的论证二关键词：快递公司送货最优化图模型多目标动态规划TSP模型三问题重述：在快递公司送货策略中，确定业务员人数和各口的行走路线是本题的关键这个问题町以描述为:一中 心仓库（或配送调度中心）拥有最大负重为25kg的业务员m人，负责对30个客八进行货物分送工作， 客户i的快件量为已知，求满足需求的路程最短的人员行驶路径,且使用尽虽少的人数，并满足以下 条件：1） 每条送快件的路径上各个客户的需求量Z和不超过个人授大负重。

2） 每个客户的需求必须满足，且只能由一•个人送货.3） 每个业务员每天平均工作吋间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为 25km/h<>4） 为了计算方便，我们将快件一律用重量來衡量，平均每天收到总重量为184.5千克表一为题中所给的数据：表最大载重量25kg重载时速20km/h途中的平均速度25km/h重载酬金3 元/km*kg业务员工作时间上限6h空载时速30km/h每个送货点停留时间lOmin空载酬金2 元/km备注1、快件一律用重量來衡量2、假定街道方向均平行于坐标轴处于实际情况的考虑，木研究中对人的最人行程不加限制•木论文试图从最优化的介度，建立起满足设 计要求的送货的数学模型，借助于计算机的高速运算与逻辑判断能力，求出满足题意要求的结果四问题分析：从公司总部配出一个人，到任意未配送的送货点，然后将这个人配到最近的未服务的送货点范用之内的 邻居，并使送货时间小于6小时，各送货点总重量不超过25kg继续上述指派，直到各点总重量超过 25kg,或者送货时间大于6小时最后业务员返回总部，记录得到的对行行程（即路线）对另一个业 务员重复上述安排，直到没冇未服务的送货点。

对得到的可行的行程安排解中的每一条路径，求解一个 旅行商问题，决定访问指派给每-条行程的业务员的顺序，最小化运输总距离得到可行解的行程安排 解后退出根据题意的要求，每个人的工作时间不超过6小时，且必须从早上9点钟开始派送，到当天17点之前（即在8小时之内）派送完毕且 空处 =8,故至少需要8条路线表二列出了题中任意两配送 25kg点间的距离表二：任意两点间的距离矩阵0123 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 300123456789 ■4■ CsJ CO oo 1A ■ ■ ■ ■ 1A ■ ■ « *4■4■ 1A ■ ■2212222222236107582014266545828995444333333332222222111216520375697110903154404 3 3 3 3 3 2 2 2 2 2 2 2 2 12 2 2 11122 61157o29 37 34 4424 31 29 3923 31 28 3820 28 25 3518 26 23 3321 29 26 3615 23 20 3013 21 18 2814 22 19 2917 25 22 3215 23 20 3013 17 14 249 17 14 248 16 13 237 15 12 228 16 15 2315 19 22 2613 15 20 207 9 14 167 2 10 7 1716 14 9 1720 18 13 2317 15 10 140 5 7 12 105 0 8 7 157 8 0 512 7 5 0 1010 15 7 1013 12 6 714 17 9 1249853608920 32222221122 610758601423 3 3 2 2 2 2 2 2 2 2 10504993837 2222222211 7218O5594H 「.I 22212221111 83297082364177 C\l CxJ CxJ 11 11 C^J 1A 1A 1A 11 11 117 2 12 2 28 3 22 2 22482062202042 22 22 22 2679 4 5 3-11 11 -ooo 52 23 82 29 41 275 3 0 411 1x oi 116 0 6 012 2 20 6 8 22 2 2 22 8 12 2 25 161- 2 1-o2 o3 35 33 31A rty3 24 22 27 56247 82 13 42 1722o522526o65o105no 4166o6o5102 2I 2 22 22 2212282822273 72 29 32 31 53 34 82 29 31 24 8243032252050569118141615121420202122211824282727213634293734444146116540557 56 67 111313111213121515191818202725202825353237206 o2 26 o2 2065534275229421111221223235731- T324819429961 ■ ■ ■ ■ O'J ■ ■ OxJ oo21930831885011122112122343596053007211222212232309598619663821222222233376045386330511222212233321150831885 022223223233432201942996122223223233491A_81191A8110 0 122 2 2 29 2 6 3 812 2 2 25 3 0 512 2 22 2 9 412 123 3 0 512 2 24 4 1612 2 24 4 1612 2 2 20530072 221223231232068 3 3 0 5112 2 24因为距离是对称的,即从送货点i到送货点j的距离等于从j到i的距离。

记作:dij.表三给出了客户的需求，为了完成送快递的任务，每个人在T作时间范围内，可以承担两条英至 更多的线路表中给出了送货点序号，送货点编号，快件量T,以及送货点的直角坐标表三序号送货点快件最T坐标(km)序号送货点快件量T坐标(km)XyXY1183216163. 521622& 21517175.86183365418187. 51117445.54719197.815125630820153.4199654.531121326.2225777. 27922226.8210882.39623232.4279991.410224247.6151910106.514025259.6151411114. 11732626102017121212. 7146272712211313135.812928286.02242014143.810122929& 1251615204.671430304.22818五模型假设：(1) 街道方向均平行于坐标轴，且在该前提下，业务员可以任意选择路线2) 无塞车现象，即业务员送快递途中不受任何外界因素影响，11业务员的休息时间不包括在最人工 作时间6个小时内。

3) 业务员人数不限制4) 每个业务员的路线一旦确定，便不再更改5) 每个业务员送快递是独立的，每人之间互不影响6) 业务员到某送货点后必须把该送货点的快件送完7) 每个业务员每天的工作时间不超过6个小时8) 业务员冋到快递公司后停留一个小时六主要符号说明：Ti：序号为i的送货点的快件重最(xi , yi)序号为i的送货点的处标M姿业务员送货总重载费用M空：业务员送货总空载费用M总：业务员送货总费用N：业务员送货的总次数m：业务员人数mj：第j个业务员送货的次数.[1,业务员在序号为i的送货点送快件at = <[0,业务员在序号为i的送货点没有送快件,.〔1,第k条路线选择序号为i的送货点是最远点hi = “0,第k条路线选择序号为i的送货点不是最远点七模型建立与求解：7.1问题一模型本模型考虑用多冃标动态规划求解由于问题一中只耍求给出一个合理的方案，且未涉及到业务员工资 问题，故只要满足条件——业务员的工作时间上限是6个小时以及每条路线的最人载重量不人于25kg 即可，本模型中追加两个目标——路程最短和人员最少可以通过以下两种方法实现：(1)每一个行 程的笫一个送货点是距离总部最近的未服务的送货点。

用这种方法，即可得到一组运行路线，总的运行 公里数，以及总费用2)每一个行程的第一个送货点是距离总部最远的未服务的送货点然后以该 点为基准，选择距它最近的点，加上约束条件，也可得到一组数据然后比较两组结果，通过函数拟合。