文章信息
- 林玉英, 邱荣祖
- LIN Yuying, QIU Rongzu
- 基于遗传-禁忌算法的木材物流网络优化
- Optimization of timber logistics network based on the genetic-tabu algorithm
- 森林与环境学报,2017, 37(3): 309-314.
- Journal of Forest and Environment,2017, 37(3): 309-314.
- http://dx.doi.org/10.13324/j.cnki.jfcf.2017.03.010
-
文章历史
- 收稿日期: 2016-08-19
- 修回日期: 2016-10-24
木材物流网络是以木材为对象的特殊物流网络,是由多个木材物流节点和线路共同组成的复杂的网状结构,通过建立数学模型并求解,可得到木材物流网络优化方案。由于木材物流网络优化需要考虑的因素很多,建立的模型十分复杂,普通算法运算效率低且难以得到满意解,现通常采用智能优化算法。目前,不少学者对木材物流网络优化的相关问题进行了研究,主要包括节点选址[1-4]、运输优化[5-7]、网络系统优化[8-12],智能算法在其中得到了一些应用,但单一智能算法在求解模型时存在局限性,难以得到满意的求解结果,越来越多学者尝试混合智能算法以解决问题。遗传-禁忌算法作为科学高效的混合智能算法,广泛应用于众多领域[13-17],但在木材物流网络优化领域研究较少。在林业信息化的背景下,应结合计算机技术与数学模型,构建物流决策支持系统与物流信息平台,对木材物流系统进行优化[18-19]。因此,以系统优化方法构建木材物流网络优化的数学模型,在研究模型算法的基础上,采用C#编程求解,并结合地理信息系统软件(ArcGIS)实现方案可视化,探讨遗传-禁忌算法求解模型的策略和流程,为木材物流决策提供技术支持。
1 木材物流网络优化模型建立木材在伐区被伐倒后,通过木材物流网络,采用直达或中转运输的方式,从供材点运送到各个需材点,从系统的角度建立数学模型,考虑模型假设和约束条件,具体如下。
1.1 模型假设木材产品有多种表现形态,对象为多品种(原木、薪材、枝桠材等), 木材物流中心建设投资费用较大,其选址有严格的标准,根据实地条件选择备选地址,并设定每个备选物流中心的最大吞吐量;假设每个供材点或需材点(包括物流中心)所供应或需求的木材材种和相应的数量为已知。模型中的费用说明:单位运输费用为在最优路径情况下的费用,不同的道路等级(如高速公路、国道、省道、县道等)的运输费用不同;流转单价包括物流相关费用和管理费用,即单位木材在物流中心中转而产生的费用;固定投资费即木材物流中心基本建设管理费用均摊到每年的费用(在预计使用年限内)。
1.2 模型建立木材物流网络优化的目标是使整个木材网络耗费的总成本最低。从系统的角度,综合考虑选址与运输总成本最小化,因此总成本为木材物流中心运营管理成本与木材运输成本。其中,木材物流中心运营管理成本由变动处理成本和固定成本2部分构成,木材运输成本为直达与中转运输成本的求和。此外,木材物流中心在木材淡季时,为系统外的用户提供物流服务(如仓储、装卸搬运和流通加工等),可获得利润,这部分费用要从总成本中扣除。因此,建立木材物流网络优化的模型如下:
$\begin{align} & \text{min}F=\sum\limits_{h=0}^{H}{\sum\limits_{i=0}^{I}{\sum\limits_{d=0}^{K}{{{x}_{idh}}}}}{{C}_{idh}}+\sum\limits_{h=0}^{H}{\sum\limits_{i=0}^{I}{\sum\limits_{j=0}^{J}{{{x}_{ijh}}}}}{{C}_{ijh}}+\sum\limits_{h=0}^{H}{\sum\limits_{d=0}^{K}{\sum\limits_{j=0}^{J}{{{x}_{djh}}}}} \\ & {{C}_{djh}}+\left( \sum\limits_{d=0}^{K}{{{F}_{d}}}{{Z}_{d}}+\sum\limits_{h=0}^{H}{\sum\limits_{j=0}^{J}{\sum\limits_{d=0}^{K}{{{x}_{djh}}}}}{{q}_{dh}}-\sum\limits_{h=0}^{H}{\sum\limits_{d=0}^{K}{{{y}_{dh}}}}{{m}_{dh}} \right) \\ \end{align}$ |
xijh≥δijhEh (i= 1,2,…,I;j= 1,2,…,J;h=1,2,…,H)
xijh≥δijhM (i= 1,2,…,I;j= 1,2,…,J;h=1,2,…,H)
$\begin{align} & \sum\limits_{k=1}^{K}{{{x}_{idh}}}+\sum\limits_{j=1}^{J}{{{x}_{ijh}}}\le {{S}_{ih}}\left( i=1,~2,~\cdots ,~I;h=1,~2,~\cdots ,~H \right) \\ & \sum\limits_{d=1}^{K}{{{x}_{djh}}}+\sum\limits_{i=1}^{I}{{{x}_{ijh}}}\le {{D}_{jh}}~(j~=\text{ }1,2,~\cdots ,J;~h=1,2,\cdots ,H) \\ & \sum\limits_{h=1}^{H}{{{x}_{djh}}}\sum\limits_{i=1}^{I}{{{x}_{idh}}}+{{y}_{dh}}\le {{Q}_{d}}{{Z}_{d}}~(d~=1,2,~\cdots ,K) \\ & \sum\limits_{i=1}^{I}{{{x}_{idh}}}\ge \sum\limits_{j=1}^{J}{{{x}_{djh}}}(d=1,2,~\cdots ,K;~h=1,2,~\cdots ,H) \\ \end{align}$ |
xidh, xijh, xdjh≥0 ∀h, i, j, k
${{Z}_{d}}=\left\{ \begin{array}{*{35}{l}} 0 & 备选木材物流中心d未被选中 \\ 1 & 备选木材物流中心d被选中 \\ \end{array} \right.$ |
${{\delta }_{ijh}}=\left\{ \begin{array}{*{35}{l}} 0 & 供材点i与需材点j存在材种h的供需关系 \\ 1 & 供材点i与需材点j不存在材种h的供需关系 \\ \end{array} \right.$ |
式中:F为木材网络耗费的总成本;H为木材材种的数目;I、J为供材点、需材点的数目,K为木材物流中心的数目。xidh为每年将第h种木材从供材点i运送到木材物流中心d的数量(采用中转运输的方式,m3·a-1);Cidh为采用中转运输方式所产生单位运输费用(元·m-3),即每年将第h种木材从供材点i运送到木材物流中心d产生的单位运输费用。xijh为每年将第h种木材从供材点i直接运送至需材点j的数量(采用中转运输的方式,m3·a-1);Cijh为将第h种木材从供材点i直接运送至需材点j的单位运输成本(采用中转运输的方式,元·m-3)。xdhj为每年将第h种木材从木材物流中心d运送至需材点j的数量(采用中转运输的方式,m3·a-1);Cdjh为每年将第h种木材通过木材物流中心d中转,完成简单的流通加工作业之后,再运送至需材点j的单位运输成本(采用中转运输的方式,元·m-3)。Fd为木材物流中心d的流转固定费用(元·a-1),将一次性的建设成本年分摊到年;qdh为第h种木材在木材物流中心d中转之后产生的流转单价(元·m-3);Zd为0、1变量,取值为0时,表示第d个木材物流中心未被选中,否则被选中。ydh为系统外的客户每年在木材物流中心d中转的第h种木材的木材数量(m3·a-1);mdh为第h种木材在木材物流中心d中转获得的单位利润(元·m-3)。δijh为0、1变量,取决于供材点i与需材点j是否存在木材h的供需关系,取1表示存在供需关系,取0表示不存在供需关系;Eh为预先设定的可以直达运输的第h种木材的最低订货批量;M为一足够大的整数,取值为远大于各需材点的需求量;Sih为第i个供材点的第h种木材的最大供应能力;Djh为第j个需材点对第h种木材的需求量;Qd为木材物流d的吞吐量。
2 基于遗传-禁忌算法的模型求解上述模型综合考虑了选址与运输的优化,且物流中心数量不确定,是多对多的网络问题,模型较为复杂,求解也相对困难,普通算法难以求解得到所需要的满意解,而且求解效率低下。随着智能优化算法的发展和应用,可采用智能优化算法解决此类大规模的复杂问题。由于单一的智能优化算法各具优势和不足,将遗传算法与禁忌搜索算法相结合形成遗传-禁忌算法,二者优势互补解决此类问题,兼具较好的全局与局部搜索能力,以期得到更加满意的计算速度和结果。
由于木材物流网络的特殊性,采用遗传-禁忌算法进行求解的过程与一般问题相比有所不同,设计的求解流程如图 1所示。适应值的确定应具体问题具体分析,建立的模型追求费用最小化,这与适应度值的变化方向相反。当目标值减小时,适应值增大,而适应值越大,对应染色体的解越好。因此,设计木材物流网络优化适应度函数如下
$\begin{align} & f\left( h_{i}^{t} \right)=1-\frac{u\left( h_{i}^{t} \right)}{u_{\text{max}}^{t}+u_{\text{minu}}^{t}} \\ & u\left( h_{i}^{t} \right)=F\left( h_{i}^{t} \right)+C(h_{i}^{t}) \\ \end{align}$ |
式中:f(hit)为第t代种群中个体i的适应度函数对应的值;F(hit)为第t代种群中个体i的目标函数对应的值;C(hit)为第t代种群中个体i的惩罚函数对应的值;u max t, u min t表示种群t中具有最大值与最小值的个体。
3 实例分析 3.1 研究区概况与数据来源选取福建省三明永安市为研究区域,针对永安林业(集团)股份有限公司(简称永林集团)木材供需的物流网络,进行实证研究。福建省三明永安市位于福建省的中西部,具有良好的气候和土壤条件,林业产业较发达,森林覆盖率高达83.2%,是中国南方重点林区县(市)。该市作为闽西北的交通枢纽,公路网密布,交通发达,为永林集团在该区域木材物流中心的选址和木材物流网络的构建提供了很好的支撑作用。永林集团是国内首家以森林资源为主要经营对象的上市公司,其主要产品有木材、家具、纤维板等。永林集团森林经营分公司在永安市设有7个主要供材节点,分别是福庄、福溪、半村、元沙、大坑、燕江、小陶;4个主要的需材节点,分别是永安人造板厂、三明青山纸业、永林蓝豹、永安福星建材。需在满足各需材节点木材需求的前提下,以系统成本最小化为目标,对该集团永安市境内的木材物流网络进行优化。
本研究的数据来源于对集团调研得到的空间数据、属性数据和业务数据。空间数据包含永安市的道路图、林相图、地形图和遥感图等;属性数据是指空间要素相对应的属性信息,土地面积与土地等级、道路等级与道路长度、地价信息等;业务数据主要包括供材点的年均供应量、需材点的年均需求量备选物流中心的建设成本、单位流转费用及规模等,假设Hi(i=1,2) 分别为原木和薪材,Si(i=1,2,…,7) 为供材点,Di(i=1,2,…,4) 为需材点。综合考虑该区域木材物流中心选址的原则(经济合理性、交通便利性、发展空间等)和影响因素(地质和地形条件、交通条件、周边环境等)、根据永林集团物流部门管理层给出的选址标准及建设的预算,结合ArcGIS软件的空间分析功能,选出了4个备选物流中心地块(K1、K2、K3和K4)。具体的业务数据如表 1、表 2、表 3所示。由表 2可知,该集团的薪材(H2)全部运往永安人造板厂(D1),其物流网络较为简单,因此以下主要对原木(H1)的木材物流网络进行优化,以探讨模型算法的应用。
供材点 Supply sites |
供应量Supply quantity/m3 | |
H1 | H2 | |
S1 | 24 000 | 5 920 |
S2 | 43 900 | 10 890 |
S3 | 20 045 | 4 165 |
S4 | 25 800 | 5 567 |
S5 | 38 050 | 8 465 |
S6 | 27 198 | 4 800 |
S7 | 28 899 | 6 066 |
物流中心 Potential logistics center |
年均建设成本 Annual constructioncost /(yuan·a-1) |
候选点规模 Scale of potential site /m3 |
单位流转费用Unit conversion cost/(yuan·m-3) | |
H1 | H2 | |||
K1 | 79 000 | 85 000 | 20 | 24 |
K2 | 105 500 | 131 000 | 23 | 20 |
K3 | 98 300 | 100 190 | 15 | 25 |
K4 | 85 299 | 801 000 | 25 | 20 |
由于上述模型是假设最优路径情况下的单位运输成本,应用ArcGIS软件可找出各物流节点的最优路径,根据不同道路的木材单位运输成本,计算供材点、备选物流中心和需材点之间不同材种的单位运输成本(表 4、表 5)。
物流中心 Logistics center |
单位运输费用Per-unit transportation cost/(yuan·m-3·km-1) | ||||||||||
S1 | S2 | S3 | S4 | S5 | S6 | S7 | D1 | D2 | D3 | D4 | |
K1 | 17 | 10 | 14 | 15 | 15 | 18 | 14 | 2 | 4 | 3 | 4 |
K2 | 15 | 19 | 18 | 16 | 14 | 14 | 18 | 4 | 6 | 7 | 4 |
K3 | 14 | 15 | 16 | 14 | 18 | 16 | 13 | 5 | 8 | 3 | 6 |
K4 | 18 | 11 | 17 | 12 | 13 | 13 | 15 | 5 | 3 | 4 | 7 |
需材点 Demand sites |
单位运输费用Per-unit transportation cost/(yuan·m-3·km-1) | ||||||
S1 | S2 | S3 | S4 | S5 | S6 | S7 | |
D1 | 23 | 21 | 24 | 22 | 29 | 15 | 18 |
D2 | 27 | 26 | 14 | 26 | 17 | 19 | 15 |
D3 | 15 | 27 | 23 | 15 | 27 | 21 | 22 |
D4 | 17 | 25 | 15 | 18 | 25 | 17 | 27 |
根据木材物流网络优化问题的特点,将备选木材物流中心的数目及相应的运营成本、供材点的个数和供材量、需材点的个数和需求量、单位材积的运输费用等数据代入,按照遗传-禁忌算法的流程对该问题进行求解。采用十进制编码,编码长度为75,取群体规模为200,交叉概率(Pc)取80%,变异率(Pm)设为1.5%。最大迭代次数为250,由于运算难度较大,采用C#编写遗传-禁忌算法的运算程序,最佳物流中心有2个,分别是K1和K4,最小成本为1 536 578元,具体求解结果如表 6所示。
节点 Site |
需材量Demand quantity/m3 | 供材量 Supply quantity/m3 |
||||
D2 | D3 | D4 | K1 | K4 | ||
S1 | 8 312 | 5 232 | 10 357 | 0 | 0 | 23 901 |
S2 | 23 571 | 0 | 0 | 10 604 | 9 723 | 43 898 |
S3 | 1 850 | 14 630 | 3 455 | 0 | 0 | 19 935 |
S4 | 11 360 | 0 | 3 081 | 10 132 | 0 | 24 573 |
S5 | 19 681 | 0 | 6 808 | 9 901 | 0 | 36 390 |
S6 | 8 130 | 0 | 0 | 11 099 | 7 100 | 26 329 |
S7 | 14 891 | 6 232 | 7 354 | 0 | 0 | 28 477 |
K1 | 0 | 41 736 | 0 | 0 | 0 | 41 736 |
K4 | 0 | 0 | 16 820 | 0 | 0 | 16 820 |
合计Total | 87 795 | 68 730 | 47 875 | 41 736 | 16 823 | 262 059 |
结合ArcGIS可视化功能,将优化方案显示(图 2)。结果分析发现,木材物流网络经优化后,物流成本为1 536 578元,与优化前的物流成本1 674 800元相比降低8.25%,而且避免了木材物流舍近求远、迂回运输以及运力浪费等问题,节省了运输时间,提高了顾客满意度。另外,为了对比分析求解效率和精度,在求解程序中设置同样的参数,采用3种不同的算法进行运算。在求解效率方面,只用禁忌搜索算法所需的运算时间最短,为1 s;只遗传算法所需的运算时间最长,为5 s;而采用遗传-禁忌混合算法居中,为3 s。精度上,若单独用禁忌搜索算法,仅适用于物流节点数目较少的情况,若供需节点数目不断增多,采用这种方法则无法获得较为满意的解;如果单独采用遗传算法,由于这种方法全局搜索时,收敛速度过慢导致所需运算时间太长。因此,综合考虑求解效率和精度,采用遗传-禁忌混合算法能够更好地解决此类复杂问题,在可以接受的时间内,获得较高满意度的解。
4 小结从系统的角度出发,同时考虑木材物流网络系统内的综合费用[12]和为系统外的用户提供服务所获得的收益,构建木材物流网络优化的模型,针对数学模型的复杂性,传统算法求解困难,提出应用遗传算法与禁忌搜索算法混合而成的智能优化算法,通过取长补短,以弥补单一智能优化算法的不足之处,以便更好更快地解决问题。采用C#编写相应的求解程序,运行可得到木材物流中心的位置和数量,以及物流节点间的运输优化方案,再结合ArcGIS可视化功能,对方案进行显示。研究结果表明,模型考虑较为全面,采用遗传-禁忌混合智能算法与单一算法和传统算法相比,能够得到更加满意的收敛速度和求解精度;该模型与算法具有科学性和实用性,优化后的方案能够节省运输时间,降低物流成本;通过编程求解和ArcGIS方案显示,能够快速有效地得出优化方案,大大提高了求解效率。
由于本研究的立足点是企业,追求的是成本最小化,模型考虑是企业生产实际情况,以实现经济效益最优。此外,木材作为森林资源还具有社会效益和环境效益,后续研究的模型应进一步考虑和协调森林三大效益,促进森林的可持续发展。
[1] | 张兰怡, 林玉英, 邱荣祖. 基于BPNN的木材物流中心选址方法与实证分析[J]. 福建林学院学报, 2014, 34(1): 82–86. |
[2] | FIGUEIRA G, AMORIM P, GUIMARÃES L, et al. A decision support system for the operational production planning and scheduling of an integrated pulp and paper mill[J]. Computers & Chemical Engineering, 2015, 77: 85–104. |
[3] | 郝斯琪, 沈微. 基于SLP方法的木材物流中心布局:以绥芬河地区为例[J]. 森林工程, 2015, 31(1): 159–163. |
[4] | 邱荣祖, 林雅惠, 钟聪儿. 基于ArcGIS的木材物流中心选址[J]. 林业科学, 2010, 46(6): 113–117. DOI:10.11707/j.1001-7488.20100618 |
[5] | 刘娜翠, 邱荣祖. 基于遗传算法的木材运输方案优化技术[J]. 福建农林大学学报(自然科学版), 2010, 30(4): 380–384. |
[6] | 张淑芬, 邢艳秋, 吴红波, 等. 基于GIS和RS技术的木材运输线路优化研究:以吉林省汪清林区为例[J]. 森林工程, 2011, 27(2): 48–51, 60. |
[7] | ACUNA M, MIROWSKI L, GHAFFARIYAN M R, et al. Optimising transport efficiency and costs in Australian wood chipping operations[J]. Biomass and Bioenergy, 2012, 46: 291–300. DOI:10.1016/j.biombioe.2012.08.014 |
[8] | 陈诚, 邱荣祖. 多周期木材物流网络优化研究[J]. 福建林学院学报, 2014, 34(3): 274–278. |
[9] | 王忠伟, 宋雨屏. 动态环境下林产品物流网络模型研究[J]. 物流技术, 2012, 31(8): 240–242. |
[10] | KONG J, RÖNNQVIST M. Coordination between strategic forest management and tactical logistic and production planning in the forestry supply chain[J]. International Transactions in Operational Research, 2014, 21(5): 703–735. DOI:10.1111/itor.12089 |
[11] | LAITILA J, ROUTA J. Performance of a small and a medium sized professional chippers and the impact of storage time on Scots pine (Pinus sylvestris) stem wood chips characteristics[J]. Silva Fennica, 2015, 49(5): 1–19. |
[12] | 陈诚, 邱荣祖. 基于混合整数规划模型的木材物流网络优化[J]. 中南林业科技大学学报, 2013, 33(1): 94–98. |
[13] | 张全全, 谭文安. 基于遗传-禁忌算法的应急救援前摄性调度优化[J]. 计算机技术与发展, 2016, 26(6): 119–122. |
[14] | 郭强, 朱若函, 张晓萌. 基于遗传禁忌算法优化的模糊神经网络垂直切换算法[J]. 计算机应用研究, 2016, 33(3): 840–842, 847. |
[15] | 周骞, 韦凤连, 刘菊. 基于遗传禁忌算法的公交线路发车间隔优化[J]. 交通科学与工程, 2015, 31(2): 81–86. |
[16] | 熊杰, 杨东升, 王允森. 遗传禁忌搜索算法在工业机器人结构参数辨识上的应用[J]. 组合机床与自动化加工技术, 2015(12): 4–7, 11. |
[17] | 吴晓燕. 路标图像识别的禁忌搜索遗传算法研究[J]. 计算机工程与设计, 2014, 35(6): 2109–2113. |
[18] | 林玉英, 林宇洪, 邱荣祖. 木材物流决策支持系统的研究现状与展望[J]. 物流工程与管理, 2012, 34(11): 79–82. DOI:10.3969/j.issn.1674-4993.2012.11.030 |
[19] | 周新年, 赖阿红, 周成军, 等. 山地森林生态采运研究进展[J]. 森林与环境学报, 2015, 35(2): 185–192. |