We apply branch-and-price guided search to a real-world maritime inventory routing problem, in which the inventory of a single product, which is produced and consumed at multiple sites, and its transport, which is done with a heterogeneous fleet of vessels, is managed over a finite horizon. Computational experiments demonstrate that branch-and-price guided search quickly produces solutions that are near-optimal and of better quality than those produced by a state-of-the-art, commercial integer programming solver that is given much more time. We also develop local search schemes to further reduce the time needed to find high quality solutions and present computational evidence of their efficacy.