Benders' decomposition for robust travel time-constrained inventory routing problem

The time-constrained inventory routing problem (TCIRP) is a variant of the standard inventory routing problem (IRP), in which each vehicle's trip duration must not exceed a predefined maximum duration limit. In this paper, we consider the TCIRP on a network in which arc travel times are uncertain. In particular, we investigate the case where the only available information on the arc travel times is that they take values in symmetric and bounded intervals around their mean values. To solve this problem, a robust optimisation approach that generates solutions with a controlled level of conservatism is implemented. To cope with the complexity of the resulting robust counterpart, we develop a Benders' decomposition-based heuristic. Furthermore, we describe how the valid inequalities developed for the IRP can be strengthened so that the Benders' decomposition master problem can be solved effectively. We compare the proposed approach with two standard approaches for finding robust solutions. The analysis of the results show that the proposed method is able to find robust solutions that are not too conservative in reasonable time.