1. A branch-and-cut algorithm for the truck dock assignment problem with operational time constraints
- Author
-
Rahimeh Neamatian Monemi, Gilles Goncalves, Shahin Gelareh, Frédéric Semet, Laboratoire de Génie Informatique et d'Automatique de l'Artois (LGI2A), Université d'Artois (UA), Évaluation des Systèmes de Transports Automatisés et de leur Sécurité (IFSTTAR/COSYS/ESTAS), Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-PRES Université Lille Nord de France, Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Université de Lille-Ecole Centrale de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Ecole Centrale de Lille-Centre National de la Recherche Scientifique (CNRS), and Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Mathematical optimization ,Programmation ,Information Systems and Management ,analyse des contraintes ,General Computer Science ,Dimension (graph theory) ,0211 other engineering and technologies ,Polytope ,02 engineering and technology ,Management Science and Operations Research ,valid inequalities ,Industrial and Manufacturing Engineering ,quai ,dimension ,DOCK ,0202 electrical engineering, electronic engineering, information engineering ,Time constraint ,[INFO]Computer Science [cs] ,Mathematics ,021103 operations research ,Truck dock assignment ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,Modeling and Simulation ,facet-defining inequalities ,polytope ,020201 artificial intelligence & image processing ,Node (circuits) ,Linear independence ,[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] ,Algorithm ,Assignment problem ,Branch and cut ,algorithme - Abstract
International audience; 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.
- Published
- 2016
- Full Text
- View/download PDF