IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v320y2025i1p115-131.html
   My bibliography  Save this article

Exact and heuristic approaches for the ship-to-shore problem

Author

Listed:
  • Wagenvoort, M.
  • Bouman, P.C.
  • van Ee, M.
  • Lamballais Tessensohn, T.
  • Postek, K.

Abstract

After a natural disaster such as a hurricane or flooding, the navy can help by bringing supplies, clearing roads, and evacuating victims. If destinations cannot be reached over land, resources can be transported using smaller ships and helicopters, called connectors. To start aid on land as soon as possible this must be done efficiently. In the ship-to-shore problem, trips with their accompanying resources are determined while minimising the makespan. Limited (un)loading capacities, heterogeneous connector characteristics and constraints posed by priority of the resources and grouping of the resources (resource sets) all require that the connector trips are carefully coordinated. Despite the criticality of this coordination, existing literature does not consider resource sets and has only developed heuristics. We provide a formulation that incorporates resource sets and develop (i) an exact branch-and-price algorithm and (ii) a tailored greedy heuristic that can provide upper bounds. We find that 84% of our 98 practical instances terminate within an hour in on average 80 s. Our greedy heuristic can find optimal solutions in two-thirds of these instances, mostly for instances that are very constrained in terms of the delivery order of resources. When improvements are found by the branch-and-price algorithm, the average gap with the makespan of the greedy solution is 40% and, in most cases, these improvements are obtained within three minutes. For the 20 artificial instances, the greedy heuristic has consistent performance on the different types of instances. For these artificial instances improvements of on average 35% are found in reasonable time.

Suggested Citation

  • Wagenvoort, M. & Bouman, P.C. & van Ee, M. & Lamballais Tessensohn, T. & Postek, K., 2025. "Exact and heuristic approaches for the ship-to-shore problem," European Journal of Operational Research, Elsevier, vol. 320(1), pages 115-131.
  • Handle: RePEc:eee:ejores:v:320:y:2025:i:1:p:115-131
    DOI: 10.1016/j.ejor.2024.08.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724006404
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2024.08.017?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. P. Chardaire & G. P. McKeown & S. A. Verity-Harrison & S. B. Richardson, 2005. "Solving a Time-Space Network Formulation for the Convoy Movement Problem," Operations Research, INFORMS, vol. 53(2), pages 219-230, April.
    2. Julia Rieck & Jürgen Zimmermann, 2010. "A new mixed integer linear model for a rich vehicle routing problem with docking constraints," Annals of Operations Research, Springer, vol. 181(1), pages 337-358, December.
    3. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Chris T., 2016. "The Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries and Two-Dimensional Loading Constraints," European Journal of Operational Research, Elsevier, vol. 251(2), pages 369-386.
    4. I Gribkovskaia & G Laporte & A Shlopak, 2008. "A tabu search heuristic for a routing problem arising in servicing of offshore oil and gas platforms," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(11), pages 1449-1459, November.
    5. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    6. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    7. Ursavas, Evrim, 2017. "A benders decomposition approach for solving the offshore wind farm installation planning at the North Sea," European Journal of Operational Research, Elsevier, vol. 258(2), pages 703-714.
    8. Schneider, M. & Stenger, A. & Goeke, D., 2014. "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62382, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    9. Behnke, Martin & Kirschstein, Thomas & Bierwirth, Christian, 2021. "A column generation approach for an emission-oriented vehicle routing problem on a multigraph," European Journal of Operational Research, Elsevier, vol. 288(3), pages 794-809.
    10. Natashia Boland & Mike Hewitt & Luke Marshall & Martin Savelsbergh, 2019. "The price of discretizing time: a study in service network design," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 195-216, June.
    11. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.
    12. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    13. Bredström, David & Rönnqvist, Mikael, 2007. "A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints," Discussion Papers 2007/7, Norwegian School of Economics, Department of Business and Management Science.
    14. Zhao, Xing & Ji, Kang & Xu, Peng & Qian, Wen-wen & Ren, Gang & Shan, Xiao-nian, 2020. "A round-trip bus evacuation model with scheduling and routing planning," Transportation Research Part A: Policy and Practice, Elsevier, vol. 137(C), pages 285-300.
    15. Hiermann, Gerhard & Puchinger, Jakob & Ropke, Stefan & Hartl, Richard F., 2016. "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, Elsevier, vol. 252(3), pages 995-1018.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Xu, Min & Meng, Qiang, 2019. "Fleet sizing for one-way electric carsharing services considering dynamic vehicle relocation and nonlinear charging profile," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 23-49.
    2. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    3. Schmidt, Jeanette & Tilk, Christian & Irnich, Stefan, 2024. "Using public transport in a 2-echelon last-mile delivery network," European Journal of Operational Research, Elsevier, vol. 317(3), pages 827-840.
    4. Alexander Jungwirth & Guy Desaulniers & Markus Frey & Rainer Kolisch, 2022. "Exact Branch-Price-and-Cut for a Hospital Therapist Scheduling Problem with Flexible Service Locations and Time-Dependent Location Capacity," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1157-1175, March.
    5. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    6. Hiermann, Gerhard & Hartl, Richard F. & Puchinger, Jakob & Vidal, Thibaut, 2019. "Routing a mix of conventional, plug-in hybrid, and electric vehicles," European Journal of Operational Research, Elsevier, vol. 272(1), pages 235-248.
    7. Gutiérrez-Jarpa, Gabriel & Desaulniers, Guy & Laporte, Gilbert & Marianov, Vladimir, 2010. "A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows," European Journal of Operational Research, Elsevier, vol. 206(2), pages 341-349, October.
    8. Qin, Hu & Moriakin, Anton & Xu, Gangyan & Li, Jiliu, 2024. "The generator distribution problem for base stations during emergency power outage: A branch-and-price-and-cut approach," European Journal of Operational Research, Elsevier, vol. 318(3), pages 752-767.
    9. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    10. Jiliu Li & Zhixing Luo & Roberto Baldacci & Hu Qin & Zhou Xu, 2023. "A New Exact Algorithm for Single-Commodity Vehicle Routing with Split Pickups and Deliveries," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 31-49, January.
    11. Raeesi, Ramin & Zografos, Konstantinos G., 2022. "Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping," European Journal of Operational Research, Elsevier, vol. 301(1), pages 82-109.
    12. Shyam S. G. Perumal & Jesper Larsen & Richard M. Lusby & Morten Riis & Tue R. L. Christensen, 2022. "A column generation approach for the driver scheduling problem with staff cars," Public Transport, Springer, vol. 14(3), pages 705-738, October.
    13. Paul A. Chircop & Timothy J. Surendonk & Menkes H. L. van den Briel & Toby Walsh, 2022. "On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage," Annals of Operations Research, Springer, vol. 312(2), pages 723-760, May.
    14. Alvo, Matías & Angulo, Gustavo & Klapp, Mathias A., 2021. "An exact solution approach for an electric bus dispatch problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    15. Zeighami, Vahid & Saddoune, Mohammed & Soumis, François, 2020. "Alternating Lagrangian decomposition for integrated airline crew scheduling problem," European Journal of Operational Research, Elsevier, vol. 287(1), pages 211-224.
    16. Koza, David Franz, 2019. "Liner shipping service scheduling and cargo allocation," European Journal of Operational Research, Elsevier, vol. 275(3), pages 897-915.
    17. Tilk, Christian & Rothenbächer, Ann-Kathrin & Gschwind, Timo & Irnich, Stefan, 2017. "Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster," European Journal of Operational Research, Elsevier, vol. 261(2), pages 530-539.
    18. Thomas Breugem & Twan Dollevoet & Dennis Huisman, 2022. "Is Equality Always Desirable? Analyzing the Trade-Off Between Fairness and Attractiveness in Crew Rostering," Management Science, INFORMS, vol. 68(4), pages 2619-2641, April.
    19. Bouarab, Hocine & El Hallaoui, Issmail & Metrane, Abdelmoutalib & Soumis, François, 2017. "Dynamic constraint and variable aggregation in column generation," European Journal of Operational Research, Elsevier, vol. 262(3), pages 835-850.
    20. Christian Tilk & Nicola Bianchessi & Michael Drexl & Stefan Irnich & Frank Meisel, 2018. "Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem," Transportation Science, INFORMS, vol. 52(2), pages 300-319, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:320:y:2025:i:1:p:115-131. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.