Instance space analysis for the car sequencing problem

Yuan Sun (), Samuel Esler (), Dhananjay Thiruvady (), Andreas T. Ernst (), Xiaodong Li () and Kerri Morgan ()
Additional contact information
Yuan Sun: Monash University
Samuel Esler: Monash University
Dhananjay Thiruvady: Deakin University
Andreas T. Ernst: Monash University
Xiaodong Li: RMIT University
Kerri Morgan: Deakin University

Annals of Operations Research, 2024, vol. 341, issue 1, No 3, 69 pages

Abstract: Abstract 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 2-D space using dimensionality reduction techniques. The resulting 2-D 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.

Keywords: Combinatorial optimization; Machine learning; Instance space analysis; Algorithm selection; Car sequencing (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-022-04860-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:341:y:2024:i:1:d:10.1007_s10479-022-04860-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-022-04860-8

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().