Hybrid optimization methods for time-dependent sequencing problems

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.