Two local search approaches for solving real-life car sequencing problems

Bertrand Estellon, Frédéric Gardi and Karim Nouioua

European Journal of Operational Research, 2008, vol. 191, issue 3, 928-944

Abstract: The NP-hard problem of car sequencing appears as the heart of the logistic process of many car manufacturers. The subject of the ROADEF'2005 challenge addressed a car sequencing problem proposed by the car manufacturer RENAULT, more complex than the academic problem generally addressed in the literature. This paper describes two local search approaches for this problem. In the first part, a new approach by very large-scale neighborhood search is presented. This approach, designed during the qualification stage preceding the final, is based on an original integer linear programming formulation. The second part is dedicated to the approach which enabled us to win the ROADEF'2005 challenge. Inspired by the latest works on the subject, this one is based on very fast explorations of small neighborhoods. Our contribution here is mainly algorithmic, in particular by showing how much exploiting invariants speeds up the neighborhood evaluation and contributes to the diversification of the search. Finally, the two approaches are compared and discussed through an extensive computational study on RENAULT's benchmarks. The main conclusion drawn at this point is that sophisticated metaheuristics are useless to solve car sequencing problems. More generally, our victory on ROADEF'2005 challenge demonstrates that algorithmic aspects, sometimes neglected, remain the key ingredients for designing and engineering high-performance local search heuristics.

Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00447-X
Full text for ScienceDirect subscribers only

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:eee:ejores:v:191:y:2008:i:3:p:928-944

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().