Review and comparison of three methods for the solution of the car sequencing problem

The car sequencing problem is the ordering of the production of a list of vehicles which are of the same type, but which may have options or variations that require higher work content and longer operation times for at least one assembly workstation. A feasible production sequence is one that does not schedule vehicles with options in such a way that one or more workstations are overloaded. In variations of the problem, other constraints may apply. We describe and compare three approaches to the modeling and solution of this problem. The first uses integer programming to model and solve the problem. The second approaches the question as a constraint satisfaction problem (CSP). The third method proposes an adaptation of the Ant Colony Optimization for the car sequencing problem. Test-problems are drawn from CSPLib, a publicly available set of problems available through the Internet. We quote results drawn both from our own work and from other research. The literature review is not intended to be exhaustive but we have sought to include representative examples and the more recent work. Our conclusions bear on likely research avenues for the solution of problems of practical size and complexity. A new set of larger benchmark problems was generated and solved. These problems are available to other researchers who may wish to solve them using their own methods.