LocalSolver vs Gurobi on the Car Sequencing Problem with Paint-Shop Batching Constraints

The Car Sequencing Problem with Paint-Shop Batching Constraints was initially submitted by the car manufacturer Renault at the 2005 Challenge of the French Society of Operations Research and Decision Support (ROADEF). The problem is to schedule the production of cars along production lines while respecting the assembly line and paint shop requirements. Cars with the most complicated options must be evenly distributed throughout the total processed cars. Spray guns must be washed with paint solvent regularly and in-between two different car colors. We illustrate on this page how LocalSolver outperforms traditional general-purpose optimization solvers like Gurobi 9.1.

Input data

The instances are given on the challenge’s website in three sets A, B, and X. In this benchmark, we compare the results obtained by LocalSolver and its competitors for different solving times, on the 80 instances. The objective values are confronted to the best know solutions for these instances.

Mathematical models of the Car Sequencing Problem with Paint-Shop Batching Constraints

Mixed-Integer Linear Programming (MILP) model

The results reported for Gurobi are obtained using the standard Mixed-Integer Programming (MIP) modeling approach. The main decision is assigning a vehicle class to each position in the production line. Due to the workshop specificities, the MIP model requires many auxiliary binary and integer decisions. These decisions track the positions of the different classes of cars and their options along the production line and the number of violations of the even distribution of complicated options. All decision variables must be linked to their corresponding constraint, resulting in a vast constrained model.

LocalSolver model

Within the data is given an initial production sequence, respecting the constraints in terms of the number of classes produced. The problem can then be considered as a permutation problem based on this initial sequence. With LocalSolver, this translates into the use of a list variable, combined with a partition constraint, ensuring that everything will be produced as expected. Everything else can be deduced from these decisions. It is therefore defined as LSExpression in the LocalSolver model as recommended in our Modeling Guide.

function model() {
    sequence <- list(nbPositions);

    constraint partition(sequence);
    for[p in 0..startPosition-1]
        constraint sequence[p] == p;

    nbCarsWindows[o in 0..nbOptions-1][j in startPosition-windowSize[o]+1..nbPositions-1] 
            <- sum[k in 0..windowSize[o]-1 : j + k >= 0 && j + k < nbPositions]
            (options[initialSeq[sequence[j + k]]][o]);

    nbViolationsWindows[o in 0..nbOptions-1] 
            <- sum[j in startPosition-windowSize[o]+1..nbPositions-1]
            (max(0, nbCarsWindows[o][j] - maxCarsPerWindow[o]));

    objectiveHigh <- sum[o in 0..nbOptions-1 : isPriorityOption[o]](nbViolationsWindows[o]);
    objectiveLow <- sum[o in 0..nbOptions-1 : !isPriorityOption[o]](nbViolationsWindows[o]);

    colorChange[p in startPosition-1..nbPositions-2] 
            <- colorClass[initialSeq[sequence[p]]] != colorClass[initialSeq[sequence[p+1]]];

    objectiveColor <- sum[p in startPosition-1..nbPositions-2](colorChange[p]);

    for[p in startPosition..nbPositions-paintBatchLimit-2]
        constraint or[p2 in 0..paintBatchLimit-1](colorChange[p + p2]);

    objectives[COLOR] <- objectiveColor;
    objectives[HIGH] <- objectiveHigh;
    objectives[LOW] <- objectiveLow;

    objective <- COEF_0 * objectives[0] + COEF_1 * objectives[1] + COEF_2 * objectives[2];
}

Gurobi and LocalSolver results on the Car Sequencing Problem with Paint-Shop Batching Constraints

We compare the performance of both solvers with the solving time used in the competition: 10 minutes. We also add results obtained within 1 minute to illustrate the solver’s behavior with short running times. The objective is a linear combination of lexicographic goals. For the sake of readability, we only compare the first objective which is different from the best-known solution for at least one solver. The comparison is made between LocalSolver 11.0 and Gurobi 9.1, known as a state-of-the-art MIP solver. Both are used without any tuning. The best-known solutions are the best solutions found during the competition by using dedicated algorithms.

With up to 400 cars to assemble, LocalSolver reaches the best-known value for the first differentiating objective. Gurobi, however, has difficulty to comes towards the best-known value even for small instances and even more as the size increases. LocalSolver can scale, with solutions still close to the best known on the largest instances with up to 1500 cars. Increasing the running time is insufficient for Gurobi to catch up, while LocalSolver keeps descending towards the best-known solutions.

Conclusion

While LocalSolver’s modeling is straightforward and more manageable than classical MILP formulations, it results in high-quality solutions after only 1 minute of running time, even on large-scale instances, which is not the case with state-of-the-art MILP solvers like Gurobi.

You can find the complete model of the Car Sequencing Problem with Paint-Shop Batching Constraints and many other Scheduling problems in Python, Java, C#, and C++ in our Example Tour.

Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to exchange about your optimization problems.

Share