送箱集卡失约下多箱区箱位分配及场桥调度优化

doi:10.16183/j.cnki.jsjtu.2022.501

摘要/Abstract

摘要：

船舶进港前,为避免到港船舶无法按班期及时离港,码头需在规定时间内完成集港作业.堆场按送箱集卡预约到港时间制定箱位分配及场桥调度计划,若送箱集卡失约会导致计划失效,进而产生翻箱问题,影响装船效率.针对送箱集卡失约对箱位分配计划、场桥调度计划及集卡等待时间的影响,提出送箱集卡失约下多箱区箱位分配及场桥调度优化问题.考虑集卡预约时段、场桥间安全距离等约束,以集港时间最短为目标,建立混合整数规划模型.设计混合遗传变邻域算法求解模型,在改进遗传算法的基础上增强其局部搜索能力,通过对比不同算法的实验结果可以看出,该算法收敛速度快,求解结果优.结合集卡实际到港时间,衡量失约对不同情景内完工时间和集卡等待时间扰动,提出干扰恢复策略.实验表明,提出的干扰恢复策略能缩短作业完工时间、降低因送箱失约导致的翻箱量,缩短送箱集卡等待时间,提高堆场作业效率.

关键词: 自动化集装箱码头, 集卡失约, 箱位分配, 场桥调度, 启发式算法

Abstract:

Container collection should be completed within the specified time limit to prevent the arriving ships from being unable to leave the port on schedule. The storage yard should formulate a container allocation plan and yard crane scheduling plan based on the scheduled arrival time of container delivery and loading. Otherwise, the plan will become invalid, which will lead to the problem of container turnover and loading inefficiency. Aimed at the impact of the non-engagement of container delivery and truck collection on the container location allocation plan, yard crane scheduling plan, and the waiting time of the truck, an optimization problem of container location allocation and yard crane scheduling in multi-container areas under non-engagement of container delivery and truck collection is proposed. Considering the constraints such as the booking period of the truck and the safe distance between the two yard cranes, a mixed integer programming model is established with the goal of minimizing the time of port concentration. The hybrid genetic variable neighborhood algorithm is used to solve the model. A comparison of the experimental results of different algorithms indicates that the algorithm in this paper has a fast convergence speed and excellent solution results. Based on the actual arrival time of the container truck, a disturbance recovery strategy is proposed to measure the impact of non-engagement on the completion time and container truck waiting time in different scenarios, an interference recovery strategy is proposed. Experiments show that the interference recovery strategy proposed in this paper not only shortens the job completion time and the number of containers overturned due to box delivery breach, but also reduces the waiting time of container delivery trucks.

Key words: automated container terminal, non-engagement of container delivery truck, storage space allocation, yard crane scheduling, heuristic algorithm

中图分类号:

U691

范厚明, 马晓斌, 彭文豪, 岳丽君, 马梦知. 送箱集卡失约下多箱区箱位分配及场桥调度优化[J]. 上海交通大学学报, 2023, 57(10): 1261-1272.

FAN Houming, MA Xiaobin, PENG Wenhao, YUE Lijun, MA Mengzhi. Container Allocation in Multi-Blocks and Optimization of Yard Crane Dispatching in Non-Engagement of Container Delivery Truck[J]. Journal of Shanghai Jiao Tong University, 2023, 57(10): 1261-1272.

图/表 14

图1

图2

图3

图4

图5

图6

表1

表2

CPLEX求解预优化模型与HGAVNS算法对比表

序号	箱区规模	箱量	CPLEX		HGAVNS算法		$f 2 - f 1 f 1$ /%
序号	箱区规模	箱量	f₁/min	计算时间/s	f₂/min	计算时间/s	$f 2 - f 1 f 1$ /%
1	1×40×10×5	16	12.62	3.58	12.62	6.85	0
2	1×40×10×5	21	17.26	9.31	17.26	10.45	0
3	3×40×10×5	16	10.65	45.16	10.65	60.03	0
4	3×40×10×5	21	14.64	149.15	15.14	78.93	3.4
5	3×40×10×5	30	17.64	323.00	18.22	126.22	3.28
6	3×40×10×5	36	26.42	1 452.31	27.36	150.42	3.55
7	3×40×10×5	42	28.64	3 485.68	29.58	164.20	3.28
8	3×40×10×5	52	35.64	8 468.24	36.83	186.72	3.33
9	3×40×10×5	60	—	>10 000	37.09	270.25	—

表2

表3

表4

图7

图8

图9

图10

参考文献 12

[1]	马梦知, 范厚明, 计明军, 等. 集装箱码头送箱集卡预约与场桥调度协同优化[J]. 交通运输系统工程与信息, 2018, 18(3): 202-209.
	MA Mengzhi, FAN Houming, JI Mingjun, et al. Integrated optimization of truck appointment for export containers and crane deployment in a container terminal[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(3): 202-209.
[2]	GHAREHGOZLI A, ZAERPOUR N. Stacking outbound barge containers in an automated deep-sea terminal[J]. European Journal of Operational Research, 2018, 267(3): 977-995. doi: 10.1016/j.ejor.2017.12.040 URL
[3]	YU H, NING J Z, WANG Y, et al. Flexible yard management in container terminals for uncertain retrieving sequence[J]. Ocean & Coastal Management, 2021, 212: 105794.
[4]	GALLE V, BARNHART C, JAILLET P. Yard Crane Scheduling for container storage, retrieval, and relocation[J]. European Journal of Operational Research, 2018, 271(1): 288-316. doi: 10.1016/j.ejor.2018.05.007 URL
[5]	TORKJAZI M, HUYNH N, SHIRI S. Truck appointment systems considering impact to drayage truck tours[J]. Transportation Research Part E: Logistics and Transportation Review, 2018, 116: 208-228. doi: 10.1016/j.tre.2018.06.003 URL
[6]	尹延冬, 靳志宏. 集装箱码头失约集卡出口箱落箱位选择优化[J]. 科学技术与工程, 2021, 21(25): 10956-10966.
	YIN Yandong, JIN Zhihong. Optimization of slot selection of export containers under truck no-showing situation in a container terminal[J]. Science Technology and Engineering, 2021, 21(25): 10956-10966.
[7]	SHA M, ZHANG T, LAN Y, et al. Scheduling optimization of yard cranes with minimal energy consumption at container terminals[J]. Computers & Industrial Engineering, 2017, 113: 704-713. doi: 10.1016/j.cie.2016.03.022 URL
[8]	MALDONADO S, GONZÁLEZ-RAMÍREZ R G, QUIJADA F, et al. Analytics meets port logistics: A decision support system for container stacking operations[J]. Decision Support Systems, 2019, 121: 84-93. doi: 10.1016/j.dss.2019.04.006 URL
[9]	DE MELO DA SILVA M, ERDOĞAN G, BATTARRA M, et al. The block retrieval problem[J]. European Journal of Operational Research, 2018, 265(3): 931-950. doi: 10.1016/j.ejor.2017.08.048 URL
[10]	范厚明, 孔靓, 岳丽君. 考虑出口箱进出场及预翻箱的箱位分配与场桥调度协同优化[J]. 运筹与管理, 2021, 30(6): 26-34. doi: 10.12005/orms.2021.0176
	FAN Houming, KONG Liang, YUE Lijun. Yard crane scheduling and storage space allocation considering container storage, retrieval, and pre-marshalling[J]. Operations Research and Management Science, 2021, 30(6): 26-34. doi: 10.12005/orms.2021.0176
[11]	陈超, 台伟力, 杨逸蓝, 等. 出口箱随机入港下的箱区选择与箱位分配协调调度[J]. 上海交通大学学报, 2014, 48(4): 544-550.
	CHEN Chao, TAI Weili, YANG Yilan, et al. Coordinated scheduling problem for block choice and slot arrangement under outbound container random arrival[J]. Journal of Shanghai Jiao Tong University, 2014, 48(4): 544-550.
[12]	KRESS D, DORNSEIFER J, JAEHN F. An exact solution approach for scheduling cooperative gantry cranes[J]. European Journal of Operational Research, 2019, 273(1): 82-101. doi: 10.1016/j.ejor.2018.07.043

序号	总箱量	先到先服务策略 f₁ /min	本文策略		$\frac{f_{1}-f_{2}}{f_{2}}$/%
序号	总箱量	先到先服务策略 f₁ /min	f₂ /min	计算时间/s	$\frac{f_{1}-f_{2}}{f_{2}}$/%
1	30	26.58	19.60	138.59	26.26
2	60	43.66	37.09	270.25	17.71
3	90	66.14	54.33	488.99	17.86
4	120	84.76	68.84	662.68	18.78
5	150	107.33	88.08	961.50	17.94
6	180	129.00	101.31	1 396.32	21.47
7	210	142.40	121.03	1 834.14	15.01
8	240	162.08	139.64	2 402.24	13.85
9	270	183.48	153.76	3 132.09	16.20
10	300	201.77	170.46	3 587.80	15.52

偏离程度	失约数量	完工时间/min			外集卡等待时间/min			计算时间/s
偏离程度	失约数量	策略1	策略2	本文策略	策略1	策略2	本文策略	计算时间/s
T⁰_n±σ_n	5	156.59	158.88	153.85	13.67	12.99	9.04	336.21
	10	157.20	159.29	157.54	14.42	14.08	9.86	614.74
	20	159.40	160.24	157.71	16.09	14.81	6.53	1 152.57
	30	159.82	158.78	160.97	15.37	15.41	5.24	1 727.04
	40	160.39	162.89	162.45	15.62	16.82	3.66	1 853.59
T⁰_n±2σ_n	5	161.14	159.22	151.80	15.29	12.85	8.22	334.60
	10	164.79	162.96	156.78	15.23	12.58	9.38	635.42
	20	165.62	163.29	159.91	18.40	13.87	8.06	1 140.15
	30	171.53	167.22	163.83	20.60	18.30	5.67	1 692.83
	40	173.85	170.80	163.82	20.60	18.33	3.47	2 243.80
T⁰_n±3σ_n	5	177.21	167.87	159.38	18.96	14.21	11.20	330.19
	10	179.28	172.64	160.48	24.62	18.08	9.78	704.33
	20	181.22	173.25	163.59	25.46	20.43	8.39	1 293.72
	30	182.15	176.47	164.86	26.36	23.15	6.41	1 721.61
	40	187.13	178.63	163.63	28.49	25.16	3.58	2 436.29
T⁰_n±4σ_n	5	186.08	175.85	150.93	22.54	16.57	8.92	348.53
	10	191.05	178.33	166.04	22.64	16.04	11.05	706.58
	20	185.06	173.14	164.33	26.49	20.87	8.93	1 236.50
	30	192.48	179.29	162.61	32.44	25.81	5.65	1 783.83
	40	193.81	182.98	158.98	34.00	30.34	3.74	2 386.66
T⁰_n±5σ_n	5	218.94	205.25	163.78	27.15	17.22	9.87	290.43
	10	220.90	212.09	167.85	30.12	20.45	7.30	710.48
	20	240.24	222.44	160.29	36.14	25.06	5.54	1 185.01
	30	248.41	230.48	170.39	39.14	30.21	4.93	1 895.23
	40	259.18	227.71	172.75	43.09	36.33	4.02	2 277.01