第16组-B题---快递公司送货策略

1 数 学 建 模 论 文 题目 题目 快递公司的运送策略 学校学校 中原工学院信息商务学院组 成员 邝光辉 魏胜伦 唐锦锦 2012 年 8 月 29 日 2 快递公司送货策略 摘要摘要 本论文是关于快递公司送货策略的优化问题 就是在给定送货地点和给定送货量 和送货时间的约束条件下 确定所需业务员人数 每个业务员的运行线路 总的运行 公里数 以及费用最少的策略 本文主要从最短路径和费用最省两个角度来考虑问题 建立三个数学模型 模型一 本题主要运用的的最优化线性规划中的 0 1 整数规划建立约束条件 将 送货点抽象为一个点 且任意两点间的距离为这两点横纵坐标差的绝对值之和 先从 最远点开始出发 一次查找临近点 并考虑总重量小于 25kg 以此来划分区域 最后 利用最近插入法来寻求最优解 假设每条线路由不同的业务员来完成 模型二 运用的是图论中最小生成树的原理 在满足约束条件的前提下求的最短 距离 模型三 在问题一的基础上 重新建立模型求解 得到目标结果 关键词 快递公司送货 最优化 0 1 整数规划 最近插入法 最小生成树 3 1 问题重述 目前 快递行业正蓬勃发展 为我们的生活带来更多方便 一般地 所有快件到 达某地后 先集中存放在总部 然后由业务员分别进行派送 对于快递公司 为了保 证快件能够在指定的时间内送达目的地 必须有足够的业务员进行送货 但是 太多 的业务员意味着更多的派送费用 由此我们得知 确定业务员的人数和各自行走路线是本题的主要步骤 求满足需 求的路程最短的人员行驶路线 且使用尽量少的人数 并满足以下条件 1 每天的快件必须在规定的时间 9 00 17 00 8 小时 内全部送完 2 每个业务员每天平均工作时间不超过 6 小时 在每个送货点停留的时间为 10 分钟 途中速度为 25km h 3 每次出发业务员所携带的快件重量不超过 25kg 4 为了计算方便 我们将快件一律用重量来衡量 平均每天收到总重量为 184 5 千克 5 下表所给的数据为每个送货点的位置和快件重量 并且公司总部位于坐标 原点处 如图 2 并且假设送货运行路线均为平行于坐标轴的折线 坐标 km 坐标 km 送货点 快件量 T kg xy 送货点 快件量 T kg xy 1832163 5216 28 215175 8618 3654187 51117 45 547197 81512 6308153 4199 54 5311216 2225 77 279226 8210 82 396232 4279 91 4102247 61519 106 5140259 61514 4 114 117326102017 1212 714627122113 135 8129286 02420 143 81012298 12516 204 6714304 22818 510152025 x 5 10 15 20 y 图 2 送货点分布图 1 请你运用有关数学建模的知识 给该公司提供一个合理的送货策略 即需要多少 业务员 每个业务员的运行线路 以及总的运行公里数 2 如果业务员携带快件时的速度是 20km h 获得酬金 3 元 km kg 而不携带快件时 的速度是 30km h 酬金 2 元 km 请为公司设计一个费用最省的策略 3 如果可以延长业务员的工作时间到 8 小时 公司的送货策略将有何变化 2 问题的分析 在问题 1 中 平均每天收到的总重量为 184 5 千克 每个人的最大负重是 25 千克 即 184 5 25 7 38 可知需要 8 条路线对这些快件进行运送 利用从最远点出发依次查 找符合条件限制的各个区域 求得 8 条行走路线 然后根据最近插入法对路线进行优 化 根据优化后得出的路线求的各条路线的路程 和在速度为 25km h 的条件下得出走 完每条路所需的时间 有题意知 每个业务员的工作时间不小于 6 小时 在此基础上 将工作时间短的路线进行合并 进而求的在完成总的送货量且工作时间小于 6 小时的 条件下 所需的总的业务员数 在问题 2 中 业务员的速度改变 分成携带快件和不携带两种情况下的具有不同 的速度 分别为 20km h 30km h 且业务员的薪酬与其工作过程中的行走的总路程有关 以费用最省建立目标函数 建立动态规划数学模型 每人工作时间不超过 6 小时且每 5 次出发最多只带 25 千克的重量 列出目标函数和约束条件 来找出每条路线的送货点 问题 3 将业务员工作时间延长至 8 小时 在 1 的基础上将时间约束条件改为 8 个 小时 在满足条件基础下 对问题 1 的路线进行合并 得出公司的送货策略 3 模型的假设与符号说明 3 1 模型的假设 1 初始模型中 假设每条路线对应不同的业务员 2 每个业务员每天的工作时间不超过 6 个小时 且送完货后必须再回公司报到 3 业务员的休息时间不包括在最大工作时间 6 个小时内 4 每个业务员送快递是独立的 每人之间互不影响 5 业务员到某送货点后必须把该送货点的快件送完 6 假设业务员送货运行路线均为平行于坐标轴的折线 7 无塞车现象 即业务员送快递途中不受任何外界因素影响 且业务员的休息时间 不包括在最大工作时间 6 个小时内 3 2 符号说明 1 1 0 ij ij a ij 在第条路线上业务员向第个送货点送快件 在第条路线上业务员不向第个送货点送快件 2 1 0 ij ij s ij 第条路线上选择第个送货点是最远点 第条路线上选择第个送货点不是最远点 3 表示第 j 个送货点坐标 xy jj 4 第 j 个送货点所需快件重量 j m 4 模型的建立与求解 问题 1 本题中考虑一个目标 总运行公里数最短 可以用以下方法 先假设每条线路由 不同的业务员来完成 即需要 8 名业务员来完成运送快递 然后在人数不变的情况下 本题先从最远点开始出发 依次查找临近点 并考虑总重量小于 25kg 以此来划分区 域 最后利用最近插入法来寻求最优解 最后根据表中的时间的约束 对业务员人数 安排进行重新调整 根据题意每个业务员工作时间不超过 6 小时 又因为 184 5 25 7 38 即派送这些快件至少需要 8 个业务员 因此问题 1 只需满足两个条件即可 1 业务员工作时间不超过 6 小时 2 每条线路上最大载重不超过 25kg 由于快递员从公司出发最多只能载 25kg 因此 6 1 30 1 25 ijj j a m 在每一条线路上 每一个送货点只能选择一次 因此 2 8 1 1 ij i a 在每条线路上只有一个最远点 即 3 30 1 1 ij j s 一条线路上至少有一个货点 4 0 ijij ijij as as 即 业务员在每个货点停留 10min 而业务员每天工作不超过 6 小时 因此 6 30 1 2 1 6 256 10 10 ijxy ij j ij ij sjj a a s 且或 或 因此 此模型满足路程最短目标函数 建立如下模型 830 11 min2 ijxy ij sjj 约束条件为 30 1 8 1 30 1 30 1 1 1 25 2 1 6 256 01 01 ij j ij i ijij ijj j ijxy ij j ij ij s a as sta m sjj a s a 或 或 因为 30 这个点距原点最远 因此假设先从 30 出发 29 是距离 30 最近的送货点 7 而且两点的快件重量和为 12 3kg 小于每个人的最大负重 可以继续指配 接着 28 是 距离 29 最近的点 此时三点的快件重量和为 18 3kg 仍小于 25 还可以继续指配 剩余 送货点中 23 距离 28 最近 其实距离 28 最近的点有 23 24 26 27 四个点 但是结合快 递重量 将其从小到大依次排列 快递重量大者先选 但需满足总重量要求 综合考 虑选择 23 同理确定下一个点选择 15 再继续扩充 会超出最大限载重 故返回原 点 该路线总送货重量为 24 1 所以第一条路线为 015232829300 用该算法得到的所有路线为 1 030292823150 2 0262780 3 024251490 4 01817201660 5 0212211100 6 0191370 7 012430 8 05210 现在这五个送货点之间的最优访问路径的是一个015232829300 典型单回路问题 可以根据单回路运输模型 TSP 求解 一般而言 用比较法求解 TSP 模型求解有最邻近法和最近插入法两种 由最近插入法比最近邻点法得到的结果更好 由于已经构成一个子回路 但现在要将 28 插入 但是 28 送货点有 3029300 个位子可以插入 1 插入到 0 和 30 之间 2 插入到 30 和 29 之间 3 插入到 29 和 0 之间 分析比较 得出插入到 0 和 30 之间 增量最小 同理将 23 和 15 用最近插入法 可以得出最优化路线为 015232930280 用这种方法可以依次对剩下的七条路线进行优化 进而得出所有的优化送货路 1 028302923150 2 0262780 3 024251490 4 02018171660 5 0112122100 6 0191370 7 041230 8 02510 每个业务员所工作的具体情况如下表所示 业务员编号过站数所用时间 小 时 总路程 千米 总载重量 千 克 154 8310024 1 8 233 547624 3 343 396822 4 453 155824 4 542 835423 6 632 665420 8 732 184224 2 831 632820 7 合计 3024 21480184 5 根据上述表格中的时间 可以读出每个业务员每天工作不超过 6 小时的最佳匹配 方案 又考虑每个业务员所经过工作站之间的距离 即 1 业务员 3 和业务员 8 的工作可以合并为一个人来做 2 业务员 4 和业务员 7 的工作可以合并为一个人来做 3 业务员 5 和业务员 6 的工作可以合并为一个人来做 由此得出每位快递员的送货路线为 1 028302923150 2 0262780 3 0242514902510 4 0201817166041230 5 0112122100191370 现列表如下 业务员编号过站数所用时间 小时 总载重量 千克 总路程 千米 154 8324 1100 233 5424 376 34 33 39 1 6322 4 20 768 28 9 45 33 15 2 1824 4 24 258 42 54 32 83 2 6623 6 20 854 54 合计 3024 21 184 5 480 下图为各条路线优化前与优化后所用时间比较 0 2 4 6 12345678 时时间间 优化前所用 时间 优化后所用 时间 下图为各条路线优化前与优化后经过路程比较 10 0 20 40 60 80 100 120 12345678 路路程程 优化前路 程 优化后路 程 运行路线如下 11 路线进行合并后每个人的行走路线 问题 2 问题二中由于业务员所得的费用是最主要的 业务员安排 路线选择都是为了总 费用的最小化提供条件 所以应首先考虑路费 之后再考虑业务员的安排 为了使总 能够费用最少 总的思路是先送货给离快递公司最近且快件最重的送货点 以此类推 在保证时间 载重量有限的前提下 沿途把快递送完 最终让业务员最远点空载返回 根据这一思路 全部路线业务员的重载费用可表示为 30 1 1 3 jxy j Mmjj 某路线业务员经过的路径选择应遵循以下原则 1 近者优先原则 某业务员最近起始送货点的选择直接关系到费用的多少 所 以该业务员在沿途往送货终点站中应尽量把较近点的快件送完 不让下一条路线再把 较近点作为起始送货站 2 少走重复路原则 由于在路途相等的条件下 重载费用要比空载费用大得多 因此 尽量让业务员空载行走 12 3 坐标贴近原则 在同一条路线中 离原点较近送货点的坐标仅次于较远点的 坐标 4 路线较少原则 路线多 一方面 相对最远点的选择多 跑的空路多 费用 就多 另一方面 过分地强调短暂效益 出动路线多 会引起业务员的反感 不利于 以后的人员控制 根据上述分析及基本假设 业务员送货的费用可以表示如下 重载费用 30 1 1 3 jxy j Mmjj 空载费用 830 2 11 2 ijxy ij Msjj 根据题意可知 业务员在第 i 条线路运送与不运送货物 所需时间 1 2 20 30 ijxy ijxy sjj T sjj T 所以总约束条件为 1 时间约束 30 1 1 6 30206 ijxyijxy ij j sjjsjj a 2 载重量约束 30 1 25 ijj j a m 3 路线约束 0 ijij as 10 10 ij ij a s 或 或 问题二选货物点的方法类似于问题一 例如 第一条行程中访问了节点 0 1 3 4 5 0 是因为 1 距离原点最近 因此由 1 出发 3 是距离 1 点最近的点 而且两处快件 量之和为 14kg 小于每个人最大负重量 可以继续指配 接着 4 是距离 3 最近的点 而且三处快件量之和为 19 5kg 仍小于 25kg 还可以继续指配 在剩下的未服务送货 点中 5 距离 4 最近 其实距离 4 最近的点有 2 5 6 7 四个点 然后考虑该点需求 的快件量 将其从大到小依次排列 快件量需求大者优先 但超过 25kg 上限的点舍去 这里 2 7 被舍去 故选择了 5 总快件量之和为 24kg 再继续扩充 发现就会超出 25kg 这个上限 因此选择返回 所以 0 1 3 4 5 就为第一条路线所含有的送货点 并且因为每个点周围的临近点中 之间距离最短 其所需路费就越少 并且因为每个点周围的临近点中 之间距离最短 其所需路费就越少 根据路线约束 13 条件 3 以及坐标知 送货点 1 2 首先必须作为某路线的最近起始送货点 再结合 时间约束条件 载重量约束条件 每次出发不能超过 25kg 以及上述分析的有关内容 依次选出各路线的次近点 并做统筹兼顾 一直到满足约束条件的最大值为止 因此得出八个业务员的行进路线 1 013450 2 0213760 3 01012890 4 0161720140 5 022212315110 6 01925240 7 01826280 8 02729300 由此我们得知各业务员的具体路线和所得费用 现列表如下 业务员编号过站总数所用时间 小 时 总载重 千克 总费用 元 142 0324767 5 242 7324 21390 6 342 5722 91357 5 443 1017 71438 4 555 2022 92680 6 633 33252310 2 734 1723 52620 14 834 3024 32891 9 合计 3027 46184 515456 7 由上表可知 1 第一条路线和第六条路线可以由一名业务员来完成 2 第二条路线和第三条路线可以由一名业务员来完成 所以总共需要 6 名业 务员 即最后确定行走路线为 1 0134501925240 2 02137601012890 3 0161720140 4 022212315110 5 01826280 6 02729300 在以上方案中 本问题得到的总费用最小值为 15456 7 元 每条路线行走的过程如下 15 问题 3 由于问题将业务员的工作时间延长到 8 个小时 又因为业务员的工作时间加上休 息时间总和不能超过 8 个小时 所以只需在问题一所建模型与假设的基础上 只需对 问题中对时间的约束进行改变即可 因此 此模型满足路程最短目标函数 建立如下模型 830 11 min2 ijxy ij sjj 约束条件为 30 1 8 1 30 1 30 1 1 1 25 2 1 8 256 01 01 ij j ij i ijij ijj j ijxy ij j ij ij s a as sta m sjj a s a 或 或 根据题意可知 问题三和问题一的目标函数一样 约束条件只是增加其中工作时 间为 8 小时 不优先考虑费用 即 此问题所建立模型所得行进路线与问题一的行进 路线一样 即 1 028302923150 2 0262780 3 024251490 4 02018171660 5 0112122100 6 0191370 7 041230 8 02510 每个业务员所工作的具体情况如下表所示 业务员编号过站数所用时间 小 时 总路程 千米 总载重量 千 克 16 154 8310024 1 233 547624 3 343 396822 4 453 155824 4 542 835423 6 632 665420 8 732 184224 2 831 632820 7 合计 3024 21480184 5 因为工作时间增为 8 小时 所以用类似于问题一的方法可进一步优化 但考虑到 每个业务员工作时间尽量相差不大