Adaptive local search algorithm for solving car sequencing problem

I. Ozan Yilmazlar

doi:10.1016/j.jmsy.2023.05.018

2023-06-01

PRE

I. Ozan Yilmazlar *

Mary E. Kurz

DOI：10.1016/j.jmsy.2023.05.018

原文链接

摘要

En 中文

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.

Keyword:

Car sequencing

Local search

Metaheuristics

CSPLib

ROADEF

Adaptive local search

Simulated annealing

Variable neighborhood search