具有设施容量选择的两阶段设施选址问题研究

doi:10.15960/j.cnki.issn.1007-6093.2023.03.006

摘要/Abstract

摘要：

设施位置与设施容量是影响供应链长期运营成本和服务质量的重要因素，也是企业获得竞争优势的两个决定性因素。针对设施选址及容量选择优化问题，本文提出以最小化成本为目标的混合整数规划模型，对工厂和仓库的位置及容量，工厂到仓库的产品流和客户到仓库的分配进行优化。根据模型特点设计拉格朗日松弛算法对其进行求解，为了提高解的质量，本文开发混合模拟退火禁忌搜索算法对拉格朗日松弛算法的求解结果进行改进。本文利用随机生成的大量具有不同规模及参数的实例对算法的有效性进行检验，数值实验表明该算法适用于同时优化设施选址及容量选择问题。

关键词: 两阶段设施选址, 设施容量, 拉格朗日松弛算法, 混合模拟退火禁忌搜索算法

Abstract:

The facility location and size are important factors that affect operation cost and service quality of supply chain, and also two decisive factors for enterprises to gain competitive advantage. In order to optimize facility location and size simultaneously, a mixed integer programming model is formulated to minimize the total costs, and to decide the location of plants and depots, select sizes for the plants, determine the product flows from the plants to the depots and assign the customers to the depots. According to characteristics of the problem model, a Lagrangian relaxation algorithm is designed to solve the problem, and a hybrid simulated annealing tabu search algorithm is developed to further improve the solution quality. To test the validity of the proposed algorithm, a large number of randomly generated instances of different sizes and parameters are provided. The numerical results indicate that the proposed algorithm is effective and efficient for the two-echelon facility location problem with choice of facility size.

Key words: two-echelon facility location problem, facility size, Lagrangian relaxation algorithm, hybrid simulated annealing tabu search algorithm

中图分类号:

吴廷映, 王瑶, 周支立, 任亚婷. 具有设施容量选择的两阶段设施选址问题研究[J]. 运筹学学报, 2023, 27(3): 83-95.

Tingying WU, Yao WANG, Zhili ZHOU, Yating REN. A two-echelon facility location problem with choice of facility size[J]. Operations Research Transactions, 2023, 27(3): 83-95.

图/表 5

表1

表2

表3

表4

表5

参考文献 15

1	Cooper L . Location-allocation problems[J]. Operation Research, 1963, 11 (3): 331- 343. doi: 10.1287/opre.11.3.331
2	Revelle C S , Eiselt H A , Daskin M S . A bibliography for some fundamental problem categories in discrete location science[J]. European Journal of Operational Research, 2008, 184 (3): 817- 848. doi: 10.1016/j.ejor.2006.12.044
3	Melo M T , Nickel S , Saldanha-da-Gama F . Facility location and supply chain management-A review[J]. European Journal of Operational Research, 2009, 196 (2): 401- 412. doi: 10.1016/j.ejor.2008.05.007
4	Klose A . An LP-based heuristic for two-stage capacitated facility location problems[J]. Journal of the Operational Research Society, 1999, 50 (2): 157- 166. doi: 10.1057/palgrave.jors.2600675
5	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. doi: 10.1016/S0377-2217(99)00300-8
6	Fernandes D R M , Rocha C , Aloise D , et al. A simple and effective genetic algorithm for the two-stage capacitated facility location problem[J]. Computers & Industrial Engineering, 2014, 75, 200- 208.
7	金莉, 朱云龙, 申海. 三级物流网络选址-路径问题建模与求解算法研究[J]. 控制与决策, 2010, 25 (08): 1195-1200, 1206
8	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. doi: 10.1016/j.ejor.2018.11.062
9	张震, 李延晖, 张琦. 考虑退货的多商品多来源闭环选址库存问题模型与算法[J]. 工业工程与管理, 2018, 23 (06): 137- 146.
10	Harkness J , Revelle C . Facility location with increasing production costs[J]. European Journal of Operational Research, 2003, 145 (1): 1- 13. doi: 10.1016/S0377-2217(02)00176-5
11	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.
12	Pisinger D . An expanding-core algorithm for the exact 0-1 knapsack problem[J]. European Journal of Operational Research, 1995, 87 (1): 175- 187. doi: 10.1016/0377-2217(94)00013-3
13	Swarnkar R , Tiwari M K . Modeling machine loading problem of FMSs and its solution methodology using a hybrid tabu search and simulated annealing-based heuristic approach[J]. Robotics & Computer Integrated Manufacturing, 2004, 20 (3): 199- 209.
14	Küçükoğlu İ , Öztürk N . An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows[J]. Computers & Industrial Engineering, 2015, 86, 60- 68.
15	Cornuejols G , 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. doi: 10.1016/0377-2217(91)90261-S

算例	$ \|I\|\times\|J\|\times\|K\| $	$ G_{\rm Lag} $		$ G_H $		$ G_{HC} $	$ T_{\rm Lag} $	$ T_H $	$ T_{{\rm Lag}H} $	$ T_C $
算例	$ \|I\|\times\|J\|\times\|K\| $	Avg	Max	Avg	Max	Avg	Avg	Avg	Avg	Avg
1	5$ \times $10$ \times $40	2.00	2.42	1.75	2.35	0.58	9.6	7.4	17.0	1 980.8
2	10$ \times $20$ \times $80	1.74	2.34	1.38	1.92	0.40	23.6	17.1	40.7	12 312.4
3	15$ \times $30$ \times $120	1.62	2.06	1.29	1.84	0.70	43.8	28.1	71.9	6 998.2
4	20$ \times $40$ \times $160	1.37	1.72	1.00	1.40	0.40	75.4	44.4	119.8	5 052.7
5	25$ \times $50$ \times $200	1.17	1.46	0.85	1.32	0.31	143.8	52.2	196.0	5 429.6
6	30$ \times $60$ \times $240	0.99	1.17	0.62	0.84	0.16	217.2	61.6	278.8	7 819.4
7	35$ \times $70$ \times $280	0.88	1.01	0.64	0.88	0.23	355.2	82.2	437.4	8 141.6
8	40$ \times $80$ \times $320	0.81	0.98	0.57	0.71	$ -0.24 $	514.6	109.2	623.8	6 017.8
9	45$ \times $90$ \times $360	0.78	0.87	0.52	0.62	$ -0.31 $	675.9	229.4	905.3	7 000.9
10	50$ \times $100$ \times $400	0.74	0.84	0.51	0.62	$ -0.45 $	982.1	332.7	1 314.8	5 651.6
Average		1.21		0.91		0.18

算例	$ \|I\|\times\|J\|\times\|K\| $	$ R_{cpd} $	$ G_{\rm Lag} $		$ G_H $		$ T_{\rm Lag} $	$ T_H $	$ T_{{\rm Lag}H} $
算例	$ \|I\|\times\|J\|\times\|K\| $	$ R_{cpd} $	Avg	Max	Avg	Max	Avg	Avg	Avg
1	35$ \times $70$ \times $280	1.5	0.88	1.11	0.62	0.80	281.4	86.3	367.7
2	35$ \times $70$ \times $280	2.0	0.97	1.09	0.66	0.84	325.2	87.7	412.9
3	35$ \times $70$ \times $280	2.5	1.00	1.13	0.68	0.83	387.7	78.3	466.0
4	35$ \times $70$ \times $280	3.0	1.17	1.60	0.86	1.11	503.5	82.0	585.5
5	50$ \times $100$ \times $400	1.5	0.62	0.75	0.37	0.48	805.3	155.8	961.1
6	50$ \times $100$ \times $400	2.0	0.72	0.87	0.51	0.68	880.2	148.6	1 028.8
7	50$ \times $100$ \times $400	2.5	0.82	1.12	0.54	0.79	1 124.7	148.9	1 273.5
8	50$ \times $100$ \times $400	3.0	0.95	1.12	0.64	0.76	1 441.1	146.5	1 587.6
Average			0.89		0.61

算例	$ \|I\|\times\|J\|\times\|K\| $	$ R_{cdd} $	$ G_{\rm Lag} $		$ G_H $		$ T_{\rm Lag} $	$ T_H $	$ T_{{\rm Lag}H} $
算例	$ \|I\|\times\|J\|\times\|K\| $	$ R_{cdd} $	Avg	Max	Avg	Max	Avg	Avg	Avg
1	35$ \times $70$ \times $280	1.5	0.89	1.10	0.60	0.83	342.4	122.2	464.6
2	35$ \times $70$ \times $280	2.0	0.94	1.03	0.68	0.76	348.6	80.6	429.2
3	35$ \times $70$ \times $280	2.5	1.02	1.26	0.66	0.76	323.2	73.1	396.3
4	35$ \times $70$ \times $280	3.0	0.98	1.18	0.67	0.79	330.2	67.3	397.5
5	50$ \times $100$ \times $400	1.5	0.76	0.94	0.48	0.67	975.0	182.2	1 157.2
6	50$ \times $100$ \times $400	2.0	0.83	1.01	0.54	0.59	907.9	125.1	1 033.0
7	50$ \times $100$ \times $400	2.5	0.77	1.01	0.54	0.80	947.4	97.3	1 044.7
8	50$ \times $100$ \times $400	3.0	0.81	0.91	0.55	0.70	777.4	105.2	882.6
Average			0.88		0.59

算例	$ \|I\|\times\|J\|\times\|K\| $	$ \|SP_i\| $	$ G_{\rm Lag} $		$ G_H $		$ T_{\rm Lag} $	$ T_H $	$ T_{{\rm Lag}H} $
算例	$ \|I\|\times\|J\|\times\|K\| $	$ \|SP_i\| $	Avg	Max	Avg	Max	Avg	Avg	Avg
1	35$ \times $70$ \times $280	2	0.93	1.20	0.66	0.80	273.8	82.2	356.0
2	35$ \times $70$ \times $280	3	0.89	1.03	0.58	0.71	349.7	87.1	436.8
3	35$ \times $70$ \times $280	4	0.91	1.13	0.59	0.72	382.8	75.8	458.6
4	35$ \times $70$ \times $280	5	0.88	1.11	0.60	0.83	437.8	87.9	525.7
5	35$ \times $70$ \times $280	6	0.93	1.10	0.69	0.90	498.2	77.0	575.2
6	50$ \times $100$ \times $400	2	0.78	0.84	0.55	0.65	832.1	150.8	982.9
7	50$ \times $100$ \times $400	3	0.75	0.85	0.49	0.55	898.7	173.4	1 072.1
8	50$ \times $100$ \times $400	4	0.78	0.88	0.49	0.53	1 030.2	164.7	1 194.9
9	50$ \times $100$ \times $400	5	0.74	0.85	0.52	0.62	1 191.0	186.0	1 377.0
10	50$ \times $100$ \times $400	6	0.75	0.89	0.49	0.61	1 296.4	177.7	1 474.1
Average			0.83		0.57

算例	$ \|I\|\times\|J\|\times\|K\| $	$ \|SD_j\| $	$ G_{\rm Lag} $		$ G_H $		$ T_{\rm Lag} $	$ T_H $	$ T_{{\rm Lag}H} $
算例	$ \|I\|\times\|J\|\times\|K\| $	$ \|SD_j\| $	Avg	Max	Avg	Max	Avg	Avg	Avg
1	35$ \times $70$ \times $280	2	0.89	1.05	0.58	0.83	248.6	74.1	322.7
2	35$ \times $70$ \times $280	3	0.94	1.10	0.65	0.70	345.5	93.6	439.1
3	35$ \times $70$ \times $280	4	0.88	1.03	0.59	0.87	421.2	71.9	493.1
4	35$ \times $70$ \times $280	5	0.83	1.19	0.63	0.83	509.1	77.2	586.3
5	35$ \times $70$ \times $280	6	0.86	1.04	0.61	0.79	631.6	77.3	708.9
6	50$ \times $100$ \times $400	2	0.76	0.96	0.49	0.54	712.6	138.0	850.6
7	50$ \times $100$ \times $400	3	0.73	0.91	0.50	0.57	872.8	123.7	996.5
8	50$ \times $100$ \times $400	4	0.72	0.79	0.49	0.54	1 143.0	152.2	1 295.2
9	50$ \times $100$ \times $400	5	0.80	0.93	0.57	0.67	1 222.1	115.7	1 337.8
10	50$ \times $100$ \times $400	6	0.76	0.87	0.50	0.66	1 509.0	165.9	1 674.9
Average			0.82		0.56