Cruise itinerary schedule design

ABSTRACT

The Cruise Itinerary Schedule Design (CISD) problem determines the optimal sequence of a given set of ports of call (a port of call is an intermediate stop in a cruise itinerary) and the arrival and departure times at each port of call in order to maximize the monetary value of the utility at ports of call minus the fuel cost. To solve this problem, in view of the practical observations that most cruise itineraries do not have many ports of call, we first enumerate all sequences of ports of call and then optimize the arrival and departure times at each port of call by developing a dynamic programming approach. To improve the computational efficiency, we propose effective bounds on the monetary value of each sequence of ports of call, eliminating non-optimal sequences without invoking the dynamic programming algorithm. Extensive computational experiments are conducted and the results show that, first, using the bounds on the profit of each sequence of ports of call considerably improves the computational efficiency; second, the total profit of the cruise itinerary is sensitive to the fuel price and hence an accurate estimation of the fuel price is highly desirable; third, the optimal sequence of ports of call is not necessarily the sequence with the shortest voyage distance, especially when the ports do not have a natural geographic sequence.

KEYWORDS:

• Cruise shipping
• schedule design
• itinerary planning
• dynamic programming

Acknowledgements

The authors thank Professor Mark Daskin and three reviewers for their valuable comments and constructive suggestions that significantly improved the quality of this article.

Funding

This research is supported by the National Natural Science Foundation of China (71671107, 71422007), Shanghai Social Science Research Program (2014BGL006).

Notes

1 It is often considered that one cabin has two beds (two lower berths) when calculating the capacity of cruise ships. Any extra beds in a cabin are referred to as “upper berths.”  The actual average number of beds per cabin in a cruise ship is usually higher than two.

Additional information

Notes on contributors

Shuaian Wang

Shuaian Wangis an Associate Professor of Maritime Studies at the Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University. He received his Ph.D. in Transportation Engineering from the National University of Singapore. His research interests include container shipping, port and maritime logistics, cruise shipping, intermodal freight transportation, and transportation engineering. He serves on the editorial boards of Transportation Research Part B, Transportation Research Part E, and Transportation Letters. His work is published in academic journals including IISE Transactions, Naval Research Logistics, European Journal of Operational Research, Transportation Science, Computers and Operations Research, Journal of the Operational Research Society, Transportation Research Parts A, B, C, and E, and Maritime Policy & Management.

Kai Wang

Kai Wang is a Ph.D. candidate in the Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University. His research interests include cruise shipping, port logistics, maritime transportation, and optimization algorithms. He has published papers in academic journals including Transportation Research Part B, Naval Research Logistics, Computers and Operations Research, IEEE Transactions on Systems, Man, and Cybernetics: Systems, etc.

Lu Zhen

Lu Zhen is a Professor and a Vice Dean in the School of Management, Shanghai University, Shanghai, People's Republic of China. He obtained B.E. and Ph.D. degrees from Shanghai Jiao Tong University in 2003 and 2008, respectively. He then worked as a post-doctoral research fellow at the National University of Singapore from 2008 to 2010. Since 2011, he has worked at the Department of Management Science and Engineering, School of Management, Shanghai University. His research interests include port operations, maritime logistics, supply chain management, and knowledge management. He has published more than 40 papers in reputable journals such as Transportation Science, Transportation Research Part B, Naval Research Logistics, and European Journal of Operational Research. He serves as an Associate Editor of IMA Journal of Management Mathematics, Asia-Pacific Journal of Operational Research, Journal of Industrial and Production Engineering, etc.

Xiaobo Qu

Xiaobo Qu is a Senior Lecturer in transport engineering with the School of Civil and Environmental Engineering, University of Technology Sydney, Sydney, Australia. He received his Ph.D. in Transport Engineering from the National University of Singapore. His research is focused on practically improving transport safety, efficiency, equity, and sustainability through traffic flow and network modeling and optimization. His work is published in academic journals including IISE Transactions, Transportation Research Part A, Part B, Part C, Part E, European Journal of Operational Research, Accident Analysis and Prevention, and Journal of Transportation Engineering – ASCE. He is a recipient of the prestigious Endeavour Cheung Kong Fellowship in 2017.