分销网络设计的数学建模

分销网络设计问题

摘要

本文针对多供应商、多产品、多经销商的分销配送网络的优化设计问题，建立了整数规划模型，利用遗传算法，找出了成本最小的供应链。

针对题目中既定制造厂商以及需求地，要求最优分销网络以实现建立和经营分销网络所需费用及产品的生产和运输费用总和最小的分销的供应网络的问题，以分销网络建立和经营费用、运输费用以及产品生产费用之和最小为目标函数，以每个分销中心可对应分销点数量的上下限、各工厂对分销中心的供货量应满足由该分销中心供货的各个需求点的总需求、各工厂供应的各种商品的总和不超过其生产能力以及各分销中心的仓储能力的限制等条件为约束，建立了整数规划模型。由于网络线路复杂，可行解数量多，若采用传统的分支定界法，程序的时间复杂度较高。本文通过设计遗传算法，对决策变量——分销中心选址以及各分销中心到分销点的供货路线安排进行编码，计算出了最优分销网络：将需求地4,5,9分别建为分销中心，最少费用为38511124元，具体商品配送方式见表1。

本文针对分销配送网络设计问题，采用经典的整数规划模型，将复杂的分配关系通过经典的整数规划模型表示，并设计遗传算法对计算过程进行了优化，提高了模型的可操作性。

关键词：二级分销网络 整数规划 遗传算法

§1问题重述

随着市场的全球化趋势,供应链企业要为地理上分散的多个用户提供产品和相关的服务，由于用户需求的多样性，为了加快响应速度，往往建立多个分厂。各分厂可生产该企业产品集合中的某些产品，该企业有多个需求地。为加强对分销环节的管理，考虑在这些需求地中选择一些建立分销中心，在分销中心建立仓库，而在没有被选为分销中心的需求地建立分销点，且每个分销点只能由一个分销中心供货。

现某制造企业有3个分厂，生产两种产品,两种产品可以在任意分厂加工制造，共有10个需求地， 每个分销中心分管的分销点最少2个，最多3个，详细数据见附录。现为该企业设计分销网络，使得计划期内建立和经营分销网络所需费用及产品的生产和运输费用最小。需完成如下设置：

（1） 选择哪些需求地建立分销中心，每个分销中心负责为哪些分销商供货。 （2） 如何根据需求情况合理地安排各分厂的生产，即确定各分厂生产产品的种

类和数量。

（3） 决定如何安排运输流，即确定各分厂运送到分销中心的产品种类和数量及

各分销中心运送到各分销商的产品种类和数量。

§2问题分析

问题要求通过设计该分销网络，使得计划期内建立和经营分销网络所需费用及产品的生产和运输费用最小，即为系统总成本最小的优化问题，并进行以下分析：该企业的二级分销网络结构以及系统总成本构成可用下图表示：

图1 二级分销网络结构以及系统总成本构成图

根据该网络图，可知确定分销中心的选址，分销中心与分销点的供货关系，工厂运往分销中心产品种类与数量，工厂根据需求状况生产的产品种类和数量，各分销中心运往各分销商产品种类和数量是实现最优的关键，因此该问题属于典型的“分配-选址”问题。对于该类问题，首先需对其优化目标，即系统总成本进行分析得到目标函数，其次需对该分销网络因具体实际情况所产生的约束条件进行分析。

优化目标系统总成本Q构成：

（1）建立和经营分销网络所需固定费用：Q1 （2）产品从各分销中心到各分销点的运输费用：Q2 （3）产品从各分厂到各分销中心的运输费用：Q3 （4） 产品生产的成本：Q4

（5）产品在分销机构中的流转量产生的管理费用：Q5 则优化目标函数可表示为：Q Q1 Q2 Q3 Q4 Q5 由实际情况所产生的约束条件： （1）需求地的分销机构唯一

（2）只有被选为分销中心后可向分销点供货，同时限定每个分销中心可供货的分销点数量上下限。

（3）供需平衡，即工厂供货量=分销点与分配中心需求量

（4）工厂产品供应量不超过其生产能力，产品生产能力=基准产品生产能 （5）工厂产品供应量不超过各分销中心的存储能力平衡 由此结合优化目标函数和约束条件建立0-1整数规划模型。

§3模型假设

⒈运输费用与运输量成正比，与运输距离成线性关系； ⒉分销中心与工厂之间的订货提前期是确定的，订货的分销中心能及时地为分销点补充库存；

⒊不考虑分销点库存成本；

§4符号说明

工厂序号 需求地序号 产品序号

产品j由第k分销中心到第l个分销点的单位运费 第l个需求地对产品j的需求量

产品j由工厂i到第k个分销中心的单位运输费用 工厂i生产产品j的单位生产成本 建设管理第k个分销中心所需固定费用 建设管理第k个分销点所需固定费用 产品第k个分销中心的单位流转费用 产品第l个分销点的单位流转费用 工厂i对产品j的生产能力系数 工厂i对基准产品的生产能力

第k个分销中心对产品j的存储能力系数 第k个分销中心对基准产品的存储能力

k,l

j

ajkl blj cijk dij sk wk fk gl

hij pi

nkj mk

§5模型建立与求解

5.1模型的建立

问题要求为该企业设计分销网络，使得计划期内建立和经营分销网络所需费用及产品的生产和运输费用最小，因此建立0-1整数规划模型来描述该优化问题。

5.1．1决策变量

由题目设定进行分析得到，优化变量包括：

0,第k个需求地设为分销点

（1）分销中心选址xk，xk

1,第k个需求地设为分销中心 （2）分销中心与分销点供货关系ykl，

0,第k个需求地不负责向第l个需求地供货

ykl

1,第k个需求地负责向第l个需求地供货

（3）工厂i运往分销中心k产品j的数量zijk

5.1．2目标函数

通过对该二级分销网络的成本进行分析，系统总成本包括：

（1）建立和经营分销网络所需固定费用成本，可表示为分销中心与分销点所需固定费用两部分之和，故有：

Q1 [skxk wk(1 xk)]

k 110

式中，sk表示在第k个需求地建立和经营分销中心所需固定费用，wk表示在第k个需求地建立和经营分销点所需固定费用，(1 xk)为分销点选址的0-1决策变量。

（2）产品从各分销中心到各分销点的运输费用，由分销中心运往分销点产品的单位运费与产品在分销点需求量的乘积构成，则可表示为：

Q2

210

i 1k 1l 1,k l

a

10

ikllj

bykl

式中，aikl表示产品j由分销中心k运往分销点l的单位运费，blj表示产品j由分销点l的数量。

（3）产品从各分厂到各分销中心的运输费用，由工厂向分销中心运送产品的单位运输费用与由工厂运往分销中心产品数量的乘积得到，则可表示为：

Q3 cijkzijk

i 1j 1k 1

3210

式中，（分销中心）运送产品j的单位运输费用，cijk表示由工厂i向第k个需求地

zijk表示由工厂i运往第k个需求地（分销中心）产品j的数量。

（4）产品生产的成本，由工厂生产产品单位生产成本与工厂运往分销中心产品数量的乘积构成，则可表示为

Q4 dij zijk

i 1j 1

k 1

3210

式中，dij表示工厂i生产产品j的单位生产成本。

（5）产品在分销机构中的流转量产生的管理费用，由工厂运往分销中心的产品流转量管理费用费与分销中心运往分销点的产品流转量管理费用构成，流转管理费用可由产品的单位流转量管理费用与产品流转量的乘积得到，流转管理费用表示如下：

Q5 zijkxkfk (1 xl)glblj

k 1i 1j 1

l 1j 1

1032102

式中，fk表示产品在第k个需求地（分销中心）的单位流转量管理费用，gl表示产品在第l个需求地（分销点）的单位流转量管理费用。 综上所述，则系统总成本可表示如下：

Q [skxk wk(1 xk)]

k 123

10

10

3

2

10210

i 1k 1l 1,k l

a

10

ikllj

bykl cijkzijk

i 1j 1k 1

2

3210

dij zijk zijkxkfk (1 xl)glblj

i 1j 1

k 1

k 1i 1j 1

l 1j 1

10

要求对分销网络进行设计，使得总成本最小，则该问题目标函数为minQ 5.1．1约束条件

（1）需求地的分销机构唯一，因此存在以下约束条件。

xl

k 1,k l

y

10

kl

1,(l 1, ,10)

（2）只有被选为分销中心后可向分销点供货，同时每个分销中心可供货的分销点数量最少2个，最多3个。

qLxk

l 1,l k

y

10

kl

qUxk,(k 1, ,10;qL 2,qU 3)

（3）供需平衡，即工厂供货量=分销点与分配中心需求量

l 1,l k

by

lj

10

kl

bkjxk zijk,(j 1,2;k 1, ,10)

i 1

3

（4）工厂产品供应量不超过其生产能力

z

k 1

10

ijkij

h pi,(i 1,2,3;j 1,2)

式中，hij表示工厂i对产品j的生产能力系数，pi表示工厂i对基准产品的生产能力。

（5）工厂产品供应量不超过各分销中心的存储能力平衡

z

k 1

10

ijk

nkj mk,(i 1,2,3;j 1,2)

式中，nkj表示第k个需求地（分销中心）对产品i的存储能力系数，mk表示第k个需求地（分销中心）对基准产品的存储能力。

综上所述，建立以下二级分销网络的最小成本优化问题的0-1整数规划模型：

minQ [skxk wk(1 xk)]

k 1

3

2

10

10

3

2

10210

i 1k 1l 1,k l

10

a

2

10

ikllj

bykl cijkzijk

i 1j 1k 1

3210

dij zijk zijkxkfk (1 xl)glblj

i 1j 1

k 1

k 1i 1j 1

l 1j 1

10

xl ykl 1,(l 1, ,10)

k 1,k l

10

qLxk ykl qUxk,(k 1, ,10;qL 2,qU 3)

l 1,l k

3 10

bljykl bkjxk zijk,(j 1,2;k 1, ,10)s.t. l 1,l ki 1

10

zijkhij pi,(i 1,2,3;j 1,2) k 1 10

zijknkj mk,(i 1,2,3;j 1,2) k 1

xk,ykl {0,1},zijk 0,( i,j,k,l);

5.2模型的求解

本模型网络线路复杂，可行解数量多，若采用传统的分支定界法，程序的时间复杂度较高。对此本文设计了遗传算法。 5.2.1 算法描述 Step1基因编码

分销中心位置及分销中心—分销点路线安排采用11个10进制数编码，前10位为1~10的随机排列，最后一位为1~3之间的一个随机整数。

该编码的前三位的数字所代表的位置作为分销中心位置k1 k2 k3，4、5位的数字所代表的位置由k1负责供货，6、7位的数字所代表的位置由k2负责供货，8、9位的数字所代表的位置由k3负责供货，最后一位数字决定第10位的数字所代表的位置由k1~k3中哪一个负责供货。

例如，编码 8 10 9 1 2 5 3 7 6 4 1的含义为：

8,9,10号位置作为分销中心，8负责1,2,4号位置的供货，9负责6,7号位置的供货，10负责3,5号位置的供货。

每次编码后，计算各分销中心的总需求量并与该分销中心的存储能力进行比较，验证编码的合理性。若所编码路线不合理，则重新编码。

分销中心位置及分销中心-分销点路线安排一经确定，各分销中心的总需求量也就确定，以工厂-分销中心过程总成本最小为目标函数，各工厂供货总量不超过其产能和供货量能达到各分销中心需求量为约束条件，建立线性规划模型，计算工厂-分销中心供货安排。 Step2适应度计算

适应度计算公式如下：

Fit

100000000

Q

其中Fit表示适应度，Q表示总成本。 对整个种群的适应度计算完成后，筛选出最低总成本，并记录下最低总成本所对应的基因。 Step3交叉

对基因1~10号位，可以随机产生两个1~10之间整数i,j，令

p mini{,j}q ,

maix，{j将两条基因p,q之间的部分进行依次对应，按照对应

规则对基因的1~10号位进行变换。

例如，对基因8 10 9 1 2 5 3 7 6 4

和基因 9 3 2 1 7 6 4 8 5 10

假定p=5, q=7，则基因的变换规则为2和7互换，5和6互换，3和4互换。变换后的两条基因（即子代）分别为

8 10 9 1 7 6 4 2 5 3 9 4 7 1 2 5 3 8 6 10

每次进行交叉后，对新基因所编码方案进行合理性检查，若方案不能满足模型的约束条件要求，则重新进行交叉。 Step4变异

所有基因按概率Pm=0.25进行变异，变异时利用随机整数确定变异点位置及变异方式（前移、后移、倒序）。 Step5选择

选择过程的生存率设定为0.99。将所有基因按适应度大小降序排列，从前至后选择原种群规模99%数量的基因组成新的种群。 Step6终止条件

算法每次运行100代后即停止。 5.2.3计算结果

将需求地4,5,9建设为分销中心，4负责6、10的货物供应，5负责3、7的货物供应，9负责1、2、8的货物供应

以上方案下总成本为：38511224元。 5.2.4计算结果分析

观测遗传算法中每一代最高适应度的大小随代数的变化如下图

图2 种群最大适应度随代数的变化

由上图可以看出，种群的最大适应度总体随代数增加而上升，可见该算法的计算过程在逐步接近模型最优解，说明算法设计是较为合理的。但最大适应度随代数有较大波动，说明算法稳定性有待提高。

§6模型评价与推广

6.1模型优点 本文对于多决策变量的复杂二级分销网络的问题提出建立统一的整数规划模型，使该最小费用模型不仅仅局限于该分销网络，具有普适性。并且，对于模型的计算没有采取传统的分支定界法，而是通过自行设计遗传算法，降低了算法的时间复杂性，使模型更加高效，使得对于数据规模更大的分销网络该模型同样适用，且可以保证计算的可操作性。 6.2模型缺点

通过遗传算法降低了模型求解的难度，但得到的该题目的分销网络设计方案 并不能保证为全局最优。而采用遍历搜索的方式，虽由于数据规模较大，需花费时间较长，但可以得到全局最优方案。

§7参考文献

[1]司守奎、孙玺菁，《数学建模算法与应用》，国防工业出版社，2011年版； [2]吴孟达，《数学建模教程》，高等教育出版社，2011年版； [3]先强，刘卫宁，《基于改进遗传算法的二级分销网络优化模型及求解》，重庆大学，2008年；

本文来源：https://www.bwwdw.com/article/9uti.html