×

zbMATH — the first resource for mathematics

Optimally solving the generalized serial-lock scheduling problem from a graph-theory-based multi-commodity network perspective. (English) Zbl 07354065
Summary: In this study, we propose a general model for the generalized serial-lock scheduling problem (GSLSP), innovatively from a multi-commodity network (MCN) perspective. The MCN-based approach allows the formulation of a mixed integer linear programming (MILP) model, which is capable of finding the optimal solution to the GSLSP. In order to verify the effectiveness of the proposed method, a large number of instances with various lock configurations are tested, which corroborates that the proposed MCN-based GSLSP approach attests optimality for single-lock problems with less computational burden than the conventional exact methods. It can also solve multiple series-connected lock problems to optimality within reasonable computational time. Thereafter, we also investigate the impact of a serial-lock system’s symmetry on the performance of the proposed MCN-based method when used for transferring ships.
MSC:
90Bxx Operations research and management science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bierwirth, C.; Meisel, F., A follow-up survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research, 244, 3, 675-689 (2015) · Zbl 1346.90326
[2] Bugarski, V.; BačKalić, T.; Kuzmanov, U., Fuzzy decision support system for ship lock control, Expert Systems with Applications, 40, 10, 3953-3960 (2013)
[3] Carlo, H. J.; Vis, I. F.; Roodbergen, K. J., Storage yard operations in container terminals: Literature overview, trends, and research directions, European Journal of Operational Research, 235, 2, 412-430 (2014) · Zbl 1305.90007
[4] Dai, M. D.; Schonfeld, P., Metamodels for estimating waterway delays through series of queues, Transportation Research Part B: Methodological, 32, 1, 1-19 (1998)
[5] Evans, G. W., An overview of techniques for solving multiobjective mathematical programs, Management Science, 30, 11, 1268-1282 (1984) · Zbl 0551.90090
[6] Ji, B.; Yuan, X.; Yuan, Y., Orthogonal design-based NSGA-III for the optimal lockage co-scheduling problem, IEEE Transactions on Intelligent Transportation Systems, 18, 8, 2085-2095 (2016)
[7] Ji, B.; Yuan, X.; Yuan, Y., A hybrid intelligent approach for co-scheduling of cascaded locks with multiple chambers, IEEE Transactions on Cybernetics, 49, 4, 1236-1248 (2018)
[8] Ji, B.; Yuan, X.; Yuan, Y.; Lei, X.; Fernando, T.; Iu, H. H., Exact and heuristic methods for optimizing lock-quay system in inland waterway, European Journal of Operational Research, 277, 2, 740-755 (2019) · Zbl 1430.90269
[9] Ji, B.; Yuan, X.; Yuan, Y.; Lei, X.; Herbert, H., An adaptive large neighborhood search for solving generalized lock scheduling problem: Comparative study with exact methods, IEEE Transactions on Intelligent Transportation Systems (2019)
[10] Lodi, A.; Martello, S.; Monaci, M., Two-dimensional packing problems: A survey, European Journal of Operational Research, 141, 2, 241-252 (2002) · Zbl 1081.90576
[11] Lübbecke, E.; Lübbecke, M. E.; Möhring, R. H., Ship traffic optimization for the kiel canal, Operations Research, 67, 3, 791-812 (2019)
[12] Martinelli, D.; Schonfeld, P., Approximating delays at interdependent locks, Journal of Waterway, Port, Coastal, and Ocean Engineering, 121, 6, 300-307 (1995)
[13] Nauss, R. M., Optimal sequencing in the presence of setup times for tow/barge traffic through a river lock, European Journal of Operational Research, 187, 3, 1268-1281 (2008) · Zbl 1137.90427
[14] Passchyn, W., Scheduling locks on inland waterways (2016), Ph. D. thesis, KU Leuven, Ph.D. thesis
[15] Passchyn, W.; Briskorn, D.; Spieksma, F. C., Mathematical programming models for lock scheduling with an emission objective, European Journal of Operational Research, 248, 3, 802-814 (2016) · Zbl 1346.90380
[16] Passchyn, W.; Coene, S.; Briskorn, D.; Hurink, J. L.; Spieksma, F. C.; Berghe, G. V., The lockmasterâs problem, European Journal of Operational Research, 251, 2, 432-441 (2016) · Zbl 1346.90597
[17] Petersen, E. R.; Taylor, A. J., An optimal scheduling system for the welland canal, Transportation science, 22, 3, 173-185 (1988) · Zbl 0645.90040
[18] Pisinger, D.; Sigurd, M., The two-dimensional bin packing problem with variable bin sizes and costs, Discrete Optimization, 2, 2, 154-167 (2005) · Zbl 1077.90057
[19] Prandtstetter, M.; Ritzinger, U.; Schmidt, P.; Ruthmair, M., A variable neighborhood search approach for the interdependent lock scheduling problem, Proceedings of the european conference on evolutionary computation in combinatorial optimization, 36-47 (2015), Springer
[20] Smith, L. D.; Nauss, R. M., Investigating strategic alternatives for improving service in an inland waterway transportation system, International Journal of Strategic Decision Sciences, 1, 2, 62-81 (2010)
[21] Smith, L. D.; Sweeney, D.; Campbell, J. F., Simulation of alternative approaches to relieving congestion at locks in a river transportion system, Journal of the Operational Research Society, 60, 4, 519-533 (2009) · Zbl 1163.90411
[22] Verstichel, J.; Berghe, G. V., A late acceptance algorithm for the lock scheduling problem, Proceedings of the Logistik Management, 457-478 (2009), Springer
[23] Verstichel, J.; Berghe, G. V., Scheduling serial locks: A green wave for waterbound logistics, Proceedings of the sustainable Logistics and Supply Chains, 91-109 (2016), Springer
[24] Verstichel, J.; Berghe, G. V., Simulation and optimization for ship lock scheduling: a case study, Proceedings of the 7th international conference on information, intelligence, systems & applications (iisa), 1-6 (2016), IEEE
[25] Verstichel, J.; De Causmaecker, P.; Berghe, G. V., Scheduling algorithms for the lock scheduling problem, Procedia-Social and Behavioral Sciences, 20, 806-815 (2011)
[26] Verstichel, J.; De Causmaecker, P.; Spieksma, F.; Berghe, G. V., The generalized lock scheduling problem: An exact approach, Transportation Research Part E: Logistics and Transportation Review, 65, 16-34 (2014)
[27] Verstichel, J.; De Causmaecker, P.; Spieksma, F. C.; Berghe, G. V., Exact and heuristic methods for placing ships in locks, European Journal of Operational Research, 235, 2, 387-398 (2014) · Zbl 1305.90262
[28] Verstichel, J.; Kinable, J.; De Causmaecker, P.; Berghe, G. V., A combinatorial Benders’ decomposition for the lock scheduling problem, Computers &amp Operations Research, 54, 117-128 (2015) · Zbl 1348.90318
[29] Wilson, H. G., On the applicability of queueing theory to lock capacity analysis, Transportation Research, 12, 3, 175-180 (1978)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.