Low-emission berth allocation by optimizing sailing speed and mooring time
Abstract
To investigate the relations among delay times (weighted by vessels’ handling times), the emissions during the vessels’ sailing and mooring in a Berth Allocation Problem (BAP) where the berth times and sailing speeds are formulated as decision variables. The vessels’ delay times are computed comparing to the vessels’ Expected Departure Times (EDTs); the sailing emission is determined by the sailing speed and distance; the mooring emission is positive to the mooring time at terminal. Multi-objective mixed-integer programs are established, and the nonlinear functions between emissions and sailing speeds are transferred to linear ones by the Second-Order Cone Programming (SOCP) method. Solution methods are further developed based on e-constraint and stage-based methods by considering the preferences of objectives. Four groups of experiments are conducted to demonstrate the formulations, effects of vessels’ handling times and EDTs on the solutions, and the reduced emissions affected by the number of vessels in the schedules. Experimental results demonstrated that the efficiency purpose is not absolutely conflict with the environment purposes for some instances, and so they can be pursued at the same time; improving the vessels’ handling efficiency help expand the ranges of berth times and sailing speeds, resulting in reducing the delay times and emissions; advancing the EDTs can improve the terminal operators’ service quality to shipping companies, while the weighted delay times and emission may be increased.
Keyword : container terminal, berth allocation problem, shipping, fuel consumption, low-emission logistics, logistics management
How to Cite
Hu, Z.-H. (2020). Low-emission berth allocation by optimizing sailing speed and mooring time. Transport, 35(5), 486-499. https://doi.org/10.3846/transport.2020.14080
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Alizadeh, F.; Goldfarb, D. 2003. Second-order cone programming, Mathematical Programming 95(1): 3–51. https://doi.org/10.1007/s10107-002-0339-5
Bierwirth, C.; Meisel, F. 2010. A survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research 202(3): 615–627. https://doi.org/10.1016/j.ejor.2009.05.031
Bierwirth, C.; Meisel, F. 2015. A follow-up survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research 244(3): 675–689. https://doi.org/10.1016/j.ejor.2014.12.030
Browning, L.; Façanha, C.; Papson, A.; Ang-Olson, J.; Hartley, S.; Carr, E. 2010. Representing Freight in Air Quality and Greenhouse Gas Models. National Cooperative Freight Research Program (NCFRP) Report 4. Transportation Research Board, Washington, DC, US. 169 p. https://doi.org/10.17226/14407
Chang, D.; Jiang, Z.; Yan, W.; He, J. 2010. Integrating berth allocation and quay crane assignments, Transportation Research Part E: Logistics and Transportation Review 46(6): 975–990. https://doi.org/10.1016/j.tre.2010.05.008
Choi, B.-C.; Lee, K.; Leung, J. Y.-T.; Pinedo, M. L.; Briskorn, D. 2012. Container scheduling: complexity and algorithms, Production and Operations Management 21(1): 115–128. https://doi.org/10.1111/j.1937-5956.2011.01238.x
Corbett, J. J.; Fischbeck, P. 1997. Emissions from ships, Science 278(5339): 823–824. https://doi.org/10.1126/science.278.5339.823
COSCO. 2009. COSCO Sustainable Development Report 2008. China Ocean Shipping Group (COSCO). 191 p. Available from Internet: http://en.coscoshipping.com/module/download/downfile.jsp?filename=370bc81c14d94c29b240183a2cbf4449.pdf
Dedes, E. K.; Hudson, D. A.; Turnock, S. R. 2012. Assessing the potential of hybrid energy technology to reduce exhaust emissions from global shipping, Energy Policy 40: 204–218. https://doi.org/10.1016/j.enpol.2011.09.046
Du, Y.; Chen, Q.; Quan, X.; Long, L.; Fung, R. Y. K. 2011. Berth allocation considering fuel consumption and vessel emissions, Transportation Research Part E: Logistics and Transportation Review 47(6): 1021–1037. https://doi.org/10.1016/j.tre.2011.05.011
Elwany, M. H.; Ali, I.; Abouelseoud, Y. 2013. A heuristics-based solution to the continuous berth allocation and crane assignment problem, Alexandria Engineering Journal 52(4): 671–677. https://doi.org/10.1016/j.aej.2013.09.001
Eyring, V.; Isaksen, I. S. A.; Berntsen, T.; Collins, W. J.; Corbett, J. J.; Endresen, O.; Grainger, R. G.; Moldanova, J.; Schlager, H.; Stevenson, D. S. 2010. Transport impacts on atmosphere and climate: shipping, Atmospheric Environment 44(37): 4735–4771. https://doi.org/10.1016/j.atmosenv.2009.04.059
Fagerholt, K.; Gausel, N. T.; Rakke, J. G.; Psaraftis, H. N. 2015. Maritime routing and speed optimization with emission control areas, Transportation Research Part C 52: 57–73. https://doi.org/10.1016/j.trc.2014.12.010
Fagerholt, K.; Laporte, G.; Norstad, I. 2010. Reducing fuel emissions by optimizing speed on shipping routes, Journal of the Operational Research Society 61(3): 523–529. https://doi.org/10.1057/jors.2009.77
Fagerholt, K.; Psaraftis, H. N. 2015. On two speed optimization problems for ships that sail in and out of emission control areas, Transportation Research Part D: Transport and Environment 39: 56–64. https://doi.org/10.1016/j.trd.2015.06.005
Franc, P.; Sutto, L. 2014. Impact analysis on shipping lines and European ports of a cap-and-trade system on CO2 emissions in maritime transport, Maritime Policy & Management: the Flagship Journal of International Shipping and Port Research 41(1): 61–78. https://doi.org/10.1080/03088839.2013.782440
Fransoo, J. C.; Lee, C.-Y. 2013. The critical role of ocean container transport in global supply chain performance, Production and Operations Management 22(2): 253–268. https://doi.org/10.1111/j.1937-5956.2011.01310.x
Gibbs, D.; Rigot-Muller, P.; Mangan, J.; Lalwani, C. 2014. The role of sea ports in end-to-end maritime transport chain emissions, Energy Policy 64: 337–348. https://doi.org/10.1016/j.enpol.2013.09.024
Golias, M. M.; Saharidis, G. K.; Boile, M.; Theofanis, S.; Ierapetritou, M. G. 2009. The berth allocation problem: optimizing vessel arrival time, Maritime Economics & Logistics 11(4): 358–377. https://doi.org/10.1057/mel.2009.12
Guan, Y.; Cheung, R. K. 2004. The berth allocation problem: models and solution methods, OR Spectrum 26(1): 75–92. https://doi.org/10.1007/s00291-003-0140-8
Hendriks, M.; Laumanns, M.; Lefeber, E.; Udding, J. T. 2010. Robust cyclic berth planning of container vessels, OR Spectrum 32(3): 501–517. https://doi.org/10.1007/s00291-010-0198-z
Hu, Q.-M.; Hu, Z.-H.; Du, Y. 2014. Berth and quay-crane allocation problem considering fuel consumption and emissions from vessels, Computers & Industrial Engineering 70: 1–10. https://doi.org/10.1016/j.cie.2014.01.003
Kim, K. H.; Moon, K. C. 2003. Berth scheduling by simulated annealing, Transportation Research Part B: Methodological 37(6): 541–560. https://doi.org/10.1016/S0191-2615(02)00027-9
Kontovas, C.; Psaraftis, H. N. 2011. Reduction of emissions along the maritime intermodal container chain: operational models and policies, Maritime Policy & Management: the Flagship Journal of International Shipping and Port Research 38(4): 451–469. https://doi.org/10.1080/03088839.2011.588262
Lim, A. 1998. The berth planning problem, Operations Research Letters 22(2–3): 105–110. https://doi.org/10.1016/S0167-6377(98)00010-8
Lindstad, H.; Sandaas, I.; Strømman, A. H. 2015. Assessment of cost as a function of abatement options in maritime emission control areas, Transportation Research Part D: Transport and Environment 38: 41–48. https://doi.org/10.1016/j.trd.2015.04.018
Masiol, M.; Harrison, R. M. 2014. Aircraft engine exhaust emissions and other airport-related contributions to ambient air pollution: a review, Atmospheric Environment 95: 409–455. https://doi.org/10.1016/j.atmosenv.2014.05.070
Mavrotas, G. 2009. Effective implementation of the ε-constraint method in multi-objective mathematical programming problems, Applied Mathematics and Computation 213(2): 455–465. https://doi.org/10.1016/j.amc.2009.03.037
Park, K. T.; Kim, K. H. 2002. Berth scheduling for container terminals by using a sub-gradient optimization technique, Journal of the Operational Research Society 53(9): 1054–1062. https://doi.org/10.1057/palgrave.jors.2601412
Park, Y.-M.; Kim, K. H. 2003. A scheduling method for berth and quay cranes, OR Spectrum 25(1): 1–23. https://doi.org/10.1007/s00291-002-0109-z
Raa, B.; Dullaert, W.; Schaeren, R. V. 2011. An enriched model for the integrated berth allocation and quay crane assignment problem, Expert Systems with Applications 38(11): 14136–14147. https://doi.org/10.1016/j.eswa.2011.04.224
Rodriguez-Molins, M.; Ingolotti, L.; Barber, F.; Salido, M. A.; Sierra, M. R.; Puente, J. 2014. A genetic algorithm for robust berth allocation and quay crane assignment, Progress in Artificial Intelligence 2(4): 177–192. https://doi.org/10.1007/s13748-014-0056-3
Schrooten, L.; De Vlieger, I.; Panis, L. I.; Chiffi, C.; Pastori, E. 2009. Emissions of maritime transport: a European reference system, Science of the Total Environment 408(2): 318–323. https://doi.org/10.1016/j.scitotenv.2009.07.037
Seyedalizadeh Ganji, S. R.; Babazadeh, A.; Arabshahi, N. 2010. Analysis of the continuous berth allocation problem in container ports using a genetic algorithm, Journal of Marine Science and Technology 15(4): 408–416. https://doi.org/10.1007/s00773-010-0095-9
Song, D.-P.; Xu, J. 2012. An operational activity-based method to estimate CO2 emissions from container shipping considering empty container repositioning, Transportation Research Part D: Transport and Environment 17(1): 91–96. https://doi.org/10.1016/j.trd.2011.06.007
Stahlbock, R.; Voß, S. 2008. Operations research at container terminals: a literature update, OR Spectrum 30(1): 1–52. https://doi.org/10.1007/s00291-007-0100-9
Starcrest Consulting Group. 2011. Port of Los Angles Inventory of Air Emissions – 2010. Technical Report ADP#050520-525. Starcrest Consulting Group, LLC, Poulsbo, WA, US. 226 p. Available from Internet: https://kentico.portoflosangeles.org/getmedia/26d2bb85-c08c-4776-afce-40677296e048/2010_Air_Emissions_Inventory
Steenken, D.; Voß, S.; Stahlbock, R. 2004. Container terminal operation and operations research – a classification and literature review, OR Spectrum 26(1): 3–49. https://doi.org/10.1007/s00291-003-0157-z
Svindland, M. 2018. The environmental effects of emission control area regulations on short sea shipping in Northern Europe: the case of container feeder vessels, Transportation Research Part D: Transport and Environment 61: 423–430. https://doi.org/10.1016/j.trd.2016.11.008
Vis, I. F. A.; De Koster, R. 2003. Transshipment of containers at a container terminal: an overview, European Journal of Operational Research 147(1): 1–16. https://doi.org/10.1016/S0377-2217(02)00293-X
Wang, F.; Lim, A. 2007. A stochastic beam search for the berth allocation problem, Decision Support Systems 42(4): 2186–2196. https://doi.org/10.1016/j.dss.2006.06.008
Yang, C.; Wang, X.; Li, Z. 2012. An optimization approach for coupling problem of berth allocation and quay crane assignment in container terminal, Computers & Industrial Engineering 63(1): 243–253. https://doi.org/10.1016/j.cie.2012.03.004
Yau, P. S.; Lee, S.-C.; Ho, K. F. 2012. Speed profiles for improvement of maritime emission estimation, Environmental Engineering Science 29(12): 1076–1084. https://doi.org/10.1089/ees.2011.0399
Zeng, Q.; Hu, X.; Wang, W.; Fang, Y. 2011a. Disruption management model and its algorithms for berth allocation problem in container terminals, International Journal of Innovative Computing, Information and Control 7(5): 2763–2773.
Zeng, Q.; Yang, Z.; Hu, X. 2011b. Disruption recovery model for berth and quay crane scheduling in container terminals, Engineering Optimization 43(9): 967–983. https://doi.org/10.1080/0305215X.2010.528411
Zhen, L.; Chew, E. P.; Lee, L. H. 2011. An integrated model for berth template and yard template planning in transshipment hubs, Transportation Science 45(4): 483–504. https://doi.org/10.1287/trsc.1100.0364
Bierwirth, C.; Meisel, F. 2010. A survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research 202(3): 615–627. https://doi.org/10.1016/j.ejor.2009.05.031
Bierwirth, C.; Meisel, F. 2015. A follow-up survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research 244(3): 675–689. https://doi.org/10.1016/j.ejor.2014.12.030
Browning, L.; Façanha, C.; Papson, A.; Ang-Olson, J.; Hartley, S.; Carr, E. 2010. Representing Freight in Air Quality and Greenhouse Gas Models. National Cooperative Freight Research Program (NCFRP) Report 4. Transportation Research Board, Washington, DC, US. 169 p. https://doi.org/10.17226/14407
Chang, D.; Jiang, Z.; Yan, W.; He, J. 2010. Integrating berth allocation and quay crane assignments, Transportation Research Part E: Logistics and Transportation Review 46(6): 975–990. https://doi.org/10.1016/j.tre.2010.05.008
Choi, B.-C.; Lee, K.; Leung, J. Y.-T.; Pinedo, M. L.; Briskorn, D. 2012. Container scheduling: complexity and algorithms, Production and Operations Management 21(1): 115–128. https://doi.org/10.1111/j.1937-5956.2011.01238.x
Corbett, J. J.; Fischbeck, P. 1997. Emissions from ships, Science 278(5339): 823–824. https://doi.org/10.1126/science.278.5339.823
COSCO. 2009. COSCO Sustainable Development Report 2008. China Ocean Shipping Group (COSCO). 191 p. Available from Internet: http://en.coscoshipping.com/module/download/downfile.jsp?filename=370bc81c14d94c29b240183a2cbf4449.pdf
Dedes, E. K.; Hudson, D. A.; Turnock, S. R. 2012. Assessing the potential of hybrid energy technology to reduce exhaust emissions from global shipping, Energy Policy 40: 204–218. https://doi.org/10.1016/j.enpol.2011.09.046
Du, Y.; Chen, Q.; Quan, X.; Long, L.; Fung, R. Y. K. 2011. Berth allocation considering fuel consumption and vessel emissions, Transportation Research Part E: Logistics and Transportation Review 47(6): 1021–1037. https://doi.org/10.1016/j.tre.2011.05.011
Elwany, M. H.; Ali, I.; Abouelseoud, Y. 2013. A heuristics-based solution to the continuous berth allocation and crane assignment problem, Alexandria Engineering Journal 52(4): 671–677. https://doi.org/10.1016/j.aej.2013.09.001
Eyring, V.; Isaksen, I. S. A.; Berntsen, T.; Collins, W. J.; Corbett, J. J.; Endresen, O.; Grainger, R. G.; Moldanova, J.; Schlager, H.; Stevenson, D. S. 2010. Transport impacts on atmosphere and climate: shipping, Atmospheric Environment 44(37): 4735–4771. https://doi.org/10.1016/j.atmosenv.2009.04.059
Fagerholt, K.; Gausel, N. T.; Rakke, J. G.; Psaraftis, H. N. 2015. Maritime routing and speed optimization with emission control areas, Transportation Research Part C 52: 57–73. https://doi.org/10.1016/j.trc.2014.12.010
Fagerholt, K.; Laporte, G.; Norstad, I. 2010. Reducing fuel emissions by optimizing speed on shipping routes, Journal of the Operational Research Society 61(3): 523–529. https://doi.org/10.1057/jors.2009.77
Fagerholt, K.; Psaraftis, H. N. 2015. On two speed optimization problems for ships that sail in and out of emission control areas, Transportation Research Part D: Transport and Environment 39: 56–64. https://doi.org/10.1016/j.trd.2015.06.005
Franc, P.; Sutto, L. 2014. Impact analysis on shipping lines and European ports of a cap-and-trade system on CO2 emissions in maritime transport, Maritime Policy & Management: the Flagship Journal of International Shipping and Port Research 41(1): 61–78. https://doi.org/10.1080/03088839.2013.782440
Fransoo, J. C.; Lee, C.-Y. 2013. The critical role of ocean container transport in global supply chain performance, Production and Operations Management 22(2): 253–268. https://doi.org/10.1111/j.1937-5956.2011.01310.x
Gibbs, D.; Rigot-Muller, P.; Mangan, J.; Lalwani, C. 2014. The role of sea ports in end-to-end maritime transport chain emissions, Energy Policy 64: 337–348. https://doi.org/10.1016/j.enpol.2013.09.024
Golias, M. M.; Saharidis, G. K.; Boile, M.; Theofanis, S.; Ierapetritou, M. G. 2009. The berth allocation problem: optimizing vessel arrival time, Maritime Economics & Logistics 11(4): 358–377. https://doi.org/10.1057/mel.2009.12
Guan, Y.; Cheung, R. K. 2004. The berth allocation problem: models and solution methods, OR Spectrum 26(1): 75–92. https://doi.org/10.1007/s00291-003-0140-8
Hendriks, M.; Laumanns, M.; Lefeber, E.; Udding, J. T. 2010. Robust cyclic berth planning of container vessels, OR Spectrum 32(3): 501–517. https://doi.org/10.1007/s00291-010-0198-z
Hu, Q.-M.; Hu, Z.-H.; Du, Y. 2014. Berth and quay-crane allocation problem considering fuel consumption and emissions from vessels, Computers & Industrial Engineering 70: 1–10. https://doi.org/10.1016/j.cie.2014.01.003
Kim, K. H.; Moon, K. C. 2003. Berth scheduling by simulated annealing, Transportation Research Part B: Methodological 37(6): 541–560. https://doi.org/10.1016/S0191-2615(02)00027-9
Kontovas, C.; Psaraftis, H. N. 2011. Reduction of emissions along the maritime intermodal container chain: operational models and policies, Maritime Policy & Management: the Flagship Journal of International Shipping and Port Research 38(4): 451–469. https://doi.org/10.1080/03088839.2011.588262
Lim, A. 1998. The berth planning problem, Operations Research Letters 22(2–3): 105–110. https://doi.org/10.1016/S0167-6377(98)00010-8
Lindstad, H.; Sandaas, I.; Strømman, A. H. 2015. Assessment of cost as a function of abatement options in maritime emission control areas, Transportation Research Part D: Transport and Environment 38: 41–48. https://doi.org/10.1016/j.trd.2015.04.018
Masiol, M.; Harrison, R. M. 2014. Aircraft engine exhaust emissions and other airport-related contributions to ambient air pollution: a review, Atmospheric Environment 95: 409–455. https://doi.org/10.1016/j.atmosenv.2014.05.070
Mavrotas, G. 2009. Effective implementation of the ε-constraint method in multi-objective mathematical programming problems, Applied Mathematics and Computation 213(2): 455–465. https://doi.org/10.1016/j.amc.2009.03.037
Park, K. T.; Kim, K. H. 2002. Berth scheduling for container terminals by using a sub-gradient optimization technique, Journal of the Operational Research Society 53(9): 1054–1062. https://doi.org/10.1057/palgrave.jors.2601412
Park, Y.-M.; Kim, K. H. 2003. A scheduling method for berth and quay cranes, OR Spectrum 25(1): 1–23. https://doi.org/10.1007/s00291-002-0109-z
Raa, B.; Dullaert, W.; Schaeren, R. V. 2011. An enriched model for the integrated berth allocation and quay crane assignment problem, Expert Systems with Applications 38(11): 14136–14147. https://doi.org/10.1016/j.eswa.2011.04.224
Rodriguez-Molins, M.; Ingolotti, L.; Barber, F.; Salido, M. A.; Sierra, M. R.; Puente, J. 2014. A genetic algorithm for robust berth allocation and quay crane assignment, Progress in Artificial Intelligence 2(4): 177–192. https://doi.org/10.1007/s13748-014-0056-3
Schrooten, L.; De Vlieger, I.; Panis, L. I.; Chiffi, C.; Pastori, E. 2009. Emissions of maritime transport: a European reference system, Science of the Total Environment 408(2): 318–323. https://doi.org/10.1016/j.scitotenv.2009.07.037
Seyedalizadeh Ganji, S. R.; Babazadeh, A.; Arabshahi, N. 2010. Analysis of the continuous berth allocation problem in container ports using a genetic algorithm, Journal of Marine Science and Technology 15(4): 408–416. https://doi.org/10.1007/s00773-010-0095-9
Song, D.-P.; Xu, J. 2012. An operational activity-based method to estimate CO2 emissions from container shipping considering empty container repositioning, Transportation Research Part D: Transport and Environment 17(1): 91–96. https://doi.org/10.1016/j.trd.2011.06.007
Stahlbock, R.; Voß, S. 2008. Operations research at container terminals: a literature update, OR Spectrum 30(1): 1–52. https://doi.org/10.1007/s00291-007-0100-9
Starcrest Consulting Group. 2011. Port of Los Angles Inventory of Air Emissions – 2010. Technical Report ADP#050520-525. Starcrest Consulting Group, LLC, Poulsbo, WA, US. 226 p. Available from Internet: https://kentico.portoflosangeles.org/getmedia/26d2bb85-c08c-4776-afce-40677296e048/2010_Air_Emissions_Inventory
Steenken, D.; Voß, S.; Stahlbock, R. 2004. Container terminal operation and operations research – a classification and literature review, OR Spectrum 26(1): 3–49. https://doi.org/10.1007/s00291-003-0157-z
Svindland, M. 2018. The environmental effects of emission control area regulations on short sea shipping in Northern Europe: the case of container feeder vessels, Transportation Research Part D: Transport and Environment 61: 423–430. https://doi.org/10.1016/j.trd.2016.11.008
Vis, I. F. A.; De Koster, R. 2003. Transshipment of containers at a container terminal: an overview, European Journal of Operational Research 147(1): 1–16. https://doi.org/10.1016/S0377-2217(02)00293-X
Wang, F.; Lim, A. 2007. A stochastic beam search for the berth allocation problem, Decision Support Systems 42(4): 2186–2196. https://doi.org/10.1016/j.dss.2006.06.008
Yang, C.; Wang, X.; Li, Z. 2012. An optimization approach for coupling problem of berth allocation and quay crane assignment in container terminal, Computers & Industrial Engineering 63(1): 243–253. https://doi.org/10.1016/j.cie.2012.03.004
Yau, P. S.; Lee, S.-C.; Ho, K. F. 2012. Speed profiles for improvement of maritime emission estimation, Environmental Engineering Science 29(12): 1076–1084. https://doi.org/10.1089/ees.2011.0399
Zeng, Q.; Hu, X.; Wang, W.; Fang, Y. 2011a. Disruption management model and its algorithms for berth allocation problem in container terminals, International Journal of Innovative Computing, Information and Control 7(5): 2763–2773.
Zeng, Q.; Yang, Z.; Hu, X. 2011b. Disruption recovery model for berth and quay crane scheduling in container terminals, Engineering Optimization 43(9): 967–983. https://doi.org/10.1080/0305215X.2010.528411
Zhen, L.; Chew, E. P.; Lee, L. H. 2011. An integrated model for berth template and yard template planning in transshipment hubs, Transportation Science 45(4): 483–504. https://doi.org/10.1287/trsc.1100.0364