{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T07:10:18Z","timestamp":1778915418795,"version":"3.51.4"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:00:00Z","timestamp":1642636800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:00:00Z","timestamp":1642636800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2022,5]]},"DOI":"10.1007\/s10479-021-04474-6","type":"journal-article","created":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:04:11Z","timestamp":1642637051000},"page":"723-760","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage"],"prefix":"10.1007","volume":"312","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8823-7966","authenticated-orcid":false,"given":"Paul A.","family":"Chircop","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0989-6168","authenticated-orcid":false,"given":"Timothy J.","family":"Surendonk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Menkes H. L.","family":"van den Briel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2998-8668","authenticated-orcid":false,"given":"Toby","family":"Walsh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,20]]},"reference":[{"key":"4474_CR1","unstructured":"Ahuja, R., Magnanti, T., & Orlin, J. (1993). Network flows: Theory, algorithms, and applications. Prentice Hall."},{"key":"4474_CR2","unstructured":"Akca, Z., Ralphs, T. K., & Berger, R. T. (2010). Solution methods for the multi-trip elementary shortest path problem with resource constraints. Optimization Online. http:\/\/www.optimization-online.org\/DB_HTML\/2011\/03\/2962.html."},{"issue":"1","key":"4474_CR3","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1287\/trsc.1100.0333","volume":"45","author":"J Andersen","year":"2011","unstructured":"Andersen, J., Christiansen, M., Crainic, T. G., & Gr\u00f8nhaug, R. (2011). Branch and price for service network design with asset management constraints. Transportation Science, 45(1), 33\u201349.","journal-title":"Transportation Science"},{"issue":"3","key":"4474_CR4","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1287\/opre.46.3.316","volume":"46","author":"C Barnhart","year":"1998","unstructured":"Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Va, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316\u2013329.","journal-title":"Operations Research"},{"key":"4474_CR5","doi-asserted-by":"crossref","unstructured":"Ben Amor, H., & Val\u00e9rio de Carvalho, J. (2005). Cutting stock problems. In G. Desaulniers, J. Desrosiers, & M. M. Solomon (Eds.), Column generation (pp. 131\u2013161). Springer.","DOI":"10.1007\/0-387-25486-2_5"},{"issue":"2","key":"4474_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1287\/inte.26.2.59","volume":"26","author":"GG Brown","year":"1996","unstructured":"Brown, G. G., Dell, R. F., & Farmer, R. A. (1996). Scheduling Coast Guard district cutters. Interfaces, 26(2), 59\u201372.","journal-title":"Interfaces"},{"key":"4474_CR7","doi-asserted-by":"crossref","unstructured":"\u00c7apar, \u0130., Keskin, B. B., & Rubin, P. A. (2015). An improved formulation for the maximum coverage patrol routing problem. Computers & Operations Research, 59, 1\u201310.","DOI":"10.1016\/j.cor.2014.12.002"},{"key":"4474_CR8","unstructured":"Chircop, P. A. (2017). Column generation approaches to patrol asset scheduling with complete and maximum coverage requirements (Doctoral dissertation, University of New South Wales). https:\/\/doi.org\/1959.4\/57656"},{"issue":"4","key":"4474_CR9","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1177\/1548512919883955","volume":"18","author":"PA Chircop","year":"2021","unstructured":"Chircop, P. A., & Surendonk, T. J. (2021). On integer linear programming formulations of a patrol boat scheduling problem with complete coverage requirements. The Journal of Defense Modeling and Simulation: Applications, Methodology, Technology, 18(4), 429\u2013439.","journal-title":"The Journal of Defense Modeling and Simulation: Applications, Methodology, Technology"},{"key":"4474_CR10","unstructured":"Chircop, P. A., Surendonk, T. J., van den Briel, M. H. L., & Walsh, T. (2013). A column generation approach for the scheduling of patrol boats to provide complete patrol coverage. In J. Piantadosi, R. S. Anderssen, & J. Boland (Eds.), Proceedings of the 20th international congress on modelling and simulation (pp. 1110\u20131116). Modelling and Simulation Society of Australia and New Zealand."},{"key":"4474_CR11","doi-asserted-by":"crossref","unstructured":"Chircop, P. A., Surendonk, T. J., van den Briel, M. H. L., & Walsh, T. (2021). A branch-and-price framework for the maximum covering and patrol routing problem. In A. T. Ernst, S. Dunstall, R. Garc\u00eda-Flores, M. Grobler, & D. Marlow (Eds.), Data and decision sciences in action 2 (pp. 59\u201380). Springer.","DOI":"10.1007\/978-3-030-60135-5_5"},{"issue":"1","key":"4474_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/trsc.1030.0036","volume":"38","author":"M Christiansen","year":"2004","unstructured":"Christiansen, M., Fagerholt, K., & Ronen, D. (2004). Ship routing and scheduling: Status and perspectives. Transportation Science, 38(1), 1\u201318.","journal-title":"Transportation Science"},{"key":"4474_CR13","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1023\/A:1018921527269","volume":"81","author":"M Christiansen","year":"1998","unstructured":"Christiansen, M., & Nygreen, B. (1998). A method for solving ship routing problems with inventory constraints. Annals of Operations Research, 81, 357\u2013378.","journal-title":"Annals of Operations Research"},{"key":"4474_CR14","unstructured":"Chvatal, V. (1983). Linear programming. Macmillan."},{"key":"4474_CR15","doi-asserted-by":"crossref","unstructured":"Conforti, M., Cornu\u00e9jols, G., & Zambelli, G. (2014). Integer programming. Springer.","DOI":"10.1007\/978-3-319-11008-0"},{"key":"4474_CR16","unstructured":"Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd edn.). The MIT Press."},{"issue":"1","key":"4474_CR17","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1287\/opre.8.1.101","volume":"8","author":"GB Dantzig","year":"1960","unstructured":"Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101\u2013111.","journal-title":"Operations Research"},{"issue":"3","key":"4474_CR18","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1016\/0377-2217(95)00231-6","volume":"87","author":"K Darby-Dowman","year":"1995","unstructured":"Darby-Dowman, K., Fink, R. K., Mitra, G., & Smith, J. W. (1995). An intelligent system for US Coast Guard cutter scheduling. European Journal of Operational Research, 87(3), 574\u2013585.","journal-title":"European Journal of Operational Research"},{"key":"4474_CR19","doi-asserted-by":"crossref","unstructured":"Desaulniers, G., Desrosiers, J., & Solomon, M. M. (2002). Accelerating strategies in column generation methods for vehicle routing and crew scheduling problems. In Essays and surveys in metaheuristics (pp. 309\u2013324). Springer.","DOI":"10.1007\/978-1-4615-1507-4_14"},{"key":"4474_CR20","unstructured":"Desrochers, M. (1986). La fabrication d\u2019horaires de travail pour les conducteurs d\u2019autobus par une m\u00e9thode de g\u00e9n\u00e9ration de colonnes (Unpublished doctoral dissertation). Centre de Recherche sur les Transports, Universit\u00e9 de Montr\u00e9al."},{"issue":"3","key":"4474_CR21","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1080\/03155986.1988.11732063","volume":"26","author":"M Desrochers","year":"1988","unstructured":"Desrochers, M., & Soumis, F. (1988). A generalized permanent labeling algorithm for the shortest-path problem with time windows. Information Systems and Operations Research, 26(3), 191\u2013212.","journal-title":"Information Systems and Operations Research"},{"issue":"1","key":"4474_CR22","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.ejor.2015.05.067","volume":"247","author":"R Dewil","year":"2015","unstructured":"Dewil, R., Vansteenwegen, P., Cattrysse, D., & Oudheusden, D. V. (2015). A minimum cost network flow model for the maximum covering and patrol routing problem. European Journal of Operational Research, 247(1), 27\u201336.","journal-title":"European Journal of Operational Research"},{"key":"4474_CR23","doi-asserted-by":"crossref","unstructured":"Easton, K., Nemhauser, G., & Trick, M. (2004). CP based branch-and-price. In M. Milano (Ed.), Constraint and integer programming (pp. 207\u2013231). Springer.","DOI":"10.1007\/978-1-4419-8917-8_7"},{"key":"4474_CR24","unstructured":"Fang, F., Stone, P., & Tambe, M. (2015). When security games go green: Designing defender strategies to prevent poaching and illegal fishing. In Proceedings of the 24th international joint conference on artificial intelligence (pp. 2589\u20132595). AAAI Press."},{"issue":"6","key":"4474_CR25","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1287\/mnsc.47.6.833.9810","volume":"47","author":"M Fischetti","year":"2001","unstructured":"Fischetti, M., Lodi, A., Martello, S., & Toth, P. (2001). A polyhedral approach to simplified crew scheduling and vehicle scheduling problems. Management Science, 47(6), 833\u2013850.","journal-title":"Management Science"},{"issue":"1","key":"4474_CR26","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1287\/mnsc.5.1.97","volume":"5","author":"LR Ford","year":"1958","unstructured":"Ford, L. R., & Fulkerson, D. R. (1958). A suggested computation for maximal multi-commodity network flows. Management Science, 5(1), 97\u2013101.","journal-title":"Management Science"},{"issue":"6","key":"4474_CR27","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"PC Gilmore","year":"1961","unstructured":"Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849\u2013859.","journal-title":"Operations Research"},{"key":"4474_CR28","doi-asserted-by":"crossref","unstructured":"Gualandi, S., & Malucelli, F. (2009). Constraint programming-based column generation. 4OR, 7(2), 113\u2013137.","DOI":"10.1007\/s10288-009-0101-4"},{"key":"4474_CR29","doi-asserted-by":"crossref","unstructured":"Hahn, R. A., & Newman, A. M. (2008). Scheduling United States Coast Guard helicopter deployment and maintenance at Clearwater Air Station, Florida. Computers & Operations Research, 35(6), 1829\u20131843.","DOI":"10.1016\/j.cor.2006.09.015"},{"key":"4474_CR30","doi-asserted-by":"crossref","unstructured":"He, F., & Qu, R. (2012). A constraint programming based column generation approach to nurse rostering problems. Computers & Operations Research, 39(12), 3331\u20133343.","DOI":"10.1016\/j.cor.2012.04.018"},{"issue":"10","key":"4474_CR31","doi-asserted-by":"publisher","first-page":"1284","DOI":"10.1057\/palgrave.jors.2602300","volume":"58","author":"MET Horn","year":"2006","unstructured":"Horn, M. E. T., Jiang, H., & Kilby, P. (2006). Scheduling patrol boats and crews for the Royal Australian Navy. Journal of the Operational Research Society, 58(10), 1284\u20131293.","journal-title":"Journal of the Operational Research Society"},{"issue":"4","key":"4474_CR32","first-page":"1576","volume":"22","author":"YC Hsieh","year":"2015","unstructured":"Hsieh, Y. C., You, P. S., Lee, P. J., & Lee, Y. C. (2015). A novel encoding scheme based evolutionary approach for the bi-objective grid patrol routing problem with multiple vehicles. Scientia Iranica. Transaction B, Mechanical Engineering, 22(4), 1576\u20131585.","journal-title":"Scientia Iranica. Transaction B, Mechanical Engineering"},{"key":"4474_CR33","doi-asserted-by":"crossref","unstructured":"Irnich, S., & Desaulniers, G. (2005). Shortest path problems with resource constraints. In G. Desaulniers, J. Desrosiers, & M. M. Solomon (Eds.), Column generation (pp. 33\u201365). Springer.","DOI":"10.1007\/0-387-25486-2_2"},{"issue":"1","key":"4474_CR34","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.tre.2011.07.005","volume":"48","author":"BB Keskin","year":"2012","unstructured":"Keskin, B. B., Li, S., Steil, D., & Spiller, S. (2012). Analysis of an integrated maximum covering and patrol routing problem. Transportation Research Part E: Logistics and Transportation Review, 48(1), 215\u2013232.","journal-title":"Transportation Research Part E: Logistics and Transportation Review"},{"key":"4474_CR35","doi-asserted-by":"crossref","unstructured":"Kim, J., Song, B. D., & Morrison, J. R. (2013). On the scheduling of systems of UAVs and fuel service stations for long-term mission fulfillment. Journal of Intelligent & Robotic Systems, 70(1\u20134), 347\u2013359.","DOI":"10.1007\/s10846-012-9727-0"},{"key":"4474_CR36","doi-asserted-by":"publisher","unstructured":"L\u00fcbbecke, M. E. (2001). Engine scheduling by column generation (Doctoral dissertation). Braunschweig University of Technology. https:\/\/doi.org\/10.24355\/dbbs.084-200511080100-720","DOI":"10.24355\/dbbs.084-200511080100-720"},{"issue":"6","key":"4474_CR37","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1287\/opre.1050.0234","volume":"53","author":"ME L\u00fcbbecke","year":"2005","unstructured":"L\u00fcbbecke, M. E., & Desrosiers, J. (2005). Selected topics in column generation. Operations Research, 53(6), 1007\u20131023.","journal-title":"Operations Research"},{"key":"4474_CR38","doi-asserted-by":"crossref","unstructured":"Millar, H. H., & Russell, S. N. (2012). A model for fisheries patrol dispatch in the Canadian Atlantic offshore fishery. Ocean & Coastal Management, 60, 48\u201355.","DOI":"10.1016\/j.ocecoaman.2012.01.001"},{"key":"4474_CR39","doi-asserted-by":"crossref","unstructured":"Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and combinatorial optimization. Wiley.","DOI":"10.1002\/9781118627372"},{"issue":"5","key":"4474_CR40","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1002\/1520-6750(199110)38:5<669::AID-NAV3220380503>3.0.CO;2-Y","volume":"38","author":"WG Nulty","year":"1991","unstructured":"Nulty, W. G., & Ratliff, H. D. (1991). Interactive optimization methodology for fleet scheduling. Naval Research Logistics, 38(5), 669\u2013677.","journal-title":"Naval Research Logistics"},{"key":"4474_CR41","unstructured":"Shieh, E., Jain, M., Jiang, A. X., & Tambe, M. (2013). Efficiently solving joint activity based security games. In Proceedings of the 23rd international joint conference on artificial intelligence (pp. 346\u2013352). AAAI Press."},{"key":"4474_CR42","doi-asserted-by":"crossref","unstructured":"Smith, O. J., Boland, N., & Waterer, H. (2012). Solving shortest path problems with a weight constraint and replenishment arcs. Computers & Operations Research, 39(5), 964\u2013984.","DOI":"10.1016\/j.cor.2011.07.017"},{"key":"4474_CR43","doi-asserted-by":"crossref","unstructured":"Surendonk, T. J., & Chircop, P. A. (2020a). Detailed complexity proofs for the patrol boat scheduling problem with complete coverage (Technical note no. DST-Group-TN-2026). Canberra, Australian Capital Territory: Joint and Operations Analysis Division, Defence Science and Technology Group.","DOI":"10.1002\/nav.21900"},{"key":"4474_CR44","doi-asserted-by":"crossref","unstructured":"Surendonk, T. J., & Chircop, P. A. (2020b). On the computational complexity of the patrol boat scheduling problem with complete coverage. Naval Research Logistics, 67(4), 289\u2013299.","DOI":"10.1002\/nav.21900"},{"key":"4474_CR45","unstructured":"Vanderbeck, F. (1994). Decomposition and column generation for integer programs (Doctoral dissertation). Universite Catholique de Louvain. https:\/\/doi.org\/2078.1\/205381"},{"issue":"1","key":"4474_CR46","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1287\/opre.48.1.111.12453","volume":"48","author":"F Vanderbeck","year":"2000","unstructured":"Vanderbeck, F. (2000). On Dantzig\u2013Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Operations Research, 48(1), 111\u2013128.","journal-title":"Operations Research"},{"key":"4474_CR47","doi-asserted-by":"crossref","unstructured":"Vanderbeck, F. (2005). Implementing mixed integer column generation. In G. Desaulniers, J. Desrosiers, & M. M. Solomon (Eds.), Column generation (pp. 331\u2013358). Springer.","DOI":"10.1007\/0-387-25486-2_12"},{"issue":"5","key":"4474_CR48","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1287\/opre.1120.1085","volume":"60","author":"MR Wagner","year":"2012","unstructured":"Wagner, M. R., & Radovilsky, Z. (2012). Optimizing boat resources at the US Coast Guard: Deterministic and stochastic models. Operations Research, 60(5), 1035\u20131049.","journal-title":"Operations Research"},{"key":"#cr-split#-4474_CR49.1","unstructured":"Zadeh, H. S., Storey, I., & Lenarcic, J. (2009). NaMOS"},{"key":"#cr-split#-4474_CR49.2","doi-asserted-by":"crossref","unstructured":"Scheduling patrol boats and crews for the Royal Australian Navy. In 2009 IEEE aerospace conference (pp. 1-12).","DOI":"10.1109\/AERO.2009.4839720"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04474-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-021-04474-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04474-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T16:49:11Z","timestamp":1726505351000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-021-04474-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,20]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["4474"],"URL":"https:\/\/doi.org\/10.1007\/s10479-021-04474-6","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,20]]},"assertion":[{"value":"29 November 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}