An efficient implementation of a VNS/ILS heuristic for a real-life car sequencing problem

The car sequencing problem consists in sequencing a given set of cars to be produced in a single day. We address one of the variants of this problem, in which the objective of minimizing the number of violations of assembly constraints has a stronger weight than the minimization of the number of paint color changes. We present and describe in details a VNS/ILS approach for approximately solving this problem. Computational results on real-life test instances are reported. The work presented in this paper obtained the second prize in the challenge ROADEF'2005 sponsored by Renault.