A branch-and-cut algorithm for the truck dock assignment problem with operational time constraints

Abstract : In this paper, we address a truck dock assignment problem with operational time constraint which has to be faced in the management of cross docks. More specifically, this problem is the subproblem of more involved problems with additional constraints and criteria. We propose a new integer programming model for this problem. The dimension of the polytope associated with the proposed model is identified by introducing a systematic way of generating linearly independent feasible solutions. Several classes of valid inequalities are also introduced. Some of them are proved to be facet-defining. Then, exact separation algorithms are described for separating cuts for classes with exponential number of constraints, and an efficient branch-and-cut algorithm solving real-life size instances in a reasonable time is provided. In most cases, the optimal solution is identified at the root node without requiring any branching.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01429317
Contributeur : Frédéric Semet <>
Soumis le : samedi 7 janvier 2017 - 17:44:03
Dernière modification le : mardi 3 juillet 2018 - 11:21:20

Identifiants

  • HAL Id : hal-01429317, version 1

Collections

Citation

Shahin Gelareh, Rahimeh Neamatian Monemi, Frédéric Semet, Gilles Goncalves. A branch-and-cut algorithm for the truck dock assignment problem with operational time constraints. European Journal of Operational Research, Elsevier, 2016. 〈hal-01429317〉

Partager

Métriques

Consultations de la notice

159