A path relinking approach with ejection chains for the generalized assignment problem

doi:10.1016/j.ejor.2004.08.015

A path relinking approach with ejection chains for the generalized assignment problem

2006-03-01

93

PRE

AI

DOI：10.1016/j.ejor.2004.08.015

Original

Original request for help

Save

Abstract

En 中文

The generalized assignment problem is a classical combinatorial optimization problem known to be NP-hard. It can model a variety of real world applications in location, allocation, machine assignment, and supply chains. The problem has been studied since the late 1960s, and computer codes for practical applications emerged in the early 1970s. We propose a new algorithm for this problem that proves to be more effective than previously existing methods. The algorithm features a path relinking approach, which is a mechanism for generating new solutions by combining two or more reference solutions. It also features an ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. Computational comparisons on benchmark instances show that the method is not only effective in general, but is especially effective for types D and E instances, which are known to be very difficult. (c) 2004 Elsevier B.V. All rights reserved.

Keywords:

metaheuristics

scatter search

path relinking

ejection chains

generalized assignment problem

A path relinking approach with ejection chains for the generalized assignment problem

Abstract

AI Summary

Journal

Organization