基于Floyd最短路径算法的教材中心选址问题

摘 要 针对日益多元化的教育装备，校区分散、规模庞大的高校必须考虑其购买、管理、维护成本，因此，装备中心的选址尤为重要。依据Floyd算法，深入探讨装备中心的选址问题，并给出量化的计算结果，为教育装备的管理工作提供依据。

关键词 教育装备；最短路径；Floyd算法

中图分类号：G48 文献标识码：B

文章编号：1671-489X（2014）04-0040-03

以计算机和互联网为代表的现代科技迅猛发展，越来越多的具有高科技含量的装备在教育领域得到了广泛应用，使教育装备的分配、管理、保障、运输和更新等工作变得更加复杂。这势必要求学校的管理人员不仅要定性、更要定量地研究教育装备的决策问题，否则将无法做出可行性决策，更不要提什么优化了。同时，我国的社会发展阶段和经济发展水平共同决定了教育经费的数目是有限的，在保证日常教学和科研的前提下，如何尽可能地压缩管理成本是教育装备管理工作中面临的难题。

因此，本文以如何使教育装备在运输过程中的成本最低为切入点，提出教育装备中心选址的最优化问题，采用Floyd最短路径算法实现其求解，为教育装备的管理工作提供科学依据。

1 数学模型

图论的产生和发展经历了200多年历史，1736年瑞士著名数学家欧拉（L.Euler）提出并解决了“哥尼斯堡七桥问题”，标志着图论的起源[1]。随着现代生产和科学技术的迅猛发展，特别是计算机的出现和互联网的普及，使图论方法得以快速扩展，图论已成为现代数学科学中的一门引人注目的新兴学科，渗透到物理学、化学、电工学、管理学、控制论、信息论等诸多学科[2-3]。

最短路径的求取是图论中的一个典型问题。所谓最短路径是指在指定网络中两点间的一条距离最小的路[4]。在求解网络上任意节点间最短路径的方法中，学术界一致公认的较好的算法是Dijkstra和Floyd算法。这两个方法的主要区别是：Dijkstra算法可以计算从图中某一点到其他各点的最短路径；Floyd算法主要用于计算图中所有点之间的最短路径。显然，在研究教育装备运输问题时，可以采用Dijkstra方法进行计算，从而得到装备中心到目标学校之间的最短路径。

当目标学校有多个校区时，装备中心地址的选择必须考虑多方面因素，其中最基本的一点是保证该装备中心到所有校区的最短路径之和最小。此时，如果采用狄克斯屈拉算法，需要计算备选地址和各个校区之间的最短距离，该过程需要重复多次，且计算繁琐；而计算图中所有点之间的最短路径正是Floyd算法所“擅长”的。因此，本文在研究教育装备中心的选址问题时，优选Floyd算法。

表1中每行的合计数表示教材配送中心建于该校区时，满足所有校区每学期教学需要的大学英语教材运输的册千米数。从表中可以看出C列的合计数最小，表明当把教材配送中心建于C校区时，教材运输的册千米数最小，为107 500。

3 结论

虽然规模庞大的高校校区比较分散，但是每学年在每个校区开设的专业和在校生规模基本保持不变，这就保证了每个校区每学年需要的教育装备数目基本保持稳定。因此，高校在建设装备中心时的选址问题必须充分考虑如何使总的运输成本最低，往往一个错误的决策将导致在以后每次装备运输中都产生浪费。本文依据Floyd最短路径算法给出了定量计算，通过本文的实例相信可以为每位管理者提供崭新的思路。

参考文献

[1]李慧.教育装备运筹规划[M].北京：北京大学出版社，2010：100-116.

[2]辛宇.基于运筹学图论的物流网络优化研究[J].中国外资，2011（6）：125-127.

[3]蒋智凯.浅谈运筹学教学[J].重庆科技学院学报：社会科学版，2010（24）：176-177.

[4]徐俊明.图论及其应用[M].3版.北京：中国科学技术大学出版社，2010：84-90.

[5]唐建清，邹国霞.基于Floyd算法的旅游路径智能选择系统设计[J].中国科技信息.2006（14）：101-103

[6]杨军庆，安容瑾.基于弗洛伊德算法的各院校间最短路径问题的求解[J].甘肃科技纵横，2010（5）：28-29

[7]王樱，徐雨明，王静.校园道路网最短路径的分析与实现[J].衡阳师范学院学报，2004，12（6）：77-79.