We consider a generalization of the multiple knapsack problem that combines assignment and loading. The problem can arise in military and emergency situations in which one is required to refurnish a unit with a number of different goods available at different locations. We present a mathematical model and study Lagrangian and surrogate relaxations. We propose heuristic and metaheuristic approaches which we use to develop two overall approximation algorithms: a self-contained polynomial-time heuristic and a more time consuming matheuristic approach that makes use of a MILP solver. Solution times and accuracy of lower and upper bounds are computationally evaluated on a real military data set and on sets of both realistic and randomly generated instances.
Homsi G., Jordan J., Martello S., Monaci M. (2021). The assignment and loading transportation problem. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 289(3), 999-1007 [10.1016/j.ejor.2019.07.039].
The assignment and loading transportation problem
Homsi G.;Martello S.
;Monaci M.
2021
Abstract
We consider a generalization of the multiple knapsack problem that combines assignment and loading. The problem can arise in military and emergency situations in which one is required to refurnish a unit with a number of different goods available at different locations. We present a mathematical model and study Lagrangian and surrogate relaxations. We propose heuristic and metaheuristic approaches which we use to develop two overall approximation algorithms: a self-contained polynomial-time heuristic and a more time consuming matheuristic approach that makes use of a MILP solver. Solution times and accuracy of lower and upper bounds are computationally evaluated on a real military data set and on sets of both realistic and randomly generated instances.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.