Adaptive local search algorithm for solving car sequencing problem

The global competitive environment leads companies to consider how to produce high-quality products at a lower cost. Mixed-model assembly lines (MMAL) are often designed such that average station work satisfies the time allocated to each station, but some models with work-intensive options require more than the allocated time. Sequencing varying models in a mixed-model assembly line is the short-term decision problem that has the objective of preventing line stoppage resulting from a station work overload. Accordingly, a good allocation of models is necessary to avoid work overload. The car sequencing problem (CSP) is a specific version of the mixed-model sequencing problem that minimizes the work overload by controlling the sequence of models. In order to do that, CSP restricts the number of work-intensive options by applying capacity rules. Consequently, the objective is to find the sequence with the minimum number of capacity rule violations. In this study, we show that exact solution procedures are insufficient for application in industry. however, we provide five improved lower bounds for CSPLib instances by solving problems optimally with a subset of options. Additionally, we present four local search metaheuristics that are commonly used to solve CSP. The local search algorithms are compared over CSP benchmark instances, including CSPLib and ROADEF Challenge 2005. The computational experiments show that an Adaptive Local Search (ALS) provides a significant advantage by not requiring tuning on the operator weights due to its adaptive control mechanism. Moreover, results show that the algorithmic effort should focus on randomly exploring more non-deteriorated solutions instead of systematic search or spending time visiting deteriorated solutions to escape local optima.

Automated summary

The global competitive environment requires companies to produce high-quality products at a lower cost. To avoid work overload in mixed-model assembly lines, the car sequencing problem (CSP) controls the sequence of models and restricts the number of work-intensive options. This study shows that exact solution procedures are insufficient for industry application, but provides improved lower bounds for CSPLib instances and compares different local search metaheuristics for solving CSP.