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

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

摘要/Abstract

摘要：

生产与物流的集成调度对供应链集成化发展至关重要。然而，现有研究主要集中于生产计划与国内物流的集成调度，而对生产计划与海运方案集成调度的研究相对较少。本文结合海外订单的两个关键特征：广泛应用的分批运输策略和普遍存在的客户期望离岸日期的弹性，提出了带分批运输限制的生产计划与海运方案集成调度问题。本文以最小化总成本和总交付时间偏差为双目标，构建了集成调度混合整数规划模型。为高效求解该模型，本文提出了一种结合全局NSGA-II搜索和局部贪婪搜索的模因算法。在该算法中，设计了定制化的组合规则引导初始种群生成算子和自适应选择算子。本文通过对小规模和大规模问题实例的算法对比实验，验证了所提算法在提升解的质量和多样性方面具有显著优势。算法消融实验进一步分析了各算子的贡献程度。与传统的生产计划与海运方案两阶段独立优化模型相比，所提的集成调度模型能够同时有效降低总成本和总交付时间偏差。最后，结合具体制造商案例，本文给出了相应的管理启示。

关键词: 生产计划, 海运方案, 分批运输, 集成调度, 模因算法

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

中图分类号:

F273

陈盈盈,罗贺,肖向才, 等. 带分批运输限制的生产计划与海运方案集成调度问题研究[J]. 中国管理科学, 2026, 34(6): 202-214.

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.

图/表 20

图1

表1

符号定义"

符号	定义
集合
$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$ 完工时间

表1

图2

图3

图4

图5

表2

模型参数及其分布特征"

参数	分布特征
$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

表2

图6

图7

图8

表3

图9

图10

图11

表4

表5

ISM与TIOM的RPC对比"

$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

表5

图12

图13

图14

图15

参考文献 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