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

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

Abstract

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

CLC Number:

F505

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.

Figures/Tables 15

符号	说明	符号	说明
$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$

参数	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

References 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.

配送站点	居民分配方案	配送站点	居民分配方案
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

算例数据		ENSGA-II			MOPSO			NSGA-II
算例数据		F₁	F₂	RT	F₁	F₂	RT	F₁	F₂	RT
SET1	C30_4	216	93	5.9	232	99	7.7	254	105	8.1
	C30_6	230	86	6.3	256	94	8.2	269	101	8.6
	C30_8	239	81	6.7	264	89	8.9	287	93	9.2
SET2	C60_4	327	169	8.6	358	175	10.9	376	181	11.7
	C60_6	340	158	9.2	373	167	10.5	398	170	11.4
	C60_8	335	145	10.9	366	153	12.7	382	162	12.1
	C60_10	371	151	10.3	394	172	11.7	415	183	12.8
SET3	C90_6	529	245	11.5	565	264	12.5	596	278	14.9
	C90_8	548	227	12.4	577	249	14.3	605	256	16.5
	C90_10	556	241	13.2	591	255	14.7	613	269	16.8
	C90_13	540	232	14.5	585	243	15.3	622	255	17.6
	C90_16	591	263	15.7	627	298	16.5	650	309	18.3
SET4	C120_6	623	347	20.4	655	365	22.1	688	373	23.4
	C120_8	649	335	21.5	673	359	24.4	697	386	25.5
	C120_10	667	302	23.2	698	344	26.8	726	357	28.1
	C120_13	688	316	24.9	723	356	28.5	755	372	29.7
	C120_16	675	292	26.6	716	315	29.9	743	336	31.6
	C120_20	634	284	29.2	682	304	33.5	701	325	34.4
平均		487	220	15.1	519	239	17.2	543	251	18.4
T检验					-17.3	-7.0	--	-20.7	-8.3	--
P值					1.6E-12	1.1E-06	--	8.8E-14	1.2E-07	--

[1]	ZHU Jiang-hua, ZHANG Xu-mei, DAN Bin, LIU Mo-lin, MA Song-xuan. Government Subsidy Strategies of Fresh Products Considering Capital Constraints under Uncertain Demand [J]. Chinese Journal of Management Science, 2022, 30(8): 231-242.
[2]	WANG Yong, ZHANG Jie, LIU Yong, XU Mao-zeng. Optimization of Fresh Goods Multi-Center Vehicle Routing Problem Based on Resource Sharing and Temperature Control [J]. Chinese Journal of Management Science, 2022, 30(11): 272-285.
[3]	GONG Yuan-yuan, XIAO Yong-bo. Dynamic Inventory Rationing for Cross-Season Sales of Fresh Products [J]. Chinese Journal of Management Science, 2019, 27(7): 83-93.
[4]	XIAO Yong-bo, WU Peng, WANG Ya-lan. Pricing Strategies for Fresh Products with Multiple Quality Levels Based on Customer Choice Behavior [J]. Chinese Journal of Management Science, 2010, 18(1): 58-65.

Location-routing Problem of Fresh Product Distribution in Epidemic Environment

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 29

Related Articles 4

Metrics

Comments

Recommended 0