A Lagrangian-ACO matheuristic for car sequencing

Dhananjay Raghavan Thiruvady, Andreas Tilman Ernst, Mark Wallace

    Research output: Contribution to journalArticleResearchpeer-review

    15 Citations (Scopus)


    In this study, we investigate a hybrid Lagrangian relaxation ant colony optimisation for optimisation version of the car sequencing problem. Several cars are required to be scheduled on an assembly line and each car requires a number of options such as sunroof and/or air conditioning. These cars are required to be sequenced such that sub-sequences of specific sizes may only include a limited number of any option. While this is usually a hard constraint, in this study we treat it as a soft constraint and further require the utilisation of options be modulated across the sequence leading to the optimisation problem. We investigate various Lagrangian heuristics, ant colony optimisation (ACO) and hybrids of these methods. The results show that the Lagrangian-ACO hybrid is the best performing method for up to 300 cars.

    Original languageEnglish
    Pages (from-to)279-296
    Number of pages18
    JournalEURO Journal on Computational Optimization
    Issue number4
    Publication statusPublished - 1 Nov 2014


    • Ant colony optimisation
    • Car sequencing
    • Hybrid methods
    • Lagrangian relaxation

    Cite this