Dynamic programming algorithms for selection of waste disposal ports in cruise shipping

Shuaian Wang, Lu Zhen, Dan Zhuge

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)


The cruise industry has maintained a steady growth in the past 20 years. Due to the large number of cruise passengers and regulations on sea environment protection, determining at which ports to dispose of the waste generated onboard a cruise ship is a key decision to reduce the cost for a cruise company. We address four versions of the problem: the cruise itinerary is either static or dynamic and the amount of waste generated on each voyage leg is either deterministic or stochastic. We propose a polynomial-time solution algorithm for the static deterministic model, and the idea of the algorithm can also be used to solve the static stochastic model and the dynamic deterministic model. Second, we identify the structure of the optimal policy to the dynamic stochastic problem, based on which an efficient dynamic programming algorithm is developed. Extensive numerical experiments derived from problems of real-case scales demonstrate the efficiency of the proposed algorithms.

Original languageEnglish
Pages (from-to)235-248
Number of pages14
JournalTransportation Research Part B: Methodological
Publication statusPublished - Feb 2018


  • Cruise ship
  • Dynamic programming
  • Waste disposal
  • Water transportation

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Cite this