A traveling salesman problem with pickups and deliveries, time windows and draft limits: Case study from chemical shipping

• A forward dynamic programming algorithm is proposed to solve an in-port routing problem.
• The imposition of label extension rules significantly increase computational efficiency.
• The proposed algorithm greatly outperforms the commercial solver Xpress.
• The approach can efficiently solve real problems in the chemical shipping industry.

This paper introduces and studies a real in-port ship routing and scheduling problem faced by chemical shipping companies. We show that this problem can be modeled as a Traveling Salesman Problem with Pickups and Deliveries, Time Windows and Draft Limits (TSPPD-TWDL). We propose a mathematical formulation for the TSPPD-TWDL and suggest a solution method based on forward dynamic programming (DP) to solve the problem. A set of label extension rules are also proposed to accelerate and enhance the performance of the algorithm. Computational studies show that the label extension rules are essential to the DP-algorithm, and the proposed solution method is able to solve real-sized in-port routing and scheduling problems in chemical shipping efficiently.