LocalSolver


Benchmark — 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. Here we show 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

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.

With LocalSolver, the only decision variables are the choice of a class for each position. All can be deduced from these decisions, and are therefore defined as LSExpression in the LocalSolver model as recommended in our Modeling Guide.


function model() {
  for[c in 1..nbClasses][p in 1..startPosition-1]
    classPosition[c][p] <- initialSequence[p] == c;
  
  for[c in 1..nbClasses][p in startPosition..nbPositions] 
    classPosition[c][p] <- bool();
  
  for[c in 1..nbClasses]
    constraint sum[p in 1..nbPositions](classPosition[c][p]) == nbVehiclesClass[c];
  
  for[p in 1..nbPositions]
    constraint sum[c in 1..nbClasses](classPosition[c][p]) == 1;
  
  for[p in 1..nbPositions][o in 1..nbOptions]
    optionPosition[o][p] <- or[c in 1..nbClasses : optionsClass[c][o]](classPosition[c][p]);
  
  for[o in 1..nbOptions][p in startPosition-denomOption[o]+1..nbPositions] {
    nbOptionsWindow[o][p] <- sum[w in p..p+denomOption[o]-1 : w >= 1 && w <= nbPositions](optionPosition[o][w]);
    violationsWindow[o][p] <- max(nbOptionsWindow[o][p] - numOption[o], 0);
  }
  
  objectiveHigh <- sum[o in 1..nbOptions : isPriorityOption[o]][p in startPosition-denomOption[o]+1..nbPositions](violationsWindow[o][p]);
  objectiveLow <- sum[o in 1..nbOptions : !isPriorityOption[o]][p in startPosition-denomOption[o]+1..nbPositions](violationsWindow[o][p]);
  
  for[p in startPosition-1..nbPositions][r in 0..nbColors]
    colorPosition[r][p] <- or[c in 1..nbClasses : colorClass[c] == r](classPosition[c][p]);
  
  for[p in startPosition-1..nbPositions-1]
    colorChange[p] <- or[r in 0..nbColors](xor(colorPosition[r][p], colorPosition[r][p+1]));
    
  for[p in startPosition..nbPositions-paintBatchLimit]
    constraint or[q in p..p+paintBatchLimit-1](colorChange[q]);
  
  objectiveColor <- sum[p in startPosition-1..nbPositions-1](colorChange[p]);
  
  objectives[COLOR] <- objectiveColor;
  objectives[HIGH] <- objectiveHigh;
  objectives[LOW] <- objectiveLow;

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

Results

Here 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 that is different from the best-known solution for at least one solver. The comparison is made between LocalSolver 10.5 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, 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 of state-of-the-art MILP solvers like Gurobi.

You can find the complete model of the classical Car Sequencing Problem in Python, Java, C#, C++, and LSP in our Example Tour.

We are at your disposal to accompany you in the discovery of LocalSolver. Don't hesitate to contact us for any further information or support.

Contact us - Disclaimer - Privacy policy - Copyright 2022 LocalSolver