A study of constraint programming heuristics for the car-sequencing problem

摘要

In the car-sequencing problem, a number of cars have to be sequenced on an assembly line respecting several constraints. This problem was addressed by both Operations Research (OR) and Constraint Programming (CP) communities, either as a decision problem or as an optimization problem. In this paper, we consider the decision variant of the car sequencing problem and we propose a systematic way to classify heuristics for solving it. This classification is based on a set of four criteria, and we consider all relevant combinations for these criteria. Some combinations correspond to common heuristics used in the past, whereas many others are novel. Not surprisingly, our empirical evaluation confirms earlier findings that specific heuristics are very important for efficiently solving the car-sequencing problem (see for instance Smith, 1996), in fact, often as important or more than the propagation method. Moreover, through a criteria analysis, we are able to get several new insights into what makes a good heuristic for this problem. In particular, we show that the criterion used to select the most constrained option is critical, and the best choice is fairly reliably the "load" of an option. Similarly, branching on the type of vehicle is more efficient than branching on the use of an option. Overall, we can therefore indicate with a relatively high confidence which is the most robust strategy, or at least outline a small set of potentially best strategies. Last, following a remark in Regin and Puget (1997) stating that the notion of slack used in heuristics induces a pruning rule, we propose an algorithm for this method and experimentally evaluate it, showing that, although computationally cheap and easy to implement, this is in practice a very efficient way to solve car-sequencing benchmarks.