一个具有仓库容量选择的两阶段设施选址问题的模型及算法

doi:10.12066/j.issn.1007-2861.2281

上海大学学报(自然科学版) ›› 2022, Vol. 28 ›› Issue (6): 996-1007.doi: 10.12066/j.issn.1007-2861.2281

一个具有仓库容量选择的两阶段设施选址问题的模型及算法

吴廷映¹(), 任亚婷¹, 周支立²

1.上海大学管理学院, 上海 200444
2.西安交通大学管理学院, 陕西西安 710049

收稿日期:2020-06-12 出版日期:2022-12-30 发布日期:2023-01-31
通讯作者: 吴廷映 E-mail:tingyingwu@shu.edu.cn
作者简介:吴廷映(1982-), 男, 博士, 研究方向为管理科学.E-mail: tingyingwu@shu.edu.cn

A two-echelon capacitated facility location problem with depot size selection

WU Tingying¹(), REN Yating¹, ZHOU Zhili²

1. School of Management, Shanghai University, Shanghai 200444, China
2. School of Management, Xi'an Jiaotong University, Xi'an 710049, Shaanxi, China

Received:2020-06-12 Online:2022-12-30 Published:2023-01-31
Contact: WU Tingying E-mail:tingyingwu@shu.edu.cn

摘要/Abstract

摘要：

设施选址及其规模选择优化对供应链的长期战略成本和运营成本有着重要影响, 是提高企业利润和竞争力的关键决策之一, 也是运筹优化领域研究的热点与难点. 针对已有的两阶段设施选址问题,(two-stage facility location problem, TSFLP),研究中缺乏对设施容量选择的优化, 在设施选址问题基础上引入了设施容量选择的优化, 同时确定了工厂的位置、仓库的位置和容量、从工厂到仓库的产品流以及客户到仓库的分配, 建立了以最小化总成本为目标的混合整数规划模型, 并基于模型特点设计了适合求解此问题的拉格朗日松弛(Lagrangean relaxation, LR)方法和混合变邻域禁忌搜索,(hybrid variable neighborhood tabu search, HVNTS)算法. 基于随机生成的大量具有不同参数的实例, 验证了所提出的算法可有效求解大规模的、且需同时优化设施选址及容量选择的问题.

关键词: 设施选址, 仓库容量选择, 拉格朗日松弛, 混合变邻域禁忌搜索

Abstract:

Facility location is a problematic point in modern enterprise production and operation management. Further, it is a decisive factor affecting enterprises' efficiency because of the shortage of facility capacity selection in the existing two-stage facility location study. This study introduced the optimisation decision technology of facility capacity selection simultaneously. The problem was predominately in opening plants and depots, selecting the size of depots, determining the product flows from the opened plants to the opened depots, and the customers' assignments to the opened depots to satisfy the customers' demands. A mixed-integer programming model to minimise the total cost was proposed. The Lagrangean relaxation (LR) approach and hybrid variable neighbourhood tabu search (HVNTS) algorithm were designed to solve this problem. A large number of instances were randomly generated and tested to evaluate the effectiveness of the proposed method. The results verified that this method could solve the problem of large-scale facility location with depot size selection.

Key words: facility location, depot size selection, Lagrangian relaxation (LR), hybrid variable neighbourhood tabu search (HVNTS)

中图分类号:

C931.1

吴廷映, 任亚婷, 周支立. 一个具有仓库容量选择的两阶段设施选址问题的模型及算法[J]. 上海大学学报(自然科学版), 2022, 28(6): 996-1007.

WU Tingying, REN Yating, ZHOU Zhili. A two-echelon capacitated facility location problem with depot size selection[J]. Journal of Shanghai University（Natural Science Edition）, 2022, 28(6): 996-1007.

图/表 8

图1

图2

表1

表2

表3

表4

表5

表6

参考文献 22

[1]	Melo M T, Nickel S, Saldanha-Da-Gama F. Facility location and supply chain manag ement: a review[J]. European Journal of Operational Research, 2009, 196(2): 401-412.
[2]	Akyuz M H, Oncan T, Altinel I K, et al. Beam search heuristics for the single and multi-commodity capacitated multi-facility weber problems[J]. Computers & Operations Research, 2013, 40(12):3056-3068.
[3]	Goldengorin B, Ghosh D, Sierksma G, et al. Branch and peg algorithms for the simple plant location problem[J]. Computers & Operations Research, 2003, 30(7): 967-981.
[4]	Klose A. A Lagrangean relax-and-cut approach for the two-stage capacitated facility location problem[J]. European Journal of Operational Research, 2000, 126(2): 408-421.
[5]	Sun M. Solving the uncapacitated facility location problem using tabu search[J]. Computers & Operations Research, 2006, 33(9): 2563-2589.
[6]	郭崇慧, 覃华勤. 一种改进的禁忌搜索算法及其在选址问题中的应用[J]. 运筹与管理, 2008, 17(1): 18-23.
[7]	Sun M. A tabu search heuristic procedure for the capacitated facility location problem[J]. Journal of Heuristics, 2012, 18(1): 91-118.
[8]	俞武扬, 吕静. 需求导向的容量设施竞争选址问题研究[J]. 运筹与管理, 2019, 28(10): 13-19.
[9]	Guastaroba G, Speranza M G. A heuristic for BILP problems: the single source capacitated facility location problem[J]. European Journal of Operational Research, 2014, 238(2): 438-450.
[10]	Yang Z, Chu F, Chen H. A cut-and-solve based algorithm for the single-source capacitated facility location problem[J]. European Journal of Operational Research, 2012, 221(3): 521-532.
[11]	Al-Yakoob S M, Sherali H D. A mathematical modelling and optimization approach for a maritime facility location transshipment problem[J]. Informatica, 2018, 29(4): 609-632.
[12]	Klose A, Drexl A. Facility location models for distribution system design[J]. European Journal of Operational Research, 2005, 162(1): 24-29.
[13]	杨丰梅, 华国伟, 邓猛, 等. 选址问题研究的若干进展[J]. 运筹与管理, 2005, 14(6): 1-7.
[14]	Tragantalerngsak S, Holt J, Ronnqvist M, et al. An exact method for the two-echelon, single-source, capacitated facility location problem[J]. European Journal of Operational Research, 2000, 123(3): 473-489.
[15]	Hinojosa Y, Puerto J, Fernandez F R. A multiperiod two-echelon multicommodity capacitated plant location problem[J]. European Journal of Operational Research, 2000, 123(2): 271-291.
[16]	Wu L Y, Zhang X S, Zhang J L. Capacitated facility location problem with general setup cost[J]. Computers & Operations Research, 2006, 33(5): 1226-1241.
[17]	Carrizosa E, Ushakov A, Vasilyev I. A computational study of a nonlinear minsum facility location problem[J]. Computers & Operations Research, 2012, 39(11): 2625-2633.
[18]	Yang Z, Chen H, Chu F, et al. An effective hybrid approach to the two-stage capacitated facility location problem[J]. European Journal of Operational Research, 2019, 275(2): 467-480.
[19]	张震, 李延晖, 张琦. 考虑退货的多商品多来源闭环选址库存问题模型与算法[J]. 工业工程与管理, 2018, 23(6): 137-146.
[20]	Wu T Y, Chu F, Yang Z, et al. A lagrangean relaxation approach for a two-stage capacitated facility location problem with choice of depot size[C]// International Conference on Networking. 2015:39-44.
[21]	Cornuejols G F, Sridharan R, Thizy J M. A comparison of heuristics and relaxations for the capacitated plant location problem[J]. European Journal of Operational Research, 1991, 50(3):280-297.
[22]	Klose A. An LP-based heuristic for two-stage capacitated facility location problems[J]. The Journal of the Operational Research Society, 1999, 50(2): 157-166.

一个具有仓库容量选择的两阶段设施选址问题的模型及算法

A two-echelon capacitated facility location problem with depot size selection

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 22

相关文章 2

编辑推荐

Metrics

本文评价

[1]	王国欣;沈秋英;孙小玲. 带工业约束和交易费用的离散投资组合最优化[J]. 上海大学学报(自然科学版), 2007, 13(6): 736-740 .
[2]	盛红波;孙娟;孙小玲. 0-1多项式背包问题的一种精确算法[J]. 上海大学学报(自然科学版), 2006, 12(4): 389-393 .