×

zbMATH — the first resource for mathematics

Exact and heuristic methods for optimizing lock-quay system in inland waterway. (English) Zbl 1430.90269
Summary: This paper focuses on lock and quay co-scheduling problem (LQCP) so that delay time of ships at a lock and time spent at the quay are minimized. The task can be regarded as a main problem where an alternative mode for a ship is determined by solving two sub-problems of lock scheduling and berth allocation. For the first time, the LQCP considers the discrete berth allocation of container ships and the mooring constraints of lock scheduling. A mixed integer linear programming (MILP) model is formulated for the LQCP and small-scale problems are solved by branch and bound method. In addition, fuzzy logic control based heuristic method is proposed to handle large-scale LQCP. Specifically, a fuzzy-controlled quantum inspired gravitational search algorithm is proposed to search optimal mode combinations for the main problem iteratively. In each iteration, Tabu search based multi-order best fit algorithm is proposed to solve lock scheduling sub-problem and an adaptive large neighborhood search algorithm is applied to solve berth allocation sub-problem. The MILP and heuristic methods are tested on 42 instances, in which the MILP is implemented in Gurobi 7.5.1. Experimental results indicate that the MILP model can handle different traffic situations. The proposed heuristic method shows tiny optimality gap for small-scale instances and outperforms Gurobi on most of medium-large scale instances with respect to solution quality and computation time. Furthermore, comparison between different heuristics on medium and large scale instances confirms that the fuzzy logic control based heuristic outperforms other heuristic methods.

MSC:
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90C70 Fuzzy and other nonstochastic uncertainty mathematical programming
Software:
Gurobi; irace
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bierwirth, C.; Meisel, F., A survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research, 202, 3, 615-627, (2010) · Zbl 1176.90373
[2] 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
[3] Bugarski, V.; Backalic, T.; Kuzmanov, U., Fuzzy decision support system for ship lock control, Expert Systems with Applications, 40, 10, 3953-3960, (2013)
[4] Burke, E. K.; Kendall, G.; Whitwell, G., A new placement heuristic for the orthogonal stock-cutting problem, Operations Research, 52, 4, 655-671, (2004) · Zbl 1165.90690
[5] Caris, A.; Limbourg, S.; Macharis, C., Integration of inland waterway transport in the intermodal supply chain: A taxonomy of research challenges, Journal of Transport Geography, 41, 126-136, (2014)
[6] Chen, Z.; Yuan, X.; Ji, B., Design of a fractional order PID controller for hydraulic turbine regulating system using chaotic non-dominated sorting genetic algorithm II, Energy Conversion and Management, 84, 390-404, (2014)
[7] Cordeau, J. F.; Laporte, G.; Legato, P., Models and tabu search heuristics for the berth-allocation problem, Transportation Science, 39, 4, 526-538, (2005)
[8] De Oliveira, R. M.; Mauri, G. R.; Lorena, L. A., Clustering search for the berth allocation problem, Expert Systems with Applications, 39, 5, 5499-5505, (2012)
[9] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 13, 5, 533-549, (1986) · Zbl 0615.90083
[10] Hansen, P.; Oguz, C., A note on formulations of the static and dynamic berth allocation problems, les Cahiers du GERAD, 30, 1-17, (2003)
[11] Hien, N. T.; Hoai, N. X., A brief overview of population diversity measures in genetic programming, (Proceedings of the 3rd Asian-pacific workshop on genetic programming. Proceedings of the 3rd Asian-pacific workshop on genetic programming, Hanoi, Vietnam. Citeseer, (2006)), 128-139
[12] Huang, S.-C.; Jiau, M.-K.; Lin, C.-H., Optimization of the carpool service problem via a fuzzy-controlled genetic algorithm, IEEE Transactions on Fuzzy Systems, 23, 5, 1698-1712, (2015)
[13] Ibrahim, A.; Mohamed, A.; Shareef, H., Optimal power quality monitor placement in power systems using an adaptive quantum-inspired binary gravitational search algorithm, International Journal of Electrical Power & Energy Systems, 57, 404-413, (2014)
[14] Imai, A.; Nishimura, E.; Papadimitriou, S., The dynamic berth allocation problem for a container port, Transportation Research Part B: Methodological, 35, 4, 401-417, (2001)
[15] 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, (2017)
[16] Ji, B.; Yuan, X.; Yuan, Y., Modified NSGA-II for solving continuous berth allocation problem: Using multiobjective constraint-handling strategy, IEEE Transactions on Cybernetics, 47, 9, 2885-2895, (2017)
[17] 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, (2019)
[18] Kanovic, Z.; Bugarski, V.; Backalic, T., Ship lock control system optimization using GA, PSO and ABC: A comparative review, Promet-Traffic & Transportation, 26, 1, 23-31, (2014)
[19] Lalla-Ruiz, E.; Exposito-Izquierdo, C.; Melian-Batista, B., A set-partitioning-based model for the berth allocation problem under time-dependent limitations, European Journal of Operational Research, 250, 3, 1001-1012, (2016) · Zbl 1346.90503
[20] Lalla-Ruiz, E.; Vob, S.; Exposito-Izquierdo, C., A popmusic-based approach for the berth allocation problem under time-dependent limitations, Annals of Operations Research, 253, 2, 871-897, (2017) · Zbl 1380.90121
[21] Len-Rios, F. (2002). Ship lift system and method for transportation of ships with recycling water system in canal. US Patent, US 2002/0119010 A1, Aug. 29, 2002.
[22] Liang, J.; Yuan, X.; Yuan, Y., Nonlinear dynamic analysis and robust controller design for Francis hydraulic turbine regulating system with a straight-tube surge tank, Mechanical System and Signal Processing, 85, 927-946, (2017)
[23] 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
[24] Lopez-Ibanez, M.; Dubois-Lacoste, J.; Perez Caceres, L., The irace package: Iterated racing for automatic algorithm configuration, Operations Research Perspectives, 3, 43-58, (2016)
[25] Mauri, G. R.; Ribeiro, G. M.; Lorena, L. A., An adaptive large neighborhood search for the discrete and continuous berth allocation problem, Computers & Operations Research, 70, 140-154, (2016) · Zbl 1391.90662
[26] Nezamabadi-pour, H., A quantum-inspired gravitational search algorithm for binary encoded optimization problems, Engineering Applications of Artificial Intelligence, 40, 62-75, (2015)
[27] Parragh, S. N.; Cordeau, J. F., Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows, Computers & Operations Research, 83, 28-44, (2017) · Zbl 1458.90127
[28] 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
[29] 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
[30] Rashedi, E.; Nezamabadi-Pour, H.; Saryazdi, S., GSA: A gravitational search algorithm, Information Sciences, 179, 13, 2232-2248, (2009) · Zbl 1177.90378
[31] Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40, 4, 455-472, (2006)
[32] Smith, L.; Nauss, R., Investigating strategic alternatives for improving service in an inland waterway transportation system, Decision making theories and practices from analysis to strategy, 117-136, (2012), IGI Global
[33] Smith, L.; Sweeney, D.; Campbell, J., A simulation model to evaluate decision rules for lock operations on the Upper Mississippi River, (Proceedings of the 40th annual Hawaii international conference in system sciences. Proceedings of the 40th annual Hawaii international conference in system sciences, IEEE, (2007)), 56
[34] Smith, L. D.; Sweeney, D. C.; Campbell, J. F., Simulation of alternative approaches to relieving congestion at locks in a river transportation system, Journal of the Operational Research Society, 60, 4, 519-533, (2010) · Zbl 1163.90411
[35] Ting, C. J.; Wu, K. C.; Chou, H., Particle swarm optimization algorithm for the berth allocation problem, Expert Systems with Applications, 41, 4, 1543-1550, (2014)
[36] Van Broekhoven, E.; De Baets, B., Only smooth rule bases can generate monotone mamdani-assilian models under center-of-gravity defuzzification, IEEE Transactions on Fuzzy Systems, 17, 5, 1157-1174, (2009)
[37] Verstichel, J.; Berghe, G. V., Scheduling serial locks: A green wave for waterbound logistics, Sustainable logistics and supply chains (Contributions to management science), 91-109, (2016), Springer: Springer Cham Heidelberg New York Dordrecht London
[38] Verstichel, J.; Vanden Berghe, G., A late acceptance algorithm for the lock scheduling problem, Logistik management, 457-478, (2009), Physica-Verlag HD, Springer
[39] Verstichel, J.; De Causmaecker, P.; Berghe, G. V., Scheduling algorithms for the lock scheduling problem, Procedia-Social and Behavioral Sciences, 20, 806-815, (2011)
[40] Verstichel, J.; De Causmaecker, P.; Spieksma, F., The generalized lock scheduling problem: An exact approach, Transportation Research Part E: Logistics and Transportation Review, 65, 16-34, (2014)
[41] Verstichel, J.; De Causmaecker, P.; Spieksma, F. C., Exact and heuristic methods for placing ships in locks, European Journal of Operational Research, 235, 2, 387-398, (2014) · Zbl 1305.90262
[42] Verstichel, J.; Kinable, J.; De Causmaecker, P., A combinatorial Benders’ decomposition for the lock scheduling problem, Computers & Operations Research, 54, 117-128, (2015) · Zbl 1348.90318
[43] Wang, K.; Zhen, L.; Wang, S., Column generation for the integrated berth allocation, quay crane assignment, and yard assignment problem, Transportation Science, 52, 4, 739-1034, (2018)
[44] Wilson, W. W.; Dahl, B. L.; Taylor, R. D., Impacts of lock capacity expansion on delay costs for grain shipped on the Mississippi River, Journal of Transport Economics and Policy (JTEP), 45, 1, 129-154, (2011)
[45] Yuan, X.; Ji, B.; Yuan, Y., An efficient chaos embedded hybrid approach for hydro-thermal unit commitment problem, Energy Conversion and Management, 91, 225-237, (2015)
[46] Yuan, X.; Wang, P.; Yuan, Y., A new quantum inspired chaotic artificial bee colony algorithm for optimal power flow problem, Energy Conversion and Management, 100, 1-9, (2015)
[47] Yuan, X.; Ji, B.; Yuan, Y., Co-scheduling of lock and water-land transshipment for ships passing the dam, Applied Soft Computing, 45, 150-162, (2016)
[48] Zhang, X.; Lin, J.; Guo, Z., Vessel transportation scheduling optimization based on channel-berth coordination, Ocean Engineering, 112, 145-152, (2016)
[49] Zhang, D.; Zou, F.; Li, S., Green supply chain network design with economies of scale and environmental concerns, Journal of Advanced Transportation, (2017)
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.