Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems

Ibrahim Muter, S. Ilker Birbil, Guvenc Sahin

Research output: Contribution to journalArticle

25 Citations (Scopus)

Abstract

We propose a new generic framework for solving combinatorial optimization problems that can be modeled as a set covering problem. The proposed algorithmic framework combines metaheuristics with exact algorithms through a guiding mechanism based on diversification and intensification decisions. After presenting this generic framework, we extensively demonstrate its application to the vehicle routing problem with time windows. We then conduct a thorough computational study on a set of well-known test problems, where we show that the proposed approach not only finds solutions that are very close to the best-known solutions reported in the literature, but also improves them. We finally set up an experimental design to analyze the effects of different parameters used in the proposed algorithm.
Original languageEnglish
Pages (from-to)603-619
JournalINFORMS Journal on Computing
Volume22
Issue number4
DOIs
Publication statusPublished - 23 Mar 2010

Fingerprint

Vehicle routing
Combinatorial optimization
Design of experiments
Metaheuristics
Optimization problem
Set covering problem
Diversification
Experimental design
Vehicle routing problem
Time windows

Cite this

Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems. / Muter, Ibrahim; Birbil, S. Ilker; Sahin, Guvenc.

In: INFORMS Journal on Computing, Vol. 22, No. 4, 23.03.2010, p. 603-619.

Research output: Contribution to journalArticle

@article{d9708f840f6d4db3b3cf7b3f515b507b,
title = "Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems",
abstract = "We propose a new generic framework for solving combinatorial optimization problems that can be modeled as a set covering problem. The proposed algorithmic framework combines metaheuristics with exact algorithms through a guiding mechanism based on diversification and intensification decisions. After presenting this generic framework, we extensively demonstrate its application to the vehicle routing problem with time windows. We then conduct a thorough computational study on a set of well-known test problems, where we show that the proposed approach not only finds solutions that are very close to the best-known solutions reported in the literature, but also improves them. We finally set up an experimental design to analyze the effects of different parameters used in the proposed algorithm.",
author = "Ibrahim Muter and Birbil, {S. Ilker} and Guvenc Sahin",
year = "2010",
month = "3",
day = "23",
doi = "10.1287/ijoc.1090.0376",
language = "English",
volume = "22",
pages = "603--619",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "4",

}

TY - JOUR

T1 - Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems

AU - Muter, Ibrahim

AU - Birbil, S. Ilker

AU - Sahin, Guvenc

PY - 2010/3/23

Y1 - 2010/3/23

N2 - We propose a new generic framework for solving combinatorial optimization problems that can be modeled as a set covering problem. The proposed algorithmic framework combines metaheuristics with exact algorithms through a guiding mechanism based on diversification and intensification decisions. After presenting this generic framework, we extensively demonstrate its application to the vehicle routing problem with time windows. We then conduct a thorough computational study on a set of well-known test problems, where we show that the proposed approach not only finds solutions that are very close to the best-known solutions reported in the literature, but also improves them. We finally set up an experimental design to analyze the effects of different parameters used in the proposed algorithm.

AB - We propose a new generic framework for solving combinatorial optimization problems that can be modeled as a set covering problem. The proposed algorithmic framework combines metaheuristics with exact algorithms through a guiding mechanism based on diversification and intensification decisions. After presenting this generic framework, we extensively demonstrate its application to the vehicle routing problem with time windows. We then conduct a thorough computational study on a set of well-known test problems, where we show that the proposed approach not only finds solutions that are very close to the best-known solutions reported in the literature, but also improves them. We finally set up an experimental design to analyze the effects of different parameters used in the proposed algorithm.

UR - http://dx.doi.org/10.1287/ijoc.1090.0376

U2 - 10.1287/ijoc.1090.0376

DO - 10.1287/ijoc.1090.0376

M3 - Article

VL - 22

SP - 603

EP - 619

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 4

ER -