Search

This paper introduces the multi-mode set covering problem, which consists of a plurality of set covering problems linked by cardinality constraints. We propose a variable neighborhood search algorithm and a greedy randomized adaptive search procedure based on a common local search routine. This routine applies a penalized relaxation of the covering constraints, tuned by self-adapting parameters, and visits a sequence of neighborhoods in a nested strategy. We compare the two heuristics with each other and with a time-limited run of a general-purpose integer linear programming solver, on a benchmark set of instances with heterogeneous structure. Both heuristics outperform the solver, though with interesting differences with respect to the various classes of instances. In particular, the variable neighborhood search algorithm proves more effective and less dependent on the specific features of the instances. [ABSTRACT FROM AUTHOR]

This paper has been motivated by the study of a real application, the transshipment container terminal of Gioia Tauro in Italy. The activities in a container terminal concern with the movement of containers from/to mother vessels and feeders and with the handling and storage of containers in the yard. For such type of applications both operational (e.g., scheduling) and tactical (e.g., planning) models, currently available in the literature, are not useful in terms of operations management and resources optimization. Indeed, the former models are too detailed for the complexity of the systems, while the latter are not able to capture the operational constraints in representing those activities which limit the nominal capacity. Herein, the container terminal, or more in general a service or production system, is represented as a network of complex substructures or platforms. The idea is to formalize the concept of platform capacity, which is used to represent the operational aspects of the container terminal in a mathematical model for the tactical planning. The problem, which consists in finding an allocation of resources in each platform in order to minimize the total delay on the overall network and on the time horizon, is modelled by a mathematical programming formulation for which we carry out a computational analysis using CPLEX-MIP solver. Moreover, we present a dynamic programming based heuristic to solve larger instances in short computational time. On all but one of the smaller instances, the heuristic solutions are also optimal. On the larger instances, the maximum gap, i.e. the percentage deviation, between the heuristic solutions and the best solutions computed by CPLEX-MIP within the time limit of 3600 s, has been 6.3%. [ABSTRACT FROM AUTHOR]