A MILP-based Column Generation Strategy for Solving Ship Routing and Scheduling Problems

M. COCCOLA; R. DONDO; C.A. MÉNDEZ

Montevideo

Workshop; VIII ALIO/EURO Workshop on Applied Combinatorial Optimization; 2014

Universidad de la República

This paper presents a novel column generation algorithm for the routing and scheduling of a fleet of multiparcel chemical tankers. In our procedure, the conventional dynamic programming route generator is replaced by an efficient continuous-time MILP-slave problem. The proposed approach outperforms the exact optimization model and other heuristic decomposition methods presented in the literature to solve a real-world example of a shipping company operating in the Asia Pacific Region.