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.