带分批运输限制的生产计划与海运方案集成调度问题研究

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

Abstract

Abstract:

With the advancement of export trade， the integrated production and maritime transportation scheduling for overseas orders confronts substantial challenges. Compared to domestic logistics， maritime transportation is more complex， involving container leasing and vessel selection. In this study， two critical characteristics of overseas orders are considered： the widespread application of batch delivery strategies and loose due dates. Subsequently， the integrated production and maritime transportation scheduling problem with batch delivery limits （IPMS-BDL） is proposed， which is a variant of the classic integrated production and distribution scheduling problem and is NP-hard.In the IPMS-BDL， production scheduling is formulated as a parallel machine scheduling problem， while maritime transportation optimizes both container leasing and vessel selection. A mixed-integer programming model （ISM） is constructed with dual objectives aimed at minimizing total cost and the total deviation in delivery times. To efficiently solve the ISM， a memetic algorithm （NGMA） is developed， which combines global NSGA-II search with local greedy search. NGMA incorporates a rule-guided initial population generation operator and an adaptive selection operator.Through comparative experiments conducted on both small and large-scale problem instances， the NGMA has demonstrated a significant enhancement in the quality and diversity of the Pareto optimal solution set. Additionally， validity comparison experiments reveal that the ISM achieves reductions of 20.87% in average total cost and 50.57% in average delivery time deviation. Notably， the ISM illustrates strong applicability under conditions of larger fluctuations in maritime transportation costs and fewer delivery batches.Ultimately， a case analysis is performed utilizing business data from representative domestic manufacturers， underscoring the considerable advantages of integrated scheduling in terms of cost control and timely delivery. This further elucidates the practical feasibility of integrated scheduling within manufacturing business processes. These research findings not only offer novel perspectives and methodologies for effectively managing overseas orders but also provide essential theoretical support for decision-making in this domain.

Key words: production scheduling, maritime transportation, batch delivery limits, integrated scheduling, memetic algorithm

CLC Number:

F273

Yingying Chen,He Luo,Xiangcai Xiao, et al. Research on Integrated Production and Maritime Transportation Scheduling Problem with Batch Delivery Limits[J]. Chinese Journal of Management Science, 2026, 34(6): 202-214.

Figures/Tables 20

符号	定义
集合
$I$	$I = i \| i = 1,2, …, I$ 表示订单集合
$J$	$J = j \| j = 1,2, …, J$ 为运输批次集合
$K$	$K = k \| k = I + 1, I + 2, …, I + K$ 表示机器集合
$I ’$	$I ’ = I ⋃ K = 1,2, …, I, I + 1, I + 2, …, I + K$ 表示海外订单与虚拟订单（机器）的总集合
$T$	$T = t \| t = t q 1, t q 2, …, t q T$ 表示集装箱可提柜日期集合
$D$	$D = d \| d = d p 1, d p 2, …, d p D$ 表示船舶开航日期集合
参数
$a i j$	如果订单 $i$ 属于运输批次 $j$ ， $a i j$ =1；否则， $a i j$ =0
$c i s t o r$	订单 $i$ 成品的日仓库仓储成本
$p i$	订单 $i$ 下所有工件的总加工时间
$g j$	运输批次 $j$ 所需集装箱数量 $g j ∈ N *$
$c t c o n t$	第 $t$ 天集装箱租赁费用单价
$c d s h i p$	第 $d$ 天船舶单个集装箱的海运费用单价
$c j s t p o$	装载运输批次 $j$ 内所有成品的集装箱在码头的日等待成本
$t i d e p$	订单 $i$ 实际离岸日期
$t i d i s$	订单 $i$ 的交付时间偏差为实际离岸日期与客户期望离岸日期差的绝对值
$[l i l o w, l i h i g h]$	订单 $i$ 客户期望离岸日期弹性区间
$h i i'$	机器装置由生产订单 $i$ 的工件调整为订单 $i'$ 的所需时间
$M 1, M 2$	两个较大的正数
决策变量
$z i i'$	如果订单 $i'$ 的工件紧接着订单 $i$ 被加工， $z i i'$ =1；否则， $z i i'$ =0
$s i$	订单 $i$ 下的工件被加工的开始时间
$u j t$	如果运输批次 $j$ 的集装箱提柜日期为第 $t$ 天， $u j t$ =1；否则， $u j t$ =0
$y j d$	如果运输批次 $j$ 的船舶开航日期为第 $d$ 天， $y j d$ =1；否则， $y j d$ =0
$v i j$	$v i j$ 为辅助决策变量。如果订单 $i$ 在运输批次 $j$ 中最后完工， $v i j = 1$ ；否则， $v i j = 0$
$e j$	$e j$ 为辅助决策变量，运输批次 $j$ 完工时间

参数	分布特征
$a i j$	U(0,1)
$c i s t o r$	U(200,800)
$p i$	U(1.5,6.5)
$g j$	U(3,6)
$c t c o n t$	U(1800,2400)
$c d s h i p$	U(3500,4500)
$c j s t p o$	250
$l i l o w$	U(20,31)-U(0,2)
$l i h i g h$	U(20,31)+U(0,2)
$h i i'$	U(0.1,0.15)
$M 1$	100
$M 2$	100

$I$	$J$	$D i f f (%)$	$R P C f 1 (%)$	$R P C f 2 (%)$
30	3	0	15.39	69.23
		20	15.76	57.14
		40	16.12	60.71
		60	16.45	54.17
30	6	0	12.17	58.33
		20	13.46	27.27
		40	15.78	44.44
		60	16.01	98.63
30	9	0	21.68	31.82
		20	22.45	68.75
		40	24.97	52.17
		60	27.55	57.69
30	12	0	25.44	27.78
		20	26.12	23.53
		40	26.78	57.89
		60	28.53	87.53
30	15	0	27.61	50.75
		20	27.98	33.33
		40	28.32	42.86
		60	29.73	14.29

References 30

[1]	陈金晓，陈剑. 从优化到重塑——大变局中的供应链高质量发展［J］. 系统工程理论与实践， 2022， 42（3）： 545-558.
	Chen J X， Chen J. From optimization to reinvention： High-quality development of supply chains in great changes［J］. Systems Engineering-Theory & Practice， 2022， 42（3）： 545-558.
[2]	何珮洋，李昆鹏，田倩南. 基于3D打印技术的备件生产与运输协同调度问题研究［J］. 中国管理科学， 2023， 31（4）： 239-249.
	He P Y， Li K P， Tian Q N. The integrated production and transportation scheduling problem based on 3D printing technology［J］. Chinese Journal of Management Science， 2023， 31（4）： 239-249.
[3]	Elmi Z， Singh P， Meriga V K， et al. Uncertainties in liner shipping and ship schedule recovery： A state-of-the-art review［J］. Journal of Marine Science and Engineering， 2022， 10（5）： 563.
[4]	Zhang A， Zheng Z， Teo C P. Schedule reliability in liner shipping timetable design： A convex programming approach［J］. Transportation Research Part B： Methodological， 2022， 155： 499-525.
[5]	Ksciuk J， Kuhlemann S， Tierney K， et al. Uncertainty in maritime ship routing and scheduling： A Literature review［J］. European Journal of Operational Research， 2023， 308（2）： 499-524.
[6]	Wang Y， Gu Y， Wang T， et al. A risk-averse approach for joint contract selection and slot allocation in liner container shipping［J］. Transportation Research Part E： Logistics and Transportation Review， 2022， 164： 102781.
[7]	Meng L， Ge H， Wang X， et al. Optimization of ship routing and allocation in a container transport network considering port congestion： A variational inequality model［J］. Ocean & Coastal Management， 2023， 244： 106798.
[8]	Moons S， Ramaekers K， Caris A， et al. Integrating production scheduling and vehicle routing decisions at the operational decision level： A review and discussion［J］. Computers & Industrial Engineering，2017，104： 224-245.
[9]	Chen Z L， Vairaktarakis G L. Integrated scheduling of production and distribution operations［J］. Management Science， 2005， 51（4）： 614-628.
[10]	Qin H， Li T， Teng Y， et al. Integrated production and distribution scheduling in distributed hybrid flow shops［J］. Memetic Computing， 2021， 13（2）： 185-202.
[11]	Zhong W， Chen Z L， Chen M. Integrated production and distribution scheduling with committed delivery dates［J］. Operations Research Letters， 2010， 38（2）： 133-138.
[12]	Yağmur E， Kesen S E. Integrated production scheduling and vehicle routing problem with energy efficient strategies： Mathematical formulation and metaheuristic algorithms［J］. Expert Systems with Applications， 2024， 237： 121586.
[13]	Chagas G O， Coelho L C， Darvish M， et al. Modeling and solving the waste valorization production and distribution scheduling problem［J］. European Journal of Operational Research， 2023， 306（1）： 400-417.
[14]	刘建军，李钦颂，曾创锋，等. 柔性装配流水车间调度与分批配送集成问题研究［J］. 计算机集成制造系统， 2025， 31（11）： 4026-4043.
	Liu J J， Li Q S， Zeng C F， et al. Flexible assembly flowshop scheduling with batch delivery［J］. Computer Integrated Manufacturing Systems， 2025， 31（11）： 4026-4043.
[15]	唐捷凯，胡蓉，钱斌，等. 混合帝国竞争算法求解带多行程批量配送的多工厂集成调度问题［J］. 电子学报， 2022， 50（7）： 1621-1630.
	Tang J K， Hu R， Qian B， et al. Hybrid imperialist competitive algorithm for solving multi-factory integrated scheduling problem with multi-trip batch delivery［J］. Acta Electronica Sinica， 2022， 50（7）： 1621-1630.
[16]	Chen J， Huang G Q， Wang J Q. Synchronized scheduling of production and outbound shipping using bilevel-based simulated annealing algorithm［J］. Computers & Industrial Engineering， 2019， 137： 106050.
[17]	Yang X， Li F， Liu Z， et al. New exact and heuristic algorithms for general production and delivery integration［J］. European Journal of Operational Research， 2024， 316（2）： 419-442.
[18]	Li F， Xu Z， Chen Z L. Production and transportation integration for commit-to-delivery mode with general shipping costs［J］. INFORMS Journal on Computing， 2020， 32（4）： 1012-1029.
[19]	Sun X T， Chung S H， Chan F T S. Integrated scheduling of a multi-product multi-factory manufacturing system with maritime transport limits［J］. Transportation Research Part E： Logistics and Transportation Review， 2015， 79： 110-127.
[20]	Hou Y， Wang H， Fu Y， et al. Multi-Objective brain storm optimization for integrated scheduling of distributed flow shop and distribution with maximal processing quality and minimal total weighted earliness and tardiness［J］. Computers & Industrial Engineering， 2023， 179： 109217.
[21]	Zhang Z， Fu Y， Gao K， et al. A cooperative evolutionary algorithm with simulated annealing for integrated scheduling of distributed flexible job shops and distribution［J］. Swarm and Evolutionary Computation， 2024， 85： 101467.
[22]	Rabet R， Ganji M， Fathi M. A simheuristic approach towards supply chain scheduling： Integrating production， maintenance and distribution［J］. Applied Soft Computing， 2024， 153： 111264.
[23]	Ishibuchi H， Yoshida T， Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling［J］. IEEE Transactions on Evolutionary Computation， 2003， 7（2）： 204-223.
[24]	Xu L， Zhang C， Xiao F， et al. A robust approach to airport gate assignment with a solution-dependent uncertainty budget［J］. Transportation Research Part B： Methodological， 2017， 105： 458-478.
[25]	Deb K， Pratap A， Agarwal S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.
[26]	Zitzler E， Thiele L. Multiobjective evolutionary algorithms： A comparative case study and the strength Pareto approach［J］. IEEE Transactions on Evolutionary Computation， 1999， 3（4）： 257-271.
[27]	Van Veldhuizen D A， Lamont G B. On measuring multiobjective evolutionary algorithm performance［C］//Proceedings of the 2000 Congress on Evolutionary Computation. CEC 00. La Jolla， CA， USA， July 16-19， IEEE， 2002： 204-211.
[28]	Yang Z， Cai X， Fan Z. Epsilon constrained method for constrained multiobjective optimization problems： Some preliminary results［C］//Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation. Vancouver， BC， Canada，July 12 - 16， ACM， 2014： 1181-1186.
[29]	Cheng R， Jin Y， Olhofer M， et al. A reference vector guided evolutionary algorithm for many-objective optimization［J］. IEEE Transactions on Evolutionary Computation， 2016， 20（5）： 773-791.
[30]	Gen M， Cheng R. Genetic algorithms and engineering optimization［M］. New York： John Wiley & Sons， 1999.

规模	HV指标				NSN指标				求解时间
规模	NG MA	NGMA-IP	NGMA-SE	NGMA-PA	NG MA	NGMA-IP	NGMA-SE	NGMA-PA	NG MA	NGMA-IP	NGMA-SE	NGMA-PA
L1	2.82	1.72	2.80	1.94	74.48	36.00	5.84	65.56	20.22	17.88	18.4	15.97
L2	2.30	1.53	2.24	2.08	70.76	14.68	4.80	73.16	23.01	20.10	22.16	18.03
L3	2.02	1.27	2.03	1.61	70.20	15.32	5.64	69.32	25.00	22.52	24.88	20.24
L4	1.11	0.83	1.06	1.03	65.88	9.92	3.68	73.84	27.74	24.78	27.62	22.21
L5	0.79	0.54	0.77	0.7	80.00	11.12	8.36	76.24	30.37	26.93	30.29	24.23
L6	1.65	1.34	1.63	1.59	12.52	4.44	4.76	10.64	43.11	39.78	40.35	35.60
L7	1.62	1.00	1.69	1.50	11.84	4.08	4.88	10.36	46.16	43.63	45.93	39.04
L8	1.57	0.87	1.31	1.51	16.32	3.56	4.40	18.44	50.80	47.33	50.69	42.38
L9	1.08	0.72	1.03	1.03	15.32	3.96	4.80	15.88	54.37	50.93	54.66	45.55
L10	0.57	0.34	0.47	0.56	12.20	3.96	4.28	9.00	58.23	54.65	58.59	48.78
L11	1.09	0.86	0.92	1.08	4.28	2.72	2.88	3.76	74.24	72.87	73.47	65.39
L12	1.31	0.83	1.13	1.18	6.32	3.56	5.08	5.56	80.48	78.08	80.92	69.87
L13	0.95	0.56	0.83	0.91	5.28	2.80	4.16	5.16	85.34	82.97	86.45	74.45
L14	0.65	0.36	0.63	0.66	6.28	3.56	4.84	6.56	90.92	87.97	92.17	78.89
L15	0.45	0.17	0.33	0.42	6.32	3.48	4.08	5.96	96.67	93.16	98.00	83.52

Research on Integrated Production and Maritime Transportation Scheduling Problem with Batch Delivery Limits

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 20

References 30

Related Articles 4

Metrics

Comments

Recommended 0

参数	NGMA	NSGA-II	RVEA	AWGA
种群规模	150	200	200	200
迭代次数	60	100	100	100
交叉概率	0.8	0.2	0.8	0.8
变异概率	0.2	0.2	0.2	0.6

[1]	Tieke Li,Yixuan Su,Wenxin Zhang,Bailin Wang. Interval Multi-objective Optimal Scheduling for Steelmaking-continuous Casting with Processing Time Uncertainty [J]. Chinese Journal of Management Science, 2024, 32(8): 95-106.
[2]	CUI Wei-wei, TAN Xin-lin. Modeling and Approach for the Energy-aware Production Scheduling Problem under TOU Tariff [J]. Chinese Journal of Management Science, 2021, 29(5): 147-156.
[3]	WANG Xu-ping, ZHANG Jun, YI Cai-yu. Integrated Scheduling of Order Picking and Delivery Under B2C E-commerce [J]. Chinese Journal of Management Science, 2016, 24(7): 101-109.
[4]	LI Tie-ke, SU Zhi-xiong. Two-Stage Genetic Algorithm for SM-CC Production Scheduling [J]. Chinese Journal of Management Science, 2009, 17(5): 68-74.