Integrated proactive-reactive approach and a hybrid adaptive large neighborhood search algorithm for berth and quay crane scheduling under uncertain combination

Enjie Wu; Jin Zhu

doi:10.3934/jimo.2022188

Article Contents

2023, Volume 19, Issue 8: 5612-5640. Doi: 10.3934/jimo.2022188

This issue Previous Article Picker routing optimization of storage stacker based on improved multi-objective iterative local search algorithm Next Article Quality investment strategies in a complementary supply chain with an unreliable supplier

Integrated proactive-reactive approach and a hybrid adaptive large neighborhood search algorithm for berth and quay crane scheduling under uncertain combination

Enjie Wu^1, and
Jin Zhu^1, ,

1.
Institute of Logistics Science and Engineering, Shanghai Maritime University, Shanghai 201306, China

^*Corresponding author: Jin Zhu
^*Corresponding author: Jin Zhu

Received: November 2021

Revised: May 2022

Early access: September 2022

Published: August 2023

The first author is supported by Shanghai Pujiang Program (16PJC043).

Abstract / Introduction Full Text(HTML) Figure(6) / Table(7) Related Papers Cited by

Abstract

The integrated berth and quay crane scheduling problem is frequently encountered in port management issue, and the dynamic random data obtained by the container terminals under uncertain combination usually makes it unworkable to execute the scheduling. To promote sustainability and adaptivity of container terminals, this paper focuses on developing an integrated proactive-reactive approach for berth and quay crane scheduling under the fluctuation of vessels' arrival time and breakdown of quay crane. The problem is modelled as a two-stage mixed integer program where the baseline schedule with robustness is established in the first stage, and the recovery schedule is established in the second stage. This study aims to minimize the total management cost deviation and total time deviation of the terminal scheduling, so as to implement minimal changes compared with the baseline schedule. Therefore, the scheduling performance such as robustness, recoverability and adaptability is considered. To solve this model, a hybrid adaptive large neighborhood search (HALNS) algorithm framework combined with variable neighborhood search is developed, and the greedy algorithm is developed to construct the initial feasible solution. The performance evaluation tests of the proposed algorithm are performed on the three scales of benchmark. Computational results indicate the strength of solution methods and effectiveness of the proposed model.

Keywords:

Container terminals,
proactive-reactive approach,
uncertain combination,
berth and quay crane scheduling,
hybrid adaptive large neighborhood search.

Mathematics Subject Classification: Primary: 90B06, 90B50; Secondary: 90C27.

Citation:

Full Text(HTML)

Figure 1. An illustration of the baseline schedule model with robustness

Download: Full-size image PowerPoint slide

Figure 2. An illustration of the recovery schedule model

Download: Full-size image PowerPoint slide

Figure 3. The dynamic process of implementing proactive-reaction approach

Download: Full-size image PowerPoint slide

Figure 4. Overall flowchart of HALNS

Download: Full-size image PowerPoint slide

Figure 5. Convergence tendency of GAP(%) between HALNS and ALNS

Download: Full-size image PowerPoint slide

Figure 6. Comparison of average CPU time and average GAP of three algorithms

Download: Full-size image PowerPoint slide

Table 1. Summary of related literatures

literature	Berth property	Uncertain combination	Strategy	Algorithm
Zhou et al. [43]	Discrete	AT+OT	Proactive	GA
Han et al. [7]	Discrete	AT+OT	Proactive	GA
Rodriguez et al. [24]	Continuous	AT+OT	Proactive	Meta-heuristic
Xiang et al. [36]	Discrete	AT+QC quantity	Proactive	Decomposition algorithm (DA)
Zeng et al. [41]	Continuous	Disruption events	Reactive	Local rescheduling and tabu search
Li et al. [17]	Continuous	AT+OT	Reactive	Heuristic
Xiang et al. [37]	Discrete	Disruption events	Reactive	Rolling horizon heuristic
Iris et al. [12]	Continuous	AT+QC handling rates	Proactive-reactive	Heuristic
Tan et al. [27]	Continuous	AT+OT	Proactive-reactive	GA with heuristic
Our study	Continuous	AT+breakdown of QC	Proactive-reactive	Hybrid ALNS

| Show Table

DownLoad: CSV

Table 2. Parameters for setting instance size.

Instance size	N	L	Q	Planning horizon
Small-size	18	1200	12	3 days
Small-size	20	1200	12	3 days
Medium-size	30	1800	18	4 days
Medium-size	34	1800	18	4 days
Large-size	44	2400	24	5 days
Large-size	50	2400	24	5 days

| Show Table

DownLoad: CSV

Table 3. Vessel's information in the benchmark

Class	Vessel length (m)	Handling volume (TEU)	Number of QCs can be assigned
Feeder	U[70,200]	U[400,600]	[1, 2]
Medium	U[210,300]	U[1000, 1200]	[2, 4]
Jumbo	U[310,400]	U[1800, 2400]	[4, 6]

| Show Table

DownLoad: CSV

Table 4. Comparison results

				HALNS			ALNS			GA
	No	N	Z	OBJ	T(s)	GAP(%)	OBJ	T(s)	GAP(%)	OBJ	T(s)	GAP(%)
Large-size	1	18	134.16	{135.73	622	1.17	136.59	521	1.81	140.63	479	4.82
	2	18	122.36	122.42	567	0.05	122.62	491	0.21	128.50	456	5.02
	3	18	142.18	145.35	590	2.23	145.69	582	2.47	149.69	471	5.28
	4	18	107.07	108.70	489	1.52	109.40	495	2.18	110.05	434	2.78
	5	18	134.43	137.43	582	2.30	138.37	469	2.93	143.75	441	6.93
	6	20	123.47	123.87	590	0.32	124.78	547	1.06	127.00	502	2.86
	7	20	122.83	126.31	637	2.83	125.66	563	2.30	129.59	531	5.50
	8	20	156.30	158.27	529	1.26	156.74	499	0.28	164.08	465	4.98
	9	20	107.10	110.56	598	3.23	109.42	546	2.17	110.27	481	2.96
	10	20	133.44	137.32	616	2.91	137.60	542	3.12	141.01	517	5.67
			avg	582	1.78		526	1.85		478	4.68
Medium-size	1	30	183.24	187.36	1248	2.25	188.98	1133	3.13	195.04	984	6.44
	2	30	194.45	201.74	1147	3.75	203.57	1044	4.69	208.63	970	7.29
	3	30	195.41	199.22	1322	1.95	199.92	1293	2.31	206.27	991	5.56
	4	30	184.96	187.20	1129	1.21	188.16	954	1.73	194.17	838	4.98
	5	30	173.43	178.04	1241	2.66	180.28	1157	3.95	181.84	946	4.85
	6	34	198.97	205.12	1544	3.09	207.98	1427	4.53	212.42	1054	6.76
	7	34	167.02	174.35	1302	4.39	177.26	1003	6.13	181.63	951	8.75
	8	34	213.42	220.72	1353	3.42	223.96	1278	4.94	230.13	836	7.83
	9	34	204.55	212.16	1405	3.72	214.00	1369	4.62	214.51	1152	4.87
	10	34	229.28	239.51	1319	4.46	241.13	1212	5.17	245.95	1098	7.27
			avg	1301	3.09		1187	4.12		982	6.46
Large-size	1	44	289.20	306.84	2249	6.10	312.36	2387	8.01	338.71	1957	17.12
	2	44	237.32	247.43	2368	4.26	251.04	2283	5.78	283.60	2211	19.50
	3	44	238.21	253.24	2144	6.31	256.62	2489	7.73	278.85	2016	17.06
	4	44	261.24	275.76	2524	5.56	280.75	2396	7.47	308.42	1962	18.06
	5	44	338.41	349.00	2485	3.13	359.49	2378	6.23	396.08	2027	17.04
	6	50	353.96	372.54	2621	5.25	383.76	2474	8.42	423.23	2283	19.57
	7	50	263.45	283.50	2752	7.61	287.69	2477	9.20	310.77	2403	17.96
	8	50	343.36	361.25	2519	5.21	371.55	2456	8.21	398.61	2236	16.09
	9	50	370.09	380.64	2910	2.85	390.78	2849	5.59	425.64	2261	15.01
	10	50	246.81	265.37	2783	7.52	268.21	2711	8.67	283.41	2284	14.83
			avg	2536	5.38			2490	7.53		2164	17.22

| Show Table

DownLoad: CSV

Table 5. Performance of the proposed model

Instance size	Costs and efficiency				Robustness	Recoverability
Instance size	Total management cost of terminal	Average operation Time for a vessel	Average time deviation for a vessel	The operating cost of QCs	Average buffer time for a vessel	The Number of rescheduled vessels
20	416.23	8.51	3.21	93.61	8.02	3.25
20	528.74	8.05	2.73	96.19	7.53	2.60
20	445.03	9.10	3.61	88.23	8.25	3.29
20	377.20	8.42	2.88	93.52	7.32	1.83
20	401.56	8.27	3.27	88.23	8.14	3.18
Avg	433.75	8.47	3.14	92.39	7.85	2.83
30	585.32	8.90	3.59	219.02	5.71	5.39
30	615.37	8.39	3.28	200.96	5.98	4.61
30	549.75	9.05	3, 12	201.79	6.22	5.65
30	608.15	8.63	3.03	206.00	5.56	5.87
30	538.17	8.50	3.47	215.08	6.38	5.93
Avg	579.35	8.69	3.30	208.57	5.97	5.49
50	862.37	8.43	3.84	482.95	4.80	9.25
50	878.68	8.61	3.07	458.19	4.58	9.51
50	975.12	8.09	3.92	501.41	4.02	9.98
50	938.42	9.23	3.23	465.80	4.34	8.50
50	802.21	8.91	3.78	450.75	5.11	9.46
Avg	891.36	8.65	3.57	471.82	4.57	9.34

| Show Table

DownLoad: CSV

Table 6. Impact of uncertainty degree $ \Delta B $

Instance size	$ \Delta B $	$ P_a $	Our model				Rescheduling model
Instance size	$ \Delta B $	$ P_a $	$ C I $	ADP of CI	$ T I $	ADP of TI	$ C I $	ADP of CI	$ T I $	ADP of TI
	2	50%	178.32		1.94		181.70		2.61
20	4	30%	216.00	219.33	2.47	2.28	253.14	248.09	3.04	2.96
	6	15%	293.27		2.76		361.51		3.58
	8	5%	427.51		3.11		541.34		4.21
	2	50%	255.30		1.55		263.21		2.82
30	4	30%	281.35	298.73	2.63	2.19	332.75	321.16	3.23	3.15
	6	15%	353.26		3.08		407.10		3.71
	8	5%	473.72		3.23		573.28		4.33
	2	50%	301.24		1.89		357.51		3.17
50	4	30%	392.53	365.60	2.53	2.33	442.38	428.34	3.82	3.61
	6	15%	462.10		2.96		552.73		4.20
	8	5%	558.12		3.72		679.25		4.92

| Show Table

DownLoad: CSV

Table 7. Impact of uncertainty degree $ t_d $

Instance size	$ t_d $	$ P_b $	Our model				Rescheduling model
Instance size	$ t_d $	$ P_b $	$ C I $	ADP of CI	$ T I $	ADP of TI	$ C I $	ADP of CI	$ T I $	ADP of TI
	5	20%	175.31		1.41		211.05		2.36
20	15	60%	248.70	265.79	1.98	1.92	295.26	312.60	4.78	4.82
	25	20%	407.52		2.23		466.17		7.39
	5	20%	213.65		1.58		256.30		2.62
30	15	60%	286.21	305.42	2.02	2.08	347.52	364.49	5.15	5.22
	25	20%	454.84		2.77		523.60		8.02
	5	20%	285.30		1.86		334.73		3.20
50	15	60%	352.63	371.39	2.46	2.44	445.80	451.90	6.14	6.23
	25	20%	513.74		2.97		587.35		9.52

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Ö. Ş. Akpunar and Ş. Akpinar, A hybrid adaptive large neighbourhood search algorithm for the capacitated location routing problem, Expert Systems with Applications, 168 (2021), 114304. doi: 10.1016/j.eswa.2020.114304.
[2]	C. Bierwirth and F. Meisel, A follow-up survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research, 244 (2015), 675-689. doi: 10.1016/j.ejor.2014.12.030.
[3]	J. H. Chen, D.-H. Lee and J. X. Cao, A combinatorial benders' cuts algorithm for the quayside operation problem at container terminals, Transportation Research Part E: Logistics and Transportation Review, 48 (2012), 266-275. doi: 10.1016/j.tre.2011.06.004.
[4]	S. W. Cho, H. J. Park and C. Lee, An integrated method for berth allocation and quay crane assignment to allow for reassignment of vessels to other terminals, Maritime Economics & Logistics, 23 (2021), 123-153. doi: 10.1057/s41278-020-00173-4.
[5]	E. Demir, T. Bektaş and G. Laporte, An adaptive large neighborhood search heuristic for the pollution-routing problem, European Journal of Operational Research, 223 (2012), 346-359. doi: 10.1016/j.ejor.2012.06.044.
[6]	M. Golias, I. Portal, D. Konur, E. Kaisar and G. Kolomvos, Robust berth scheduling at marine container terminals via hierarchical optimization, Computers & Operations Research, 41 (2014), 412-422. doi: 10.1016/j.cor.2013.07.018.
[7]	X.-l. Han, Z.-q. Lu and L.-f. Xi, A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time, European Journal of Operational Research, 207 (2010), 1327-1340.
[8]	J. He, C. Tan, W. Yan, W. Huang, M. Liu and H. Yu, Two-stage stochastic programming model for generating container yard template under uncertainty and traffic congestion, Advanced Engineering Informatics, 43 (2020), 101032. doi: 10.1016/j.aei.2020.101032.
[9]	M. Hendriks, M. Laumanns, E. Lefeber and J. T. Udding, Robust cyclic berth planning of container vessels, OR spectrum, 32 (2010), 501-517. doi: 10.1007/s00291-010-0198-z.
[10]	Q.-M. Hu, Z.-H. Hu and Y. Du, Berth and quay-crane allocation problem considering fuel consumption and emissions from vessels, Computers & Industrial Engineering, 70 (2014), 1-10. doi: 10.1016/j.cie.2014.01.003.
[11]	IMF, Global Trade's Recovery Hits Record High, Managing divergent recoveries, Washington, DC, 2021.
[12]	Ç. Iris and J. S. L. Lam, Recoverable robustness in weekly berth and quay crane planning, Transportation Research Part B: Methodological, 122 (2019), 365-389. doi: 10.1016/j.trb.2019.02.013.
[13]	Ç. Iris, D. Pacino and S. Ropke, Improved formulations and an adaptive large neighborhood search heuristic for the integrated berth allocation and quay crane assignment problem, Transportation Research Part E: Logistics and Transportation Review, 105 (2017), 123-147. doi: 10.1016/j.tre.2017.06.013.
[14]	J. Karafa, M. M. Golias, S. Ivey, G. K. Saharidis and N. Leonardos, The berth allocation problem with stochastic vessel handling times, The International Journal of Advanced Manufacturing Technology, 65 (2013), 473-484. doi: 10.1007/s00170-012-4186-0.
[15]	C.-Y. Lee and D.-P. Song, Ocean container transport in global supply chains: Overview and research opportunities, Transportation Research Part B: Methodological, 95 (2017), 442-474. doi: 10.1016/j.trb.2016.05.001.
[16]	H. Li, C. Zhou, B. K. Lee, L. H. Lee, E. P. Chew and R. S. M. Goh, Capacity planning for mega container terminals with multi-objective and multi-fidelity simulation optimization, Iise Transactions, 49 (2017), 849-862. doi: 10.1080/24725854.2017.1318229.
[17]	M. Z. Li, J. G. Jin and C. X. Lu, Real-time disruption recovery for integrated berth allocation and crane assignment in container terminals, Transportation Research Record, 2479 (2015), 49-59. doi: 10.3141/2479-07.
[18]	C. Liang, Y. Huang and Y. Yang, A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning, Computers & Industrial Engineering, 56 (2009), 1021-1028. doi: 10.1016/j.cie.2008.09.024.
[19]	C. Liu, L. Zheng and C. Zhang, Behavior perception-based disruption models for berth allocation and quay crane assignment problems, Computers & Industrial Engineering, 97 (2016), 258-275. doi: 10.1016/j.cie.2016.04.008.
[20]	R. Masson, F. Lehuédé and O. Péton, An adaptive large neighborhood search for the pickup and delivery problem with transfers, Transportation Science, 47 (2013), 344-355. doi: 10.1287/trsc.1120.0432.
[21]	G. R. Mauri, G. M. Ribeiro, L. A. N. Lorena and G. Laporte, An adaptive large neighborhood search for the discrete and continuous berth allocation problem, Computers & Operations Research, 70 (2016), 140-154. doi: 10.1016/j.cor.2016.01.002.
[22]	G. Mejía and F. Yuraszeck, A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times, European Journal of Operational Research, 285 (2020), 484-496. doi: 10.1016/j.ejor.2020.02.010.
[23]	F. Rodrigues and A. Agra, An exact robust approach for the integrated berth allocation and quay crane scheduling problem under uncertain arrival times, European Journal of Operational Research, 295 (2021), 499-516. doi: 10.1016/j.ejor.2021.03.016.
[24]	M. Rodriguez-Molins, M. A. Salido and F. Barber, Robust scheduling for berth allocation and quay crane assignment problem, Mathematical Problems in Engineering, 2014 (2014), Art. ID 834927, 17 pp. doi: 10.1155/2014/834927.
[25]	X. T. Shang, J. X. Cao and J. Ren, A robust optimization approach to the integrated berth allocation and quay crane assignment problem, Transportation Research Part E: Logistics and Transportation Review, 94 (2016), 44-65. doi: 10.1016/j.tre.2016.06.011.
[26]	J. F. Sze, S. Salhi and N. Wassan, A hybridisation of adaptive variable neighbourhood search and large neighbourhood search: Application to the vehicle routing problem, Expert Systems with Applications, 65 (2016), 383-397. doi: 10.1016/j.eswa.2016.08.060.
[27]	C. Tan and J. He, Integrated proactive and reactive strategies for sustainable berth allocation and quay crane assignment under uncertainty, Annals of Operations Research, (2021), 1-32. doi: 10.1007/s10479-020-03891-3.
[28]	G. Tasoglu and G. Yildiz, Simulated annealing based simulation optimization method for solving integrated berth allocation and quay crane scheduling problems, Simulation Modelling Practice and Theory, 97 (2019), 101948. doi: 10.1016/j.simpat.2019.101948.
[29]	Y. B. Türkoğulları, Z. C. Taşkın, N. Aras and İ. K. Altınel, Optimal berth allocation and time-invariant quay crane assignment in container terminals, European Journal of Operational Research, 235 (2014), 88-101. doi: 10.1016/j.ejor.2013.10.015.
[30]	Y. B. Türkoğulları, Z. C. Taşkın, N. Aras and İ. K. Altınel, Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals, European Journal of Operational Research, 254 (2016), 985-1001. doi: 10.1016/j.ejor.2016.04.022.
[31]	N. Umang, M. Bierlaire and A. L. Erera, Real-time management of berth allocation with stochastic arrival and handling times, Journal of Scheduling, 20 (2017), 67-83. doi: 10.1007/s10951-016-0480-2.
[32]	UNCTAD, Global Trade's Recovery Hits Record High, Global Trade Update, United Nations, New York and Geneva, 2021.
[33]	E. Ursavas and S. X. Zhu, Optimal policies for the berth allocation problem under stochastic nature, European Journal of Operational Research, 255 (2016), 380-387. doi: 10.1016/j.ejor.2016.04.029.
[34]	K. Wang, L. Zhen, S. Wang and G. Laporte, Column generation for the integrated berth allocation, quay crane assignment, and yard assignment problem, Transportation Science, 52 (2018), 812-834. doi: 10.1287/trsc.2018.0822.
[35]	Z. Wang and C. Guo, Minimizing the risk of seaport operations efficiency reduction affected by vessel arrival delay, Industrial Management & Data Systems, 118 (2018), 1498-1509. doi: 10.1108/IMDS-12-2017-0563.
[36]	X. Xiang and C. Liu, An almost robust optimization model for integrated berth allocation and quay crane assignment problem, Omega, 104 (2021), 102455. doi: 10.1016/j.omega.2021.102455.
[37]	X. Xiang, C. Liu and L. Miao, Reactive strategy for discrete berth allocation and quay crane assignment problems under uncertainty, Computers & Industrial Engineering, 126 (2018), 196-216. doi: 10.1016/j.cie.2018.09.033.
[38]	X. Xiang, C. Liu and L. Miao, A bi-objective robust model for berth allocation scheduling under uncertainty, Transportation Research Part E: Logistics and Transportation Review, 106 (2017), 294-319. doi: 10.1016/j.tre.2017.07.006.
[39]	Y. Xu, Q. Chen and X. Quan, Robust berth scheduling with uncertain vessel delay and handling time, Annals of Operations Research, 192 (2012), 123-140. doi: 10.1007/s10479-010-0820-0.
[40]	H. Yang, V. Low, C. Zhang, L. Zheng and L. Miao, Behaviour perception-based disruption models for the parallel machine capacitated lot-sizing and scheduling problem, International Journal of Production Research, 55 (2017), 3058-3072. doi: 10.1080/00207543.2016.1234083.
[41]	Q. Zeng, Z. Yang and X. Hu, Disruption recovery model for berth and quay crane scheduling in container terminals, Engineering Optimization, 43 (2011), 967-983. doi: 10.1080/0305215X.2010.528411.
[42]	L. Zhen and D.-F. Chang, A bi-objective model for robust berth allocation scheduling, Computers & Industrial Engineering, 63 (2012), 262-273. doi: 10.1016/j.cie.2012.03.003.
[43]	P.-f. Zhou and H.-g. Kang, Study on berth and quay-crane allocation under stochastic environments in container terminal, Systems Engineering-Theory & Practice, 28 (2008), 161-169. doi: 10.1016/S1874-8651(09)60001-6.
[44]	I. Žulj, S. Kramer and M. Schneider, A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem, European Journal of Operational Research, 264 (2018), 653-664. doi: 10.1016/j.ejor.2017.06.056.