考虑两种服务功能的粮食产后服务中心选址问题及Benders分解算法

doi:10.16381/j.cnki.issn1003-207x.2022.0939

摘要/Abstract

摘要：

粮食安全关系到国计民生，是国家安全的重要基础。粮食产后服务中心建设作为“优质粮食工程”的重要内容，是降低粮食产后环节损失的有效手段，对保障国家粮食安全有重要意义。本文考虑粮食产量的不确定性和粮食产后服务中心的多功能特性，建立了基于二阶段随机规划的粮食产后服务中心选址问题模型，对服务中心的选址、规模、能力分配和粮食物流进行决策。根据模型的特点，采用Benders分解算法进行求解，并用多重割、有效不等式和下界提升策略对算法进行加速。通过随机算例实验，验证了算法的有效性和加速后的算法相比于通用求解器Gurobi的优势。评估随机解的价值，发现考虑粮食产量随机性的随机解相比于确定解可以带来平均0.8%的成本节约。在实例分析中，根据湖北省84个县级区域粮食产量数据，利用提出的模型和算法得到湖北省粮食产后服务中心的最优地理位置分布、建设规模及能力分配方案，验证了模型和算法对于真实问题的有效性和可行性。

关键词: 粮食产后服务中心, 多功能特性, 选址-分配, 两阶段随机规划, Benders分解算法

Abstract:

Food security bears on the national economy and the people's livelihood， and is an important foundation for national security. The construction of thepost-harvest grain service center is a powerful means to reduce post-harvest grain loss， which is of great significance to guarantee national food security.In this paper， the location problem of post-harvest grain service centers is studied. Based on the reality and the emphasis of this study， the following assumptions are made：（a）The post-harvest grain service center has two kinds of service capabilities， i.e.， cleaning&drying and storage；（b）All raw grain should be transported from the producing area to the service centers for “cleaning&drying” first， while the following "storage" service is optional， and the grain that does not receive “storage” service needs to be transported back to its origin；（c）Transportation of grain between service centers is not considered；（d）Grain yields obey some normal distribution. Before grain yieldsare determined， the following decisions should be made：（a） The number， location， and scale of service centers to be built；（b）The allocation of two service capabilities in each service center. After grain yields have been determined， grain logistics decisions between the producing areas and the service centers need to be made.Considering the two-stage decision characteristic and the assumption of the randomness of grain yields， a two-stage stochastic programming model is established to represent this problem. Based on the structural characteristics of the model， the Benders decomposition algorithm（BD） is used to solve it. Moreover， the multi-cut method， two sets of valid inequalities， and a lower bound lifting strategy are applied to accelerate the algorithm.In the test on random instances， the effectiveness of the algorithm acceleration methods and the advantages of the accelerated BD compared with the general solver Gurobi in solution accuracy are first verified. Then， the value of the stochastic solution （VSS） is calculated and it is obtained that the stochastic solutions considering the randomness of grain yields can bring an average cost saving of 0.8% compared with the deterministic solutions. In the real case study， based on the grain yield data of 84 county-level regions in Hubei Province， the optimal geographical distribution， construction scale， and capacity allocation scheme of grain post-production service centers in Hubei Province are obtained using the proposed model and algorithm， which verifies the model and algorithm for real problems.This is the first study on the location problem of post-harvest grain service centers. It enriches the existing literature onthe location-allocation problem by considering the capacity allocation decision in the model. The model is widely applicable to location problems of centers with multiple capabilities.

Key words: post-harvest grain service center, multi-functional characteristic, location-allocation, two-stage stochastic programming, Benders decomposition algorithm

中图分类号:

F224

张子卿, 王林, 王思睿, 张金隆. 考虑两种服务功能的粮食产后服务中心选址问题及Benders分解算法[J]. 中国管理科学, 2025, 33(2): 141-149.

Ziqing Zhang, Lin Wang, Sirui Wang, Jinlong Zhang. The Location of Post-harvest Grain Service Centers Considering Two Service Capabilities and Benders Decomposition Algorithm[J]. Chinese Journal of Management Science, 2025, 33(2): 141-149.

图/表 7

图1

表1

符号说明"

集合	含义描述
$I$	$粮食产地集合, i ∈ I$
$J$	$服务中心候选点集合, j ∈ J$
$L$	$服务中心容量水平集合, l ∈ L$
$S$	$粮食产量的情境集合, s ∈ S$
参数	含义描述
$p (ξ = s)$	$随机变量产量情境 ξ 取 s 的概率$
$O i s$	$s 情境下, i 的粮食产量$
$λ$	$粮食经过清理干燥后剩余的重量比例$
$μ i$	$i 地粮食清理干燥后 “ 代储存 ” 的比例$
$f j l$	$在 j 建立容量水平为 l 的服务中心的固定成本$
$m l$	$l 水平服务中心的最大容量$
$c 1$	$粮食清理干燥设施的单位购置成本$
$c 2$	$粮食储存设施的单位购置成本$
$h 1$	$单位粮食清理干燥设施需占容量$
$h 2$	$单位粮食储存设施需占容量$
$q 1$	$单位粮食清理干燥设施的服务能力$
$q 2$	$单位粮食储存设施的服务能力$
$d i j$	$i 到 j 的距离$
$p c i$	$i 地原粮未得到处理的单位惩罚费用$
$e 1$	$从产地到服务中心的单位运费$
$e 2$	$从服务中心到产地的单位运费$
决策变量	含义描述
$x j l$	$是否在 j 建立能力水平为 l 的服务中心$
$α j$	$j 购置粮食清理干燥设施的数量$
$β j$	$j 购置粮食储存设施的数量$
$r i s$	$在 s 情境下, i 地未进行处理的原粮数量$
$y i j s$	$在 s 情境下, 从 i 运输到 j 的原粮数量$
$z i j s$	$在 s 情境下, 从 j 运回 i 的粮食数量$

表1

参数设置"

参数	设置	参数	设置
$a v g i$	~U(0,40000)	$p c i$	50
$O i$	~N $(a v g i, 0.4 a v g i)$	$h 1$	5000
$L$	3	$h 2$	5000
$m$	(20000,40000,60000)	$q 1$	5000
$f$	(20000,40000,60000)	$q 2$	5000
$λ$	0.5	$e 1$	0.1
$μ i$	~U(0.5,0.7)	$e 2$	0.1
$c 1$	500	$d i j$	~U(1,100)
$c 2$	200	$p (ε = s)$	1/ $S$

表1

表2

图2

表3

图3

参考文献 24

1	Nourbakhsh S M， Bai Y， Maia G D N， et al. Grain supply chain network design and logistics planning for reducing post-harvest loss［J］.Biosystems Engineering， 2016， 151： 105-115.
2	Mogale D G， Kumar M， Kumar S K， et al. Grain silo location-allocation problem with dwell time for optimization of food grain supply chain network［J］.Transportation Research Part E： Logistics and Transportation Review， 2018， 111： 40-69.
3	赵泉午，姚珍珍，林娅. 面向新零售的生鲜连锁企业城市配送网络优化研究［J］. 中国管理科学， 2021，29（9）： 168-179.
	Zhao Q W， Yao Z Z， Lin Y. Research on urban distribution network optimization of fresh chain enterprises under new retail［J］. Chinese Journal of Management Science， 2021， 29（9）： 168-179.
4	赖红兵. 中国粮食产量波动及其结构分析［J］.农业技术经济， 2009（5）： 91-96.
	Lai H B. Analysis of grain yield fluctuation and its structure in China［J］. Journal of Agrotechnical Economics，2009（5）： 91-96.
5	Snyder L V. Facility location under uncertainty： A review［J］. IIE Transactions， 2006， 38（7）： 547-564.
6	Birge J R， Louveaux F. Introduction to stochastic programming［M］. New York： Springer， 2011.
7	葛洪磊，刘南. 复杂灾害情景下应急资源配置的随机规划模［J］.系统工程理论与实践， 2014，34（12）：3034-3042.
	Ge H L， Liu N. A stochastic programming model for relief resources allocation problem based on complex disaster scenarios［J］.Systems Engineering - Theory & Practice， 2014， 34（12）： 3034-3042.
8	Üster H， Memişoğlu G. Biomass logistics network design under price-based supply and yield uncertainty［J］. Transportation Science， 2018， 52（2）： 474-492.
9	Rawls C G， Turnquist M A. Pre-positioning of emergency supplies for disaster response［J］.Transportation Research Part B： Methodological， 2010，44（4）：521-534.
10	于冬梅，高雷阜，赵世杰. 考虑凸形障碍的应急设施选址与资源分配决策研究［J］.系统工程理论与实践， 2019， 39（5）： 1178-1188.
	Yu D M， Gao L F， Zhao S J. Emergency facility location-allocation problem with convex barriers［J］. Systems Engineering - Theory & Practice， 2019， 39（5）： 1178-1188.
11	蒲松，夏嫦.基于二阶段随机规划的城市医疗废弃物回收网络设计［J］.中国管理科学，2021，29（5）： 166-172.
	Pu S， Xia C. A Two-stage stochastic programming approach for urban medical waste recycling network design［J］. Chinese Journal of Management Science， 2021， 29（5）： 166-172.
12	Liu W， Kong N， Wang M， et al. Sustainable multi-commodity capacitated facility location problem with complementarity demand functions［J］. Transportation Research Part E： Logistics and Transportation Review， 2021， 145： 102165.
13	Benders J F. Partitioning procedures for solving mixed-variables programming problems［J］. Numerische Mathematik， 1962， 4（1）： 238-252.
14	Shapiro A. Stochastic programming approach to optimization under uncertainty［J］. Mathematical Programming， 2007， 112（1）： 183-220.
15	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.
16	Ruszczyński A. Decomposition methods in stochastic programming［J］. Mathematical Programming， 1997， 79（1）： 333-353.
17	Bodur M， Dash S， Günlük O， et al. Strengthened Benders cuts for stochastic integer programs with continuous recourse［J］. INFORMS Journal on Computing， 2017， 29（1）： 77-91.
18	Rahmaniani R， Ahmed S， Crainic T G， et al. The Benders dual decomposition method［J］. Operations Research， 2020， 68（3）： 878-895.
19	Birge J R， Louveaux F V. A multicut algorithm for two-stage stochastic linear programs［J］. European Journal of Operational Research，1988，34（3）： 384-392.
20	Rei W， Cordeau J F， Gendreau M， et al. Accelerating benders decomposition by local branching［J］. Informs Journal on Computing，2009， 21（2）： 333-345.
21	Rahmaniani R， Crainic T G， Gendreau M， et al. The Benders decomposition algorithm： A literature review［J］. European Journal of Operational Research， 2017， 259（3）： 801-817.
22	Rahmaniani R， Crainic T G， Gendreau M， et al. Accelerating the benders decomposition method： Application to stochastic network design problems［J］. SIAM Journal on Optimization， 2018， 28（1）： 875-903.
23	Birge J R. The value of the stochastic solution in stochastic linear programs with fixed recourse［J］. Mathematical Programming， 1982， 24（1）： 314-325.
24	《湖北农村统计年鉴》编辑委员会.《湖北农村统计年鉴》［M］.北京：中国统计出版社，2021.
	Editorial Board of Hubei Rural Statistical Yearbook. Hubei rural statistical yearbook［M］.Beijing： China Statistics Press，2021.

算例	BD		BD+I		BD+I+II		GB
算例	时间(s)	gap(%)	时间(s)	gap(%)	时间(s)	gap(%)	时间(s)	gap(%)
(20,20,100)	2000	95.53	1769	0.00	592	0.00	264	0.00
(20,20,200)	2000	95.74	2000	0.05	1485	0.00	2000	0.80
(40,20,100)	2000	91.67	2000	0.47	2000	0.20	2000	0.72
(40,20,200)	2000	93.36	2000	0.44	2000	0.22	2000	1.02
(40,40,100)	2000	97.00	2000	35.60	2000	0.37	2000	1.78
(40,40,200)	2000	97.14	2000	3.63	2000	1.06	2000	5.03
(60,20,100)	2000	95.98	2000	0.56	2000	0.43	2000	0.74
(60,20,200)	2000	95.30	2000	0.74	2000	0.57	2000	3.30
(60,40,100)	2000	97.41	2000	27.65	2000	1.19	2000	4.24
(60,40,200)	2000	96.11	2000	49.74	2000	3.40	2000	10.71
(60,60,100)	2000	97.52	2000	37.22	2000	1.00	2000	6.69
(60,60,200)	2000	97.10	2000	54.85	2000	1.81	2000	8.04
(80,20,100)	2000	93.63	2000	0.47	2000	0.12	2000	0.87
(80,20,200)	2000	96.71	2000	1.18	2000	0.46	2000	3.11
(80,40,100)	2000	96.78	2000	44.37	2000	2.01	2000	7.49
(80,40,200)	2000	96.79	2000	40.61	2000	4.95	2000	13.66
(80,60,100)	2000	97.58	2000	37.26	2000	2.65	2000	8.26
(80,60,200)	2000	96.82	2000	38.38	2000	4.25	2000	8.77
(100,20,100)	2000	94.67	2000	0.63	2000	0.20	2000	0.69
(100,20,200)	2000	95.74	2000	3.66	2000	0.78	2000	5.23
(100,40,100)	2000	96.35	2000	34.28	2000	2.15	2000	7.98
(100,40,200)	2000	96.36	2000	52.69	2000	9.10	2000	10.42
(100,60,100)	2000	97.18	2000	41.01	2000	4.60	2000	10.76
(100,60,200)	2000	97.18	2000	40.95	2000	8.64	2000	14.97

算例	随机解				确定解				VSS	VSS/EEV（%）
算例	EEV	固定成本	物流成本	惩罚成本	RP	固定成本	物流成本	惩罚成本	VSS	VSS/EEV（%）
(20,20,100)	1108521.9	694400.0	385389.0	28732.8	1110266.7	694400.0	387055.7	28811.0	1744.9	0.16
(20,20,200)	1108690.1	694400.0	385967.0	28323.1	1109674.9	694400.0	386560.1	28714.8	984.8	0.09
(40,20,100)	1070497.2	716100.0	314261.4	40135.9	1072493.1	694400.0	312719.9	65373.2	1995.9	0.19
(40,20,200)	1071195.8	716100.0	314668.2	40427.7	1072765.5	694400.0	313129.5	65236.0	1569.6	0.15
(40,40,100)	1697102.8	1367100.0	284911.4	45091.4	1698736.6	1345400.0	285499.5	67837.1	1633.8	0.10
(60,20,100)	1022154.9	672700.0	306602.7	42852.2	1033427.2	651000.0	309013.7	73413.5	11272.3	1.10
(60,20,200)	1028353.0	694400.0	306862.8	27090.2	1032143.9	651000.0	307680.6	73463.2	3790.9	0.37
(60,60,100)	2180487.6	1887900.0	250912.3	41675.3	2189638.6	1866200.0	250278.9	73159.7	9150.9	0.42
(80,20,100)	1135864.3	759500.0	346879.8	29484.6	1160686.5	716100.0	345596.2	98990.3	24822.2	2.19
(80,20,200)	1136070.0	759500.0	346051.5	30518.4	1162292.5	716100.0	346877.5	99314.9	26222.5	2.31
(100,20,100)	1205798.4	802900.0	353579.9	49318.5	1220586.4	759500.0	344952.6	116133.9	14788.0	1.23
(100,20,200)	1207921.2	802900.0	355656.4	49364.8	1223120.9	759500.0	347364.5	116256.3	15199.6	1.26

[1]	张瑶,张煜炜,李珍萍,吴玉文. 随机需求下多种应急医疗物资联合储备与分配问题研究[J]. 中国管理科学, 2024, 32(7): 129-137.
[2]	庄峻,杨东. 面向生鲜电商的前置仓选址及订单履约决策优化研究[J]. 中国管理科学, 2024, 32(2): 188-198.
[3]	乔岩,冉伦,李金林,王志远. 基于两阶段随机规划的远程会诊预约调度问题研究[J]. 中国管理科学, 2024, 32(1): 86-93.
[4]	张玲玲, 王明征. 考虑工作量均衡的护士联合调度决策优化模型及算法研究[J]. 中国管理科学, 2023, 31(3): 177-185.
[5]	赵泉午, 赵军平, 林娅. 基于O2O的大型零售企业城市配送网络优化研究[J]. 中国管理科学, 2017, 25(9): 159-167.
[6]	薛松, 曾博, 王跃锦. 基于Benders分解算法的跨区互联电力系统协调规划模型[J]. 中国管理科学, 2016, 24(5): 119-126.