Hybrid optimization methods for time-dependent sequencing problems

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

Research output: Contribution to journalArticleAcademicpeer-review

22 Citations (Scopus)
2 Downloads (Pure)

Abstract

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
Volume259
Issue number3
DOIs
Publication statusPublished - 16 Jun 2017
Externally publishedYes

Keywords

  • Additive bounding
  • Constraint programming
  • Decision diagrams
  • Sequencing

Fingerprint

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

Cite this