IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v59y2008i11d10.1057_palgrave.jors.2602469.html
   My bibliography  Save this article

A tabu search heuristic for a routing problem arising in servicing of offshore oil and gas platforms

Author

Listed:
  • I Gribkovskaia

    (Molde University College)

  • G Laporte

    (HEC Montréal)

  • A Shlopak

    (Molde University College)

Abstract

This paper introduces a pickup and delivery problem encountered in servicing of offshore oil and gas platforms in the Norwegian Sea. A single vessel must perform pickups and deliveries at several offshore platforms. All delivery demands originate at a supply base and all pickup demands are also destined to the base. The vessel capacity may never be exceeded along its route. In addition, the amount of space available for loading and unloading operations is limited at each platform. The problem, called the Single Vehicle Pickup and Delivery Problem with Capacitated Customers consists of designing a least cost vehicle (vessel) route starting and ending at the depot (base), visiting each customer (platform), and such that there is always sufficient capacity in the vehicle and at the customer location to perform the pickup and delivery operations. This paper describes several construction heuristics as well as a tabu search algorithm. Computational results are presented.

Suggested Citation

  • 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.
    • Handle: RePEc:pal:jorsoc:v:59:y:2008:i:11:d:10.1057_palgrave.jors.2602469
    DOI: 10.1057/palgrave.jors.2602469
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2602469
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2602469?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. Mosheiov, Gur, 1994. "The Travelling Salesman Problem with pick-up and delivery," European Journal of Operational Research, Elsevier, vol. 79(2), pages 299-310, December.
    2. Gribkovskaia, Irina & Halskau, Oyvind sr. & Laporte, Gilbert & Vlcek, Martin, 2007. "General solutions to the single vehicle routing problem with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 180(2), pages 568-584, July.
    3. Nagy, Gabor & Salhi, Said, 2005. "Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 162(1), pages 126-141, April.
    4. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Christiansen, Marielle & Fagerholt, Kjetil & Nygreen, Bjørn & Ronen, David, 2013. "Ship routing and scheduling in the new millennium," European Journal of Operational Research, Elsevier, vol. 228(3), pages 467-483.
    2. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    3. Ulsrud, Karl Petter & Vandvik, Anders Helgeland & Ormevik, Andreas Breivik & Fagerholt, Kjetil & Meisel, Frank, 2022. "A time-dependent vessel routing problem with speed optimization," European Journal of Operational Research, Elsevier, vol. 303(2), pages 891-907.
    4. Qian, Fubin & Gribkovskaia, Irina & Laporte, Gilbert & Halskau sr., Øyvind, 2012. "Passenger and pilot risk minimization in offshore helicopter transportation," Omega, Elsevier, vol. 40(5), pages 584-593.
    5. Cruz, Roberto & Bergsten Mendes, André & Bahiense, Laura & Wu, Yue, 2019. "Integrating berth allocation decisions in a fleet composition and periodic routing problem of platform supply vessels," European Journal of Operational Research, Elsevier, vol. 275(1), pages 334-346.
    6. Liu, Ran & Xie, Xiaolan & Garaix, Thierry, 2014. "Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics," Omega, Elsevier, vol. 47(C), pages 17-32.
    7. Amiri, Mohsen & Amin, Saman Hassanzadeh & Tavakkoli-Moghaddam, Reza, 2019. "A Lagrangean decomposition approach for a novel two-echelon node-based location-routing problem in an offshore oil and gas supply chain," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 96-114.
    8. Halvorsen-Weare, Elin E. & Fagerholt, Kjetil & Nonås, Lars Magne & Asbjørnslett, Bjørn Egil, 2012. "Optimal fleet composition and periodic routing of offshore supply vessels," European Journal of Operational Research, Elsevier, vol. 223(2), pages 508-517.
    9. Vieira, Bruno S. & Ribeiro, Glaydston M. & Bahiense, Laura & Cruz, Roberto & Mendes, André B. & Laporte, Gilbert, 2021. "Exact and heuristic algorithms for the fleet composition and periodic routing problem of offshore supply vessels with berth allocation decisions," European Journal of Operational Research, Elsevier, vol. 295(3), pages 908-923.
    10. Maciel M. Queiroz & André Bergsten Mendes, 2020. "Critical Success Factors of the Brazilian Offshore Support Vessel Industry: A Flexible Systems Approach," Global Journal of Flexible Systems Management, Springer;Global Institute of Flexible Systems Management, vol. 21(1), pages 33-48, June.
    11. Ksciuk, Jana & Kuhlemann, Stefan & Tierney, Kevin & Koberstein, Achim, 2023. "Uncertainty in maritime ship routing and scheduling: A Literature review," European Journal of Operational Research, Elsevier, vol. 308(2), pages 499-524.

    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. Yu, Junfang & Dong, Yuanyuan, 2013. "Maximizing profit for vehicle routing under time and weight constraints," International Journal of Production Economics, Elsevier, vol. 145(2), pages 573-583.
    2. Hoff, Arild & Gribkovskaia, Irina & Laporte, Gilbert & Løkketangen, Arne, 2009. "Lasso solution strategies for the vehicle routing problem with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 192(3), pages 755-766, February.
    3. Gábor Nagy & Niaz A. Wassan & M. Grazia Speranza & Claudia Archetti, 2015. "The Vehicle Routing Problem with Divisible Deliveries and Pickups," Transportation Science, INFORMS, vol. 49(2), pages 271-294, May.
    4. Pandelis, D.G. & Karamatsoukis, C.C. & Kyriakidis, E.G., 2013. "Finite and infinite-horizon single vehicle routing problems with a predefined customer sequence and pickup and delivery," European Journal of Operational Research, Elsevier, vol. 231(3), pages 577-586.
    5. Maria João Santos & Pedro Amorim & Alexandra Marques & Ana Carvalho & Ana Póvoa, 2020. "The vehicle routing problem with backhauls towards a sustainability perspective: a review," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 358-401, July.
    6. Ganesh, K. & Narendran, T.T., 2007. "CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up," European Journal of Operational Research, Elsevier, vol. 178(3), pages 699-717, May.
    7. T-S Chang & Y-F Liao, 2011. "Routing strategies for integrating forward distribution and reverse collection," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(6), pages 971-981, June.
    8. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Chris T., 2010. "An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries," European Journal of Operational Research, Elsevier, vol. 202(2), pages 401-411, April.
    9. Phuong Khanh Nguyen & Teodor Gabriel Crainic & Michel Toulouse, 2017. "Multi-trip pickup and delivery problem with time windows and synchronization," Annals of Operations Research, Springer, vol. 253(2), pages 899-934, June.
    10. Liu, Ran & Xie, Xiaolan & Augusto, Vincent & Rodriguez, Carlos, 2013. "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care," European Journal of Operational Research, Elsevier, vol. 230(3), pages 475-486.
    11. Michael E. Fragkos & Vasileios Zeimpekis & Vasilis Koutras & Ioannis Minis, 2022. "Supply planning for shelters and emergency management crews," Operational Research, Springer, vol. 22(1), pages 741-777, March.
    12. Roel G. van Anholt & Leandro C. Coelho & Gilbert Laporte & Iris F. A. Vis, 2016. "An Inventory-Routing Problem with Pickups and Deliveries Arising in the Replenishment of Automated Teller Machines," Transportation Science, INFORMS, vol. 50(3), pages 1077-1091, August.
    13. Gribkovskaia, Irina & Halskau, Oyvind sr. & Laporte, Gilbert & Vlcek, Martin, 2007. "General solutions to the single vehicle routing problem with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 180(2), pages 568-584, July.
    14. Qian, Fubin & Gribkovskaia, Irina & Laporte, Gilbert & Halskau sr., Øyvind, 2012. "Passenger and pilot risk minimization in offshore helicopter transportation," Omega, Elsevier, vol. 40(5), pages 584-593.
    15. Qiuping Ni & Yuanxiang Tang, 2023. "A Bibliometric Visualized Analysis and Classification of Vehicle Routing Problem Research," Sustainability, MDPI, vol. 15(9), pages 1-37, April.
    16. Niaz A. Wassan & A. Hameed Wassan & Gábor Nagy, 2008. "A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries," Journal of Combinatorial Optimization, Springer, vol. 15(4), pages 368-386, May.
    17. Hernández-Pérez, Hipólito & Rodríguez-Martín, Inmaculada & Salazar-González, Juan-José, 2016. "A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 251(1), pages 44-52.
    18. Bruno P. Bruck & Manuel Iori, 2017. "Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries," Operations Research, INFORMS, vol. 65(6), pages 1597-1614, December.
    19. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    20. repec:dar:wpaper:62383 is not listed on IDEAS
    21. Salazar-González, Juan-José & Santos-Hernández, Beatriz, 2015. "The split-demand one-commodity pickup-and-delivery travelling salesman problem," Transportation Research Part B: Methodological, Elsevier, vol. 75(C), pages 58-73.

    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:pal:jorsoc:v:59:y:2008:i:11:d:10.1057_palgrave.jors.2602469. 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.palgrave-journals.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.