突发传染病环境下生鲜配送的选址-路径问题

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

摘要/Abstract

摘要：

为有效解决突发传染病背景下生鲜商品的“无接触”配送问题，在综合考虑传染病影响、商品易腐性、温控特性、站点选址和车辆-无人机协同配送路径规划的情况下，提出了基于传染病背景下生鲜配送的选址-路径问优化问题。首先，构建由车辆-无人机配送的运输成本、配送站点运营固定成本、冷藏车辆温控成本组成的总成本最小以及配送过程中生鲜商品价值损失最小的双目标优化模型。然后，根据问题特征提出一种两阶段混合启发式算法进行求解。改进的K-means三维聚类算法执行聚类方案内和不同聚类方案间的迭代优化，解决了配送站点选址问题；ENSGA-II混合算法通过扫描算子生成初始解、基于NSGA-II主循环框架嵌入灵活的存储结构和相应的禁忌搜索准则，求解了车辆-无人机路径规划问题。最后，基于算例分析和灵敏度分析探讨了生鲜配送选址-路径优化方案，生鲜商品配送的温控设置和无人机载重量选择。并通过与 $ε$ 约束法、MOPSO算法和NSGA-II算法的比较分析，进一步验证了模型和两阶段混合启发式算法的有效性和可行性。

关键词: 生鲜商品, 温度控制, 两阶段混合启发式算法, 配送站点选址, 车辆-无人机路径

Abstract:

In order to effectively solve the “contactless” distribution problem of fresh product under the background of sudden infectious diseases， taking into account the impact of the infectious diseases， commodity perishability， temperature control characteristic， site location and coordinated delivery routing planning of vehicle-drone， the location-routing problem of fresh product distribution based on infectious disease background is proposed. A bi-objective optimization model is constructed to minimize the total cost of logistics operation and the value loss of fresh product. Then， an efficient two-phase hybrid heuristic algorithm based on the improved K-means clustering and the extended Non-dominated Sorting Genetic Algorithm-II （ENSGA-II） is devised according to the problem characteristics. The improved K-means three-dimensional clustering algorithm solves the location problem of the distribution site by performing iterative optimization within the clustering scheme and among different clustering schemes； The ENSGA-II hybrid algorithm generates the initial solution through the scanning operator， controls the search for the Pareto optimal frontier based on the NSGA-II main loop framework， and embeds flexible storage structure and corresponding tabu search criteria to solve the problem of vehicle-drone routing problem. Finally， based on the case analysis， the location strategy of distribution site and the coordinated delivery route of vehicle-drone are obtained. According to the sensitivity analysis， the optimal temperature control setting and drone load capacity selection for fresh product distribution are obtained. And through a comparative analysis with $ε -$ constraint method， MOPSO algorithm and NSGA-II algorithm， the validity and feasibility of the bi-objective optimization model and the two-stage hybrid heuristic algorithm are verified. The research results show that an optimal vehicle-drone distribution plan can effectively reduce the objective values and realize the “contactless” delivery for ensuring the safety of vehicles and personnel in non-epidemic areas. A new theoretical basis and method reference is provided for the decision-making for the location-routing problem of fresh product distribution.

Key words: fresh products, temperature control, two-stage hybrid heuristic algorithm, location of distribution site, vehicle-drone routing

中图分类号:

F505

张杰, 李妍峰. 突发传染病环境下生鲜配送的选址-路径问题[J]. 中国管理科学, 2025, 33(3): 196-208.

Jie Zhang, Yanfeng Li. Location-routing Problem of Fresh Product Distribution in Epidemic Environment[J]. Chinese Journal of Management Science, 2025, 33(3): 196-208.

图/表 15

图1

表1

参考文献 29

1	Govindan K， Jafarian A， Khodaverdi R， et al. Two-echelon multiple-vehicle location-routing problem with time windows for optimization of sustainable supply chain network of perishable food［J］. International Journal of Production Economics， 2014， 152： 9-28.
2	Wang S， Tao F， Shi Y. Optimization of location-routing problem for cold chain logistics considering carbon footprint［J］. International Journal of Environmental Research and Public Health， 2018， 15（1）： 86.
3	Macedo R， Alves C， Hanafi S， et al. Skewed general variable neighborhood search for the location routing scheduling problem［J］. Computers & Operations Research， 2015， 61： 143-152.
4	马艳芳，应斌，周晓阳，等. 基于冲突合作关系的生鲜选址-路径多主体优化模型与算法［J］. 系统工程理论与实践， 2020， 40（12）： 3194-3209.
	Ma Y F， Ying B， Zhou X Y， et al. Multi-agent optimization model and algorithm for perishable food location-routing problem with conflict and coordination［J］. Systems Engineering-Theory & Practice， 2020， 40（12）： 3194-3209.
5	王成林，郑颖，皇甫宜龙，等. 生鲜类物流配送网络选址-路径优化问题研究［J］. 数学的实践与认识， 2020， 50（10）： 33-43.
	Wang C L， Zheng Y， Huangfu Y L， et al. Study on optimization problem for location-routing of fresh logistics distribution network［J］. Mathematics in Practice and Theory， 2020， 50（10）： 33-43.
6	Devapriya P， Ferrell W， Geismar N. Integrated production and distribution scheduling with a perishable product［J］. European Journal of Operational Research， 2017， 259（3）： 906-916.
7	方文婷，艾时钟，王晴，等. 基于混合蚁群算法的冷链物流配送路径优化研究［J］. 中国管理科学， 2019， 27（11）：107-115.
	Fang W T， Ai S Z， Wang Q， et al. Research on cold chain logistics distribution path optimization based on hybrid ant colony algorithm［J］. Chinese Journal of Management Science， 2019， 27（11）：107-115.
8	Murray C C， Chu A G. The flying sidekick traveling salesman problem： Optimization of drone-assisted parcel delivery［J］. Transportation Research Part C： Emerging Technologies， 2015， 54： 86-109.
9	Carlsson J G， Song S. Coordinated logistics with a truck and a drone［J］. Management Science， 2018， 64（9）： 4052-4069.
10	Chang Y S， Lee H J. Optimal delivery routing with wider drone-delivery areas along a shorter truck-route［J］. Expert Systems with Applications， 2018， 104： 307-317.
11	Boysen N， Briskorn D， Fedtke S， et al. Drone delivery from trucks： Drone scheduling for given truck routes［J］. Networks， 2018， 72（4）： 506-527.
12	Karak A， Abdelghany K. The hybrid vehicle-drone routing problem for pick-up and delivery services［J］. Transportation Research Part C： Emerging Technologies， 2019， 102： 427-449.
13	Ham A M. Integrated scheduling of m-truck， m-drone， and m-depot constrained by time-window， drop-pickup， and m-visit using constraint programming［J］. Transportation Research Part C： Emerging Technologies， 2018， 91： 1-14.
14	Moshref-Javadi M， Lee S， Winkenbach M. Design and evaluation of a multi-trip delivery model with truck and drones［J］. Transportation Research Part E： Logistics and Transportation Review， 2020， 136： 101887.
15	Ho G T S， Ip W H， Lee C K M， et al. Customer grouping for better resources allocation using GA based clustering technique［J］. Expert Systems with Applications， 2012， 39（2）： 1979-1987.
16	Wang Z. Delivering meals for multiple suppliers： Exclusive or sharing logistics service［J］. Transportation Research Part E： Logistics and Transportation Review， 2018， 118： 496-512.
17	Dukkanci O， Kara B Y， Bektas T. The green location-routing problem［J］. Computers & Operations Research， 2019， 105： 187-202.
18	Wang H J， Du L J， Ma S H. Multi-objective open location-routing model with split delivery for optimized relief distribution in post-earthquake［J］. Transportation Research Part E： Logistics and Transportation Review， 2014， 69： 160-179.
19	Beausoleil R P. “MOSS” multiobjective scatter search applied to non-linear multiple criteria optimization［J］. European Journal of Operational Research， 2006， 169（2）： 426-449.
20	Martínez-Salazar I A， Molina J， Ángel-Bello F， et al. Solving a bi-objective transportation location routing problem by metaheuristic algorithms［J］. European Journal of Operational Research， 2014， 234（1）： 25-36.
21	Mamaghani E J， Davari S. The bi-objective periodic closed loop network design problem［J］. Expert Systems with Applications， 2020， 144： 113068.
22	Leng L L， Zhang J L， Zhang C M， et al. Decomposition-based hyperheuristic approaches for the bi-objective cold chain considering environmental effects［J］. Computers and Operations Research， 2020， 123： 105043.
23	Feng M， Fry M J， Ohlmann J W. Model-based capacitated clustering with posterior regularization［J］. European Journal of Operational Research， 2018， 271（2）： 594-605.
24	Wang Y， Zhang J， Guan X Y， et al. Collaborative multiple centers fresh logistics distribution network optimization with resource sharing and temperature control constraints［J］. Expert Systems with Applications， 2021， 165： 113838.
25	Deb K， Pratap A， Agarwal S， et al. A fast and elitist multi-objective genetic algorithm： NSGA-II［J］. IEEE Transactions on Evolutionary Computation， 2002（6）： 182-197.
26	王晶，刘昊天，赵然. 基于食品安全的生鲜食品冷链运营优化研究［J］. 系统工程理论与实践， 2018， 38（1）： 122-134.
	Wang J， Liu H T， Zhao R. The optimization of cold chain operation based on fresh food safety［J］. Systems Engineering-Theory & Practice， 2018， 38（1）： 122-134.
27	Solomon M. Algorithms for the vehicle routing and scheduling problems with time window constraints［J］. Operations Research， 1987， 35（2）： 254-265.
28	Farrokhi‑Asl H， Makui A， Jabbarzadeh A， et al. Solving a multi-objective sustainable waste collection problem considering a new collection network［J］. Operational Research， 2020， 20： 1977-2015.
29	Coello C A C， Pulido G T， Lechuga M S. Handling multiple objectives with particle swarm optimization［J］. IEEE Transactions on Evolutionary Computation， 2004， 8（3）： 256-279.

符号	说明	符号	说明
$K$	车辆集合, $k ∈ K$	$q s$	居民s 的易腐品需求, $∀ s ∈ S$
$D$	无人机集合, $d ∈ D$	$c g$	单位生鲜商品的价格
$N 0$	车辆出发或到达的点集合, $N 0 = N ⋃ 0$	$ϑ$	没有温控调节下生鲜商品单位时间内的价值损耗
$W$	温控集合, $w ∈ W$	$α w$	生鲜商品在温控为w时的新鲜度衰减系数
$C 0$	无人机出发或到达的点集合, $C 0 = N 0 ⋃ S 2$	$(x ˜ i, y ˜ i)$	网络中节点i的地理坐标, $∀ i ∈ V$
$λ$	在同一时段内配送站点的最大取货人数	$[e i, l i]$	网络中节点i的服务时间窗, $∀ i ∈ N ⋃ S 2$
$c k$	车辆k的单位距离运输成本	$c n$	配送站点n的固定成本, $∀ n ∈ N$
$c ¯ d$	无人机d的单位距离飞行成本	$M$	一个足够大的整数
$g w$	单位时间内车辆在温控w时的温控成本	$β n m$	车辆从节点n到m的行驶距离, $∀ n, m ∈ N 0, n ≠ m$
$Q k$	车辆k的最大装载量	$β ¯ i j$	无人机从节点i到j的飞行距离, $∀ i, j ∈ C 0, i ≠ j$
$Q ¯ d$	无人机d的最大装载量	$v k$	车辆的行驶速度, $∀ k ∈ K$
$E n$	备选站点n的服务能力	$v ¯ d$	无人机的飞行速度, $∀ d ∈ D$
$x n m k$	若车辆k从节点n行驶至节点m为1, 否则为0, $∀ n, m ∈ N 0, n ≠ m, k ∈ K$
$o i j d$	若无人机d从节点i飞行至节点j为1, 否则为0, $∀ i, j ∈ C 0, i ≠ j, d ∈ D$
$t n k$	车辆k到达配送站点n的时间, $∀ n ∈ N, k ∈ K$
$t ¯ i d$	无人机d到达隔离居民点i的时间, $∀ i ∈ S 2, d ∈ D$
$C T n k$	车辆k上的无人机降落到达配送地点n的时间, $∀ n ∈ N, k ∈ K$
$r n$	配送站点n关于生鲜商品的配送量, $∀ n ∈ N$
$y n w k$	若配送站点n的生鲜商品被车辆k以温控w进行配送为1, 否则为0, $∀ n ∈ N, w ∈ W$
$y p k$	若车辆k路线中出动架次p为1, 否则为0, $∀ p ∈ P, k ∈ K$
$f n s$	若居民s 被备选站点n服务为1, 否则为0, $∀ s ∈ S, n ∈ N$
$z n$	若第n个备选站点被选择成为一个配送站点为1, 否则为0, $∀ n ∈ N$

配送站点	居民分配方案	配送站点	居民分配方案
EDS1	C9,C15,C16,C28,C54,C56,C59,C72,C79	EDS10	C26,C29,C35,C38,C64
EDS2	C20,C44,C46,C48,C55,C70,C78	EDS11	C2,C22,C25,C31,C45,C67,C74,C76
EDS3	C3,C14,C30,C41,C47,C71,C73	EDS12	C34,C37,C58,C65,C68,C69
EDS4	C4,C17,C18,C66	EDS13	C1,C12,C40,C42,C50,C57,C77
EDS5	C6,C32,C36,C49,C63,C80	DS14	站点未被选中
EDS6	C11,C53,C60,C62	DS15	站点未被选中
EDS7	C5,C8,C10,C19,C21,C24,C43,C61	DS16	站点未被选中
EDS8	C23,C33,C39,C51	DS17	站点未被选中
EDS9	C7,C13,C52,C75	DS18	站点未被选中

运输工具		具体路线信息
车辆1		Depot→EDS10→EDS8→EDS12→EDS5→EDS3→EDS6→EDS9→Depot
车辆2		Depot→EDS1→EDS4→EDS2→EDS13→EDS11→EDS7→Depot
车辆1	无人机1	EDS10→C64→EDS8,EDS8→C51→EDS12,EDS12→C69→EDS6,EDS6→C53→C62→EDS9
	无人机2	EDS12→C65→C58→EDS5,EDS5→C63→EDS3,EDS3→C71→EDS9,EDS6→C75→EDS9
	无人机3	EDS12→C68→EDS5,EDS5→C80→EDS3,EDS3→C73→EDS6,EDS6→C60→EDS9,EDS8→C52→EDS9
车辆2	无人机4	EDS1→C59→C72→EDS2,EDS2→C55→EDS11,EDS11→C67→EDS7,EDS2→C61→EDS7
	无人机5	EDS1→C56→EDS1,EDS1→C79→EDS2,EDS2→C70→C78→EDS13,EDS13→C57→C77→EDS11,EDS11→C76→EDS7
	无人机6	EDS1→C54→EDS4,EDS4→C66→EDS11,EDS11→C74→EDS7

参数	0	1	2	3	4	5	6	7	8
COP	10.92	11.42	11.96	12.55	13.19	13.90	14.68	15.56	16.53
$g w$	2.4	2.3	2.2	2.1	2.0	1.9	1.8	1.7	1.6
$α w$	0.4	0.5	0.6	0.7	0.8	0.9	1	1.1	1.2

算例数据	居民数量	配送站点	ENSGA-II				$ε$ 约束法
算例数据	居民数量	配送站点	SM	MID		RT	SM	MID	RT
1	10	2	0.412	0.804	4.1		0.393	0.786	7.7
2	10	3	0.426	0.815	4.5		0.404	0.793	8.5
3	20	2	0.552	0.963	5.5		0.524	0.927	10.2
4	20	3	0.579	0.971	5.6		0.551	0.945	21.8
5	20	4	0.622	1.134	5.9		0.585	1.006	34.9
6	30	5	0.771	1.349	6.1		0.722	1.244	57.2
7	30	6	0.798	1.415	6.7		0.756	1.339	71.7
8	40	4	0.908	1.612	7.8		0.883	1.431	132.5
9	40	5	0.955	1.631	8.3		0.927	1.522	239.3
10	40	6	0.983	1.669	9.9		0.955	1.617	365.2
平均			0.771	1.343	6.4		0.670	1.161	94.9