The family capacitated vehicle routing problem

Raquel Bernardino and Ana Paias

European Journal of Operational Research, 2024, vol. 314, issue 3, 836-853

Abstract: In this article, we address the family capacitated vehicle routing problem (F-CVRP), an NP-hard problem that generalizes both the FTSP and the capacitated vehicle routing problem. The F-CVRP has practical application in warehouse management in warehouses with scattered storage. We present several mixed integer linear programming formulations for this problem and establish a theoretical and empirical comparison. We also propose valid inequalities adapted from known routing problems from the literature. Some formulations are solved using a branch-and-cut algorithm, which is tested with a newly generated data set. The computational experiment allows us to identify the instances’ most challenging characteristics and the exact methods’ limitations. Finally, we develop an iterated local search (ILS) algorithm to efficiently obtain feasible solutions for the instances that could not be solved to proven optimality. The ILS algorithm is very efficient and can improve the upper bounds obtained by the exact methods within the set time limit.

Keywords: Routing; Family traveling salesman problem; Projection results; Branch-and-cut algorithm; Iterated local search algorithm (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723008172
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:314:y:2024:i:3:p:836-853

DOI: 10.1016/j.ejor.2023.10.042

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 ().