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

Abstract

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.

Keywords:

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

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 The new solution will usually be an improvement on the initial solution, or on rare occasions, the initial solution itself where no improvements can be found.

2 Please refer to the original paper for full details.

3 A gap of 0.5% was selected based on experimentation on a range of instances.

4 We found in preliminary experiments with the Perron & Shaw dataset that there was no significant difference between a quarter, half or three-quarters. Hence, we chose the middle value of a half.

5 LRACO was re-run on the same machines to ensure there is no dependency in the results associated with the resources used to obtain results.

6 This window size is obtained from parametric tests which are detailed in Appendix.

7 These results are re-implemented so that LRACO and the LNS-based algorithms can be compared directly.