Séminaire conjoint avec la Chaire en logistique et en transport.

We consider a single-period fuel delivery problem in which a distribution company has to transport multiple types of fuel from a depot to a set of service stations using a heterogeneous set of multi-compartment vehicles. Among other characteristics, the problem includes time windows, a limit on the duration of each route, unsplit compartments, and split deliveries. We propose two mixed integer programming (MIP) formulations and a logic-based Benders decomposition approach. The first formulation is an arc-based model while the second is based on the possible trips. The logic-based Benders decomposition follows a trip-based principle and breaks down the problem into a generalized assignment master problem and a subproblem responsible for identifying violated feasibility cuts implicated by the time-related constraints. It takes advantage of the problem-specific characteristics that allow efficiently solving the resulting subproblems. The computational experiments using synthetic instances show that the logic-based Benders decomposition outperforms the other formulations and is very effective in solving the considered benchmark instances.