双循环策略下岸桥与跨运车的联合调度

doi:10.11772/j.issn.1001-9081.2021122042

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP391.9

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

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.

图/表 20

图1 岸桥与跨运车的联合作业流程

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

表1 参数符号说明

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$

表1 参数符号说明

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$

表2 缓存区内时间变量的描述

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$

表2 缓存区内时间变量的描述

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$

图2 算法流程

Fig. 2 Algorithm flowchart

表3 编码表

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

图3 Exchange

Fig. 3 Exchange

图4 2-Opt

Fig. 4 2-Opt

表4 参数

Tab. 4 Parameter

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

表4 参数

Tab. 4 Parameter

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

表5 任务集合

Tab. 5 Task collection

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

图5 基于贪婪算法的响应性禁忌搜索算法收敛图

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

表6 联合作业任务序列

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

表7 岸桥与跨运车调度表

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

表8 算法性能分析表

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	—	—	—	—

图6 完工时间比较

Fig. 6 Completion time comparison

图7 岸桥平均使用率比较

Fig. 7 Comparison of average utilization rate of quay crane

图8 跨运车使用率比较

Fig. 8 Comparison of average utilization rate of straddle carriers

图9 岸桥等待时间

Fig. 9 Waiting time of quay crane

图10 完工时间变化情况

Fig. 10 Change of completion time

图11 岸桥使用率变化情况

Fig. 11 Changes in utilization rate of quay crane

图12 跨运车使用率变化情况

Fig. 12 Changes in utilization rate of straddle carriers

参考文献 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]	马学森, 许雪梅, 蒋功辉, 乔焰, 周天保. 混合自适应粒子群工作流调度优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 474-483.
[2]	郑万波, 陈慧敏, 吴燕清, 夏云霓. 基于应急救援的信息共享策略仿真[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 306-311.
[3]	顾浩杰, 张军. 基于波环粒子的实时水波仿真方法[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3876-3883.
[4]	蔡兴泉, 封丁惟, 王通, 孙辰, 孙海燕. 基于时间注意力机制和EfficientNet的视频暴力行为检测[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3564-3572.
[5]	王杰科, 李琳, 张海龙, 郑利平. 虚拟现实大空间下多虚拟目标被动触觉交互方法[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3544-3550.
[6]	侯守明, 贾超兰, 张明敏. 用于虚拟现实系统的眼动交互技术综述[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3534-3543.
[7]	孙海燕, 陈云博, 封丁惟, 王通, 蔡兴泉. 基于注意力模型和轻量化YOLOv4的林业害虫检测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3580-3587.
[8]	李多芹, 方贤文, 王丽丽, 邵叱风. 基于感知成本的流程模型与事件日志有效对齐[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3154-3161.
[9]	马英杰肖靖赵耿曾萍杨亚涛. 可控网格多涡卷混沌系统族及其硬件电路实现[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	李汉伦, 任建国. P2P网络中基于特征行为检测的恶意代码传播模型[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2125-2131.
[11]	陈海龙, 杨畅, 杜梅, 张颖宇. 基于边界自适应SMOTE和Focal Loss函数改进LightGBM的信用风险预测模型[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2256-2264.
[12]	刘亚平, 张惠珍, 张莉, 刘优优. 带时间窗同时送取货选址路径问题及其烟花算法求解[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2292-2300.
[13]	邓世权, 叶绪国. 基于深度Q网络的多目标任务卸载算法[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1668-1674.
[14]	张斯, 张必山, 马忠军. 传染病在多层星型耦合网络上的资源控制[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1547-1553.
[15]	吴晴晴, 周丽华, 寸轩懿, 杜国王, 姜懿庭. 异质信息网络中基于有向无环图的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 895-903.