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

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

CLC Number:

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.

Figures/Tables 5

References 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

A two-echelon facility location problem with choice of facility size

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 15

Related Articles 6

Recommended Articles

Metrics

Comments

[1]	GU Cunchang, ZHANG Yuzhong. The sum of squares of the machine completion times minimization scheduling problem on two identical parallel machines [J]. Operations Research Transactions, 2015, 19(1): 99-107.
[2]	GU Cunchang, ZHANG Yuzhong. The coordination of transportation and serial batching scheduling [J]. Operations Research Transactions, 2014, 18(4): 111-118.
[3]	DAI Yuhong, LIU Xinwei. Advances in linear and nonlinear programming [J]. Operations Research Transactions, 2014, 18(1): 69-92.
[4]	YANG Muming, HUANG Yakui, DAI Yuhong. Linear relaxation solution based heuristics for a class of multi-product facility location problems [J]. Operations Research Transactions, 2019, 23(3): 15-26.
[5]	ZHONG Weiya, SHI Yimei. Robust optimization of rehearsal scheduling under uncertain duration [J]. Operations Research Transactions, 2020, 24(3): 77-86.
[6]	CAO Li, MA Zhanxin, MA Shengyun. The synthesis technology and efficiency analysis of multi-level complex index system [J]. Operations Research Transactions, 2020, 24(4): 39-50.