A column generation heuristic for a dynamic generalized assignment problem |
| |
Authors: | Luigi Moccia Jean-François Cordeau Maria Flavia Monaco Marcello Sammarra |
| |
Affiliation: | 1. Istituto di Calcolo e Reti ad Alte Prestazioni, Consiglio Nazionale delle Ricerche, Via P. Bucci 41C, 87036 Rende (CS), Italy;2. Dipartimento di Elettronica, Informatica e Sistemistica, Università della Calabria, via P. Bucci 41C, 87036 Rende (CS), Italy;3. TER-ENETEC Tecnologie per gli Usi Finali dell’Energia, ENEA Ente per le Nuove Tecnologie, l’Energia e l’Ambiente, C. R. Trisaia, s.s. Jonica 106, km 419+500, 75026 Rotondella (MT), Italy;4. Canada Research Chair in Logistics and Transportation and CIRRELT, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Canada H3T 2A7 |
| |
Abstract: | This paper studies the dynamic generalized assignment problem (DGAP) which extends the well-known generalized assignment problem by considering a discretized time horizon and by associating a starting time and a finishing time with each task. Additional constraints related to warehouse and yard management applications are also considered. Three linear integer programming formulations of the problem are introduced. The strongest one models the problem as an origin–destination integer multi-commodity flow problem with side constraints. This model can be solved quickly for instances of small to moderate size. However, because of its computer memory requirements, it becomes impractical for larger instances. Hence, a column generation algorithm is used to compute lower bounds by solving the linear program (LP) relaxation of the problem. This column generation algorithm is also embedded in a heuristic aimed at finding feasible integer solutions. Computational experiments on large-scale instances show the effectiveness of the proposed approach. |
| |
Keywords: | Generalized assignment problem Dynamic problem Column generation Warehouse management Yard management |
本文献已被 ScienceDirect 等数据库收录! |
|