Large neighbourhood search based on mixed integer programming and ant colony optimisation for car sequencing

Dhananjay Thiruvady, Kerri Morgan, Amiza Amir, Andreas T. Ernst

Research output: Contribution to journalArticleResearchpeer-review


We investigate the problem of scheduling a sequence of cars to be placed on an assembly line. Stations, along the assembly line install options (e.g. air conditioning), but have limited capacities, and hence cars requiring the same options need to be distributed far enough apart. The desired separation is not always feasible, leading to an optimisation problem that minimises the violation of the ideal separation requirements. In order to solve the problem, we use a large neighbourhood search (LNS) based on mixed integer programming (MIP). The search is implemented as a sliding window, by selecting overlapping subsequences of manageable sizes, which can be solved efficiently. Our experiments show that, with LNS, substantial improvements in solution quality can be found.

Original languageEnglish
Pages (from-to)2696-2711
Number of pages16
JournalInternational Journal of Production Research
Issue number9
Publication statusPublished - 2 May 2020


  • ant colony optimisation
  • car sequencing
  • large neighbourhood search
  • mixed integer programming
  • scheduling

Cite this