A column generation approach and new bounds for the car sequencing problem

作者：Jahren Eivind^*; Asin Acha Roberto

来源：Annals of Operations Research, 2018, 264(1-2): 193-211.

DOI：10.1007/s10479-017-2663-4

• Combinatorial optimization
• Industrial car sequencing
• Integer linear programming
• Column generation

The subject of the 2005 ROADEF challenge was a variation of the car scheduling problem based on the needs of the Renaultfactories. In this paper we revisit this problem to investigate how further contributions can be made in order to close the gap between exact and heuristic methods that exists for this problem. For the benchmark set used in the final round of the competition we report new lower bounds for 7 out of the 19 instances by using an improved ILP formulation of the problem. We also present a new column generation based exact method for solving the ILP problem which outperforms branch-and-bound in obtaining upper bounds for these problems.

• 出版日期2018-5