最小费用最大流模型在运输网络优化中的应用

郭京生　刘璘

摘要：运用图论的相关理论知识，针对物流系统中运输网络的特点，以最大限度的提高运输效率，同时以节约运输总成本为目标，提出了解决运输网络优化问题的最小费用最大流网络模型，并利用matlab编程实现，为优化物流运输网络路线提供了一种可行方法。

关键词：运输网络；最小费用最大流；网络流量；matlab

中图分类号：F25文献标识码：A文章编号：16723198（2015）17005302

0引言

运输作为现代物流过程的主要职能之一，是物流各项业务的中心活动。同时，运输产生的费用也是供应链和整个物流系统成本结构的重要组成部分。可以说，一个高效率、低成本和高反应能力的运输网络对一个成功的物流配送体系至关重要，这就使得运输网络的优化成为配送体系中一项重要的运营决策，关系到物流设计体系的成功与否。运输网络的优化主要是对运输路线的安排，即选择合理的配送路线，既能保证配送效率的最大化，又能同时使运输成本最低。

图论是运筹学中一个重要的分支，是用来描述运输网络的数学理论基础。本文基于图论的相关理论知识，针对物流运输中最小费用最大流问题，建立了基于matlab的优化数学模型，以求最大限度的提高运输效率，同时节约运输费用。

1最小费用最大流模型

1.1网络流量基本概念及定义

为了实现对网络流量最大流值和最低成本的优化，首先需明确几个基本定义：

定义1：容量—费用网络。给定一个有向图D=V，A，对任意的弧vi，vj∈A，设lij，uij为弧的运输容量上下界函数，其中0≤lij≤uij，也称uij为弧的容量；cij是弧vi，vj上单位流量的费用，称之为费用函数；对任意的节点vi∈V，称avi为节点vi的供应量或需求量，称之为供需函数，且满足vi∈Va（vi）=0。由此得到的网络称为容量—费用网络。

定义2：可行流及其总费用。设fij是给定网络N上的由节点vi到节点vj的一个流量，且满足：

f+（vi）-f-（vi）=f（vi）

lij≤fij≤uij （1）

式中，f+vi=vj∈Vfij，f-vi=vj∈Vfji，分別称为流出和流入节点vi的流量，fvi为该节点的净输出量。

当满足式（1）时，则称f=fij为网络N 上的一个可行流，且可行流f的总费用为

c（f）=（vi，vj）∈Acijfij （2）

1.2最小费用问题概念及数学模型

最小费用问题是物流运输网络优化的核心问题，目标是在满足供应条件的前提下，寻求供应网络总成本最小的最优解。

根据上述定义，最小费用问题属于线性规划问题。其数学模型如下：

min z=c（f）=（vi，vj）∈Acijfij （3）

约束条件为式（1）。

其中，目标函数是通过网络N供应的总成本最小。决策变量fij指通过弧vi，vj的流量。约束条件有供应点的净流量（总流出量减去总流入量）为正，所有需求点的净流量为负，对于所有中转点（中间点）的净流量为0，所有弧的流量受到弧的容量lij，uij的限制，且弧的流量为非负。

1.3最大流问题概念及数学模型

最大流问题也与网络中的流有关，但是其优化目标与最小费用流不同，最大流问题是寻求一个可行流的方案，使得通过网络的流量最大。

根据最大流问题的概念，最大流问题也属于线性规划问题。其数学模型如下：

max z=fvs （4）

除满足约束条件式（1）外，还应满足式（5）：

f+（vi）-f-（vi）=fvs，i=s（源）

-fvs，i=t（汇）

0，i≠s，t（中转点）（5）

其中，目标函数是通过供应点vs的净流出量f（vs）（或需求点vt的净流入量f（vt））最大，决策变量是通过各个弧的流量fij，约束条件有所有中转点的净流量为0，所有弧的流量受到弧的容量lij，uij的限制，且弧的流量为非负。

1.4最小费用最大流问题概念及数学模型

前面小节中介绍的“最小费用流问题”的目标是在完成规定任务的条件下，使得网络供应的总成本最小，即解决流量一定成本最小的路线安排问题。“最大流问题”的目标是寻求一个可行流的方案，使得通过供应网络的流量最大，即不考虑成本的情况下，解决单纯的流量最大的路线安排问题。但是实际情况往往比较复杂，不仅考虑流量还需要兼顾费用。例如，物流系统中一个运输网络，不仅要争取网络中货运量最大，还要力求使总费用最小，即解决更贴合实际的流量最大成本最低的路线安排问题，这就是“最小费用最大流问题”。

因此，我们可以把“最小费用最大流问题”看成是“最小费用流问题”和“最大流问题”的结合。求解该问题自然可以分为两步：首先，按照“最大流量问题”的求解方法找到网络可通过的最大流量；其次，在保证该最大流量的前提下找到成本最小的线路。

根据最小费用最大流问题的概念，最小费用最大流问题也属于线性规划问题。其数学模型如下：

min z=（i，j）∈Acijfij （6）

s.t.f+（vi）-f-（vi）=fvs，i=s（源）

-fvs，i=t（汇）

0，i≠s，t（中转点）

0≤lij≤fij≤uij（（i，j）∈A） （7）

2算例

基于上述分析，本文以某公司链接产地到销地的物流运输体系为例进行说明。其中，产品运输网络如下图1所示，图中各弧表示运输道路。由于道路实际地质情况不同，使得每条道路上的运输费用也不同，因此优化该运输系统除考虑货物的最大流外，还需要考虑道路运输的最小费用，即可基于本文所提的最小费用最大流模型予以求解。

图1某公司产品运输网络图1中弧上括号内的数字分别表示对应运输道路的容量限制和单位运费。

对算例按照最小费用最大流问题建模，过程如下：

（1）建立最大流模型。

maxz=fvs=fs1+fs2 （8）

满足约束条件（1）。

（2）建立最小费用模型。

minz=（vi，vj）∈Acijfij （9）

满足约束条件（7）。

（3）利用MATLAB软件实现算例，在命令窗口中编写MATLAB程序并执行，得到结果如图2所示。

图2程序仿真结果由图2所示，该运输网络最大运输量为14吨，最小运输总成本为20500元，优化后的运输方案如图3所示。

图3优化运输方案3结束语

随着电子商务和物流业的迅速发展，物流运输的地位越来越受到重视。本文将最小费用最大流模型运用到物流运输网络的优化中，为优化运输网络路线提供了一种可行方法，实现了在实际优化中既考虑最大运量同时也寻求运输总成本最小化的目标。需要指出的是：在优化运输网络过程中，优化运输路线只是其中的一个部分，还需要对物流节点进行优化，比如物流节点的选址问题，这两类问题应该综合考虑进行优化，这些问题有待进一步的研究。

参考文献

[1]杜洁，郝妍，王璐.多目标应急物流运输问题优化研究[J].物流工程与管理，2010，32（4）：113114.

[2]王桂平，王衍，任嘉辰.图论算法理论、实现及应用[M].北京：北京大学出版社，2011：131208.

[3]王锐，甘凯.图论优化法在物流运输中的运用[J].商场现代化，2005，（28）：137138.

[4]张建林.MATLAB&EXCEL定量预测与决策[M].北京：电子工业出版社，2012.

[5]林方明，马建军，庞渊.物流配送决策中的运输网络优化问题研究[J].山西建筑，2004，30（08）：8485.