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. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    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. Dessouky, Maged M & Shao, Yihuan E, 2017. "Routing Strategies for Efficient Deployment of Alternative Fuel Vehicles for Freight Delivery," Institute of Transportation Studies, Working Paper Series qt0nj024qn, Institute of Transportation Studies, UC Davis.
    2. 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.
    3. 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.
    4. 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.
    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. Kritikos, Manolis N. & Ioannou, George, 2010. "The balanced cargo vehicle routing problem with time windows," International Journal of Production Economics, Elsevier, vol. 123(1), pages 42-51, January.
    7. 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.
    8. 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.
    9. Schyns, M., 2015. "An ant colony system for responsive dynamic vehicle routing," European Journal of Operational Research, Elsevier, vol. 245(3), pages 704-718.
    10. 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.
    11. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    12. 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.
    13. Campelo, Pedro & Neves-Moreira, Fábio & Amorim, Pedro & Almada-Lobo, Bernardo, 2019. "Consistent vehicle routing problem with service level agreements: A case study in the pharmaceutical distribution sector," European Journal of Operational Research, Elsevier, vol. 273(1), pages 131-145.
    14. Xiao, Yiyong & Konak, Abdullah, 2016. "The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 146-166.
    15. 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.
    16. 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.
    17. 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.
    18. 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).
    19. Max Leyerer & Marc-Oliver Sonneberg & Maximilian Heumann & Tim Kammann & Michael H. Breitner, 2019. "Individually Optimized Commercial Road Transport: A Decision Support System for Customizable Routing Problems," Sustainability, MDPI, vol. 11(20), pages 1-21, October.
    20. Benjamin C. Shelbourne & Maria Battarra & Chris N. Potts, 2017. "The Vehicle Routing Problem with Release and Due Dates," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 705-723, November.

    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.