CMSA based on set covering models for packing and routing problems

被引:1
作者
Akbay, Mehmet Anil [1 ]
Blum, Christian [1 ]
Kalayci, Can Berk [2 ]
机构
[1] Artificial Intelligence Res Inst IIIA CSIC, Campus UAB, Bellaterra 08193, Spain
[2] Pamukkale Univ, Dept Ind Engn, Denizli, Turkiye
关键词
Construct; Merge; Solve; Adapt; Set covering models; Bin packing; Routing; COLUMN GENERATION; KERNEL SEARCH; ALGORITHM; BRANCH; DELIVERY; NUMBER; DEPOT; SOLVE;
D O I
10.1007/s10479-024-06295-9
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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.
引用
收藏
页码:1 / 38
页数:38
相关论文
共 47 条
[1]   Application of CMSA to the Electric Vehicle Routing Problem with Time Windows, Simultaneous Pickup and Deliveries, and Partial Vehicle Charging [J].
Akbay, Mehmet Anil ;
Kalayci, Can Berk ;
Blum, Christian .
METAHEURISTICS, MIC 2022, 2023, 13838 :1-16
[2]   Application of Adapt-CMSA to the Two-Echelon Electric Vehicle Routing Problem with Simultaneous Pickup and Deliveries [J].
Akbay, Mehmet Anil ;
Kalayci, Can Berk ;
Blum, Christian .
EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, EVOCOP 2023, 2023, 13987 :16-33
[3]  
Angelelli E., 2002, Quantitative approaches to distribution logistics and supply chain management, P249
[4]   Kernel search: A general heuristic for the multi-dimensional knapsack problem [J].
Angelelli, Enrico ;
Mansini, Renata ;
Speranza, M. Grazia .
COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (11) :2017-2026
[5]   A Self-Adaptive Variant of CMSA: Application to the Minimum Positive Influence Dominating Set Problem [J].
Anil Akbay, Mehmet ;
Lopez Serrano, Albert ;
Blum, Christian .
INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS, 2022, 15 (01)
[6]  
Applegate D., 1999, Finding Tours in the TSP
[7]   Green vehicle routing problem: A state-of-the-art review [J].
Asghari, Mohammad ;
Al-e-hashem, S. Mohammad J. Mirzapour .
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2021, 231
[8]  
Bard JF, 1998, IIE TRANS, V30, P821, DOI 10.1023/A:1007500200749
[9]   Branch-and-price: Column generation for solving huge integer programs [J].
Barnhart, C ;
Johnson, EL ;
Nemhauser, GL ;
Savelsbergh, MWP ;
Vance, PH .
OPERATIONS RESEARCH, 1998, 46 (03) :316-329
[10]   Construct, Merge, Solve & Adapt A new general algorithm for combinatorial optimization [J].
Blum, Christian ;
Pinacho, Pedro ;
Lopez-Ibanez, Manuel ;
Lozano, Jose A. .
COMPUTERS & OPERATIONS RESEARCH, 2016, 68 :75-88