Swipe to navigate through the articles of this issue
In this paper, we address the waterway ship scheduling problem (WSSP), which finds applications in the management of ship arrivals and departures at maritime ports near channels and waterways. It incorporates practically relevant conflicts which stem from tidal changes, curfews, ship properties or traffic. We propose a reformulation of the WSSP as a variant of the multi-mode resource-constrained project scheduling problem, which incorporates time-dependent resource capacities besides earliest and latest start times for the tasks. This problem is solved through integer programming, using a compact mathematical formulation. Our approach outperforms previous methods by solving all the existing literature instances to optimality. Most of them are solved at the root node within less than 2 s.
Please log in to get access to this content
To get access to this content you need the following product:
Amirgaliyeva, Z., Mladenović, N., Todosijević, R., & Urošević, D. (2017). Solving the maximum min-sum dispersion by alternating formulations of two different problems. European Journal of Operational Research, 260(2), 444–459. CrossRef
Bartusch, M., Möhring, R. H., & Radermacher, F. J. (1988). Scheduling project networks with resource constraints and time windows. Annals of Operations Research, 16(1), 199–240. CrossRef
Beck, J. C., Prosser, P., & Selensky, E. (2002). On the reformulation of vehicle routing problems and scheduling problems. In International symposium on abstraction, reformulation, and approximation (pp. 282–289). Berlin: Springer.
Buhrkal, K., Zuglian, S., Ropke, S., Larsen, J., & Lusby, R. (2011). Models for the discrete berth allocation problem: A computational comparison. Transportation Research Part E: Logistics and Transportation Review, 47(4), 461–473. CrossRef
Campbell, J. F., Smith, L. D., Sweeney, D. C. I., Mundy, R., & Nauss, R. M. (2007). Decision tools for reducing congestion at locks on the upper Mississippi river. In 40th Hawaii international conference on system sciences, HICSS (pp. 56–56). IEEE.
Dassault Systems, D. (2017). Quintic website. Accessed Feburary 02, 2018, from http://www.quintiq.com/news-2017/panama-canal-to-launch-state-of-the-art-vessel-scheduling-and-maritime-resources-management-system.html.
Disser, Y., Klimm, M., & Lübbecke, E. (2015). Scheduling bidirectional traffic on a path. In International colloquium on automata, languages, and programming (pp. 406–418). Berlin: Springer.
Du, Y., Chen, Q., Lam, J. S. L., Xu, Y., & Cao, J. X. (2015). Modeling the impacts of tides and the virtual arrival policy in berth allocation. Transportation Science, 49(4), 939–956. CrossRef
Ernst, A. T., Oğuz, C., Singh, G., & Taherkhani, G. (2017). Mathematical models for the berth allocation problem in dry bulk terminals. Journal of Scheduling, 20(5), 459–473. CrossRef
Fischetti, M., & Monaci, M. (2014). Exploiting erraticism in search. Operations Research, 62(1), 114–122. CrossRef
Fügenschuh, A. (2011). A set partitioning reformulation of a school bus scheduling problem. Journal of Scheduling, 14(4), 307–318. CrossRef
Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207(1), 1–14. CrossRef
Iris, Ç., Pacino, D., Ropke, S., & Larsen, A. (2015). Integrated berth allocation and quay crane assignment problem: Set partitioning models and computational results. Transportation Research Part E: Logistics and Transportation Review, 81, 75–97. CrossRef
Lalla-Ruiz, E., Expósito-Izquierdo, C., Melián-Batista, B., & Moreno-Vega, J. M. (2016). A set-partitioning-based model for the berth allocation problem under time-dependent limitations. European Journal of Operational Research, 250(3), 1001–1012. CrossRef
Lalla-Ruiz, E., Shi, X., & Voß, S. (2018). The waterway ship scheduling problem. Transportation Research Part D: Transport and Environment, 60, 191–209. CrossRef
Lalla-Ruiz, E., & Voß, S. (2016a). Improving solver performance through redundancy. Journal of Systems Science and Systems Engineering, 25(3), 303–325.
Lalla-Ruiz, E., & Voß, S. (2016b). Popmusic as a matheuristic for the berth allocation problem. Annals of Mathematics and Artificial Intelligence, 76(1–2), 173–189.
López, C. O., & Beasley, J. (2016). A formulation space search heuristic for packing unequal circles in a fixed size circular container. European Journal of Operational Research, 251(1), 64–73. CrossRef
Lübbecke, E. (2015). On- and offline scheduling of bidirectional traffic. Berlin: Logos Verlag Berlin GmbH.
Norman, R.J. (1973). An algorithm for the scheduling of vessels through the Panama Canal. Ph.D. thesis, Monterey, California. Naval Postgraduate School.
Passchyn, W., Coene, S., Briskorn, D., Hurink, J. L., Spieksma, F. C. R., & Berghe, G. V. (2016). The lockmaster’s problem. European Journal of Operational Research, 251(2), 432–441. CrossRef
Reyck, B. D., & Herroelen, W. (1999). The multi-mode resource-constrained project scheduling problem with generalized precedence relations. European Journal of Operational Research, 119(2), 538–556. CrossRef
Rocha, R., Grossmann, I. E., & de Aragão, M. V. P. (2017). Petroleum supply planning: Reformulations and a novel decomposition algorithm. Optimization and Engineering, 18(1), 215–240. CrossRef
Rom, W. O., Tukel, O. I., & Muscatello, J. R. (2002). MRP in a job shop environment using a resource constrained project scheduling model. Omega, 30(4), 275–286. CrossRef
Schwindt, C., & Zimmermann, J. (2015). Handbook on project management and scheduling (Vol. 1). Berlin: Springer.
Talbot, F. B. (1982). Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 28(10), 1197–1210. CrossRef
Voß, S., & Lalla-Ruiz, E. (2016). A set partitioning reformulation for the multiple-choice multidimensional knapsack problem. Engineering Optimization, 48(5), 831–850. CrossRef
Wang, S., & Meng, Q. (2012). Robust schedule design for liner shipping services. Transportation Research Part E: Logistics and Transportation Review, 48(6), 1093–1106. CrossRef
Xu, D., Li, C. L., & Leung, J. Y. T. (2012). Berth allocation with time-dependent physical limitations on vessels. European Journal of Operational Research, 216(1), 47–56. CrossRef
Zhang, X., Lin, J., Guo, Z., & Liu, T. (2016). Vessel transportation scheduling optimization based on channel-berth coordination. Ocean Engineering, 112, 145–152. CrossRef
Zhu, G., Bard, J. F., & Yu, G. (2006). A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem. INFORMS Journal on Computing, 18(3), 377–390. CrossRef
- A multi-mode resource-constrained project scheduling reformulation for the waterway ship scheduling problem
- Publication date
- Springer US
Journal of Scheduling
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
Neuer Inhalt/© Stellmach, Neuer Inhalt/© BBL, Neuer Inhalt/© Maturus, Pluta Logo/© Pluta, Neuer Inhalt/© hww