Flexible solutions to maritime inventory routing problems with delivery time windows

•We develop a general Lagrangian heuristic scheme to deal with optimization under uncertainty where soft constraints are used to promote solution characteristics that lead to flexibility.•We build a simulator that evaluates the quality of the solutions found by the Lagrangian heuristic algorithm and determines the cost of obtaining flexible solutions.•Computational results show that by incurring a small increase in initial cost (sometimes zero), our planning strategies generate solutions that are often significantly less vulnerable to potential disruptions.

This paper studies a Maritime Inventory Routing Problem with Time Windows (MIRPTW) for deliveries with uncertain disruptions. We consider disruptions that increase travel times between ports and ultimately affect the deliveries in one or more time windows. The objective is to find flexible solutions that can accommodate unplanned disruptions. We propose a Lagrangian heuristic algorithm for obtaining flexible solutions by introducing auxiliary soft constraints that are incorporated in the objective function with Lagrange multipliers. To evaluate the flexibility of solutions, we build a simulator that generates disruptions and recovery solutions. Computational results show that by incurring a small increase in initial cost (sometimes zero), our planning strategies generate solutions that are often significantly less vulnerable to potential disruptions. We also consider the effect of lead time in being able to respond to the disruptions.