Evaluating metaheuristic solution quality for a hierarchical vehicle routing problem by strong lower bounding

Marduch Tadaros, Athanasios Migdalas, Nils-Hassan Quttineh and Torbjörn Larsson

Operations Research Perspectives, 2025, vol. 14, issue C

Abstract: We study a vehicle routing problem that originates from a Nordic distribution company and includes the essential decision-making components of the company’s logistics operations. The problem considers customer deliveries from a depot using heavy depot vehicles, swap bodies, optional switch points, and lighter local vehicles; a feature is that deliveries are made by both depot and local vehicles. The problem has earlier been solved by a fast metaheuristic, which does however not give any quality guarantee. To assess the solution quality, two strong formulations of the problem based on the column generation approach are developed. In both of these the computational complexity is mitigated through an enumeration of the switch point options. The formulations are evaluated with respect to the quality of the linear programming lower bounds in relation to the bounds obtained from a compact formulation. The strong lower bounding quality enables a significant reduction of the optimality gap compared to the compact formulation. Further, the bounds verify the high quality of the metaheuristic solutions, and for several problem instances the optimality gap is even closed.

Keywords: Vehicle routing problem; Hierarchical; Multi-echelon; Multi-switch; Column generation; Metaheuristics (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S2214716025000089
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:oprepe:v:14:y:2025:i:c:s2214716025000089

DOI: 10.1016/j.orp.2025.100332

Access Statistics for this article

Operations Research Perspectives is currently edited by Rubén Ruiz Garcia

More articles in Operations Research Perspectives from Elsevier
Bibliographic data for series maintained by Catherine Liu ().