一种基于改进蚁群算法与GIS的多约束配送中心选址方法

赵仁辉, 杨丽娜, 邵静

地球信息科学学报 ›› 2015, Vol. 17 ›› Issue (2) : 172-177.

PDF(3586 KB)
EN中文
PDF(3586 KB)
地球信息科学学报 ›› 2015, Vol. 17 ›› Issue (2) : 172-177. DOI: 10.3724/SP.J.1047.2015.00172 CSTR: 32074.14.SP.J.1047.2015.00172

一种基于改进蚁群算法与GIS的多约束配送中心选址方法

作者信息 +

A Method for Multi-constraint Location Decision of Distribution Center Based on Refined Ant Colony Algorithm and GIS

Author information +
文章历史 +

摘要

针对单一指派约束和容量约束的设施选址问题（Single Source Capacitated Facility Location Problem, SSCFLP）,建立了一种基于改进蚁群算法与GIS的配送中心选址方法。构建了以总成本费用最小为目标的配送中心选址模型;提出了适合求解SSCFLP问题的改进双层蚁群算法,将求解过程划分为彼此关联的设施选择层和需求指派层2层蚁群,采用改进的全局信息素更新策略加强双层蚁群交流,并对迭代最优解的指派关系进行局部优化;将方法应用于汽车配送中心的选址,利用GIS工具构建选址空间。实验结果表明,该选址方法能找到质量较好的选址及指派结果,对于求解同类问题具有较强的借鉴意义。

Abstract

Location decision of any logistics distribution center meets multiple constraints, such as the specific spatial environment, the single assignment constraint, the capacity of warehouses and the minimum cost of capital. This paper proposed a model based on refined ant colony algorithm and GIS tools to solve Single Source Capacitated Facility Location Problem (SSCFLP). Firstly, a location selection model was established, which met the target of minimizing the total cost. Secondly, by combining ant colony algorithm and local search, the refined bi-level ant colony optimization to solve the SSCFLP problem was proposed. The solving process was divided into two layers: the layer of choosing facilities and the layer of assigning demands. These two layers were associated with each other. In each iteration, the ants would generate solutions by selecting new sets of facility locations from the candidate sites according to the capacity constraint, and establish the assignment of each customer to a selected facility location using pseudorandom search. The iteration-best solution was optimized and memorized using local search. Then the global optimal solution could be attained through conducting multiple iterations. Finally, a location decision case of the car logistics distribution center in Binhai district was constructed. Site selection space was constructed based on GIS tools, considering demands, candidate sites and shipping cost, and other spatial factors, such as land use, hydrology and terrain. The experimental results revealed that the method was efficient and could find reasonable scheme for determining location and allocation. It had certain academic significance to other similar problems.

关键词

改进双层蚁群算法 / SSCFLP / GIS / 容量约束

Key words

refined bi-level ant colony optimization / SSCFLP / GIS / capacity constraint

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
赵仁辉, 杨丽娜, 邵静. 一种基于改进蚁群算法与GIS的多约束配送中心选址方法[J]. 地球信息科学学报, 2015, 17(2): 172-177 https://doi.org/10.3724/SP.J.1047.2015.00172
ZHAO Renhui, YANG Lina, SHAO Jing. A Method for Multi-constraint Location Decision of Distribution Center Based on Refined Ant Colony Algorithm and GIS[J]. Journal of Geo-information Science, 2015, 17(2): 172-177 https://doi.org/10.3724/SP.J.1047.2015.00172

1 引言

在一定空间范围内对配送中心的数量及区位进行合理规划,可以优化资源配置[1-2]。根据限制条件的强弱,选址模型分为多种形式。其中,对单一指派约束和容量约束的设施选址问题（Single Source Capacitated Facility Location Problem, SSCFLP）要求每个配送中心有一定的容量限制,且各需求点只由一个配送中心供应,具有较强的现实意义。SSCFLP属于双层NP-hard问题,难以用精确算法求解。近年来,学者们认识到空间搜索方法对公共设施选址具有重要意义[3-5],开展了基于元启发算法求解SSCFLP问题的研究,如粒子群算法（PSO）[6]、遗传算法（GA）[7]、模拟退火算法（SA）[8]等。
蚁群算法（Ant Colony Optimization,ACO）是通过模拟自然界中的蚂蚁行为方式和交流方式解决问题的启发式正反馈搜索算法,该算法由Dorigo于1992年提出[9-10],并广泛应用于旅行商问题[11]、二次指派问题[12]和设施选址问题[13]。已有研究利用ACO求解SSCFLP[14-15],其中文献[14]运用并行蚁群算法着重说明了群组间的交流更新策略,但未明确双层问题构建解的方法;文献[15]应用混合蚁群和局部搜索（Hybrid Ant Colony Optimization-Local Search, HACO-LS）构建了双层蚁群架构,但每获取一个设施点集合均需利用局部搜索得到对应的最优指派,计算效率较低。考虑到SSCFLP的设施选址与需求指派2个过程正向相关,选址结果直接影响指派关系,指派结果正反馈于选址决策,本文提出了改进的双层蚁群算法（Refined Bi-level Ant Colony Optimization,RB-ACO）模型,改进了信息素更新和局部搜索策略,提升了SSCFLP的求解效率。此外,随着大量空间数据的引入,将GIS与区位配置模型相结合能充分利用GIS的空间分析能力,为决策者提供具体的最佳区位空间[16-18]。

2 配送中心选址模型

本文所研究的配送中心选址为成本最小问题[19],在已有若干配送中心及集装地情况下,新建配送中心使得包含二次运输成本（集装地至配送中心、配送中心至经销商）和建设成本的总成本最小。基于SSCFLP和p-median模型,建立的配送中心选址模
型如下：
min φ ⋅ ∑ i = 1 I ∑ j = 1 J d ij u i x ij + ∑ h = 1 H ∑ j = 1 J ∑ i = 1 I d h j u i x ij + ∑ j = 1 J 2 f j y j （1）
s . t . ∑ j = 1 J x ij = 1 , ∀ i ∈ I （2）
x ij ≤ y j , ∀ i ∈ I , j ∈ J （3）
x ij ∈ 0,1 , ∀ i ∈ I , j ∈ J （4）
y j ∈ 0,1 , j ∈ J 2 （5）
y j = 1 , ∀ j ∈ J 1 （6）
b j ≤ ∑ i = 1 I u i x ij ≤ B j , ∀ j ∈ J 2 （7）
式（1）为目标函数,表示总成本费用最小。其中, I 为需求点集合; J = J 1 ∪ J 2 为设施点集合, J 1 、 J 2 分别为现有与新建设施点; H 为现有集装地集合; d ij 、 d h j 为需求点 i 到设施点 j ,集装地 h 到设施点 j 的连通成本; u i 为需求点 i 的需求量;决策变量为 x ij （表示是否将 i 点的需求指派给设施点 j ）、 y j （表示是否在 j 点新建设施点）; φ 为单位运量单位距离的运输费用; f j 为在 j 点新建设施的固定费用及管理费用等。式（2）表示任意需求点的需求被满足,且只能指派给一个设施点;式（3）表示需求点必须被指派给新建或现存的设施点;式（4）-（6）约定了决策变量的取值范围,其中,式（6）表示现有设施点将继续提供配送服务;式（7）表示容量约束,即指派给某个设施点的需求量之和应在其最大容量 B j 、最小容量 b j 之间。

3 改进的双层蚁群算法

本文在蚁群系统算法框架[11]和HACO-LS双层蚁群架构[15]基础上,提出了适合求解SSCFLP问题的改进双层蚁群算法。SSCFLP问题包括新建设施点( y j )选取和需求点( x ij )指派,据此将求解过程划分为彼此关联的2层,即设施选择层和需求指派层,2层搜索的结果共同构成完整解。通过评价解的质量以信息素形式在双层蚁群之间交流,形成正向反馈,并对迭代最优解进行局部优化以提升搜索质量。具体步骤如下：
（1）初始化,设定蚁群的相关参数和初始信息素浓度,迭代次数设为0。
（2）构建完整解,每只蚂蚁分别在设施选择层和需求指派层搜索：
① 设施选择层：随机选择新建设施数量,根据状态转移规则选出相应数量的设施点;
② 需求指派层：根据状态转移规则将需求点逐个指派给选择的设施点,关闭未被指派的设施点,新建设施数量减1。
（3）更新局部信息素。
（4）执行局部搜索,对当前迭代最优解进行局部优化。
（5）全局信息素更新,根据当前迭代最优解与至今最优解更新全局信息素。
（6）算法终止判断,达到最大迭代次数或连续多次找到相同最优解,则算法终止;否则重复步骤（2）–（5）,迭代次数加1。

3.1 设施选择层

在SSCFLP中,设施点选择的结果直接影响需求点指派的质量。为保证构建解的多样性,每只蚂蚁随机选择新建设施数量,其取值范围由需求量和设施容量限制确定（式（8））。
N = Random ∑ i = 1 I u i B j , ∑ i = 1 I u i b j （8）
根据状态转移规则从候选设施点中选择N个新建设施, q 0 为预设的伪随机参数,当随机变量 q ≤ q 0 时,选择当前质量最好的设施点;否则根据转移概率 P j w 随机产生一个设施点 J random 。
j = arg max j ∈ allowed τ j η j α , q ≤ q 0 J random , q > q 0 （9）
J random : P j w = τ j η j α ∑ τ j η j α （10）
式中, all o wed 为尚未被选择的设施点集合; τ j 、 η j 为设施点j的信息素含量和启发信息,此处的 η j 设置为Bj/fj,即与设施点的容量承载能力和费用成本相关; α 是启发信息的影响力参数。

3.2 需求指派层

N 个新建设施点确定后,蚂蚁根据状态转移规则将需求点逐个指派给选择的设施点,如式（11）–（12）所示。
v = arg max j ∈ allowed ξ ij ψ ij β ， q ≤ q ′ 0 V random ， q > q ′ 0 （11）
V random : P v w = ξ ij ψ ij β ∑ ξ ij ψ ij β （12）
式中, allowed 为剩余容量大于该需求点需求量的新建设施点集合; ξ ij 、 ψ ij 分别为需求点i和设施点j之间的信息素含量和启发信息,此处的启发信息设为 1 / d ij ,即倾向于指派给道路成本较小的设施点。为了避免不必要的成本浪费,如果某个新建设施点未被分配需求点,则关闭该设施点,蚂蚁的新建设施数量减1。

3.3 局部搜索

在HACO-LS[15]的每次迭代中,所有解的指派关系都需要通过局部搜索达到最优,效率较低。本文的RB-ACO仅对当前迭代最优解的指派关系进行局部优化,具体步骤如下：
（1）检查解的可行性,计算目标函数值;
（2）随机将一个需求点重新指派给其他新建设施点,指派关系和承载的容量随之更新;若更新后存有未被分配需求点的设施点,则关闭该设施,蚂蚁的新建设施数量减1;
（3）重复以上2步,直到获得不可再提升质量的可行解;若该解更优,则原迭代最优解被替换。
本文的局部搜索允许非可行解的出现,将以罚值的形式增加到模型目标函数的计算中,罚值如式（13）-（14）所示,M为固定值, e j 为设施点j承载的需求量超出容量限制的程度。
penalty = ∑ e j M （13）
e j = max 0 , ∑ u i - B j , b j - ∑ u i （14）

3.4 信息素更新

蚁群系统的信息素更新包含全局和局部规则。在RB-ACO算法中,每只蚂蚁 w 的双层解构建完成后随即执行局部信息素更新,对解 T w 包含的设施点 j 和指派关系 i , j 进行信息素释放,同时所有候选解的信息素自然挥发。 ρ , ρ ′ ∈ ( 0,1 ) 为衰减系数,反映了信息素挥发的速度; τ j 0 、 ξ ij 0 分别为设施选择层和需求指派层的初始信息浓度,此处的 τ j 0 设为1/fj。
τ j g + 1 = ( 1 - ρ ) τ j g + ρ τ j 0 , j ∈ T w （15）
ξ ij g + 1 = ( 1 - ρ ′ ) ξ ij g + ρ ′ ξ ij 0 , i , j ∈ T w （16）
在RB-ACO算法中,双层蚁群之间的信息素含量联系紧密,设施选择层的信息素含量参与决定选择设施,直接影响了需求指派的设施可选性;需求指派层的信息素含量指导该层指派关系,还可反馈于设施点选择。本文采用的全局信息素更新策略为：根据迭代最优解 T l 与至今最优解 T b 更新全局信息素,且设施选择层的全局信息素由解的质量和指派到每个设施点的需求点数量决定。
τ j g + 1 = ( 1 - ρ ) τ j g + ρ Δ τ j g （17）
ξ ij g + 1 = ( 1 - ρ ′ ) ξ ij g + ρ ′ Δ ξ ij g （18）
Δ τ j g = L w - L b + L w - L l × a j / L w , j ∈ T b or T l （19）
Δ ξ ij g = L w - L b + L w - L l / L w , i , j ∈ T b or T l （20）
式中, L b 、 L l 、 L w 分别为至今最优解、迭代最优解和迭代最差解的目标函数值; a j 为指派到设施点j的需求点数量。

4 多约束配送中心选址的应用实例与分析

4.1 基于GIS的选址空间构建

本文构建了天津滨海新区汽车配送中心选址问题。获取了行政区划、主要道路、土地利用、水文和地形数据,选取了39个汽车经销商、1个现有汽车配送中心和1个汽车集装地,汽车需求总量为27.435万辆。
汽车配送中心候选点的选取涉及诸多因素[20-21],根据数据获取情况,本文考虑自然环境和土地利用,在ArcGIS平台下确定设施候选点,过程如图1所示。首先在行政区划内去掉不适宜建设区域（水域、城镇建成区）,并与适宜建设区域（地势平坦）叠加,再去除面积过小的部分获得候选区域;将其与规则地理格网叠置分析,合并后的格网中心为初始候选点;对相距较近的初始候选点聚类形成239个设施候选点。
图1 设施候选点的获取流程

Fig. 1 Acquisition procedure of candidate sites

Full size|PPT slide

在已有的GIS选址研究中,多使用直线距离或路网内最短路径作为道路连通成本[20-21]。本文对需求点和设施点不在城市交通网络交汇点或边线上的情况加以分析（图2）,需求点 i 和 设施点j之间的连接边线可表示为式（21）-（24）所示4种形式,以其最低成本作为道路连通成本 d ij 。
图2 选址连通边线示意

Fig. 2 Schematic diagram of site connectivity lines

Full size|PPT slide

R ij = L i i ' + L i ' p 1 + E p 1 p n + L p n j ' + L j j ' （21）
R ij = L i i ' + L i ' p 0 + E p 0 p n + L p n j ' + L j j ' （22）
R ij = L i i ' + L i ' p 1 + E p 1 p n + 1 + L p n + 1 j ' + L j j ' （23）
R ij = L i i ' + L i ' p 0 + E p 0 p n + 1 + L p n + 1 j ' + L j j ' （24）
式中, i ′ 、 j ′ 为点到距其最近道路的垂足;E为路网内最短路径。公式中各参数可通过ArcGIS工具和坐标计算得到。

4.2 双层蚁群算法参数设置

本文的求解算法是在NetBeans平台下使用Java语言编写。对主要参数 α 、 β 、 q 0 、 q ′ 0 、 ρ 、 ρ ′ 分别在一个取值集合内进行实验,得到的最优参数取值如表1所示。经过分析,当启发信息的影响力 α 、 β 取较大值时,启发信息的影响增大,更倾向于选择 B j / f j 较大的设施点和道路连通成本较小的指派关系,算法易陷入局部最优;伪随机变量 q 0 、 q ′ 0 代表选择质量最好解和进行随机概率选择的比率,随着该值的增大,算法的空间探索性降低;信息素挥发速度 ρ 、 ρ ′ 越大,信息素减少越快,算法易于过早收敛。
表1 双层蚁群算法主要参数取值

Tab. 1 Main parameters of bi-level ant colony optimization

参数名称 取值集合 最优值
设施选择层 α（启发信息的影响力） [0.3、0.5、1、3、5、7] 1
q0（伪随机参数） [0.05、0.1、0.3、0.5、0.7] 0.1
ρ（信息素挥发速度） [0.05、0.1、0.3、0.5、0.7] 0.1
需求指派层 β（启发信息的影响力） [0.3、0.5、1、3、5、7] 3
q′0（伪随机参数） [0.05、0.1、0.3、0.5、0.7] 0.1
ρ′（信息素挥发速度） [0.05、0.1、0.3、0.5、0.7] 0.1

4.3 实验对比与分析

本实验设置的选址参数为：已有设施点容量 B exist 为10万辆,新建设施最大容量Bj为6万辆,新建设施最小容量 b j 为3万辆,单位运量单位距离运输费用 φ 为1元,每个新建设施固定费用及管理费用 f j 为300万元。根据容量限制至少应新建3个设施点,则设施选择层要对比的组合至少为 239 ! 3 ! （ 239 - 3 ） ! （约为2.24×106）种,需求指派层在此基础上最高的组合可能性为 ( 3 + 1 ) ! 39 （约为 3.02 × 10 23 ）种,无法使用穷尽搜索。
利用RB-ACO算法进行20次实验,得到的最优选址结果见表2,对应的新建设施空间分布及需求指派情况如图3所示。新建的3个设施点符合选址的实际需求：各点都位于滨海新区行政区划内,所在地块地势平坦,距离水域和居民地较远,可建设面积大于1 km2;各点的需求承载量均符合容量限制;3个新建设施点均位于京津唐高速公路附近,且基本在汽车集装地和汽车经销商中心的连线上,交通设施条件便利,保证了较低的运输成本。
表2 B-ACO的选址结果

Tab. 2 Location decision result of bi-level ant colony optimization

设施点 指派给该设施点的需求点 容量承载（万辆）
74号 4、6、8、9、11、12、18 5.994
79号 0、3、7、10、14、16、20 5.958
90号 1、2、5、13、15、19、22、23、24、25、27、29、30、32、33、35 9.512
102号 17、21、26、28、31、34、36、37、38 5.971
注： 90号为已有设施点,最大可承载容量为10万辆
图3 滨海新区汽车配送中心的空间分布及需求指派示意图

Fig. 3 Location and assignment diagrams of car logistics distribution centers in Binhai district

Full size|PPT slide

为了验证算法的改进效果,与HACO-LS[15]进行对比,结果如表3所示。RB-ACO在成本费用、标准差和时间效率上都优于HACO-LS,改进的信息素更新策略和优化迭代最优解策略较为有效。RB-ACO能够在更短的运算时间内发现较优解,且运算偏差较小,表明RB-ACO对求解SSCFLP有着良好的有效性和稳定性。
表3 算法性能对比

Tab. 3 Comparison of algorithms performance

算法 最小成本（×104元） 平均成本（×104元） 标准差（×104元） 平均计算耗时（S）
RB-ACO 2420.99 2421.97 0.52 6.92
HACO-LS 2421.12 2423.85 1.36 1850.40

5 总结

本文考虑物流配送中心选址的容量约束和指派约束,提出了改进的双层蚁群算法以求解SSCFLP问题,将设施选择层和需求指派层蚁群作为整体统一迭代优化,采用改进的信息素更新策略和优化迭代最优解策略;并利用GIS构建了天津滨海新区汽车配送中心的选址空间;通过实例运算,选址个数与区位符合实际需求,并与已有蚁群算法进行对比,证明了该套选址方案的有效性。今后需展开：（1）寻求更合适的设施选择层和需求指派层间的配合方式,使蚁群算法与SSCFLP问题更加契合;（2）大规模数据的试验,并与解决SSCFLP问题的其他元启发算法深入对比研究。

参考文献

列表( 原文顺序 | 文献年度倒序 | 文中引用次数倒序 ) 可视化分析
[1]
鲁晓春,詹荷生.关于配送中心重心法选址的研究[J].北方交通大学学报,2000,24(6):108-110.
本文引用 [1]
[2]
孙曦. 农产品物流配送中心的选址模型构建及其应用[J].北京农学院学报,2014,2(29):86-90.
本文引用 [1]
[3]
何晋强,黎夏,刘小平,等.蚁群智能及其在大区域基础设施选址中的应用[J].遥感学报,2009,13(2):246-256.
本文引用 [1]
[4]
黄玲,柳宗伟.基于神经网络的选址区位评价模型分析应用[J].地球信息科学,2004,6(2):37-41.
[5]
赵元,张新长,康停军.多叉树蚁群算法及在区位选址中的应用研究[J].地理学报,2011,66(2):279-286.
本文引用 [1]
[6]
胡伟,徐福缘,台德艺,等.基于改进粒子群算法的物流配送中心选址策略[J].计算机应用研究,2012,29(12):4489-4491.
本文引用 [1]
[7]
Maric M.An efficient genetic algorithm for solving the multi-level uncapacitated facility location problem[J]. Computing and Informatics, 2010,29(2):183-201.
本文引用 [1]
[8]
Yu V F, Lin S W, Lee W, et al.A simulated annealing heuristic for the capacitated location routing problem[J]. Computers and Industrial Engineering, 2010,58(2):288-299.
本文引用 [1]
[9]
Dorigo M.Optimization, learning and natural algorithms[D]. Italy: Department of Electronics, Politrcnico di Milano, 1992.
本文引用 [1]
[10]
Colorni A, Dorigo M, Maniezzo V.Distributed optimization by ant colonies[C]. Proceedings of the First European Conference on Artificial Life, MIT Press, 1992:134-142.
本文引用 [1]
[11]
Dorigo M, Gambardella L M.Ant colony system: A cooperative learning approach for the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997,1(1):53-66.
本文引用 [2]
[12]
殷人昆,吴阳,张晶炜.蚁群算法解决指派问题的研究和应用[J].计算机工程与科学,2008,30(4):43-46.
本文引用 [1]
[13]
高雷阜,张晓翠.基于最大最小蚂蚁系统的物流配送中心选址算法的研究[J].运筹与管理,2007,16(6):42-46.
本文引用 [1]
[14]
崔小燕,李旭宏,毛海军,等.受限单分配枢纽选址问题的并行蚁群算法[J].交通运输工程学报,2011,11(3):74-81.
本文引用 [2]
[15]
Yang L N, Sun X, Chi T H.A hybrid ant colony optimization algorithm with local search strategies to solve single source capacitated facility location problem[C]. Proceedings of International Conference on Industrial Control and Electronics Engineering (ICICEE), IEEE, 2012:83-85.
本文引用 [5]
[16]
Church R L, Sorensen P.Integrating normative location models into GIS: Problems and prospects with the p-median model[R]. Santa Barbara: National Center for Geographic Information and Analysis, 1994.
本文引用 [1]
[17]
Farahani R Z, Hekmatfar M.Facility Location: Concepts, Models, Algorithms and Case Studies[M]. New York: Springer-Verlag Berlin Heidelberg, 2009.
[18]
吴健宏,翁文国.应急避难场所的选址决策支持系统[J].清华大学学报(自然科学版),2011,51(5):632-636.
本文引用 [1]
[19]
吴坚,史忠科.基于遗传算法的配送中心选址问题[J].华南理工大学学报:自然科学版,2004,32(6):71-74.
本文引用 [1]
[20]
许婷,盛明,娄彩荣.基于GIS和蚁群算法的物流配送中心选址研究[J].测绘科学,2010,35(6):206-208.
本文引用 [2]
[21]
林娜,李志. 基于GIS和遗传算法的物流配送中心选址研究[J]. 遥感信息,2010(5):110-114.
本文引用 [2]

脚注

The authors have declared that no competing interests exist.

基金

国家自然科学基金项目(41201397)
国家科技部政策引导项目(2011FU125Z24)
PDF(3586 KB)
可视化

1188

Accesses

0

Citation

Detail
段落导航
相关文章

/

〈 〉