Instance Space Analysis for the Car Sequencing Problem
  We investigate an important research question for solving the car sequencing
problem, that is, which characteristics make an instance hard to solve? To do
so, we carry out an instance space analysis for the car sequencing problem, by
extracting a vector of problem features to characterize an instance. In order
to visualize the instance space, the feature vectors are projected onto a
two-dimensional space using dimensionality reduction techniques. The resulting
two-dimensional visualizations provide new insights into the characteristics of
the instances used for testing and how these characteristics influence the
behaviours of an optimization algorithm. This analysis guides us in
constructing a new set of benchmark instances with a range of instance
properties. We demonstrate that these new instances are more diverse than the
previous benchmarks, including some instances that are significantly more
difficult to solve. We introduce two new algorithms for solving the car
sequencing problem and compare them with four existing methods from the
literature. Our new algorithms are shown to perform competitively for this
problem but no single algorithm can outperform all others over all instances.
This observation motivates us to build an algorithm selection model based on
machine learning, to identify the niche in the instance space that an algorithm
is expected to perform well on. Our analysis helps to understand problem
hardness and select an appropriate algorithm for solving a given car sequencing
problem instance.
