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

Shahin Gelareh*, Rahimeh Neamatian Monemi, Frédéric Semet, Gilles Goncalves

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)1144-1152
Number of pages9
JournalEuropean Journal of Operational Research
Volume249
Issue number3
Early online date16 Oct 2015
DOIs
Publication statusPublished - 16 Mar 2016
Externally publishedYes

Keywords

  • Dimension
  • Facet-defining inequalities
  • Polytope
  • Truck dock assignment
  • Valid inequalities

Fingerprint

Dive into the research topics of 'A branch-and-cut algorithm for the truck dock assignment problem with operational time constraints'. Together they form a unique fingerprint.

Cite this