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

邱梦楠　朱梦茹　李进

【摘 要】本文主要研究图论在物流运输中的应用，以江苏省泰州市海陵城区为实例，通过Floyd算法，给出城区主干线上的结点间的最短路径，并通过构建欧拉回路，优化城市物流路径，提高运输效率。

【关键词】图论；物流运输；Floyd；欧拉回路；Edmonds；Fleury

图论起源于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的最小权理想匹配，得到奇次顶点的最佳匹配：

M=v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■

在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.

[责任编辑：薛俊歌]

【摘 要】本文主要研究图论在物流运输中的应用，以江苏省泰州市海陵城区为实例，通过Floyd算法，给出城区主干线上的结点间的最短路径，并通过构建欧拉回路，优化城市物流路径，提高运输效率。

【关键词】图论；物流运输；Floyd；欧拉回路；Edmonds；Fleury

图论起源于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的最小权理想匹配，得到奇次顶点的最佳匹配：

M=v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■

在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.

[责任编辑：薛俊歌]

【摘 要】本文主要研究图论在物流运输中的应用，以江苏省泰州市海陵城区为实例，通过Floyd算法，给出城区主干线上的结点间的最短路径，并通过构建欧拉回路，优化城市物流路径，提高运输效率。

【关键词】图论；物流运输；Floyd；欧拉回路；Edmonds；Fleury

图论起源于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的最小权理想匹配，得到奇次顶点的最佳匹配：

M=v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■v■，v■

在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.

[责任编辑：薛俊歌]