河北科技大学打印室选址优化

物流规划课程设计物流规划课程设计 第 1 页 共 14 页 目录目录 1 研究的问题及意义 2 1 1 研究的问题 2 1 2 研究的意义 2 2 科大校内打印室选址设计 3 2 1 候选点的选择 3 2 2 方案的选择及求解 4 2 3 优化前后的选址比较 10 3 可行性分析 11 4 可行性分析 12 5 总结 13 参考文献 14 物流规划课程设计物流规划课程设计 第 2 页 共 14 页 1 1 研究的问题及意义研究的问题及意义 1 11 1 研究的问题研究的问题 2012 年 9 月 理工学院师生整体搬迁至新校区 为了保证正常的教学秩序 河北科技大学完成了理工生活区 南公教 学生三食堂的建设并投入使用 并 且各方面服务措施正在逐步完善 然而随着学生容量的增加 同学们深刻体会 到打印复印越来越难 当同学们需打印复印作业 资料时 往往需要绞尽脑汁 有的甚至为了打印辛辛苦苦跑到西门或南门 针对此问题 我们小组两人于 11 月 16 日分别在生活广场 公共教学楼 南公教 理工生活区四大区域就 您认 为我校打印室建设是否合理 不合理之处在哪 您希望打印室建在哪里 更方便同学 进行了随机调查 结果显示 87 的同学认为打印室分布不合理 具体问题汇总如下 1 公教 D 座与 F 座打印室距离较近 经常出现供大于求 打印室机器闲 置的现象 2 理工生活区无打印室 致使学生复印文件极其不方便 通常走很远的路 或直接去校外打印 造成了很大的客源流失 3 由于浴池附近的学生比较密集 浴池附近的打印室经常出现供小于求的 现状 致使在打印文件的过程中 经常出现排队半个小时但还不能完成打印的 现象 1 2 研究的意义研究的意义 基于上述问题 我们对河北科技大学打印室选址进行了优化 合理的打印 室布局 不仅使学生们享受到快速的服务 避免其在打印过程中时间的浪费 也为学生们提供了一个高效愉悦的学习生活环境 并且合理的打印室布局 也 避免了学校打印室总客源的流失 提高打印室工作人员的工作效率 以及打印 室机器的利用率 进一步提高整体收益 物流规划课程设计物流规划课程设计 第 3 页 共 14 页 2 2 科大校内打印室选址设计科大校内打印室选址设计 2 12 1 候选点的选择候选点的选择 根据同学们上课和休息集中地 在已有的六个打印室基础上 即 浴池 公交楼 D 座 F 座 建工楼 图书馆和材料楼 我们增加了两个备选点 这两 个备选点的选择是经过我们慎重考虑的 首先必须符合学校的规定 其次是根 据同学们需求的权重 考虑到打印室建在学校餐厅附近更加容易满足需求 而 且能够成功的降低前期的投入成本 所以最后选择的两个备选点为 名族餐厅 和理工餐厅 以便于同学们更方便的打印和复制文件 图 2 1 候选点分布图 选址代号 1 浴池 2 名族餐厅 3 公教楼 D 座 4 公教楼 F 座 5 建工楼 6 图书馆 7 材料楼 8 理工餐厅 2 22 2 方案的选择及求解方案的选择及求解 物流规划课程设计物流规划课程设计 第 4 页 共 14 页 一 方案的选择 一 方案的选择 为了尽可能的不增加成本所造成的影响 我们决定将这次课程设计的主要 方向确立为调节打印室的位置 而不是改变打印室的数量 我们增加候选点只 是为了通过一次次的筛选 最终决定留下最为合适的打印室地址 能够最大程 度的满足大学生们的打印需求 综合考虑我们学过的物流选址模型 交叉中值 法 集合覆盖法 P 中值等 我们最终确立P 中值模型为最为恰当的方法 2 2 P P 中值模型介绍中值模型介绍 P 中值模型是指在一个给定数量和位置的需求集合和一个候选设施位置的 集合下 分别为 p 个设施找到合适的位置并指派每个需求点到一个特定的设施 使之达到在工厂和需求点之间的运输费用最低 P 中值模型一般适用于在工厂 或者仓库的选址问题 例如要求在它们和零售商或者顾客之间的费用最少 P 中值模型也可以通过精确的数学语言进行描述 再用数学语言进行描述 时 需要准确的表达问题的约束条件 目标 还有合理的变量定义 一般 P 中 值问题的目标函数是 Min 式 1 1 ijij NiMj i ycd 约束条件为 式 1 2 Niy Mj ij 1 式 1 3 px Mj j 式 1 5 MjNiy Mjx MjNixy ij j jij 1 0 1 0 式中 N 在研究对象中的 n 个客户 需求点 N 1 2 n 第 i 个客户的需求量 i d M 在研究对象中的 m 个拟建设施的候选地点 M 1 2 m 从地点 i 到 j 的单位运输费用 ij c P 可以建立的设施总数 p m 1 假如在 j M 建立设施 式 1 4 式 1 6 物流规划课程设计物流规划课程设计 第 5 页 共 14 页 j x j x 0 其他情况 1 假如客户在 i N 由设施 j M 来提供服务 ijij yy 0 其他的情形 式 1 1 是 P 中值模型的目标函数 约束条件式 1 2 保证每个客 户 需求点 只有一个设施来提供相应的服务 约束条件式 1 3 限制了总的 设施数目为个 约束条件式 1 4 有效地保证没有设施的地点不会有客户对应 从上面的两种 P 中值模型不同表达方式中 可以看出 求解一个 P 中值模 型需要解决两方面的问题 选择合适设施位置 数学表达中的 x 变量 指派客户到相应的设施中去 表达式中的 y 变量 一旦设施的位置确定之后 再确定每个客户到不同的设施中 使费用总和 Cij 最小就十分的简单了 与覆盖模型相似 求解一个 P 中值模型的设施选址问题 主要有两大类的 方法 精确计算法和启发式计算法 由于 P 中值模型是 NP hard 问题 因此精 确计算法一般只能求解规模较小的 P 中值问题 下面介绍一种求解 P 中值模型 的启发式算法 贪婪取走启发式算法 Greedy Drop ping Heuristic Algorithm 这种算法的基本步骤如下 P 中值模型贪婪取走算法 第一步 令当前选中设施点数 k m 即将所有 m 个候选位置都选中 第二步 将每个客户指派给 k 个设施点中举例最近的一个设施点 求出总 运输费用 Z 第三步 若 k p 输出 k 个设施点及各客户的指派结果 停止 否则 转 第四步 第四步 从 k 个设施候选点中确定一个取走点 满足 假如将它取走并将 它的客户指派给其他的最近设施点后马总费用增加量最小 物流规划课程设计物流规划课程设计 第 6 页 共 14 页 第五步 从候选点集合中删去取走点 令 k k 1 转第二步 3 3 方案的求解方案的求解 表2 1 需求与距离 候选点候选点 j j 距离距离 C Cij 12 345678 需求需求 d dj 宿舍楼1 2 250412264 70 宿舍楼3 166395 34 宿舍楼4 172339500514 40 宿舍楼5 169320650 44 宿舍楼6 189377 34 宿舍楼7 8 332176 90 宿舍楼9 32983 56 宿舍楼 10 11 339171391 72 公教 A 171208277 2 公教 B 78109300 12 公教 C 106150290 24 公教 D 478050440364 32 公教 E 150104491408 2 公教 F 600309542 4 经管楼 813665452298 16 艺术建工楼 4292450 30 外语楼 463267200 20 文法楼 424215170 18 讲堂群 52253720 6 图书馆 6630685 2 信息楼 555101525 10 电气楼 443192458 14 纺织楼 538101670 10 机械楼 52580686 16 材料楼 6350484 14 南公教 58850461 60 宿舍楼 12 13 547571150 70 宿舍楼 556578179 74 物流规划课程设计物流规划课程设计 第 7 页 共 14 页 14 15 宿舍楼16 561586205 32 上表是我们利用百度地图精确地测量出各需求地与候选点之间的距离 由 于需要测量的距离实在太多 但是有些候选地实在是不适宜一些对应的需求地 去往 例如 从宿舍楼6号楼去往图书馆打印的话实在太远了 我们就未将这些 距离标出 另外关于需求的调查我们是通过在已有的6个打印室发放问卷 主要 问题是 您来打印之前是从哪栋宿舍楼或公教楼来的 从而确定出各需求地 的日需求人数 当然 我们的数据可能存在着一定的偶然性 但并不太影响我 们的结果 首先 肯定是设施点越多越好 这样就可以尽可能的满足更多的客户 但 是 这样的话随之而来的我们不得不考虑到成本 设施点越多成本越高 并且 如果有一些设施点距离太近的话 就有可能造成不必要的成本浪费 所以 我 们决定在不影响设施点数量的前提下进行研究 下面就请欣赏我们利用 P 中值 模型的解题步骤 令 k 8 在不删除设施点的前提下 根据就近原则我们可以列出离各设施 最近的需求点 默认为该需求点的同学去其对应的设施点打印 然后根据总距 离 D 应为各需求点到指定设施点的最距离与需求人数的乘积 最后总结为如下 的表格 表 2 2 各设施点与需求点的对应关系 设施点 j j对应的需求点 i i总距离 D D 1 宿舍楼 1 2 3 4 5 6 43886 2 宿舍楼 7 8 9 10 11 32800 3 公教楼 A B C D 3822 4 公教楼 E F 1040 5 经管楼 艺术建工楼 外语楼 文法楼 11828 6 讲堂群 图书馆 信息楼 电气楼 4016 物流规划课程设计物流规划课程设计 第 8 页 共 14 页 7 纺织楼 机械楼 材料楼 南公教楼 5290 8 宿舍楼 12 13 14 15 16 30306 合计 132156 从上表我们可以很明确的看出各设施点与其对应的需求点的关系 并能从 理论上算出对应需求点 i i 到最短设施点 j j 之间的总距离 D D 其次 我们选择取走其中的一个候选点 要求满足取走该点后 将各需求 点进行重新的指派 使得各需求点到设施点的距离增加最小 令 k k 1 7 以取走设施点 1 为例 在取走设施点 1 后我们发现其在表 3 2 中对应的宿舍楼 1 6 将会选择设施点 2 也就是说其增加的总距离只表 现在设施点 2 上 最后我们作出如下的表格 表 2 3 移走设施点 1 后增加的距离 设施点 j j对应的需求点 i i移走 1 后增加的距离 2 宿舍楼 1 11 38842 3 公教楼 A B C D 0 400 5 经管楼 艺术建工楼 外语楼 文法 楼 0 6 讲堂群 图书馆 信息楼 电气楼 0 7 纺织楼 机械楼 材料楼 南公教楼 0 8 宿舍楼 12 13 14 15 16 0 增加的总距离 38842 同理 我们在移走其它设施点的时候 对应增加的距离会有所不同 具体 表现为 移走设施点 2 时 宿舍楼 7 11 将会选择设施点 1 增加的距离为 39912m 移走设施点 3 时 公教楼 A B C D 将会选择设施点 4 增加的距离 为 3102m 移走设施点 4 时 公教楼 E F 将会选择设施点 3 增加的距离为 332m 移走设施点 5 时 经管楼 艺术建工楼 外语楼 文法楼将会选择设施 点 4 增加的距离为 10310m 移走设施点 6 时 讲堂群 图书馆 电气楼将会 物流规划课程设计物流规划课程设计 第 9 页 共 14 页 选择设施点 3 而信息楼将会选择设施点 7 增加的总距离为 11894m 移走设 施点 7 时 纺织楼 机械楼将会选择设施点 6 材料楼 南公教楼则会选择设 施点 8 其增加的总距离为 42926m 移走设施点 8 时 宿舍楼 12 16 将会选 择设施点 2 其增加的距离为 61080m 根据得出的数据结合移走设施点 1 增加的距离 我们将这些数据进行整 合最终绘制成表格 见表 2 4 表 2 4 移走各设施点后增加的距离 移除的设施点增加的距离 138842 239912 33102 4332 510310 611894 742926 861080 从上表我们可以看出移走候选点 4 增加的距离最短为 332m 移走设施点 8 增加的距离最长为 61080m 采用贪婪取走法 最终决定取走候选点 4 即公 教楼 F 座的打印室所造成的距离增加最短 则总距离 D 132156 332 132488m 接下来 我们重复上一步的演算过程 同样取出该点使得总距离增加最小 然后令 k k 1 6 则可以得出 移走设施点 1 时 宿舍楼 1 6 会选择设施点 2 增加的距离为 38842m 移走设施点 2 时 宿舍楼 7 11 将会选择设施点 1 增加的距离为 39912m 移走设施点 3 时 公教楼 A B C D E 座将会选 择设施点 6 而公教楼 F 座将会选择设施点 5 增加的距离为 20452m 移走设 施点 5 时 经管楼 艺术建工楼 外语楼 文法楼将会选择设施点 3 增加的 距离为 11964m 移走设施点 6 时 讲堂群 图书馆 电气楼将会选择设施点 3 而信息楼将会选择设施点 7 增加的总距离为 11894m 移走设施点 7 时 纺 物流规划课程设计物流规划课程设计 第 10 页 共 14 页 织楼 机械楼将会选择设施点 6 材料楼 南公教楼则会选择设施点 8 其增加 的总距离为 42926m 移走设施点 8 时 宿舍楼 12 16 将会选择设施点 2 其 增加的距离为 61080m 根据我们演算过程中得结果 我们简略的将移走设施点与其对应的增加的 距离绘制成表格 具体见表 2 5 表 2 5 移除设施点与增加的距离之间的关系 移除的设施点增加的距离 138842 239912 320452 511964 611894 742926 861080 从上表我们可以看出移走候选点 6 增加的距离最短为 11894m 移走设施 点 8 增加的距离最长为 61080m 采用贪婪取走法 最终决定取走候选点 5 即 图书馆的打印室所造成的距离增加最短 则总距离 D 132156 332 11894 144382m 此时 k k 1 6 由于 k p 计算结束 综合以上计算过程 我们可以看出 在同样是选择六个打印室的情况下 我们利用 P 中值模型算出最为适宜的六个位置为 1 2 3 5 7 8 即为 浴池 名族餐厅 公教楼 D 座 建工楼 材料楼和理工餐厅 总的距离为 144382m 2 32 3 优化前后的选址比较优化前后的选址比较 我们知道在优化前的打印室的位置分别为 1 3 4 5 6 7 而通过我 们的考查得到 为满足每个需求点到相应的设施点的距离最短 最后汇总成如 下的表格 表 2 5 优化前的合理对应关系 物流规划课程设计物流规划课程设计 第 11 页 共 14 页 设施点 j j对应的需求点 i i 1 宿舍楼 1 11 3 公教楼 A B C D 4 公教楼 E F 5 经管楼 艺术建工楼 外语楼 文法楼 6 讲堂群 图书馆 信息楼 电气楼 宿舍楼 12 16 7 纺织楼 机械楼 材料楼 南公教楼 结合表 2 1 和表 2 5 通过计算得出总距离 D1 需求 距离 237034m 1 根据我们之前选择的 P 中值模型的计算 可以得出最终选择的位置为 1 2 3 5 7 8 即为 浴池 名族餐厅 公教楼 D 座 建工楼 材料楼和 理工餐厅 最后汇总成如下的表格 表 2 6 优化后的合理对应关系 设施点 j j对应的需求点 i i 1 宿舍楼 1 6 2 宿舍楼 7 11 3 图书馆 讲堂群 电气楼 公教楼 A B C D 5 经管楼 艺术建工楼 外语楼 文法楼 7 信息楼 纺织楼 机械楼 材料楼 南公教 8 宿舍楼 12 16 结合表 2 1 和表 3 6 通过计算得出总距离 D2 需求 距离 144382m 2 结合式 1 和 2 比较 D1 D2 92652m 可能这个数据大家看着比较 的抽象 我们举几个例子吧 1 正常成年人的步速一般的是 1 5m s 即 5 4km h 那么 92625 则需 要一个正常成年人不停息地行走近 17 个小时 2 河北科技大学新校区至新火车站距离为 9300m 那么 92652m 则是其近 十倍 物流规划课程设计物流规划课程设计 第 12 页 共 14 页 3 3 可行性分析可行性分析 此次课程设计我们主要对科大校内的打印室选址进行了整体优化设计 通 过调查问卷的形式我们大体统计出每天的各宿舍楼和教学楼的需求人数 同时 我们根据学校的规定 在已有的打印室基础上选定了两个候选点 希望通过 P 中值模型 设计出比较合理的打印室位置 从而比较优化前后的数据 下面我 们从需求上 经济上和服务上的可行性进行分析 从需求上分析可行性 打印室作为大学生学习过程中不可或缺的一部分 不论是在学习过程中对于老师上课时讲解的 PPT 还是在临近考试时同学们准 备的复印资料方面考虑 我们都觉得打印室必须要建在最为合理的位置 以便 于我们更好的学习 从经济上分析可行性 我们最后决定建立的打印室数量为 6 也就是说我 们并未改变打印室的数量 只是将打印室的位置进行优化调节 从这一方面考 虑的话 按照我们设计的方案执行的话 所造成的是相当之小 反而 我们从 需求上满足更多的消费者 所带来的利润肯定是比较客观的 从服务上分析可行性 按照原来的方案 理工区学生没有打印室 生活区 打印室经常供不