Hybrid optimization methods for time-dependent sequencing problems

J. Kinable, A.A. Cire, W.J. van Hoeve

Research output: Contribution to journalArticleAcademicpeer-review

30 Citations (Scopus)
2 Downloads (Pure)


In this paper, we introduce novel optimization methods for sequencing problems in which the setup times between a pair of tasks depend on the relative position of the tasks in the ordering. Our proposed methods rely on a hybrid approach where a constraint programming model is enhanced with two distinct relaxations: One discrete relaxation based on multivalued decision diagrams, and one continuous relaxation based on linear programming. Both relaxations are used to generate bounds and enhance constraint propagation. Experiments conducted on three variants of the time-dependent traveling salesman problem indicate that our techniques substantially outperform general-purpose methods, such as mixed-integer linear programming and constraint programming models.

Original languageEnglish
Pages (from-to)887-897
Number of pages11
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 16 Jun 2017
Externally publishedYes


  • Additive bounding
  • Constraint programming
  • Decision diagrams
  • Sequencing


Dive into the research topics of 'Hybrid optimization methods for time-dependent sequencing problems'. Together they form a unique fingerprint.

Cite this