Solving the Car Sequencing Problem with Constraint Logic Programming in the Automotive Industry
Thorsten Winterer · 2011
flexis AG is a software company that specialises in planning and optimisation software for the automotive industry, with offices in Europe, North America, and Asia. One of our main products is a production sequencing solver that is used by several large truck and car manufacturers. The solver is based on Constraint Programming, and in its current incarnation it is implemented in ECLPS. The Car Sequencing Problem is the problem of finding a production sequence that fulfils a given set of hard constraints and is optimal with regard to some measure, usually a weighted number of soft constraint violations. One of the earliest papers on the Car Sequencing Problem, by van Hentenryck, Simonis, and Dincbas, described a solver based on Constraint Logic Programming [3]. A general global sequencing constraint (among seq in the Global Constraint Catalog) was introduced in [1]. Later papers considered improvements to the filtering algorithm for the sequencing constraint, e.g. [4]. In recent years the focus shifted to sequencing solvers based on Local Search. A review of the 2005 ROADEF challenge states that “no constraint programming based method[s] were competing after the qualification phase” [5]. However, there are several important differences between the Car Sequencing Problem as usually defined in the literature and what one will encounter in the automotive industry. The main difference is that in the industrial practice, the focus on the classic “car sequencing” constraint is too narrow. Customers may want to place orders with the same attribute, e.g., the same colour, into blocks of a given size. Some special configurations may only be built in certain shifts. A pilot order may only be built with a gap of specified length before the rest of the order. Some orders may have to be built in a given sequence, but not necessarily consecutively. A car sequencing solver needs to be able to model such constraints, and more. One paper that describes a variant of the Car Sequencing Problem with many real-world constraints is [2]. The second main difference is that the previous sequence must be taken into account, in order to achieve a feasible continuity. Continuity is essential, since car production often operates 24 hours per day, and even where it doesn’t, the production line is never emptied. The problem of continuity is usually not considered in the academic literature, though. A third difference is the problem size. In the automotive industry sequences are often generated for a rolling horizon of between three days and one week.