CMSA based on set covering models for packing and routing problems

Mehmet Anıl Akbay (), Christian Blum () and Can Berk Kalayci ()
Additional contact information
Mehmet Anıl Akbay: Artificial Intelligence Research Institute (IIIA-CSIC)
Christian Blum: Artificial Intelligence Research Institute (IIIA-CSIC)
Can Berk Kalayci: Pamukkale University

Annals of Operations Research, 2024, vol. 343, issue 1, No 1, 38 pages

Abstract: Abstract Many packing, routing, and knapsack problems can be expressed in terms of integer linear programming models based on set covering. These models have been exploited in a range of successful heuristics and exact techniques for tackling such problems. In this paper, we show that integer linear programming models based on set covering can be very useful for their use within an algorithm called “Construct, Merge, Solve & Adapt”(CMSA), which is a recent hybrid metaheuristic for solving combinatorial optimization problems. This is because most existing applications of CMSA are characterized by the use of an integer programming solver for solving reduced problem instances at each iteration. We present applications of CMSA to the variable-sized bin packing problem and to the electric vehicle routing problem with time windows and simultaneous pickups and deliveries. In both applications, CMSA based on a set covering model strongly outperforms CMSA when using an assignment-type model. Moreover, state-of-the-art results are obtained for both considered optimization problems.

Keywords: Construct; Merge; Solve & Adapt; Set covering models; Bin packing; Routing (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06295-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:343:y:2024:i:1:d:10.1007_s10479-024-06295-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06295-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().