快递员配送路线优化模型_第1页
快递员配送路线优化模型_第2页
快递员配送路线优化模型_第3页
快递员配送路线优化模型_第4页
快递员配送路线优化模型_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

快递员配送路线优化模型 摘要 如今 随着网上购物的流行 快递物流行业在面临机遇的同时也需要不断 迎接新的挑战 如何能够提高物流公司的配送效率并降低配送过程中的成本 已成为急需我们解决的一个问题 下面 本文将针对某公司的一名配送员在配 送货物过程中遇到的三个问题进行讨论及解答 对于问题一 由于快递员的平均速度及在各配送点停留的时间已知 故可 将最短时间转换为最短路程 在此首先通过 Floyd 求最短路的算法 利用 Matlab 程序将仓库点和所有配送点间两两的最短距离求解出来 将出发点与配 送点结合起来构造完备加权图 由完备加权图确定初始 H 圈 列出该初始 H 圈 加点序的距离矩阵 然后使用二边逐次修正法对矩阵进行翻转 可以求得近似 最优解的距离矩阵 从而确定近似的最佳哈密尔顿圈 即最佳配送方案 对于问题二 依旧可以将时间问题转化为距离问题 利用问题一中所建立 的模型 加入一个新的时间限制条件 即可求解出满足条件的最佳路线 对于问题三 送货员因为快件载重和体积的限制 至少需要三次才能将快 件送达 所以需要对 100 件快件分区 即将 50 个配送点分成三组 利用距离矩 阵寻找两两之间的最短距离是 50 个配送点中最大的三组最短距离的三个点 以 此三点为基点按照准则划分配送点 关键字 Floyd 算法 距离矩阵 哈密尔顿圈 二边逐次修正法 矩阵翻转 问题重述 某公司现有一配送员 从配送仓库出发 要将 100 件快件送到其负责的 50 个配送点 现在各配送点及仓库坐标已知 货物信息 配送员所承载重物的 最大体积和重量 配送员行驶的平均速度已知 问题一 配送员将前 30 号快件送到并返回 设计最佳的配送方案 使得路程最 短 问题二 该派送员从上午 8 00 开始配送 要求前 30 号快件在指定时间前送到 设计最佳的配送方案 问题三 不考虑所有快件送达的时间限制 现将 100 件快件全部送到并返回 设计最佳的配送方案 配送员受快件重量和体积的限制 需中途返回取快件 不考虑休息时间 符号说明 n 个矩阵 n D 各个顶点的集合V 各边的集合E 每一条边 ij e 边的权 e w 加权无向图G 定点 ij v v 哈密尔顿圈C 最佳哈密尔顿圈 i f V 模型的建立 一 基本假设 1 假设送货员的始终以 24 千米 小时的速度送货 中途没有意外情况 2 假设送货员按照路径示意图行走 3 假设仓库点为第 51 点 4 假设送货员回到仓库点再次取货时间不计 2 模型建立与求解 问题一 1 数据处理 使用数据处理软件 处理附表 2 求出给定配送点之间的相互距离 最终使用 矩阵对处理数据进行数据统计整理 131916 182864 2207823 51182182 51211797 51261392 矩阵前两列表示相互连接的配送点 第三列表示相邻两配送点之间边的距 离 使用上述数据矩阵可以构造路线示意图的带权邻接矩阵 再用 Floyd 算法 求出各配送点之间的距离 2 Floyd 算法基本思想 直接在示意图的带权邻接矩阵中 通过插入定点的方法构造出 n 个矩阵 最后得到的矩阵为距离矩阵 同时求出插入点矩阵以便得到两 12 n D DD n D 点之间的最短路程 123495051 1077451916203061698910068 27745058292557022001 16926 3191658290207051738810467 0 492030625570207050356911721 50169892200117388356909928 511006816926104671172199280 令为一个加权无向图 其中表示各个顶点的集合 GV E V 其中表示各边的集合 而 图 012 n Vv v vv E ijEe ijij ev v 中每一条边都对应一个实数 则称为边的权 如果任意两边相连 G ij e e w e w 则为完备图 G 设是连通无向图 经过的每个定点正好形成一个圈 则称 GV E G 为哈密尔顿圈 简称 H 圈 最佳哈密尔顿圈是在加权图中 权最小G GV E 的哈密尔顿圈 判定一个加权图是否存在哈密尔顿圈是一个 NP 问题 而它的完 GV E 备加权图 中每条边的权等于之间的最短路径的权 中一定存 GV E E ij v v 在哈密尔顿圈 所以需要在完备加权图中寻求最佳哈密尔顿圈 该 GV E 过程需要采用二边逐次修正法并且利用矩阵翻转实现 3 二边逐次修正法的选法过程 1 任取初始 H 圈 012 1 ijn Cv vvvv v 2 对所有的 若 11i jijn 1111 ijijiijj w v vw vvw v vw v v 则在中删去边和而加入边和 形成新 0 C ij w v v 11 ij w vv 1 ii w v v 1 jj w v v 的 H 圈 即C 12 1 ijn Cv vvvv v 3 对 C 重复步骤 2 直到条件不满足为止 最终得到的即为所求 C 4 矩阵翻转 在一个矩阵中 对他的第 i 行 列 到第 j 行 列 翻转是以 i 行 列 和 j 行 列 的中心位置为转轴 旋转 180 度 这样 第 i 行 列 和第 j 行 列 位置互换 第 i 1 行 列 和第 j 1 行 列 位置互换 图一 由附录给定的快件信息可知 130 号快件总重量为 48 5kg 体积为 0 88m3 显然送货员可以一次性携带所有货物到达配送点 经统计配送点共有 21 个 即 13 14 16 17 18 21 23 24 26 27 31 32 34 36 38 40 42 V 43 45 49 首先在程序里设置限制 30 0 30 0 50 1 i i i i w v 将出发点 51 点与 21 个送货点结合起来构造完备加权图 由完备加权图确 定初始 H 圈 列出该初始 H 圈加点序的距离矩阵 然后使用二边逐次修正法对 矩阵进行翻转 可以求得近似最优解的距离矩阵 从而确定近似的最佳哈密尔 顿圈 由于使用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关 为得 到更优解 在使用软件编程时 随机搜索出若干个初始 H 圈 例如 2000 在所 有的 H 圈中筛选权值最小的一个 即就是最佳 H 圈 最佳 H 圈的近似解为 2000 1 i i f V min i f V 在中删去边和而加入边和 形成新的 0 C ij w v v 11 ij w vv 1 ii w v v 1 jj w v v H 圈 C 最终由编程得到近似最佳配送路线以及总长度 图二 最佳配送路线 解得路线总长为 54709m 耗时 226 77min 问题二 因货物可在一次性配送 故可以不用考虑送货员的最大载重与体积问题 但是较于问题一在选择路线上 需要考虑送货时间问题 不得超过指定时间 所以在问题一的程序中需要再增加时间限制 30 0 30 0 50 1 0 1 2 30 i i i i ii w v Tt i 结合问题一 使用相同方法求解最佳 H 圈 图三 最佳配送路线 26 51 解得路线总长为 54996m 耗时 227 50min 问题三 由附录给定的快件信息知 1100 号快件总重量为 148kg 体积为 2 8m3 由于考虑送货员的最大载重与体积 送货员必须分多次配送快件 送货员显然 至少需要连续三次配送 才能完成配送任务 因此问题三存在配送点分组 以及每组求最佳配送方案这两个问题 首先 需要制定一种比较合理的划分准则 使三组总长加起来最短 需要选择三个点 作为每一组的基点 要求这三个点两两之间的最短距离是 50 个配送点中最大的 三组最短距离 利用距离矩阵查找其他任意点与三个基点之间的距离 距离哪 一个基点近 就被划分在哪一组 通过计算三个基点为 9 号 28 号 43 号配送点 通过距离矩阵将 100 件 快件的配送点分组如下 表一 使用问题一与问题二中相同的方法 首先将出发点与其他组内点结合起来 配送方案重量 kg 体积 m3 一123456789 10 14 16 17 18 21 23 32 3549 90 9112 二11 12 13 15 19 20 22 25 26 28 29 30 33 41 44 46 4848 380 985 三 24 27 31 34 36 37 38 39 40 43 45 47 49 5049 720 9038 求和1482 8 构造完备加权图 由完备加权图确定初始 H 圈 列出该初始 H 圈加点序的距离 矩阵 然后使用二边逐次修正法对矩阵进行翻转 可以求得近似最优解的距离 矩阵 从而确定近似的最佳哈密尔顿圈 图四 最终由程序解得三组最佳配送路线为 第一组 解得路线总长 52743m 耗时 227 4min 第二组 1851 解得路线总长 47736m 耗时 221 4min 第三组 解得路线总长 42421m 耗时 208 2min 模型的优缺点点评 对于问题一所建立的模型 通过 Floyd 算法和二边逐次修正法找到最优

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论