A logic-based Benders decomposition approach for a fuel delivery problem with time windows, unsplit compartments, and split deliveries

Rafael A. Melo, Celso C. Ribeiro, Sebastián Urrutia and Pieter Vansteenwegen

European Journal of Operational Research, 2025, vol. 325, issue 1, 100-117

Abstract: 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 logic-based Benders decomposition also serves as a heuristic, which works by limiting the number of trips generated throughout the process. Symmetry breaking constraints and preprocessing procedures are also proposed to help solving the formulations. 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. It solved to optimality instances with up to 20 customers. The MIP heuristic obtained solutions within 7.2% of the optimal cost for all but one of the tested instances with up to 25 customers. Furthermore, it proved to be a viable approach for medium-sized instances where the exact logic-based Benders decomposition encountered difficulties.

Keywords: Routing; Multi-compartment vehicle routing problem; Fuel delivery; MIP formulations; Benders decomposition (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725001833
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:325:y:2025:i:1:p:100-117

DOI: 10.1016/j.ejor.2025.03.003

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().