国大便利店路线规划问题

物流规划课程设计 第 1 页 共 16 页 1 1 前言前言 随着社会主义市场经济的不断发展 作为 第三利润源泉 的物流对经济 活动的影响日益明显 引起了人们越来越多的重视 成为当前 最重要的竞争 领域 配送是连接生产与消费之间的一种中介服务 它是指按客户 包括零售 商店 用户等 的订货要求 包括货物种类 数量和时间等方面的要求 在物流 中心 包括配送中心 仓库 车站 港口等 进行分货 配货工作 并将配好的 货物及时送交收货人的物流活动 配送不是单纯的运输或送货 而是运输与其他活动 集货 分货 配货 的组合 是 配 与 送 的有机结合 因此对于配送问题的研究可分为对 配 和 送 两方面的研究 配 主要为配送中心选址问题 送 包括旅 行商问题 TSP 车辆路线优化问题 VRP 由于选址的外部因素 经济 基础 设施 环境等 及内部因素 企业战略 劳动力成本和素质等 的影响 单纯 考虑距离问题的选址是不合理的 因此在本文中不对 配 进行研究 主要对 送 进行研究 配送路线的优化 是配送优化中的一个关键环节 在配送过程中 配送线 路合理与否对配送速度 成本 效益影响很大 设计合理 高效的配送路线方 案 不仅可以减少配送时间 降低作业成本 提高企业的效益 而且可以更好 地为客户服务 提高客户的满意度 维护企业良好的形象 配送线路优化是指对一系列的发货点和收货点 组织适当的行车路线使车 辆有序的通过它们 在满足一定的约束条件下 货物需求量与发送量 车辆容 量限制 行驶里程限制 力争实现一定的目标 行驶里程最短 使用车辆尽可 能少 但配送作业情况复杂多变 不仅存在配送点多 货物种类多 道路网复 杂 路况多变等情况 而且运输服务地区内需求网点分布也不均匀 使得线路 优化问题是一个无确定解多项式难题 需要启发算法去求得近似最优解 配送 合理化与否是配送决策系统的重要内容 配送线路的合理与否又是配送合理化 的关键 选择合的理配送路线 对企业和社会都具有很重要的意义 对社会来说 它可以节省运输车辆 减少车辆空载率 降低了社会物流成 本 对其他企业尤其是生产企业具有重要意义 与此同时 还能缓解交通紧张 状况 减少噪声 尾气排放等运输污染 对民生和环境也有不容忽视的作用 物流规划课程设计 第 2 页 共 16 页 本文将以国大商贸连锁有限公司当前的配送线路的优化问题作为研究对象 对石家庄市内连锁便利店的需求量及运距进行分析计算 建立 VRP 数学模型 运用聚类算法和单回路法对建立的模型进行求解 对国大连锁的配送路线进行 优化 致力于为该公司提供较合理的配送方案 以期减少配送里程 降低物流 运输成本 提高该公司物流运作效率 客户服务质量和整体竞争力 物流规划课程设计 第 3 页 共 16 页 2 2 问题的提出与描述问题的提出与描述 2 12 1 国大连锁商贸有限公司的配送现状国大连锁商贸有限公司的配送现状 河北国大连锁商业有限公司是河北省较早成立并实行规范化管理的现代化 商业连锁企业 总部拥有先进的商业 MIS 系统 物流配送系统 视觉识别系统 专业培训兼管理系统 2002 年通过 ISO9001 2000 国际质量管理体系认证 36524 便利店 商标经国家商标局注册 曾连续三年跻身全国连锁百强企业 之列 公司以便利店为核心业态 经过多年的运作 现有便利店 300 多家 开 省内 24 小时营业之先河 并建立了电话网 INT 网 人力营销网 店铺网 在 省内首创了 四网并行 的商业模式 该公司是在 四网并行 的基础上 结 合企业实际 提出了信息驱动发展战略 配送中心的配送对象是分布于石家庄的加盟国大连锁商贸有限公司的便利 店 这些店基本覆盖了二环的大部分地区 也有部分二环以外部分 这些便利 店的需求在时间 数量上比较确定 一般采用自有车辆每天对这些店进行配送 配送时间一般选择在车流量较小的时段 大部分是选择在晚上 配送车辆为东 方小霸王厢式车 由于所配送货物一般为日用品和食品 车辆满载一般为一吨 各便利店需求量比较稳定一般为 0 1 0 3 吨之间 因为便利店店面较小 储藏 间也较小 因此需要每天配送 每天配送的电子系统根据各店的销售情况自动 向配送中心订货 生成配货拣货单 配送中心根据配货单向各店进行定时配送 每台配送车辆配送的超市却不是固定的 而且对各个超市进行配送时的路线选 择不固定 这样就有很大的随机性 造成时间和费用的浪费 2 22 2 提出问题提出问题 我们组针对国大便利店物流配送线路有很大的随机性 造成了人力物力时 间的浪费这一现象 对其配送线路进行科学的优化和整合 达到降低成本的目 的 通过对国大便利店的调查 我们得到 已知条件 1 所有零售便利店的集合 N 为已知 N 1 2 3 32 为便利店所在地 物流规划课程设计 第 4 页 共 16 页 2 从配送中心出发的配送车辆 经过所有需要配送的便利店 并把货物卸 下 并返回配送中心 配送车辆所经过的零售户的顺序称为路线 3 配送中心配送车辆统一 按载重量为 1 吨 4 便利店数量 地理位置为已知 且每一个便利店的需求量为已知 5 各零售点之间的距离为已知 目标 车辆应用台数 各车行走的路径 使总的距离最少 用车较少 约束条件 1 配送车辆的车载辆 一辆车的载重辆为一吨 2 地理上相对集中的零售户由一辆送货车进行送货 3 送货车辆按每天的订单数量出库 4 配送车辆尽可能满载 5 每天送货路线的工作线路基本均衡 解决思路 以聚类算法为基础 以车载量和路线最短为约束条件 运用 spss 软件的 K 均值聚类分析形成聚类区域 最后用单回路运输 TSP 模型的最近插入法进 行配送路线的优化 物流规划课程设计 第 5 页 共 16 页 3 3 方法介绍方法介绍 3 13 1 聚类算法简介聚类算法简介 聚类算法是一种新兴的多元统计方法 是当代分类学与多元分析的结合 聚类分析是将 分类对象置于一个多维空间中 按照其空间亲疏进行分类 通俗 地讲 聚类分析就是根据事 物彼此不同的属性进行辨认 将具有相似属性的事 物聚为一类 使得同一类事物具有高度的 相似性 相似或不相似的度量基于数 据对象的描述的取值来确定的 通常是利用距离进行描 述 常见的聚类分析方 法有 1 切割的聚类方法 代表算法有 K MEANS 算法 ISODATA 算法 等 2 层次的聚类方法 代表算法 CURE 算法 3 基于密度的聚类 代表算法 DBSCAN 算法 等 4 基于网格的聚类 代表算法 CLIQUE 算法等 零售行业配送线路优化需要对零售户的空间地理数据进行聚类分析 由于 数据量较大 需要一个效率高的算法 而且 K MEANS 算法 适合于数据型数据 对数据输入顺序不敏感等特点 为比较适合的一种算法 K MEANS 聚类算法的 基本思路是 首先从 n 个数据对象任意选择 k 个对象作为初始聚类中心 而 对于所剩下其它对象 则根据它们与这些聚类中心的相似度 距离 分别将它 们分配给与其最相似的 聚类中心所代表的 聚类 然后再计算每个所获新聚 类的聚类中心 该聚类中所有对象的均值 不断重复这一过程直到所有中心都 不在变化为止 k 个聚类具有以下特点 各聚类本身尽可能的紧凑 而各聚类 之间尽可能的分开 3 23 2 K MEANSK MEANS 聚类法聚类法 K MEANS 聚类算法有两个关键问题需要解决 一是初始聚类中心的个数 二是初始聚类中心的位置 1 初始聚类中心的个数 也是配送区域划分的个数 也就是为这些配送区域 送货的送货量配送车辆的台数 即 k 配送车辆的台数 车载量 1 加 1 主要考 虑车辆配装时不可能完全满载 2 初始聚类中心的位置 原算法是随机的 为提高聚类的效果 优化聚类的 结果 依照密度的分布 对初始聚类中心优化生成 以每个零售户的地理数据 物流规划课程设计 第 6 页 共 16 页 点为圆心 以数据库中零售户地理信息表中所有地理数据之间距离的平均值为 半径作圆 然后根据每个圆内的数据点的密度来排序确定初始聚类中心 这样 k means 聚类算法需要的初始中心就由以上算法生成 而无需用户进行事先 指定 整个过程包括以下几个基本步骤 1 将数据库中的每个点都看成一个类 计算所有点之间的距离 生成距离矩阵 两点之间欧式距离为 22 1 2 3 ijijiji jn Dxxyy 2 选取 2 个整数 一般 R2 2 R1 其中 R1 为数据库中所有点之间距离的平均 值 nn D D n j ij n i 11 3 以每个点为圆心 以 R1 为半径作圆 计算落在每个圆内的点的数目 即样 本密度 如求的样本密度 iij A x y i r Step1 令 0 i r Step2 取 判断其是否落在以以 R1 为半径的圆内 其判断方 iij A x y iij A x y 法为 如上述成立 则 22 1 ijijij A Ax xy yR 1ii rr Step3 判断是否所有点均已判断完 如果完毕 即为的样本密度 否则 i r i A 判断下一点 重复第二步 4 将样本密度按从大到小的顺序排列 取密度最大者作为第一个聚类中心 Z1 选择密度次大的数据点 若与第一凝聚点 Z1 之间距离大于 R2 即 Z Z 则把作为第二个凝聚点 Z2 否则继续判定下一密度最大者 若 1 2Z ZR Z 下一密度最大者的点与前面若干个凝聚点之间距离均大于 R2 则将之作为又一 新的凝聚点 如此反复迭代直到要求聚类的数目 K 3 33 3 单回路运输单回路运输 TSPTSP 模型的最近插入法模型的最近插入法 单回路运输问题是指在路线优化中 设存在节点集合 D 选择一条合适的 路径遍历所有的节点 并且要求闭合 单回路运输模型在运输决策中 主要用 于单一车辆的路径安排 目的在于在该车辆遍历所有用户的同时 达到所行驶 距离最短 物流规划课程设计 第 7 页 共 16 页 TSP 模型是单回路运输问题的最为典型的一个模型 它的全称是 Traveling Salesman Problem TSP 中文叫做旅行商问题它是一个典型的 NP Hard 问题 对于大规模的线路优化问题 无法获得最优解 只有通过启发式算法获得近优 解 TSP 模型可以如下描述 在给出的一个 n 定点网络 有向或无向 要求找 出一个包含所有 n 个定点的具有最小耗费的环路 任何一个包含网络中所有 n 个顶点的环路被称作一个回路 在旅行商问题中 要设法找到一条最小耗费的 回路 既然回路是包含所有顶点的一个循环 故可以把任意一个点作为起点 因此也是终点 这也是 TSP 模型的一个特点 最近插入法是 Rosenkrantz 和 Stearns 等人在 1977 提出的另外一种用于解 决 TSP 问题的算法 可以找到相对比较满意的解 最近插入法由 4 步来完成 1 找到最小的节点 形成一个子回路 1k C k v 11 k Tv v v 2 在剩下的节点中 寻找一个离子回路中某一节最近的节点 k v 3 在子回路中找到一条弧 i j 使得最小 然后将节点 ikkjij ccc 插入到节点之间 用两条新弧 i k k j 代替原来的 k v ij v v 弧 i j 并将节点加入到子回路中 k v 4 重复步骤 2 3 直到所有的节点都加入到子回路中 物流规划课程设计 第 8 页 共 16 页 4 4 国大便利店配送路线优化国大便利店配送路线优化 据了解 国大 36524 便利店在石家庄市区共有 304 店 我们根据其需求量 及各店面地理位置共取 32 个主要店面来做线路优化 各便利店分布如下图 4 1 图 4 1 石家庄国大便利店主要店面分布图 4 14 1 对国大便利店进行聚类分析对国大便利店进行聚类分析 建立直角坐标系如图 4 2 确定各个便利店的具体坐标位置如表 4 1 物流规划课程设计 第 9 页 共 16 页 图 4 2 便利店直角坐标系 表4 1 国大便利店具体坐标位置 编 号 12345678910111213141516 X 35 34 44 63 33 86 27 88 65 84 35 110 49 48 97 9 Y 9 79 49 07 77 25 16 08 09 44 82 92 97 67 15 33 4 编 号 17181920212223242526272829303132 X 11 5 1311 9 9 913 6119 112 310 712 35 67 22 93 91 22 5 Y 7 07 06 05 15 44 52 93 42 82 71 45 18 54 06 55 5 确定配送车辆台数 k 送货量 车载量 1 调查得国大便利店用车载重量为 1 吨 调查各个便利店的平均需求量为下表 4 2 表 4 2 国大各便利店的日平均需求量 编号需求 量 编号需求 量 编号需求 量 编号需求 量 10 1590 27170 22250 16 20 18100 2180 23260 11 30 22110 28190 17270 18 40 20120 19200 18280 16 50 18130 13210 26290 23 物流规划课程设计 第 10 页 共 16 页 60 25140 22220 12300 25 70 15150 16230 15310 29 80 25160 2240 27320 22 可知各便利店日平均需求量总和为 Q 6 43 吨 所以配送车辆台数 k 6 43 1 1 7 43 约为 K 7 辆 运用前面所述 K 均值聚类法步骤利用 spss 软件进行 K 均值聚类分析 可得 结果为表 4 3 表 4 3 聚类成员及距离 聚类成员聚类成员 编号聚类距离编号聚类距离 111 3371731 193 211 371183 820 31 386193 695 411 2882072 090 561 5822131 453 661 0262251 286 772 0332372 152 821 250245 727 921 4472551 034 1072 062265 974 114 8602741 166 124 510287 792 1321 4152911 195 142 9893061 918 1571 2253161 912 1671 258326 468 整理表 4 3 可得便利店的聚类结果表 4 4 表 4 4 聚类结果 聚类1234567 物流规划课程设计 第 11 页 共 16 页 所包含 的便利 店 1 2 3 4 29 8 9 1 3 14 17 18 19 2 1 11 12 27 22 24 25 2 6 5 6 3 0 31 32 7 10 15 16 20 2 3 28 根据表 4 4 在图中画出聚类分布图 4 3 图 4 3 聚类分布图 由 spss 软件进行聚类分析得到聚类中心的坐标位置为下表 4 5 表 4 5 最终聚类中心 最终聚类中心最终聚类中心 聚类 1234567 x 轴4 09 012 55 011 62 97 9 y 轴8 98 06 42 43 35 74 7 4 24 2 对聚类结果进行调整对聚类结果进行调整 聚类完成后 还应根据车载量这个约束条件对聚类结果进行判断调整 Step1 计算每一个聚类内的便利店需求量的总和 Step2 判断每一聚类内便利店的需求量的总和是否超过车载量 如果未超过 说明符合条件 如果超过车载量 选择该聚类中距离质心最远的点 将其拟归入距离其他 类质心距离最近的类 归入某一类前 还必须判断如归入后该类的便利店需求 量的总和是否小于车载量 如果小于 即将该数据归入该类 否则 选择欧式 物流规划课程设计 第 12 页 共 16 页 距离再次之的类作为拟归入的类 同样判断该类便利店需求量是否小于车载量 是否小于车载量 如果小于则归 否则选择距离再次之的 Step3 当所有的类零售户订单量总和都小于车载量时 暂告一段落 调整完毕以后 每一类的便利店地理位置相对集中 且订单量总量小于车 载重量 聚类 1 总需求量 Q1 0 15 0 18 0 22 0 2 0 23 0 98 车载量 聚类 2 总需求量 Q2 0 25 0 27 0 13 0 22 0 87 车载量 聚类 3 总需求量 Q3 0 22 0 23 0 17 0 26 0 88 车载量 聚类 4 总需求量 Q4 0 28 0 19 0 18 0 65 车载量 聚类 5 总需求量 Q5 0 12 0 27 0 16 0 11 0 66车载量 聚类 7 总需求量 Q7 0 15 0 2 0 16 0 2 0 18 0 15 0 16 1 2 车载量 聚类 6 需求量总和超过车载量 选取聚类 6 中距离其质心最远的点为便利 店 30 其需求量为 0 25 吨 将其归入距离其他其他聚类质心距离最近的类 为聚类 4 计算将便利店 30 归入聚类 4 中后 聚类 4 的需求总量为 0 9 吨 小 于车载量 所以聚类 4 为 11 12 28 30 聚类 7 需求量总和超过车载量 选取聚类 7 中距离其质心最远的点为便利 店 23 其需求量为 0 15 吨 将其归入距离其他其他聚类质心距离最近的类 为聚类 5 计算便利店 23 归入聚类 5 中后 聚类 5 的需求总量为 0 81 吨 小 于车载量 但聚类 7 去掉点 23 后总需求量仍大于车载量 所以继续选取聚类 7 中距离其质心最远的点为便利店 20 其需求量为 0 18 吨 将其归入距离其他 其他聚类质心距离最近的类 为聚类 5 计算便利店 20 归入聚类 5 中后 聚类 5 的需求总量为 0 99 吨 小于总车载量 同时此时聚类 7 的总需求量为 0 87 吨 也小于车载量 所以聚类 5 为 20 22 23 24 25 26 聚类 7 为 7 10 15 16 28 对聚类进行调整后 新得到的聚类如下表 4 6 表 4 6 改进后的聚类中心 聚类1234567 物流规划课程设计 第 13 页 共 16 页 所包含 的便利 店 1 2 3 4 29 8 9 1 3 14 17 18 19 2 1 11 12 27 3 0 20 22 23 2 4 25 26 5 6 3 1 32 7 10 15 16 28 4 34 3 对得到的聚类区域进行路线规划对得到的聚类区域进行路线规划 首先对聚类 1 运用最近插入法 聚类 1 中各个便利店之间的距离为 表 4 7 聚类 1 各便利店的距离 便利店 v1v2V3v4V29 v12 31 62 61 3 v20 91 82 5 v31 31 5 v41 8 v29 从 v2 出发的所有路径的大小 0 9 为最小 这样 就由节点 v2 v3 3 2 c 构成一个子回路 T v2 v3 然后考虑剩下节点 v1 v4 v29 到 v2 和 v3 中某一个节点最小的距离 1 3 由于对称性 无论将 4 插到 2 和 3 之间往返路径中 结果都是一样 4 3 c 的 构成一个新的子回路 T v2 v3 v4 v2 接着考虑剩下节点 v1 v29 到 v2 v3 v4 中某一个节点的最小距离 1 5 节点 v29 有 3 个位置可以插入 现在分析将 v29 插到那里合适 29 3 c 1 插到 3 4 间 距离 1 5 1 8 1 3 2 2 插到 2 3 间 距离 2 5 1 5 0 9 3 1 3 插到 2 4 间 距离 2 5 1 8 1 8 2 5 比较上面 3 种情况的增量 插到 3 4 之间的增量最小 所以应将 v29 加入 到 3 4 间 结果为 T v2 v3 v29 v4 v2 重复上面的步骤 再将节点 v1 加入到回路中 就可以得到最近插入法所得的解 T v2 v3 v1 v29 v4 v2 这就是行驶最短路径的相对最优解 对聚类 2 用最近插入法 同上 得最优路径 物流规划课程设计 第 14 页 共 16 页 T v8 v14 v13 v9 v8 对聚类 3 用最近插入法 同上 得最优路径 T v17 v18 v21 v19 17 对聚类 4 用最近插入法 同上 得最优路径 T v11 v30 v12 v27 v11 对聚类 5 用最近插入法 同上 得最优路径 T v20 v22 v24 v26 v25 v23 v20 对聚类 6 用最近插入法 同上 得最优路径 T v5 v6 v32 v31 v5 对聚类 7 用最近插入法 同上 得最优路径 T v7 v15 v16 v28 v10 v7 最终优化路线如表 4 8 表 4 8 最终优化路线 根据上表绘制最终优化线路图 4 4 优化后路线 聚类 12 3 1 29 4 聚类 28 14 13 9 聚类 317 18 21 19