APP下载

图论在物流运输中的实例研究

2014-12-23邱梦楠朱梦茹

科技视界 2014年14期
关键词:图论欧拉结点

邱梦楠 朱梦茹 李 进

(泰州职业技术学院,江苏 泰州225300)

图论起源于18 世纪的哥尼斯堡七桥问题,发展于四色问题,用点和边来描述事物和事物之间的关系,是对实际问题的一种抽象,能够把纷杂的信息变得有序、直观、清晰。近30 年,由于与计算机技术的结合,成为数学中发展十分迅速新兴分支,现已广泛应用于工农业生产、交通运输、通讯、电力、经济管理、工程技术、生理学、控制论等领域,因此,图论越来越受技术与管理人员的重视。

物流学作为当今颇具影响力的学科,它以物的动态转化过程为主要研究对象,揭示了物流活动的内在联系,使物流系统在经济活动中从潜隐状态显现出来。 物流网络由线路和结点两个重要部分构成,基本的网络优化问题有:最短路径问题、最小生成树问题、最大流问题和最小费用问题等。 物流运输作为重要的物流网络优化问题,其方案的设计真接影响企业的运输成本和运输时间等。

本文运用图论理论,从图与网络的角度,以江苏省泰州市海陵城区主干线为例,构建图论模型,利用Floyd 算法,给出城区主干线上的结点间最短路径,并通过构建欧拉回路,给出最优巡回运输路径。

1 建立图论模型

图1

表1

设赋权连通无向图G(V,E)是城市道路构成的网络图,其中,V 表示图中所有的顶点集(vi),E 表示由城市道路构成的弧集,道路的长度用边权d(vivj)表示,如图1 所示。

2 结点间的最短路径

该图论模型,共有24 个结点,38 条路径。

由Folyd 算法求出结点间的最短路径,如表1 所示(单位:km)。

3 最优巡回运输路线

图G 中有14 个奇点,以它们为顶点集,作一完备图,边上的权为两端点在原图G 中的最短距离,将此完备加权图记为G1。

用Edmonds 算法求出G1 的最小权理想匹配,得到奇次顶点的最佳匹配:

在G 中沿配对顶点之间的最短路径添加重复边,得欧拉图G2,如图2 所示。

再由Fleury 算法求出G2 中的欧拉巡回,即G2 中的一条欧拉巡回就是G 的一条最佳巡回运输路线,权值为87.1km。

图2

[1]辛宇.基于运筹学图论的物流网络优化研究[J].中国外资,2011,06:125+127.

[2]王锐,甘凯.图论优化法在物流运输中的运用[J].商场现代化,2005,28:137-138.

[3]郭培俊,毛海舟.高职数学建模[M].浙江:浙江大学出版社,2010,12.

猜你喜欢

图论欧拉结点
欧拉闪电猫
精致背后的野性 欧拉好猫GT
再谈欧拉不等式一个三角形式的类比
基于FSM和图论的继电电路仿真算法研究
构造图论模型解竞赛题
Ladyzhenskaya流体力学方程组的确定模与确定结点个数估计
欧拉的疑惑
点亮兵书——《筹海图编》《海防图论》
图论在变电站风险评估中的应用
基于Raspberry PI为结点的天气云测量网络实现