A meta-heuristic with orthogonal experiment for the set covering problem

A meta-heuristic with orthogonal experiment for the set covering problem

0.00 Avg rating0 Votes
Article ID: iaor2005779
Country: Netherlands
Volume: 3
Issue: 3
Start Page Number: 263
End Page Number: 283
Publication Date: Jul 2004
Journal: Journal of Mathematical Modelling and Algorithms
Authors: ,
Keywords: scheduling, heuristics
Abstract:

This paper reports an evolutionary meta-heuristic incorporating fuzzy evaluation for some large-scale set covering problems originating from the public transport industry. First, five factors characterized by fuzzy membership functions are aggregated to evaluate the structure and generally the goodness of a column. This evaluation function is incorporated into a refined greedy algorithm to make column selection in the process of constructing a solution. Secondly, a self-evolving algorithm is designed to guide the constructing heuristic to build an initial solution and then improve it. In each generation an unfit portion of the working solution is removed. Broken solutions are repaired by the constructing heuristic until stopping conditions are reached. Orthogonal experimental design is used to set the system parameters efficiently, by making a small number of trials. Computational results are presented and compared with a mathematical programming method and a GA-based heuristic.

Reviews

Required fields are marked *. Your email address will not be published.