IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v28y2014i1d10.1007_s10878-014-9732-2.html
   My bibliography  Save this article

Multi-depot vessel routing problem in a direction dependent wavefield

Author

Listed:
  • Michael J. Hirsch

    (ISEA TEK)

  • Daniel E. Schroeder

    (Raytheon Company, Intelligence, Information, and Services)

  • Alvaro Maggiar

    (Northwestern University)

  • Irina S. Dolinskaya

    (Northwestern University)

Abstract

Considerable research has been done on the vehicle routing problem and its variants; however only limited amount of existing work deals with possible environmental conditions and their effects on the vehicle routes. This paper presents the multiple-depot vehicle routing problem for surface vessels, where the vehicles must traverse a time-invariant direction-dependent medium. Our model captures environmental effects and vessel dynamics on the considered paths. Three heuristic solution methods are developed and tested on simulated scenarios. The first approach exactly solves an approximate formulation of the problem, the second approximately solves an approximate problem formulation, while the third approximately solves the exact problem. Performance of the algorithms are compared to assess the tradeoff between computational cost and quality of the found solutions.

Suggested Citation

  • Michael J. Hirsch & Daniel E. Schroeder & Alvaro Maggiar & Irina S. Dolinskaya, 2014. "Multi-depot vessel routing problem in a direction dependent wavefield," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 38-57, July.
    • Handle: RePEc:spr:jcomop:v:28:y:2014:i:1:d:10.1007_s10878-014-9732-2
    DOI: 10.1007/s10878-014-9732-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-014-9732-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-014-9732-2?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. Thibaut Vidal & Teodor Gabriel Crainic & Michel Gendreau & Nadia Lahrichi & Walter Rei, 2012. "A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems," Operations Research, INFORMS, vol. 60(3), pages 611-624, June.
    2. Hirsch, M.J. & Pardalos, P.M. & Resende, M.G.C., 2010. "Speeding up continuous GRASP," European Journal of Operational Research, Elsevier, vol. 205(3), pages 507-521, September.
    3. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    4. Laporte, Gilbert, 1992. "The vehicle routing problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(3), pages 345-358, June.
    5. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    6. Michael J. Hirsch & Héctor J. Ortiz-Peña & Chris Eck, 2012. "Cooperative Tracking of Multiple Targets by a Team of Autonomous UAVs," International Journal of Operations Research and Information Systems (IJORIS), IGI Global, vol. 3(1), pages 53-73, January.
    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. Almoustafa, Samira & Hanafi, Said & Mladenović, Nenad, 2013. "New exact method for large asymmetric distance-constrained vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 226(3), pages 386-394.
    2. Rahma Lahyani & Leandro C. Coelho & Jacques Renaud, 2018. "Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(1), pages 125-157, January.
    3. Martinhon, Carlos & Lucena, Abilio & Maculan, Nelson, 2004. "Stronger K-tree relaxations for the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 158(1), pages 56-71, October.
    4. Majsa Ammouriova & Massimo Bertolini & Juliana Castaneda & Angel A. Juan & Mattia Neroni, 2022. "A Heuristic-Based Simulation for an Education Process to Learn about Optimization Applications in Logistics and Transportation," Mathematics, MDPI, vol. 10(5), pages 1-18, March.
    5. Letchford, Adam N. & Salazar-González, Juan-José, 2019. "The Capacitated Vehicle Routing Problem: Stronger bounds in pseudo-polynomial time," European Journal of Operational Research, Elsevier, vol. 272(1), pages 24-31.
    6. Schulz, Arne & Pfeiffer, Christian, 2024. "Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems," European Journal of Operational Research, Elsevier, vol. 312(2), pages 456-472.
    7. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    8. Sandra Zajac, 2018. "On a two-phase solution approach for the bi-objective k-dissimilar vehicle routing problem," Journal of Heuristics, Springer, vol. 24(3), pages 515-550, June.
    9. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    10. Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2016. "An adaptive large-neighborhood search heuristic for a multi-period vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 95-123.
    11. Shengbin Wang & Weizhen Rao & Yuan Hong, 2020. "A distance matrix based algorithm for solving the traveling salesman problem," Operational Research, Springer, vol. 20(3), pages 1505-1542, September.
    12. Lo, Shirleen Lee Yuen & How, Bing Shen & Leong, Wei Dong & Teng, Sin Yong & Rhamdhani, Muhammad Akbar & Sunarso, Jaka, 2021. "Techno-economic analysis for biomass supply chain: A state-of-the-art review," Renewable and Sustainable Energy Reviews, Elsevier, vol. 135(C).
    13. Said Dabia & Stefan Ropke & Tom van Woensel, 2019. "Cover Inequalities for a Vehicle Routing Problem with Time Windows and Shifts," Transportation Science, INFORMS, vol. 53(5), pages 1354-1371, September.
    14. Mancini, Simona & Gansterer, Margaretha & Hartl, Richard F., 2021. "The collaborative consistent vehicle routing problem with workload balance," European Journal of Operational Research, Elsevier, vol. 293(3), pages 955-965.
    15. Hughes, Michael S. & Lunday, Brian J. & Weir, Jeffrey D. & Hopkinson, Kenneth M., 2021. "The multiple shortest path problem with path deconfliction," European Journal of Operational Research, Elsevier, vol. 292(3), pages 818-829.
    16. Julia Rieck & Jürgen Zimmermann & Matthias Glagow, 2007. "Tourenplanung mittelständischer Speditionsunternehmen in Stückgutkooperationen: Modellierung und heuristische Lösungsverfahren," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 17(4), pages 365-388, January.
    17. David Applegate & William Cook & Sanjeeb Dash & André Rohe, 2002. "Solution of a Min-Max Vehicle Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 14(2), pages 132-143, May.
    18. Tânia Rodrigues Pereira Ramos & Maria Isabel Gomes & Ana Paula Barbosa-Póvoa, 2020. "A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(1), pages 75-110, March.
    19. Ines Sbai & Saoussen Krichen & Olfa Limam, 2022. "Two meta-heuristics for solving the capacitated vehicle routing problem: the case of the Tunisian Post Office," Operational Research, Springer, vol. 22(1), pages 507-549, March.
    20. Segerstedt, Anders, 2014. "A simple heuristic for vehicle routing – A variant of Clarke and Wright's saving method," International Journal of Production Economics, Elsevier, vol. 157(C), pages 74-79.

    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:spr:jcomop:v:28:y:2014:i:1:d:10.1007_s10878-014-9732-2. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.