Skip to main content
SpringerLink
Log in

A tabu search heuristic for ship routing and scheduling with flexible cargo quantities

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

This paper presents a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies typically have a certain amount of contract cargoes that they are committed to carry, while trying to maximize their profit from optional spot cargoes. The cargo quantities are often flexible within an interval. Therefore, interwoven with the routing and scheduling decisions, the planner also has to decide the optimal cargo quantities. A tabu search algorithm embedding a specialized heuristic for deciding the optimal cargo quantities in each route is proposed to solve the problem. Computational results show that the heuristic gives optimal or near-optimal solutions to real-life cases of the problem within reasonable time. It is also shown that utilizing the flexibility in cargo quantities gives significantly improved solutions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Archetti, C., Speranza, M.G., Hertz, A.: A tabu search algorithm for the split delivery vehicle routing problem. Transp. Sci. 40(1), 64–73 (2006a)

    Article  Google Scholar 

  • Archetti, C., Savelsbergh, M.W.P., Speranza, M.G.: Worst-case analysis for split delivery vehicle routing problems. Transp. Sci. 40(2), 226–234 (2006b)

    Article  Google Scholar 

  • Bausch, D.O., Brown, G.G., Ronen, D.: Scheduling short-term marine transport of bulk products. Marit. Policy Manag. 25(4), 335–348 (1998)

    Article  Google Scholar 

  • Brønmo, G., Christiansen, M., Fagerholt, K., Nygreen, B.: A multi-start local search heuristic for ship scheduling—a computational study. Comput. Oper. Res. 34(3), 884–899 (2007a)

    Article  Google Scholar 

  • Brønmo, G., Christiansen, M., Nygreen, B.: Ship routing and scheduling with flexible cargo sizes. J. Oper. Res. Soc. 58(9), 1167–1177 (2007b)

    Article  Google Scholar 

  • Brønmo, G., Nygreen, B., Lysgaard, J.: Column generation approaches to ship scheduling with flexible cargo sizes. Working paper, Norwegian University of Science and Technology (2008)

  • Campbell, A.M.: The vehicle routing problem with demand range. Ann. Oper. Res. 144, 99–110 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  • Campbell, A.M., Savelsbergh, M.W.P.: Delivery volume optimization. Transp. Sci. 38(2), 210–233 (2004)

    Article  Google Scholar 

  • Campbell, A.M., Clarke, L.W., Savelsbergh, M.W.P.: Inventory routing in practice. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, pp. 309–330. SIAM, Philadelphia (2002)

    Google Scholar 

  • Christiansen, M., Nygreen, B.: A method for solving ship routing problems with inventory constraints. Ann. Oper. Res. 81, 357–378 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  • Christiansen, M., Fagerholt, K., Ronen, D.: Ship routing and scheduling: Status and perspectives. Transp. Sci. 38(1), 1–18 (2004)

    Article  Google Scholar 

  • Christiansen, M., Fagerholt, K., Nygreen, B., Ronen, D.: Maritime transportation. In: Barnhart, C., Laporte, G. (eds.) Handbooks in Operations Research and Management Science: Transportation, p. 113. North-Holland, Amsterdam (2007)

    Google Scholar 

  • Cordeau, J.-F., Laporte, G.: A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transp. Res. Part B 37, 579–594 (2003)

    Article  Google Scholar 

  • Cordeau, J.-F., Laporte, G., Mercier, A.: A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. 52, 928–936 (2001)

    Article  MATH  Google Scholar 

  • Desrosiers, J., Dumas, Y., Solomon, M.M., Soumis, F.: Time constrained routing and scheduling. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds.) Handbooks in Operations Research and Management Science: Network Routing, pp. 35–139. North Holland, Amsterdam (1995)

    Google Scholar 

  • Dror, M., Laporte, G., Trudeau, P.: Vehicle routing with split deliveries. Discrete Appl. Math. 50, 239–254 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  • Fagerholt, K.: A computer-based decision support system for vessel fleet scheduling—experience and future research. Decis. Support Syst. 37(1), 35–47 (2004)

    Article  Google Scholar 

  • Flatberg, T., Haavardtun, H., Kloster, O., Løkketangen, A.: Combining exact and heuristic methods for solving a vessel routing problem with inventory constraints and time windows. Ric. Oper. 29(91), 55–68 (2000)

    Google Scholar 

  • Ho, S.C., Haugland, D.: A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Comput. Oper. Res. 31, 1947–1964 (2004)

    Article  MATH  Google Scholar 

  • Kim, S.-H., Lee, K.-K.: An optimisation-based decision support system for ship scheduling. Comput. Ind. Eng. 33(3–4), 689–692 (1997)

    Google Scholar 

  • Persson, J.A., Göthe-Lundgren, M.: Shipment planning at oil refineries using column generation and valid inequalities. Eur. J. Oper. Res. 163, 631–652 (2005)

    Article  MATH  Google Scholar 

  • Ronen, D.: Marine inventory routing: Shipments planning. J. Oper. Res. Soc. 53, 108–114 (2002)

    Article  MATH  Google Scholar 

  • Sherali, H.D., Al-Yakoob, S.M., Hassan, M.M.: Fleet management models and algorithms for an oil-tanker routing and scheduling problem. IIE Trans. 31, 395–406 (1999)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Marine Technology, Norwegian University of Science and Technology, Trondheim, Norway

    Jarl Eirik Korsvik & Kjetil Fagerholt

  2. Norwegian Marine Technology Research Institute, Trondheim, Norway

    Jarl Eirik Korsvik

  3. Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, Trondheim, Norway

    Kjetil Fagerholt

Authors
  1. Jarl Eirik Korsvik
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kjetil Fagerholt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kjetil Fagerholt.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Korsvik, J.E., Fagerholt, K. A tabu search heuristic for ship routing and scheduling with flexible cargo quantities. J Heuristics 16, 117–137 (2010). https://doi.org/10.1007/s10732-008-9092-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-008-9092-0

Keywords

Search

Navigation