Optimization-based very large-scale neighborhood search for generalized assignment problems with location/allocation considerations
Author | Ghoniem, Ahmed |
Author | Flamand, Tulay |
Author | Haouari, Mohamed |
Available date | 2021-09-07T06:16:17Z |
Publication Date | 2016 |
Publication Name | INFORMS Journal on Computing |
Resource | Scopus |
ISSN | 10919856 |
Abstract | This paper introduces a novel class of generalized assignment problems with location/allocation considerations that arises in several applications including retail shelf space allocation. We consider a set of items where each item may represent a family of products and a set of variable-sized knapsacks that may represent shelves, which comprise contiguous segments having distinct attractiveness. The decision-maker seeks to assign the set of items to these knapsacks, specify their segment assignments within knapsacks, and determine their total allocated space within predetermined lower/upper bounds in a fashion that maximizes a reward-based objective function. We develop an effective optimization-based very large-scale neighborhood search (VLNS), which greatly outperforms the best solution identified by CPLEX within one CPU hour, whereas general-purpose solver heuristics failed to provide feasible solutions to most of the larger instances within a time limit comparable to the VLNS algorithm run times. Our computational study was carried out on randomly generated computationally challenging instances with up to 210 items and 42 knapsacks and on a case study motivated by a shelf space allocation problem. Our results demonstrate that the proposed approach consistently produces high-quality solutions. 2016 INFORMS. |
Language | en |
Publisher | INFORMS Inst.for Operations Res.and the Management Sciences |
Subject | Generalized assignment problems Mixed-integer programming Very large-scale neighborhood search |
Type | Article |
Pagination | 575-588 |
Issue Number | 3 |
Volume Number | 28 |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
-
Mechanical & Industrial Engineering [1342 items ]