Joint operation of quay crane and straddle carrier under dual-cycle strategy

doi:10.11772/j.issn.1001-9081.2021122042

Abstract

Abstract:

The use of straddle carrier in container terminals can reduce the operation links and reduce the types and quantity of terminal mechanical equipment， at the same time， the setting of buffer capacity is very important. Firstly， in order to reduce the overall completion time of the terminal， improve the operation efficiency of the terminal， as well as solve the spatial-temporal coordination problem caused by joint loading and unloading operation of using straddle carrier as horizontal transportation equipment with quay crane， the dual-cycle operation strategy was introduced and joint operation sequence optimization problem of quay crane and straddle carrier was studied. Secondly， a mixed integer programming model was established to minimize the total completion time. In the model， the practical constraints of dual-cycle operation of quay crane and straddle carrier， as well as the constraints of the buffer capacity of quay crane and safety time were considered. Thirdly， aiming at the limitations of traditional Tabu Search （TS） algorithm， an greedy algorithm based reactive TS algorithm was designed by introducing greedy algorithm， multi-neighborhood search method and reactive algorithm， and numerical experiments were conducted. Experimental results verify the effectiveness of the proposed model and algorithm. Finally， through the experimental analysis of the number of buffer capacity and straddle carrier， the ratio of quay crane and straddle carrier， the optimal number of straddle carriers and buffer capacity， as well as the ratio of quay crane and straddle carrier were obtained. The results show that compared with traditional terminal equipment configuration， the dual-cycle operation strategy can reduce the number of straddle carriers and improve the utilization rate of quay crane and straddle carrier.

Key words: container operation, dual-cycle strategy, buffer capacity, joint operation of quay crane and straddle carrier, reactive Tabu Search (TS) algorithm

摘要：

集装箱码头采用跨运车能够减少作业环节和码头机械设备的种类与数量，同时缓存区容量的设置至关重要。首先，为降低码头总完工时间、提高码头作业效率，并解决采用跨运车作为水平运输设备与岸桥进行联合装卸作业时产生的时空协调问题，引入了双循环操作策略，对岸桥与跨运车的联合作业序列优化问题进行研究。其次，建立以总完工时间最小化为目标，考虑岸桥与跨运车双循环操作的实际约束、岸桥缓存区容量限制、安全时间等约束的混合整数规划模型。然后，针对传统禁忌搜索（TS）算法的局限性，加入贪婪算法、多种邻域搜索方式、响应性策略，设计了基于贪婪算法的响应性TS算法，并进行了数值实验。实验结果验证了所提模型与算法的有效性。最后，通过对缓存区容量与跨运车数量、岸桥与跨运车配比的实验分析，得出了最优的跨运车数量和缓存区容量、岸桥与跨运车配比。结果表明：与传统码头设备配置相比，双循环策略可减少跨运车使用数量，提高岸桥与跨运车使用率。

关键词: 集装箱装卸, 双循环策略, 缓存区容量, 岸桥与跨运车联合作业, 响应性禁忌搜索算法

CLC Number:

TP391.9

Yuqing ZHOU, Xiaolong HAN. Joint operation of quay crane and straddle carrier under dual-cycle strategy[J]. Journal of Computer Applications, 2023, 43(2): 645-653.

周玉清, 韩晓龙. 双循环策略下岸桥与跨运车的联合调度[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 645-653.

Figures/Tables 20

Fig. 1 Joint operation flow of quay crane and straddle carrier

Tab. 1 Description of parameter symbols

类别	参数	说明	类别	参数	说明
岸桥参数	$J$	所有进出口任务集合	跨运车参数	$V$	跨运车数量
	$K$	岸桥集合		$t v$	跨运车装载或卸载一个集装箱所需时间
	$V S$	表示虚拟开始任务		$C k i l j$	空载运输时间。跨运车完成岸桥k的i任务后开始进行岸桥l的j任务之间的移动时间， $i ≠ j, k, l ∈ K$
	$V E$	表示虚拟结束任务
	$V C$	表示一个虚拟任务
	$K', K ″$	$K' = K ∪ {V S}, K ″ = K ∪ {V E}$		$t k i v$	跨运车操作岸桥k的i任务所需时间， $k ∈ K$
	$J k +$	岸桥k的所有出口箱任务集合， $k ∈ K$	时间变量	$X k j$	跨运车操作岸桥k的j任务开始时刻， $j ∈ J k, k ∈ K$
	$J k -$	岸桥k的所有进口箱任务集合， $k ∈ K$		$Y k j$	跨运车操作岸桥k的j任务结束时刻， $j ∈ J k, k ∈ K$
	$J k$	岸桥k的所有任务集合， $J k = J k + ⋃ J k -$		$X Q k j$	岸桥k开始操作j任务的时刻， $j ∈ J k, k ∈ K$
	$J k'$	$J k' = J k ∪ {V C}, k ∈ K$		$Y Q k j$	岸桥k结束操作j任务的时刻， $j ∈ J k, k ∈ K$
	$t k i j$	岸桥k处理完任务i之后进行下一个任务j的准备时间 $k ∈ K, i, j ∈ J k$		$W$	总完工时间
	$t q$	岸桥处理一个任务所需时间，包括提箱、携箱运输、放箱三个过程	决策变量	$r k i l j$	同一跨运车完成岸桥k的i任务后进行岸桥l的j任务为1，否则为0； $i ∈ J k, j ∈ J l, k, l ∈ K$
	$t s$	表示岸桥提起或放下一个集装箱所需时间		$q k i j$	岸桥k完成任务i后执行任务j为1，否则为0； $i, j ∈ J k, k ∈ K$
	$t b$	安全时间表示集装箱必须在缓存区停留的最小时间		$R k j$	岸桥人工变量； $j ∈ J k, k ∈ K$
	$t b$	安全时间表示集装箱必须在缓存区停留的最小时间		$b i j i n$	当i比j先进入缓存区为1，否则为0； $i, j ∈ J k, k ∈ K$
	$b k$	岸桥k的缓存区容量， $k ∈ K$		$b i j o u t$	在j进入缓存区之前，i未离开为0，否则为1； $i, j ∈ J k, k ∈ K$

Tab. 1 Description of parameter symbols

类别	参数	说明	类别	参数	说明
岸桥参数	$J$	所有进出口任务集合	跨运车参数	$V$	跨运车数量
	$K$	岸桥集合		$t v$	跨运车装载或卸载一个集装箱所需时间
	$V S$	表示虚拟开始任务		$C k i l j$	空载运输时间。跨运车完成岸桥k的i任务后开始进行岸桥l的j任务之间的移动时间， $i ≠ j, k, l ∈ K$
	$V E$	表示虚拟结束任务
	$V C$	表示一个虚拟任务
	$K', K ″$	$K' = K ∪ {V S}, K ″ = K ∪ {V E}$		$t k i v$	跨运车操作岸桥k的i任务所需时间， $k ∈ K$
	$J k +$	岸桥k的所有出口箱任务集合， $k ∈ K$	时间变量	$X k j$	跨运车操作岸桥k的j任务开始时刻， $j ∈ J k, k ∈ K$
	$J k -$	岸桥k的所有进口箱任务集合， $k ∈ K$		$Y k j$	跨运车操作岸桥k的j任务结束时刻， $j ∈ J k, k ∈ K$
	$J k$	岸桥k的所有任务集合， $J k = J k + ⋃ J k -$		$X Q k j$	岸桥k开始操作j任务的时刻， $j ∈ J k, k ∈ K$
	$J k'$	$J k' = J k ∪ {V C}, k ∈ K$		$Y Q k j$	岸桥k结束操作j任务的时刻， $j ∈ J k, k ∈ K$
	$t k i j$	岸桥k处理完任务i之后进行下一个任务j的准备时间 $k ∈ K, i, j ∈ J k$		$W$	总完工时间
	$t q$	岸桥处理一个任务所需时间，包括提箱、携箱运输、放箱三个过程	决策变量	$r k i l j$	同一跨运车完成岸桥k的i任务后进行岸桥l的j任务为1，否则为0； $i ∈ J k, j ∈ J l, k, l ∈ K$
	$t s$	表示岸桥提起或放下一个集装箱所需时间		$q k i j$	岸桥k完成任务i后执行任务j为1，否则为0； $i, j ∈ J k, k ∈ K$
	$t b$	安全时间表示集装箱必须在缓存区停留的最小时间		$R k j$	岸桥人工变量； $j ∈ J k, k ∈ K$
	$t b$	安全时间表示集装箱必须在缓存区停留的最小时间		$b i j i n$	当i比j先进入缓存区为1，否则为0； $i, j ∈ J k, k ∈ K$
	$b k$	岸桥k的缓存区容量， $k ∈ K$		$b i j o u t$	在j进入缓存区之前，i未离开为0，否则为1； $i, j ∈ J k, k ∈ K$

Tab. 2 Description of time variable in buffer

任务类型	j进入缓存区的时刻	j离开缓存区的时刻
$j ∈ J k +$	$Y k j$	$X Q k j$
$j ∈ J k -$	$Y Q k j$	$X k j$

Tab. 2 Description of time variable in buffer

任务类型	j进入缓存区的时刻	j离开缓存区的时刻
$j ∈ J k +$	$Y k j$	$X Q k j$
$j ∈ J k -$	$Y Q k j$	$X k j$

Fig. 2 Algorithm flowchart

Tab. 3 Coding table

任务	岸桥	SC	编号	任务	岸桥	SC	编号
11	1	3	1	21	4	7	3
12	2	1	2	22	2	2	3
13	3	4	2	23	1	5	2
14	4	6	1	24	3	9	3
15	5	8	1	25	5	10	1

Fig. 3 Exchange

Fig. 4 2-Opt

Tab. 4 Parameter

岸桥参数	值	跨运车参数	值
起升时间 $t s$ /s	30	起升时间 $t v$ /s	20
缓存区容量 $b k$	3	行驶速度/（km·h^-1）	10
缓存区安全时间 $t b$ /s	5

Tab. 4 Parameter

岸桥参数	值	跨运车参数	值
起升时间 $t s$ /s	30	起升时间 $t v$ /s	20
缓存区容量 $b k$	3	行驶速度/（km·h^-1）	10
缓存区安全时间 $t b$ /s	5

Tab. 5 Task collection

类型	任务编号
出口箱	11	13	14	21	23	25	31	35
进口箱	12	15	22	24	32	33	34

Fig. 5 Convergence graph of responsive tabu search algorithm based on greedy algorithm

Tab. 6 Joint operation task sequence

任务	岸桥任务优先级	跨运车任务优先级	跨运车编号	任务	岸桥任务优先级	跨运车任务优先级	跨运车编号
11	5	9	1	24	1	6	2
12	1	12	1	25	5	10	2
13	3	8	4	31	5	11	3
14	2	1	1	32	4	13	2
15	4	5	1	33	2	14	3
21	3	2	2	34	1	15	4
22	4	7	3	35	3	4	4
23	2	3	3

Tab. 7 Scheduling table of quay crane and straddle carrier

岸桥	任务	XQ/s	YQ/s	X/s	Y/s	SC编号
岸桥1	11	1 676	1 756	1 196	1 671	1
	12	0（223）	303	1 670	2 034	1
	13	1 776	1 856	1 158	1 560	4
	14	413	493	0	408	1
	15	323	403	408	872	1
岸桥2	21	504	584	0	458	2
	22	0（219）	299	399	834	3
	23	404	484	0	399	3
	24	319	399	458	936	2
	25	2 265	2 345	1 284	1 597	2
岸桥3	31	1 885	1965	1 424	1 880	3
	32	550	630	1 747	2073	2
	33	450	530	1 880	2 300	3
	34	0（350）	430	1 860	2 345	4
	35	1 985	2 065	0	630	4

Tab. 8 Algorithm performance analysis table

序号	基础数据	CPLEX		基于贪婪算法的响应性禁忌搜索算法		传统禁忌搜索算法		遗传算法
序号	基础数据	目标值/min	求解时间/s	目标值/min	求解时间/s	目标值/min	求解时间/s	目标值/min	求解时间/s
1	4/2/2/2	18	0.07	18	0.4	18	0.5	18	0.5
2	6/2/2/2	33	0.08	33	0.4	33	0.6	33	0.4
3	6/2/3/2	19	0.08	19	0.5	19	0.6	19	0.5
4	6/3/3/2	18	0.07	18	0.4	18	0.6	18	0.6
5	15/3/4/4	39	6 124.00	39	26.0	44	60.0	47	65.0
6	15/3/5/4	—	—	32	28.0	46	65.0	46	63.0
7	30/3/5/4	—	—	79	45.0	89	340.0	91	310.0
8	45/3/5/4	—	—	101	98.0	—	—	—	—

Fig. 6 Completion time comparison

Fig. 7 Comparison of average utilization rate of quay crane

Fig. 8 Comparison of average utilization rate of straddle carriers

Fig. 9 Waiting time of quay crane

Fig. 10 Change of completion time

Fig. 11 Changes in utilization rate of quay crane

Fig. 12 Changes in utilization rate of straddle carriers

References 21

1	吕光，王一奇，吕华忠，等. 升降式集装箱跨运车的开发［J］. 港口装卸， 2012（6）：20-21. 10.3963/j.issn.1000-8969.2012.06.008
	LYU G， WANG Y Q， LYU H Z， et al. Development of lift container straddle carrier［J］. Port Operations， 2012（6）： 20-21. 10.3963/j.issn.1000-8969.2012.06.008
2	GOODCHILD A V， DAGANZO C F. Crane double cycling in container ports： planning methods and evaluation［J］. Transportation Research Part B： Methodological， 2007， 41（8）：875-891. 10.1016/j.trb.2007.02.006
3	ZHANG H P， KIM K H. Maximizing the number of dual-cycle operations of quay cranes in container terminals［J］. Computers and Industrial Engineering， 2009， 56（3）：979-992. 10.1016/j.cie.2008.09.008
4	常祎妹，朱晓宁. 不确定因素下的集装箱码头车船间装卸作业集成调度［J］. 交通运输工程学报， 2017， 17（6）：115-124. 10.3969/j.issn.1671-1637.2017.06.013
	CHANG Y M， ZHU X N. Integrated scheduling of handling operation between train and vessel in container terminal under uncertain factor［J］. Journal of Traffic and Transportation Engineering， 2017， 17（6）： 115-124. 10.3969/j.issn.1671-1637.2017.06.013
5	孙清臣，曲林迟. 双循环操作策略下集装箱码头岸桥与集卡多船作业联合优化模型［J］. 华中师范大学学报（自然科学版）， 2018， 52（4）：538-543. 10.19603/j.cnki.1000-1190.2018.04.017
	SUN Q C， QU L C. Integrated scheduling model of quay crane and internal truck in multi-vessel operation at the container terminal under double-cycle strategy［J］. Journal of Central China Normal University （Natural Sciences）， 2018， 52（4）： 538-543. 10.19603/j.cnki.1000-1190.2018.04.017
6	高熙，孙未未. 集装箱码头岸桥最优调度理论研究和高效算法［J］. 计算机科学， 2021， 48（11A）：22-29. 10.11896/jsjkx.201200167
	GAO X， SUN W W. Theoretical research and efficient algorithm of container terminal quay crane optimal scheduling［J］. Computer Science， 2021， 48（11A）： 22-29. 10.11896/jsjkx.201200167
7	余孟齐，韩晓龙. 集装箱码头岸桥与集卡集成调度问题研究［J］. 广西大学学报（自然科学版）， 2016， 41（3）：745-753. 10.13624/j.cnki.issn.1001-7445.2016.0745
	YU M Q， HAN X L. Integrated scheduling of quay crane and yard truck in container terminals［J］. Journal of Guangxi University （Natural Science Edition）， 2016， 41（3）： 745-753. 10.13624/j.cnki.issn.1001-7445.2016.0745
8	VAHDANI B， MANSOUR F， SOLTANI M， et al. Bi-objective optimization for integrating quay crane and internal truck assignment with challenges of trucks sharing［J］. Knowledge-Based Systems， 2019， 163： 675-692. 10.1016/j.knosys.2018.09.025
9	梁承姬，卢殷云，沈佳杰. 基于滚动窗策略的岸桥集卡联合调度问题研究［J］. 计算机应用研究， 2018， 35（2）：432-437， 478. 10.3969/j.issn.1001-3695.2018.02.024
	LIANG C J， LU Y Y， SHEN J J. Study on problem of quay cranes and container trucks joint scheduling based on rolling window strategy［J］. Application Research of Computers， 2018， 35（2）： 432-437， 478. 10.3969/j.issn.1001-3695.2018.02.024
10	CHEN L， LANGEVIN A， LU Z Q. Integrated scheduling of crane handling and truck transportation in a maritime container terminal［J］. European Journal of Operational Research， 2013， 225（1）：142-152. 10.1016/j.ejor.2012.09.019
11	李坤，唐立新，陈树发. 多集装箱堆场空间分配与车辆调度集成问题的建模与优化［J］. 系统工程理论与实践， 2014， 34（1）：115-121. 10.12011/1000-6788(2014)1-115
	LI K， TANG L X， CHEN S F. Modeling and optimizing for the integrated problem with container storage allocation and truck scheduling［J］. Systems Engineering - Theory and Practice， 2014， 34（1）： 115-121. 10.12011/1000-6788(2014)1-115
12	马孙豫，杨勇生，梁承姬. 基于PSO的自动化集装箱码头双小车岸桥和AGV的协同调度［J］. 计算机应用与软件， 2018， 35（10）：17-22. 10.3969/j.issn.1000-386x.2018.10.004
	MA S Y， YANG Y S， LIANG C J. Collaborative scheduling of double-trolley quay cranes and AGV based on PSO at automated container terminal［J］. Computer Applications and Software， 2018， 35（10）： 17-22. 10.3969/j.issn.1000-386x.2018.10.004
13	张笑菊，曾庆成，陈子根，等. 基于同贝同步装卸的岸桥与集卡联合调度优化模型［J］. 上海交通大学学报， 2019， 53（2）：188-196. 10.16183/j.cnki.jsjtu.2019.02.009
	ZHANG X J， ZENG Q C， CHEN Z G， et al. Optimization model for integrated quay cranes and yard trucks scheduling based on double cycling［J］. Journal of Shanghai Jiaotong University， 2019， 53（2）： 188-196. 10.16183/j.cnki.jsjtu.2019.02.009
14	汤鹏飞，梁承姬，丁一，等. 考虑岸桥缓存区的ALV调度优化问题研究［J］. 广西大学学报（自然科学版）， 2015， 40（6）：1540-1550. 10.13624/j.cnki.issn.1001-7445.2015.1540
	TANG P F， LIANG C J， DING Y， et al. Research on automated lifting vehicles scheduling optimization under considering of buffer space of quay crane［J］. Journal of Guangxi University （Natural Science Edition）， 2015， 40（6）： 1540-1550. 10.13624/j.cnki.issn.1001-7445.2015.1540
15	KRESS D， MEISWINKEL S， PESCH E. Straddle carrier routing at seaport container terminals in the presence of short term quay crane buffer areas［J］. European Journal of Operational Research， 2019， 279（3）：732-750. 10.1016/j.ejor.2019.06.028
16	朱家栋. 集装箱港口岸桥和跨运车同步装船作业优化研究［D］. 杭州：浙江大学， 2019.
	ZHU J D. A study on optimization of synchronous loading operation of quay cranes and straddle carriers in the container terminal［D］. Hangzhou： Zhejiang University， 2019.
17	CHEN Y， CHANG D F. Modelling of dual-cycle strategy with straddle carrier at automated container terminals［J］. International Core Journal of Engineering， 2021， 7（2）：274-280.
18	安东，邱俊霖. 集装箱跨运车在中小型集装箱码头的应用［J］. 水运工程， 2021（8）：54-60. 10.3969/j.issn.1002-4972.2021.08.010
	AN D， QIU J L. Application of container straddle carriers in small and medium container terminals［J］. Port and Waterway Engineering， 2021（8）：54-60. 10.3969/j.issn.1002-4972.2021.08.010
19	PELLEGRINI P， MASCIA F， STÜTZLE T， et al. On the sensitivity of reactive tabu search to its meta-parameters［J］. Soft Computing， 2014， 18（11）：2177-2190. 10.1007/s00500-013-1192-6
20	REGO C， JAMES T， GLOVER F. An ejection chain algorithm for the quadratic assignment problem［J］. Networks， 2010， 56（3）：188-206. 10.1002/net.20360
21	马超超，赵重年，王文强，等. 国内外集装箱跨运车发展情况及趋势分析［J］. 起重运输机械， 2020（1）：40-45. 10.3969/j.issn.1001-0785.2020.01.009
	MA C C， ZHAO C N， WANG W Q， et al. Analysis on the development and trend of domestic and foreign container straddle carrier［J］. Hoisting and Conveying Machinery， 2020（1）： 40-45. 10.3969/j.issn.1001-0785.2020.01.009

[1]	Wenjie YAN, Dongyue DANG. Broad quantum state tomography model based on adaptive feature extraction [J]. Journal of Computer Applications, 2024, 44(12): 3861-3866.
[2]	Yifan WANG, Shaofu LIN, Yunjiang LI. Highway free-flow tolling method based on blockchain and zero-knowledge proof [J]. Journal of Computer Applications, 2024, 44(12): 3741-3750.
[3]	Changjiu HE, Jinghan YANG, Piyu ZHOU, Xinye BIAN, Mingming LYU, Di DONG, Yan FU, Haipeng WANG. Theoretical tandem mass spectrometry prediction method for peptide sequences based on Transformer and gated recurrent unit [J]. Journal of Computer Applications, 2024, 44(12): 3958-3964.
[4]	. Layered solving method for virtual maintenance posture in narrow aircraft space [J]. Journal of Computer Applications, 0, (): 0-0.
[5]	. DTOps: Integrated development and operation method for digital twin systems [J]. Journal of Computer Applications, 0, (): 0-0.
[6]	Zhongyu WANG, Xiaodong QIAN. Optimization of edge connection rules for supply chain network based on improved expectation maximization algorithm [J]. Journal of Computer Applications, 2024, 44(11): 3386-3395.
[7]	Yu WANG, Zhihui GUAN, Yuanpeng LI. Distributed UAV cluster pursuit decision-making based on trajectory prediction and MADDPG [J]. Journal of Computer Applications, 2024, 44(11): 3623-3628.
[8]	Xukang KAN, Gefei SHI, Xuerong YANG. ORB-SLAM2 algorithm based on dynamic feature point filtering and optimization of keyframe selection [J]. Journal of Computer Applications, 2024, 44(10): 3185-3190.
[9]	Tingwei CHEN, Jiacheng ZHANG, Junlu WANG. Random validation blockchain construction for federated learning [J]. Journal of Computer Applications, 2024, 44(9): 2770-2776.
[10]	Mengyuan HUANG, Kan CHANG, Mingyang LING, Xinjie WEI, Tuanfa QIN. Progressive enhancement algorithm for low-light images based on layer guidance [J]. Journal of Computer Applications, 2024, 44(6): 1911-1919.
[11]	FU Wujiu, ZHOU Lin, DENG Jianjie, YOU Yong. Recurrence formula for initial value problems of fractional-order autonomous dynamical systems and application [J]. Journal of Computer Applications, 0, (): 0-0.
[12]	Jun FENG, Jiankang BI, Yiru HUO, Jiakuan LI. PIPNet： lightweight asphalt pavement crack image segmentation network [J]. Journal of Computer Applications, 2024, 44(5): 1520-1526.
[13]	Han SHEN, Zhongsheng WANG, Zhou ZHOU, Changyuan WANG. Improved DV-Hop localization model based on multi-scenario [J]. Journal of Computer Applications, 2024, 44(4): 1219-1227.
[14]	Yuanyuan MA, Leilei XIE, Nan DONG, Na LIU. Opinion propagation model considering user initiative and mobility [J]. Journal of Computer Applications, 2024, 44(2): 619-627.
[15]	. Intelligent Modeling Method for Complex Systems Based on Big Data [J]. Journal of Computer Applications, 0, (): 0-0.