快递公司送货策略的优化设计

快递公司送货策略的优化设计快递公司送货策略的优化设计 摘要 在快递送货过程中 合理选择送货线路是极其重要的 它不仅可以加快配送 速度 提高服务质量 还可以有效的降低配送成本 增加经济效益 本文构建了 送货线路的规划模型 将送货问题转化为运筹学中的旅行推销问题进行求解 但在街道平行行走中 以阶梯法求最短路程 根据运输路线优化策略中的时间 的最优组法 用射线旋转法进行区域划分 以送货重量的为划分依据 90 80 利用整数规划对每一个区域进行线路规划 从而得到最优线路 该模型对物流 企业合理安排送货线路 提升运送效率有着很强的理论指导作用 因而有着重大 的实用价值 1 问题的提出 在快递传递工程中 所有快件在早上点钟到达 要求于当天点之前必 717 须派送完毕 每个业务员每天平均工作时间不超过小时 在每个送货点停留 6 的时间为分钟 途中速度为 每次出发最多能带重量 公司平 10hkm 25 kg25 均每天接受到总重量为的快件 kg 5 184 1 1 每天接收到的总重量是否全部送至个送货点 30 1 2 每个业务员工作时间不超过 8 小时 每个业务员的平均工作时间不超过 6 小时 假如某一业务员每天送完第一线路后是否再有下一次线路 1 3 如何使用射线旋转法与旅行推销问题中特殊的 阶梯法 求解 2 问题的分析 2 1 对于现实问题当中 每个送货点每天的送货量有一定的波动 对某些送货 点就单独某天是否送货 有一定的概率 根据题意 结合所有个送货点总重 30 量约等于每天接受的重量 因此我们不考虑其他因素 直接对个送货点 kg 5 184 配备送货策略 2 2 送货线路与业务员有间接关系 但送货路线数不等于业务员数 我们根据 最优送货线路的最短时间的关系组合来确定业务员的数量 因此为了消除送货 路线与业务员数的误差 我们提出以 所携带总重量的 80 90 的依据 2 3 我们提出射线旋转法 将随机的 不确定的 无规律的点进行区域划分 再对每个线路又进行线路规划 这样 可有效减少线路重复问题 他是解决 旅游途中如何经过旅游单中的城市而 不重复旅游过的城市却要行程距离最 短 其中两点直线走法 涉及到现实 生活中很多实际的问题 而 快递转 送 是旅游推销问题中的特殊问题 它以街道平行的轴进行两直角边行走 例如图 1 所示 A B C 直线走最短 但在平行街道当中 以 如上阶梯法 走最短 3 模型假设 根据个送货点所处的位置的随机性及送货过程中行走路程的重复性和行 30 程最短问题 我们 射线旋转法和阶梯法 的模型假设 其中射线旋转中依据 所携带总重量的 80 90 以整个区域划分为主 个别小区域等不符合区域以单 独进行射线旋转法划分 以做到整数规划 再对每一个区域进行线路规划 然 后用阶梯法进行求最短问题 4 符号说明 G 送货总重量 在 点所卸的货的重量 i W i 两条射线所夹送货点重量之和 n r r max W 其中 p max x n r rx W A 表示两条射线所夹送货点重量之和 n r r max W 100 max p n 1i x G W x 表示两条射线所夹部分区域记为 x A x A 在图 3 和图 4 中 表送货点数 表示 送货点所卸的货重 yx xyx 区域中走完所有送货点的最短距离 min SAx x A 表示原点到点 点最短距离 X SOx 表示点 到点所走的最短距离 min yx S xy 表示在区域中 满足的所需要的时间 min x A t x A min x S 表示区域中所夹的送货点数 n x A 表示第区域中支出金额最少所走的距离 min S Ax x A 表示在区域中 满足的所需要的时间 min x A t x A min S Ax 在区域中 给业务员所支付的费用 x A M x A A 点与 C 点的最短距离 m inSAC 5 模型建立及求解 5 1 模型建立 5 11 射线旋转法假设 5 111 以快递公司及发货中心 平行于街道的直线为坐标建立直角坐标系 射线旋转法进行划分依据 射线旋转法以送货总重量的快递公司每个业 G 务员的每次最多能携带的重量为划分依据 但为了整体划分 90 80 kg25 精确模式 在此基础上可以波动 定义送货总量的的依据 是考 90 80 G 虑到克服所有送货人所携带重量的参差性和送货路线与送货人数的相关性 这 样可以大幅度的个别因素对整体的影响 记每个发货量最大不超过 当射线旋转时与射线重合的点记 G 相应于该点出所卸的货的重量 ii YXP i W 以轴为初始射线 以点为圆心 按逆时针方向旋转 当遇到第一个点 x1 l O 时 判断 90 80 1 GW 若满足继续旋转 直临界射线 且 2 l 90 80 max n 1i i GW 时停止 并记该区域为 p max 1 n 1i i1 WA 其中 100 max p n 1i i 1 G W 以为初始射线旋转 当遇到相应下一点时 判断 2 l M 90 80 m GW 若满足继续旋转直到临界射线 且 3 l 90 80 max n 1im m GW 时停止 并记该区为 p max 2 n 1i m2 WA 以此类推 以做初始射线旋转 当遇到下一点是 k l R 90 80 r GW 若满足继续旋转直到临界射线 使满足 1k l 90 80 max n r r GW 时停止 并记该区为 p max x n r rx W A 5 112 在 5 111 中规划区域中 当射线旋转到有两个或多个点重合时且 时 我们应该如下 GW n r r max 5 1121 当射线 旋转到有两个或多个点重合或 i lGW n r r max 时 将射线继续旋转直到 使满足 1 i l 90 80 2 max n r r GW 时为止 若同时也有两个或多个点重合或时将射线继续旋转 1 i l 2 max n r r GW 直到 使满足 2 i l 90 80 3 max n r r GW 同理 若同时也有两个或多个点或时 将射线旋转直到 ji l GW j max n r r 使满足 1 ji l 90 80 1j max n r r GW 时为止 继续如上划分直到完毕 5 1122 将划分出的区域有的区域继续利用射线旋转再进行筛GW n r r max 选 选出符合条件的最优区域 5 12 阶梯法模型 行走路线像阶梯一样的模型 我们定义为阶梯模型 对于射线旋转法可以确定每条路 线所经过的送货点 至于如何走 最近 我们根据模型特点 证明 一个 公理 例 例如如图 2 所示 B 在 A C 两点的对角线的矩形里面 从 A 带你出发 经过 B C 两点 走法又回到 A 点 只能沿如图线 路走 每条线段长为 L 求证 阶梯法是走法最短的一种方式 证明 A C 行程路径 LinSAC6 m A B 行程路径 LinSAB3 m B C 行程路径 LinSBC3 m 显然 因此 当 在以 AC 为对角线的矩形里 m m m inSinSinS BCABAC 且 B 在 A 通往 C 某一条线路里 我们可直接用阶梯法走是距离最短的一条方案 5 2 求解旋转 以射线旋转法为理论依据作图解答 5 21 如图所示 以为原点 以轴为起始射线绕旋转 当Ox 0 lO 时 记该区域为 25 max n 1i i W 100 25 1 A 再以 区为起始射线绕逆时针旋转到时得到符合 1 A 1 lO 2 l 90 80 max n 1i i GW 记该区域为 74 5 18 2 A 再以区为起始射线绕旋转到时出现模糊地选法 即有两个或多个点 1 A 2 lO 1 k 重合或 故继续旋转到射线时 送货点GW n r r max 90 80 252kg 2 k 与在同一条直线上 故继续旋转 使满足313 90 80 3 max n r r W 为止 记该区域为 8 240 2 60 3 A 再以区 为起始射线绕旋转到时 使满足 3 A 3 lO 4 l 90 80 max n r GW r 为止 记该区域为 4 74 6 18 4 A 再以为起始射线绕旋转到时 使满足 4 lO 5 l 90 80 max n 1i i GW 记该区域为 6 93 8 23 5 A 最后将与轴区域记为 5 ly 90 5 22 6 A 如图 3 所示 5 22 由以上可划分出最优选点策略 区 1 A 2 A 4 A 5 A 6 A 将区用射线旋转法划出最优区 作法如下 3 A 以为初始射线 绕顺时针旋转到时得到符合 3 lO 2 k 90 80 max n 1i i GW 记该区域为 2 79 8 19 31 A 再以为初始射线 绕顺时针旋转到时得到符合 2 kO 1 k 90 80 max n 1i i GW 记该区域为 81 3 20 32 A 最后记录和 之间的区为 如图 4 所示 2 k 2 l 4 80 1 20 33 A 5 3 根据阶梯法求解行程距离最短时的优化区域的线路选择 区中 1 A min min min min min 3211329119 1 SSSS A S 277812 km54 所需时间 n S t A A 6 1 25 min min 1 1 h0 3 区中 2 A min min min min min 231523121512 2 SSSS SA 3616820 km88 所需时间 n S t A A 6 1 25 min min 2 2 3 6 1 25 75 h5 3 区中 33 A min min min min 29272927 33 SSS SA 41734 km82 所需时间 n S t A A 6 1 25 min min 33 33 2 6 1 25 82 h613 3 区中 32 A min min min min min min 301330813181 32 SSSSS SA 46256105 km92 所需时间 n S t A A 6 1 25 min min 32 32 4 6 1 25 92 h35 4 区中 31 A min min min min min 2819283193 31 SSSS SA 4417189 km88 所需时间 n S t A A 6 1 25 min min 31 31 3 6 1 25 88 h02 4 区中 4 A min min min min min min 24252414257147 4 SSSSS A S km68 所需时间 n S t A A 6 1 25 min min 5 4 4 6 1 25 68 h39 3 区中 5 A min min min min min min 18171820174204 5 SSSSS A S 28651011 km60 所需时间 n S t A A 6 1 25 min min 5 5 4 6 1 25 60 h06 3 区中 6 A min min min min min 16516252 6 SSSS S A A 18686 km38 所需时间 n S t A A 6 1 25 min min 6 6 4 6 1 25 38 h19 2 由以上计算可得总路程 总时间分别为 minminminminmin min 431323321 AAAAAA SSSSSS S minmin 65 AA SS 3860688892828854 km570 minminminmin min 31323321 AAAAA ttttt t minminmin 654 AAA ttt 19 206 339 302 435 4613 35 33 h127 27 因此平均人数 6 t Men 52 4 所以需要 5 个业务员 总的运行公里数为 570km 为了减少每个人所携带重量的相对参差性 我们将时间最短的四组组合 使 其按大小排序 第一个和第三个组合 第二个和底四的个组合 即 最小四个为 3 5 3 06 3 2 19 可得到时间为 2 19 与 3 06 3 与 3 5 的路线各一人送货 综上所述 时间为 2 19 与 3 3 06 与 3 5 3 613 4 35 4 02 的路线分别分派一个人 去送货 每人的送货路线依次为 第一个业务员 区中 9 11 32 22 10 号送货点 1 A 区中 12 15 23 号送货点点 2 A 第二业务员 区中 4 20 17 18 号送货点 5 A 区中 2 5 16 6 号送货点 6 A 第三业务员 区中 27 29 号送货点 33 A 第四业务员 区中 1 8 13 30 号送货点 32 A 第五业务员 区中 3 19 28 号送货点 31 A 5 4 根据送货路程价位 我们只能让离原点最远的点最后走 因此我们对每 个区域再进行阶梯法预算得 区中 32 送货点最后走的最短路径时 支付金额和时间分别为 1 A 32113211109109 min min min min min 1 SSSSSSA 2776612 km58 2min3 min min min min 32113211109109 1 SSSSSM A 227331 元 147 n SSSSS tA 6 1 30 min 20 min min min min min 32113211109109 1 5 6 1 30 27 20 31 h28 3 区中 23 送货点最后走的最短路径 支付金额和时间分别为 2 A min min min min min 231523121512 2 SSSSSA 3616820 km88 2 min 3 min min min 231523121512 2 SSSSM A 236344 元 204 n SSSS tA 6 1 30 min 20 min min min min 231523121512 2 5 6 1 30 36 20 44 h23 4 区中 29 送货点最后走的最短路径 支付金额和时间分别为 33 A min min min min 29272927 33 SSSSA 41734 km82 2 min 3 min min 29272927 33 SSSM A 241341 元 205 n SSS tA 6 1 30 min 20 min min min 29272927 33 2 6 1 30 41 20 41 h75 3 区中 30 送货点最后走的最短路径 支付金额和时间分别为 32 A min min min min min min 301330813181 32 SSSSSSA 46256105 km92 3 min min min min 1330813181 32 SSSSM A 2 min 30 S 246346 元 230 n SSSSS tA 6 1 30 min 20 min min min min min 301330813181 32 4 6 1 30 46 20 46 h5 4 区中 28 送货点最后走的最短路径 支付金额和时间分别为 31 A min min min min min 2819283193 31 SSSSSA 4417189 km88 3 min min min 19283193 31 SSSM A 2 min 28 S 244344 元 220 n SSSS tA 6 1 30 min 20 min min min min 2819283193 31 3 6 1 30 44 20 44 h17 4 区中 24 送货点最后走的最短路径 支付金额和时间分别为 4 A min min min min min min 24252414257147 4 SSSSSSA km68 2 min 3 min min min min 24252414257147 4 SSSSSM A 234334 元 170 n SSSSS tA 6 1 30 min 20 min min min min min 24252414257147 4 4 6 1 30 34 20 34 h5 3 区中 18 送货点最后走的最短路径 支付金额和时间分别为 5 A min min min min min min 18171820174204 5 SSSSSSA 28651011 km60 2 min 3 min min min min 18171820174204 5 SSSSSM A 228332 元 150 n SSSSS tA 6 1 30 min 20 min min min min min 18171820174204 5 4 6 1 30 28 20 32 h2 3 区中 16 送货点最后走的最短路径 支付金额和时间分别为 6 A min min min min min min 1651665262 6 SSSSSSA 186646 km40 2 min 3 min min min min 1651665262 6 SSSSSM A 218322 元 102 n SSSSS tA 6 1 30 min 20 min min min min min 1651665262 6 4 6 1 30 18 20 32 h37 2 综上所述 minminminminmin min 431323321 AAAAAA SSSSSSS minmin 65 AA SS 4060688892828858 km576 minminminmin min 31323321 AAAAA tttttt minminmin 654 AAA ttt 37 22 35 317 45 475 323 428 3 h29 minminminmin min min 31323321 AAAAA MMMMMM minminmin 654 AAA MMM 102150170220230205204147 元 1428 所需人数 6 t Men 6 29 83 4 因此需要 5 个业务员最省钱 公司将最少