Genetic Algorithm with Hybrid Integer Linear Programming Crossover Operators for the Car-Sequencing Problem

In this paper, we present three new integrative approaches for solving the classical car-sequencing problem. These hybrid approaches are essentially based on a genetic algorithm which incorporates crossover operators using an integer linear programming model during the crossover process for the construction of a solution. This form of integrative hybridization has been proposed by Cotta and Troya in a framework for hybridizing evolutionary algorithms with a branch-and-bound algorithm in order to explore the dynastic potential of the two parents' solutions and thus obtain the best offspring. However, while our crossovers also use problem-knowledge in the recombination process, they are not strictly transmitting operators and do not limit the exploration to the dynastic potential of the parents' solutions. We show that the hybrid approach outperforms a genetic algorithm with local search and other algorithms found in the literature on the CSPLib benchmarks. Although the computation times are long when integrative hybridization is used, this study well illustrates the interest of designing hybrid approaches exploiting the strengths of different methods.