Large neighborhood improvements for solving car sequencing problems

The NP-hard problem of car sequencing has received a lot of attention these last years. Whereas a direct approach based on integer programming or constraint programming is generally fruitless when the number of vehicles to sequence exceeds a hundred, several heuristics have shown their efficiency. In this paper, very large-scale neighborhood improvement techniques based on integer programming and linear assignment are presented for solving car sequencing problems. The effectiveness of this approach is demonstrated through an experimental study made on seminal CSPLIB's benchmarks.